Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
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
show 2 more comments

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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