# Prove the monotonicity of the expectation of a binary random variable function

Consider $R$ independent binary random variables $y^1, \ldots, y^R$ over the space $\{-1, +1\}$ such that $\Pr(y^j = 1) = p^j \geq 0.5$ and $\Pr(y^j = -1) = 1 - p^j$, $\forall j = 1,\ldots,R$. Moreover, let $\mathcal{J}$ denote a subset of $\mathcal{Y} = \{1, \ldots, R\}$, i.e., $\mathcal{J} \subseteq \mathcal{Y}$. I would like to prove that:

$f(\mathcal{J} \cup \{j'\}) \geq f(\mathcal{J}) \quad \forall \mathcal{J} \in 2^{\mathcal{Y}}, \forall j' \in \mathcal{Y} \setminus \mathcal{J}$

where the function $f( \cdot )$ is defined as follows:

$f(\mathcal{J}) = E\left(| \sum_{j \in \mathcal{J}} y^j |\right)$

In other words, I want to verify that the afore-mentioned expectation is monotonically non decreasing in the set $\mathcal{J}$. Thanks.

EDIT: I posed a new question about the same proof in case $f(\mathcal{J})$ is altered so that $f(\mathcal{J}) = E\left(| \sum_{j \in \mathcal{J}} logit(p^j) y^j |\right)$. The new question can be found here: Where is the fallacy in this coupling argument of two Bernoulli variables?

-

The result holds. By induction on $R$, it suffices to show that if $X=Y_1+\cdots+Y_n$ for independent $\pm1$ Bernoulli random variables $(Y_k)$ with $P[Y_k=1]=p_k\geqslant\frac12$, and if $Y$ is a $\pm1$ Bernoulli random variable independent of $(Y_k)$ with $P[Y=1]=p\geqslant\frac12$, then $$E[|X+Y|]\geqslant E[|X|].$$ Note that $E[|X+Y|]=pE[|X+1|]+(1-p)E[|X-1|]$ and that, for every integer $x$, $$p|x+1|+(1-p)|x-1|-|x|=\mathbf 1_{x=0}+(2p-1)(\mathbf 1_{x\gt0}-\mathbf 1_{x\lt0}).$$ Since $2p-1\geqslant0$ and $X$ is integer valued, $E[|X+Y|]\geqslant E[|X|]$ as soon as $$P[X\gt0]\geqslant P[X\lt0].$$ The last inequality above is not a priori obvious, fortunately it stems from a coupling argument.

To wit, one can assume that, for each $k$, $Y_k=2\mathbf 1_{U_k\leqslant p_k}-1$ where the sequence $(U_k)$ is i.i.d. uniform on the interval $(0,1)$. Let $Y^0_k=2\mathbf 1_{U_k\leqslant\frac12}-1$, then $Y_k^0\leqslant Y_k$ almost surely and the sequence $(Y^0_k)$ is i.i.d. symmetric Bernoulli. In particular, the distribution of $X^0=Y^0_1+\cdots+Y^0_k$ is symmetric hence $P[X^0\gt0]=P[X^0\lt0]$.

Finally, $X^0\leqslant X$ almost surely hence $[X^0\gt0]\subseteq[X\gt0]$ and $[X\lt0]\subseteq[X^0\lt0]$. Thus, $P[X\gt0]\geqslant P[X^0\gt0]=P[X^0\lt0]\geqslant P[X\lt0]$, and we are done.

-
Thank you for your answer. The critial steps are when you say that $Y_k^0 \leq Y_k$ and $X^0 \leq X$ hold almost surely. It seems that a formal proof should verify that $P(X^0 \leq X) = 1$. Moreover, I'm experiencing some difficulties with the notation, what do you mean by stating that $[X^0\gt0]\subseteq[X\gt0]$? Thanks. –  burton0 May 28 '13 at 9:26
The formal proof is in my answer: surely you see why $Y^0_k\leqslant Y_k$ almost surely and why this entails that $X^0\leqslant X$ almost surely. Notation: $[X\gt0]=\{\omega\in\Omega\mid X(\omega)\gt0\}$ and similarly for the other occurrences. –  Did May 28 '13 at 12:27
I am not so confident in coupling arguments, and most probably I interpreted the expression almost surely in a naive way. By taking a look at wikipedia ( link ), it seems that for each $k = 1, \ldots, n$, the variable $Y_k^0$ and $Y_k$ can be coupled so that if $Y_k^0 = 1$ then $Y^k = 1$, while if $Y_k^0 = -1$ then $Y_k = +1$ with probability $\frac{p_k - 0.5}{0.5}$. This should entail that $P(X>0) > P(X<0)$. Could you please clarify a little bit that step of the proof? thanks. –  burton0 May 28 '13 at 12:53
Naive ways are allright but could you clarify which steps of my proof need clarification? (Note that outside information is not needed here and that you can omit the word "coupling" if you want, since I provide the full construction of $Y_k$ and $Y_k^0$ which guarantees that $P[X^0\leqslant X]=1$.) –  Did May 28 '13 at 12:58
As I said, the misunderstanding arises from the fact that it is the first time that I encounter the expression 'almost surely' in the context of probability theory (moreover, english is not my mothertongue). This link clarified your statement. Thanks –  burton0 May 28 '13 at 13:27

wlog $\mathcal T = 1,...,n,.X = \sum^n Y_j, j^{\prime} = n+1$, and that is wlog because you can always go from a smaller set to a larger adding one index at a time, and just number them in the order in which you want to add. First use Jensen's inequalty/ submartingales to show that if you add a symmetric $Y_{n+1}$ the expected value of the absolute value increases. Then use the following argument to show that if $\mathbb P (X > 0) > \mathbb P ( X < 0), \mathbb E(|X + Y_{n+1}|)$ is an increasing function of $p_{n+1}$

let $X$ be integer valued, $Y$ be $\pm 1$ with $\mathbb P(Y=1) = p$. $\mathbb E (|X + Y|) = \mathbb P (X=0) + \sum_{k > 0} \mathbb P(X = k)((k+1) p + (k-1) (1-p)+ \mathbb P(X = -k)((k+1) (1-p) +( k-1)p)$.

$\frac d {dp}$ of that is something like $2 \sum_{k > 0} (\mathbb P (X=k) - \mathbb P(X=-k))$ which is positive in your case. Also, if $p_j = \frac 12$ the expectation is larger by the fact that $|X|, |X+Y_j|$ is a submartingale.

-
I initially thought $(P(X=k)−P(X=−k) > 0$ was obvious, it may not be, but I only need $P(X > 0) > P(X < 0)$ and that is obvious, since you can modify the symmetric sum ($p_j = \frac 12$) by throwing in some extra 1's. –  mike May 27 '13 at 14:15
Thank you for your answer. Unfortunately, the typesetting is not of great help. May I ask you to deepen the steps composing your proof? –  burton0 May 27 '13 at 14:15
Thank you for reformulating your explanation. By using the Jensen's inequality, I can state that: $E\left(|X + Y^{n+1}|\right) \geq |E\left(X + Y^{n+1}\right)| = |E(X) + E(Y^{n+1})| = |E(X) + (2p^{n+1} - 1)|$. What do you mean when you say simmetric $Y^{n+1}$? Given that $X$ is defined as the sum of some $Y^j$, I also do not understand your explanation on why $P(X > 0) > P(X < 0)$ should be obvious, and why such a condition should be required. Thanks. –  burton0 May 27 '13 at 20:41
symmetic: $p = \frac 12$, note that jensen gives you your inequality only in that case, so you need and extra argument to show that if you increase p your expectation increases. I say 'obvious' because if all $p_j = \frac 12$ then $\sum Y_j$ is symmetric and $P(X>0) = P(X < 0)$, To get to case where some or all $p_j > \frac 12$ simply change some of the -1's to 1's, i.e. you can get $p=\frac 34$ by generating the symmetric one and flipping -is to 1's with probability $\frac 12$. Adding ones increases the probability that $X > 0$ and decreases $P(X < 0)$ –  mike May 28 '13 at 11:28
I agree with you that if $p^j=0.5$, $\forall j=1, \ldots, n$, then $P(X>0)=P(X<0)$. However, I don't understand your explanation for the general case, i.e., $p^j > 0.5$ for some $j=1,…,n$. With respect to your example, let us alter $p^\hat{j}$ so that $p^\hat{j} = \frac{3}{4}$. At this point you claim that the $P(X>0)$ increases while the $P(X<0)$ decreases. However, I do not understand your explanation on why this should happen. Specifically, what do you mean by "you can get $p^\hat{j}=\frac{3}{4}$ by generating the symmetric one and flipping -1s to 1s with probability $\frac{1}{2}$"? –  burton0 May 28 '13 at 12:09