How to show a possion binomial random variable dominates another possion binomial random variable with a smaller probability value?

Question

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?

Answer 1

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:

Theorem

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:

Theorem

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.

Answer 2

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