# Inequality involving random variables

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.)

-

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.