3
$\begingroup$

I need to solve an optimization problem that involves an expected value like $$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$

Here $f(k,x)$ is actually a probability coming from a normal distribution. And what I need, in particular, is to solve a first order condition that involves the derivative of $F$ with respect to $x$. Numerically it is OK, but I was wondering how I could obtain a nice analytical form. I tried several things, like replacing $f(k,x)$ with other normal-like distributions, but none worked.

I need this to show some asymptotic properties, so I could use a solution that considers the case when $n\rightarrow\infty$. Also, approximations are equally welcome.

Update upon the first comment:

I can simplify $f$ in the following way. $$f(k,x)= \Pr[y\geq Ak+B(n-k)+Cx] \text{ where } y\sim N(n,\sigma).$$

And I want to solve

$$\max qF(n,x)+(1-q)G(n,x)$$

with respect to $x$ where $q\in(0,1)$ and $$G(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} g(k,x)$$ with $$g(k,x)=\Pr[y'\leq Ak+B(n-k)+Cx] \text{ where } y'\sim N(-n,\sigma).$$

Upon a comment: $p\in(0,1)$ and $A,B,C\in\mathbb R_{++}$.

$\endgroup$
4
  • $\begingroup$ I think you need to be a bit more specific: what is $f$ and what do you mean with "first order condition"? $\endgroup$ Commented Jun 22, 2015 at 17:31
  • $\begingroup$ @PerAlexandersson I tried to specify a bit more by adding an update. $\endgroup$
    – juror
    Commented Jun 22, 2015 at 20:20
  • $\begingroup$ Under what conditions on $p$, $q$, $A,B,C,\sigma$ do you want to consider the asymptotics (of the maximum or of the maximizer?)? Are the values of these parameters fixed? Is $p\in(0,1)$? Are the signs of $A,B,C$ known? $\endgroup$ Commented Jun 24, 2015 at 14:57
  • $\begingroup$ @IosifPinelis $A,B,C\in\mathbb R_{++}$ fixed and $p\in(0,1)$. $\endgroup$
    – juror
    Commented Jun 24, 2015 at 16:34

1 Answer 1

3
$\begingroup$

The maximum converges to $1$ as $n\to\infty$. Indeed, one can write $$F(n,x)=P(X_n<w)\quad\text{and}\quad G(n,x)=P(X_n>w-d), $$ where $X_n:=\dfrac{(a-b)Y_n+Z}n$, $Y_n$ and $Z$ are independent random variables (r.v.'s), $Y_n$ has the binomial distribution with parameters $(n,p)$, $Z$ is standard normal, $a:=A/\sigma$, $b:=B/\sigma$, $w:=-b_1-cx/n$, $b_1:=(B-1)/\sigma$, $c:=C/\sigma$, $d:=2/\sigma>0$. So, the maximum of $qF(n,x)+(1-q)G(n,x)$ in $x\in\mathbb{R}$ equals $m_n:=\max_{w\in\mathbb{R}} [q P(X_n<w)+(1-q)P(X_n>w-d)]$. Note that, by the law of large numbers, $X_n\to\mu:=(a-b)p$ as $n\to\infty$ (say, in probability). So, taking $w=\mu+d/2$, one has $P(X_n<w)\to1$ and $P(X_n>w-d)\to1$. On the other hand, $m_n\le q+(1-q)=1$. Thus, $m_n\to1$ as $n\to\infty$.

The signs of $A,B,C$ are irrelevant for this conclusion, as long as $A,B,C$ are fixed and $C\ne0$. The assumptions on the r.v.'s $y$ and $y'$, including their normality, are also mostly irrelevant; for instance, one can replace $y$ and $y'$ by any r.v.'s $V_n$ and $W_n$ such that for some real $\delta>0$ one has $P(V_n-W_n\ge n\delta)\to0$ as $n\to\infty$.

Addendum: juror: As I understood, you were able to rewrite $F(n,x)$ as $P(AY_n+B(n-Y_n)+Cx+Z\sigma<n)$. Then you can further rewrite this as $$P((A-B)Y_n+Z\sigma<-[(B-1)n+Cx])=P\Big(\frac{(a-b)Y_n+Z}n<-\,\frac{(B-1)+Cx/n}\sigma\Big) =P(X_n<w), $$ as was stated previously (recall the definitions of $a,b,X_n,w$). $G(n,x)$ is dealt with quite similarly.

As for the law of large numbers (LLN), here are the details. Note that $Y_n$ equals $T_1+\dots+T_n$ in distribution, where $T_1,\dots,T_n$ are independent identically distributed Bernoulli r.v.'s, with $ET_i=p$ for all $i$. Hence, by the LLN, $Y_n/n\to p$ (in distribution) as $n\to\infty$. It is also clear that $Z/n\to0$. Hence, by the Slutsky theorem, $X_n\to(a-b)p$.

Addendum 2, on $\text{arg max}$: Recall that any distribution function is monotonic. So, one can see that, for each $\delta\in(0,1)$, the mentioned convergences $P(X_n<w)\to1$ and $P(X_n>w-d)\to1$ are uniform in $w$ such that $|w-(\mu+d/2)|\le(1-\delta)d/2$. Similarly, for each real $\delta>0$, the convergence $P(X_n<w)\to0$ is uniform in $w$ such that $w-(\mu+d/2)\le-(1+\delta)d/2$ and the convergence $P(X_n>w-d)\to0$ is uniform in $w$ such that $w-(\mu+d/2)\ge(1+\delta)d/2$. It follows that, for each real $\delta>0$ and all large enough $n$, the set $\text{arg max}_{w\in\mathbb{R}} [q P(X_n<w)+(1-q)P(X_n>w-d)]$ is contained in the interval $\{w\in\mathbb{R}\colon|w-(\mu+d/2)|<(1+\delta)d/2\}$. Substituting here $w=-b_1-cx/n$, we conclude that, for each real $\delta>0$ and all large enough $n$, the set $$\text{arg max}_{x\in\mathbb{R}} [qF(n,x)+(1-q)G(n,x)] =\{x\in\mathbb{R}\colon qF(n,x)+(1-q)G(n,x)=m_n\}$$ is contained in the interval $$\{x\in\mathbb{R}\colon|cx/n+b_1+\mu+d/2|<(1+\delta)d/2\};$$ recall that $$m_n:=\max_{w\in\mathbb{R}} [q P(X_n<w)+(1-q)P(X_n>w-d)]=\max_{x\in\mathbb{R}} [qF(n,x)+(1-q)G(n,x)].$$ Similarly, for each real $\varepsilon>0$, each $\delta\in(0,1)$, and all large enough $n$, the set $\{x\in\mathbb{R}\colon qF(n,x)+(1-q)G(n,x)>m_n-\varepsilon\}$ of all $\varepsilon$-maximizers contains the set $\{x\in\mathbb{R}\colon qF(n,x)+(1-q)G(n,x)>1-\varepsilon\}$, which in turn contains the interval $$\{x\in\mathbb{R}\colon|cx/n+b_1+\mu+d/2|\le(1-\delta)d/2\}. $$

$\endgroup$
4
  • $\begingroup$ I am sorry I couldn't follow your argument although I think your approach would be of great help. For instance when I rewrite I get $P(AY_n+B(n-Y_n)+Cx+Z\sigma<n)$ but this looks something different. Also the argument where you refer to the law of large numbers is not clear to me. Could you clarify a bit more? $\endgroup$
    – juror
    Commented Jul 28, 2015 at 15:06
  • $\begingroup$ I have added the addendum with the requested details. $\endgroup$ Commented Jul 28, 2015 at 20:20
  • $\begingroup$ Thank you.. I think I see now. On the other hand, can we say something about the behavior of $\arg\max_x \left\{qF(n,x)+(1−q)G(n,x)\right\}$ as $n\rightarrow \infty$? $\endgroup$
    – juror
    Commented Jul 29, 2015 at 9:50
  • $\begingroup$ juror: I have added Addendum 2, on $\text{arg max}$, as you requested. $\endgroup$ Commented Jul 29, 2015 at 15:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .