Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have random variables $X_1,\ldots,X_n \in \{0,1\}$ which are dependent and $$\mathbb{P}[X_i=1 | X_1=x_1, \ldots, X_{i-1}=x_{i-1}, X_{i+1}=x_{i+1}, \ldots X_{n}=x_n] \geq p$$ for any $x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n \in \{0,1\}$.

I also have random variables $Z_1,\ldots,Z_n \in \{0,1\}$ which are independent and $\mathbb{P}[Z_i=1]=p$.

What is a simple and yet rigorous way to argue that for any integer $k\geq0$, $$\mathbb{P}[X_1 + \ldots + X_n > k] \geq \mathbb{P}[Z_1 + \ldots + Z_n > k].$$

(I have a very ugly way right now, but it seems that there should be a one-line argument.)

share|cite|improve this question
up vote 2 down vote accepted

Decomposing the random variable $S_{n+1}=X_1+\cdots+X_{n+1}$ into $S_{n+1}=S_n+X_{n+1}$, one gets $$ P(S_{n+1}>k)=P(S_n>k,X_{n+1}=0)+P(S_n>k-1,X_{n+1}=1)=P(S_n>k)+(*), $$ with $$ (*)=P(S_n>k-1,X_{n+1}=1)-P(S_n>k,X_{n+1}=1), $$ that is, $$ (*)=P(S_n=k,X_{n+1}=1)=P(X_{n+1}=1\mid S_n=k)P(S_n=k). $$ Now, your hypothesis means that $P(X_{n+1}=1\mid \mathcal{F}^X_n)\ge p$ almost surely, where $\mathcal{F}^X_n$ denotes the sigma-algebra generated by $\{X_k;k\le n\}$. In particular, for every event $A_n$ in $\mathcal{F}^X_n$, $$ P(X_{n+1}=1\mid A_n)\ge p. $$ For $A_n=[S_n=k]$, the formula for $(*)$ yields $$ P(S_{n+1}>k)\ge P(S_n>k)+pP(S_n=k), $$ hence $$ P(S_{n+1}>k)\ge pP(S_n>k-1)+(1-p)P(S_n>k). $$ The sums built on $(Z_n)$ satisfy this same last relation, with an equality sign instead of an inequality sign. Thus, if the inequality you want to prove holds for a given $n$ and every $k$, it holds for $n+1$ and every $k$. By a recursion over $n$, you are done.

share|cite|improve this answer
Thank you monsieur! – user915 Apr 6 '11 at 9:23

Your Answer


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