The definition of Poisson binomial distribution is shown as https://en.wikipedia.org/wiki/Poisson_binomial_distribution, where $n$ independent trails with success probabilities $p_1,p_2,\ldots,p_n$. (The binomial distribution is a special case of the Poisson binomial distribution that $p_1=p_2=\cdots=p_n$.)

Let $X$ be a random variable following a Poisson binomial distribution, where $n$ independent trails with success probabilities $p_1,p_2,\ldots,p_i,\ldots,p_n$.

Suppose that we arbitrarily reduce a probability $p_i$ to $p'_i$ ($p_i > p'_i$), and have another random variable $Y$, which follows a Poisson binomial distribution with success probabilities $p_1,p_2,\ldots,p'_i,\ldots,p_n$.

Compared to the Poisson binomial distribution followed by $X$, the Poisson binomial distribution followed by $Y$ only has the same $p_1,\ldots,p_n$ except a lower $p'_i$. My goal is to show that $P(X\geq k) \geq P(Y \geq k)$, for any fixed $k \in \{1,\ldots,n\}$. In other words, I want to prove that $P(X\geq k)$ is a monotonic increasing function of $p_i$ for all $i = 1$ to $n$. The result looks simple, but I am struggling to prove that.

Note that $P(X\geq k) = \sum_{l=k}^n \sum_{A\in F_l} \prod_{i\in A} p_i \prod_{j\in A^c} (1-p_j) $ from Wikipedia. It is very hard to use an algebraic proof to show that $P(X\geq k) \geq P(Y \geq k)$. Can somebody give me a help?

  • $\begingroup$ Start from $X=Z_1+\cdots+Z_n$ with $(Z_k)$ independent Bernoulli, $P(Z_k=1)=p_k$ and $P(Z_k=0)=1-p_k$ for every $k$, and consider $Y=Z_1+\cdots+Z_{i-1}+Z'_i+Z_{i+1}+\cdots+Z_n$ with $Z'_i$ independent of $(Z_k)_{k\ne i}$ and Bernoulli $P(Z'_i=1)=p'_i$ and $P(Z'_i=0)=1-p'_i$. It happens that $Y$ is Poisson binomial as desired and that this is doable with $$Z'_i\leqslant Z_i\qquad\text{almost surely}\qquad(\ast)$$ then $$Y\leqslant X\qquad\text{almost surely}$$ which implies that, for every $x$, $$P(Y\geqslant x)\leqslant P(X\geqslant x)$$ Now, can you realize $(\ast)$? $\endgroup$ – Did May 14 '17 at 9:22

Let $X$ and $Y$ be two random variables. A coupling between $X$ and $Y$ is a realization of $X$ and $Y$ on a common probability space, that is, a random variable $(\hat{X}, \hat{Y})$ such that $X = \hat{X}$ in distribution and $Y=\hat{Y}$ in distribution. There is a convenient characterization of stochastic domination by couplings of random variables:


Let $X$, $Y$ be two real-valued random variables. The following properties are equivalent :

  • $\mathbb{P} (X \leq t) \leq \mathbb{P} (Y \leq t)$ for all $t \in \mathbb{R}$.

  • There exists a coupling $(\hat{X}, \hat{Y})$ between $X$ and $Y$ such that $\hat{X} \geq \hat{Y}$ almost surely.

If these properties hold, we say that $X$ stochastically dominates Y. See e.g. Chapter 4.3 here [pdf]. By the way, the beginning of that text is a nice introduction to the notion of coupling, if you need it.

Let $X \sim B((p_i))$ and $X' \sim B((p'_i))$, with $p_i \geq p'_i$. We merely need to find a coupling $(\hat{X}, \hat{X}')$ between $X$ and $X'$ such that $\hat{X} \geq \hat{X}'$ almost surely. There is a common trick (see Examples 4.2 and 4.3 in the text): set $(U_i)_{1 \leq i \leq n}$ a sequence of independent random variables with uniform distribution in $[0,1]$. Let:

  • $\hat{X}_i := \mathbf{1}_{U_i \leq p_i}$ and $\hat{X} := \sum_{i = 1}^n \hat{X}_i$;

  • $\hat{X}'_i := \mathbf{1}_{U_i \leq p'_i}$ and $\hat{X}' := \sum_{i = 1}^n \hat{X}'_i$.

Then the $\hat{X}_i$ are independent with distribution $B(p_i)$, so $\hat{X} = X$ in distribution. The same holds for $\hat{X}'$ and $X'$. Hence, $(\hat{X}, \hat{X}')$ is a coupling between $X$ and $X'$. Finally, $\hat{X}_i \leq \hat{X}'_i$ for all $i$, so $\hat{X} \leq \hat{X}'$.

This result can be generalized:


Let $(X_i)_{1 \leq i \leq n}$ and $(Y_i)_{1 \leq i \leq n}$ be two sequences of independent random variables. If $X_i$ stochastically dominates $Y_i$ for all $i$, then $\sum_{i=1}^n X_i$ stochastically dominates $\sum_{i=1}^n Y_i$.

What you want can be deduced by noticing that a $B(p)$ random variable dominates a $B(q)$ random variable if $p \geq q$, and setting the $X_i$'s accordingly.

  • $\begingroup$ I was wondering if you could give me the citation of the theorem (properties). I have interests to know how to prove that. $\endgroup$ – jason May 16 '17 at 5:55
  • $\begingroup$ @jason : everything is in the linked .pdf (Theorem 4.23 and Corollary 4.27 respectively, with proofs). $\endgroup$ – D. Thomine May 16 '17 at 19:05
  • 1
    $\begingroup$ Let me add, for future readers, that the present question only uses the easy (converse) direction of the theorem. Clearly if there is a coupling with an inequality, then stochastic domination follows by inclusion of events. The other way around is not needed here (but interesting nonetheless, and the proof is very nice.) $\endgroup$ – justt Apr 24 at 7:39

For the sake of completeness, I want to provide a simpler proof based on the idea of Did.

Let $X=Z_1+\dots+Z_n$, where $Z_j$ are independent Bernoulli variables with $P(Z_j=1)=p_j$ for every $j$. Let further $X'=Z_1+\dots+Z_{i−1}+Z_{i+1}+\dots+Z_n$, where $Z_i$ is missing. Now, the cumulative distribution is given by

\begin{align*} P(X\geq k) &= P(X'\geq k \land Z_i = 0) + P(X'\geq k-1 \land Z_i = 1) \\ &= P(X'\geq k) (1-p_i) + P(X'\geq k-1)p_i \\ &= p_i P(X'= k-1) + P(X'\geq k), \end{align*} where we used that $P(X'\geq k-1) - P(X'\geq k) = P(X'= k-1)$. Now, the factor $P(X'= k-1)$ in front of $p_i$ is non-negative and therefore the cumulative distribution $P(X\geq k)$ is monotone in $p_i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.