# Is the Binomial Expectation of Convex Function Convex in p?

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.

-
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) \\,.$$ – cardinal Feb 26 '13 at 4:32
(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.) – cardinal Feb 26 '13 at 4:33
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. – 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.

-
I'd be pleased to see an argument for this that wasn't just brute force calculus. – Noah Stein Feb 25 '13 at 18:27
Thanks for making the effort to write this down! – Suvrit Feb 25 '13 at 18:28
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))$$. – R Hahn Feb 26 '13 at 2:35
Thanks Noah! I appreciate the hustle. – Hugh Medal Feb 27 '13 at 1:55
You're welcome. It was an interesting problem. – Noah Stein Feb 27 '13 at 13:20

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.

-
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. – Hugh Medal Feb 27 '13 at 2:22