Monotonicity of expectation under binominal distribution

Question

If you are playing a coin-tossing game where throwing more heads is better, then your expected score increases if the probability of “head” increases.

Formally: If $f(i)$ is monotonic in $i$, and $0 \le p \le q \le 1$, then

$$ E[f(X_p)] \le E[f(X_q)] $$

where $X_p \sim \mathit{Binom}(p,n)$, or more explicitly

$$ \sum_{i + j = n} p^i (1-p)^j \binom n i f(i) \le \sum_{i + j = n} q^i (1-q)^j \binom n i f(i) $$

How would I go about proving that?

Answer 1

Intuitively, one can approach this by considering a three-sided coin, with probabilities $p$, $q-p$ and $1-q$, and represent the binominal expectation via the multinomial expectation. This idea leads to the following proof:

$$\begin{align} \sum_{i + j = n} p^i (1-p)^j \binom n i f(i) &= \sum_{i + j = n} p^i (1-p)^j \binom n i f(i) \underbrace{\sum_{k + l = j} \left(\frac{q-p}{1-p}\right)^k \left(1-\frac{q-p}{1-p}\right)^l \binom j k}_{= 1} \\ &= \sum_{i + k + l = n} p^i (1-p)^{k + l} \binom n i f(i) \left(\frac{q-p}{1-p}\right)^k \left(1-\frac{q-p}{1-p}\right)^l \binom j k \\ &= \sum_{i + k + l = n} p^i (q-p)^k (1-q)^l \binom n i \binom j k f(i) \\ &= \sum_{i + k + l = n} p^i (q-p)^k (1-q)^l \frac{n!}{i!j!k!} k f(i) \\ &\le \sum_{i + k + l = n} p^i (q-p)^k (1-q)^l \frac{n!}{i!j!k!} f(i+k) \\ &= \sum_{i + k + l = n} \left(\frac{p}{q}\right)^i \left(1 - \frac{p}{q}\right)^k q^{i+k} (1-q)^l \binom{n}{i+k} \binom{i+k}{i} f(i+k) \\ &= \sum_{m + l = n} \underbrace{\sum_{i + k = m} \left(\frac{p}{q}\right)^i \left(1 - \frac{p}{q}\right)^k \binom{m}{i}}_{=1} q^{m} (1-q)^l \binom{n}{m} f(i+k) \\ &= \sum_{m + l = n} q^{m} (1-q)^l \binom{n}{m} f(i+k) \end{align}$$

Answer 2

Let $U_1, U_2,\ldots,U_n$ be iid random variables, uniformly distributed in $[0,1]$. For $p\in(0,1)$ define a random variable $$ X(p):=\sum_{k=1}^n 1_{\{U_k\le p\}}. $$ Clearly $X(p)$ has the binomial distribution with parameters $n$ and $p$. And if $0<p<q<1$ then $X(p)\le X(q)$. Therefore, still assuming $p<q$, for increasing $f$ you have $f(X(p))\le f(X(q))$, and so $$ E[f(X(p))] \le E[f(X(q))]. $$ The idea here ("coupling") is to use the same source of randomness (the $U_k$) to produce $p$-coin tosses and $q$-coin tosses in an ordered way!