2
$\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$
  • $\begingroup$ I think you need to be a bit more specific: what is $f$ and what do you mean with "first order condition"? $\endgroup$ – Per Alexandersson Jun 22 '15 at 17:31
  • $\begingroup$ @PerAlexandersson I tried to specify a bit more by adding an update. $\endgroup$ – juror Jun 22 '15 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$ – Iosif Pinelis Jun 24 '15 at 14:57
  • $\begingroup$ @IosifPinelis $A,B,C\in\mathbb R_{++}$ fixed and $p\in(0,1)$. $\endgroup$ – juror Jun 24 '15 at 16:34
2
$\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$
  • $\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 Jul 28 '15 at 15:06
  • $\begingroup$ I have added the addendum with the requested details. $\endgroup$ – Iosif Pinelis Jul 28 '15 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 Jul 29 '15 at 9:50
  • $\begingroup$ juror: I have added Addendum 2, on $\text{arg max}$, as you requested. $\endgroup$ – Iosif Pinelis Jul 29 '15 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.