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?

  • 1
    $\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, 2017 at 9:22

2 Answers 2


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, 2017 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, 2017 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, 2019 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .