6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 15:58

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'd be pleased to see an argument for this that wasn't just brute force calculus. $\endgroup$
    – Noah Stein
    Feb 25, 2013 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, 2013 at 2:35
  • $\begingroup$ You're welcome. It was an interesting problem. $\endgroup$
    – Noah Stein
    Feb 27, 2013 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, 2013 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, 2013 at 23:21
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2013 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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