Suppose $X$ has a binomial distribution with success probability $p$ and $n$ trials and let $h(\cdot)$ be a positive convex real-valued function.

Is the function $g(p)=\mathbb{E}[h(X)\ |\ p]$ convex in $p$?

Related questions: Binomial Expectation of Convex Function and expected values over binomial distributions

Note: Based on trial-and-error analysis, it appears to be convex. If anyone is interested, I can send them a spreadsheet with some numbers.

  • $\begingroup$ Note that we can get a related lower bound using the technique in this answer: mathoverflow.net/questions/94083/…. Namely, wlog let $0 \leq p_1 \leq p_2 \leq 1$, $t \in [0,1]$ and $p = t p_1 + (1-t) p_2$. Then, if $Y = t X_1 + (1-t) X_2$ where $X_1 \sim \mathrm{Bin}(n, p_1)$ and $X_2 \sim \mathrm{Bin}(n,p_2)$, we have $g(p) \geq \mathbb E(t X_1 + (1-t) X_2)$. In other words, together with Noah's answer, $$\mathbb E h(t X_1 + (1-t) X_2) \leq \mathbb E h(X) \leq t \mathbb E h(X_1) + (1-t)\mathbb E h(X_2) \\,.$$ $\endgroup$ – cardinal Feb 26 '13 at 4:32
  • $\begingroup$ (Furthermore, we can couple $X$, $X_1$ and $X_2$ by using the same sequence of iid $\mathcal U(0,1)$ random variables to generate the individual terms in their respective sums.) $\endgroup$ – cardinal Feb 26 '13 at 4:33
  • $\begingroup$ Corollary to Noah's result: Let $p(y)$ be a concave function on $R^+$ with domain $[0,1]$. (An example is $1−\exp{−λy}$.) Then, $g(f(y))=E[h(X) | p(y)]$ is convex on $R^+$. This corollary is useful if we want to add more details to how the probability of success, $p$, changes. Since $p(y)$ is concave, it reflects the diminishing returns associated with allocating more resources, $y$, to increase the success probability, $p$. We may also include some cost for allocating resources. $\endgroup$ – Hugh Medal Mar 29 '13 at 15:58

Here is my original answer (see below for a better one):

Writing down \[ g(p) = \sum_{k=0}^n h(k)\binom{n}{k}p^k(1-p)^{n-k} \] and differentiating twice gives \[ g''(p) = \sum_{k=0}^n h(k)\binom{n}{k} \\ \cdot \left[ k(k-1)p^{k-2}(1-p)^{n-k} - 2k(n-k)p^{k-1}(1-p)^{n-k-1} + (n-k)(n-k-1)p^k(1-p)^{n-k-2}\right]. \] Reindexing the three terms of the summation separately with substitutions $k = l+2$, $k=l+1$, and $k=l$, respectively, gives \[ g''(p) = \sum_{l=0}^{n-2} p^l(1-p)^{n-l-2}\bigg[h(l+2)\binom{n}{l+2}(l+2)(l+1) \\ -2h(l+1)\binom{n}{l+1}(l+1)(n-l-1) + h(l)\binom{n}{l}(n-l)(n-l-1)\bigg], \] and after some canceling we get \[ g''(p) = \sum_{l=0}^{n-2}\left[h(l+2)-2h(l+1)+h(l)\right]\frac{n!}{l!(n-l-2)!}p^l(1-p)^{n-l-2}. \]

So $g$ is convex on the interval $[0,1]$ whenever the second differences of $h$ (the bracketed terms) are nonnegative, e.g. when $h$ is a convex function on $\mathbb{R}$.

A better way to do this is to define the forward difference operator $\Delta$ by $(\Delta h)(l) = h(l+1) - h(l)$. Then calculations similar to, but simpler than, the ones above yield the equation \[ \frac{d}{dp}\mathbb{E}_{X\sim \textrm{Binom}(n,p)}h(X) = n\mathbb{E} _{X\sim \textrm{Binom}(n-1,p)} (\Delta h)(X). \] Applying this twice gives the desired result.

  • $\begingroup$ I'd be pleased to see an argument for this that wasn't just brute force calculus. $\endgroup$ – Noah Stein Feb 25 '13 at 18:27
  • $\begingroup$ Cool. If you want to skip the derivations, you can invoke the property of derivatives of Bernstein polynomials; in the notation from the problem $$b'(x,n)(p)=n(b(x−1,n−1)(p)−b(x,n−1)(p))$$. $\endgroup$ – R Hahn Feb 26 '13 at 2:35
  • $\begingroup$ You're welcome. It was an interesting problem. $\endgroup$ – Noah Stein Feb 27 '13 at 13:20
  • $\begingroup$ After you do the reindexing (k = l + 2, k = l +1, k = 1), the range on the sum is l = 0 to n - 2. I don't quite understand this. Can you help me understand this? I am wondering why there are not 3 separate sums, with the following upper and lower limits: 1st sum: l = -2 to (n-2) 2nd sum: l = -1 to (n-1) 3rd sum: l = 0 to n $\endgroup$ – Hugh Medal Mar 15 '13 at 21:57
  • $\begingroup$ Technically there are, but the coefficients of the binomial coefficients vanish for $l\not\in\{0,\ldots,n−2\}$. For example, the $l+2$ in the first sum vanishes for $l=−2$ and the $l+1$ for $l=−1$. $\endgroup$ – Noah Stein Mar 15 '13 at 23:21

This is known, for more general exponential families in place of the binomial one, from papers of Shaked (1980) and Schweder (1982), see http://www.jstor.org/stable/10.2307/2984960 and http://www.jstor.org/stable/10.2307/4615873.

  • $\begingroup$ Does anyone know of any references to the multivariate case? I.e., $p = (p_1,\dots,p_m)$ and $X = (X_1\sim \text{Binom}(n,p_1),\dots,X_m\sim \text{Binom}(n,p_m))$. I am interested in the case were the random variables in $X$ are independent. $\endgroup$ – Hugh Medal Feb 27 '13 at 2:22

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.