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
    Commented 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
    Commented 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
    Commented Mar 29, 2013 at 15:58

2 Answers 2

Reset to default
8
$\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
    Commented 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
    Commented Feb 26, 2013 at 2:35
  • $\begingroup$ You're welcome. It was an interesting problem. $\endgroup$
    – Noah Stein
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 27, 2013 at 2:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .