Upper Bound on Difference of Expected Values of Poisson Binomial Distributions

Question

Let $X,Y$ be $2$ Poisson Binomial Distributions supported on $[n] = \{i | i \in \mathbb{Z}, 0\leq i\leq n \}$. Denote by $d(X,Y)$ their total variation distance. I would like to find an upper bound on the absolute value of the difference of their expected values, assuming that $d(X,Y) \leq \epsilon$, where $0<\epsilon<1$.

After some experimenting in R it seems that \begin{equation} |\mathbb{E}[X] - \mathbb{E}[Y]| \leq \epsilon \log n \end{equation} holds with probability at least $9/10$, which maybe means that the correct bound lies in $\mathcal{O}(\epsilon \log n)$.

References to such bounds or ideas on how to prove this bound (or a similar one) would be very helpfull.

Answer 1

Let $X,Y$ be two Poisson Binomial Distributions. Let $\mu_x = \mathbb{E}[X],\ \mu_y = \mathbb{E}[Y],\ \sigma_x^2 = Var(X),\ \sigma_y^2 = Var(Y)$. For any $\epsilon>0$, such that $\sigma_x^2 ,\sigma_y^2 \geq n\epsilon\ln(n/e)/2$, if $X,Y$ are $\epsilon$-close, that is $d(X,Y) < \epsilon$, then \begin{align*} \left| \mu_y - \mu_x \right| \leq \frac{ 2\epsilon + \sqrt{\epsilon} \left(\sigma_x +\sigma_y\right) }{1-\epsilon} = O\left(\sqrt{\epsilon} (\sigma_x +\sigma_y)\right) \end{align*}

Proof

Let $Z$ be a random variable. Denote by $F_z,\ \bar{F}_z$ the cumulative and the complementary cumulative distribution of $Z$ respectively. Define $\delta_i :=F_x(i) - F_y(i)$. Without loss of generality assume that $\mu_y > \mu_x$. \begin{align*} \mu_y - \mu_x &= \sum_{i=0}^n \left(\bar{F}_y(i) - \bar{F}_x(i)\right) \\ & = \sum_{i=0}^n\left(F_x(i) - F_y(i)\right) \\ &\leq \sum_{i=0}^{\mu_x-\sigma_x/\sqrt{\epsilon}} \delta_i + \sum_{i=\mu_x-\sigma_x/\sqrt{\epsilon}}^{\mu_y+\sigma_y/ \sqrt{\epsilon}} \delta_i + \sum_{i=\mu_y+\sigma_y/\sqrt{\epsilon}}^{n} \delta_i \end{align*} The contribution of the lower tails of $X,Y$ is at most $\epsilon$ \begin{equation*} \sum_{i=0}^{\mu_x-\sigma_x/\sqrt{\epsilon}} \delta_i \leq \sum_{i=0}^{\mu_x-\sigma_x/\sqrt{\epsilon}} F_x(i) \ \leq\ n F_x\left(\mu_x -\sigma_x/\sqrt{\epsilon}\right) \ \leq\ n \exp\left(-\frac{2\sigma_x^2}{n\epsilon}\right) \ \leq\ \epsilon \end{equation*} For the second inequality we used the Chebyshev inequality. for the last the fact $\sigma_x^2\geq n\epsilon \ln\left(n/\epsilon\right)/2$. In the same way one can show that the contribution of the upper tails is at most $\epsilon$.

Notice that $d(X,Y) \leq \epsilon$ implies $\left| F_x(i) - F_y(i) \right| \leq \epsilon$ for every $i$. \begin{equation*} \sum_{i=\mu_x-\sigma_x/\sqrt{\epsilon}}^{\mu_y+\sigma_y/ \sqrt{\epsilon}} \leq \left( \mu_y +\sigma_y/\sqrt{\epsilon} - \mu_x + \sigma_x/\sqrt{\epsilon} \right) \epsilon = \left(\mu_y - \mu_x\right) \epsilon + \left(\sigma_x +\sigma_y\right) \sqrt{\epsilon} \end{equation*} Use the above inequalities to obtain \begin{align*} \mu_y -\mu_x &\leq 2\epsilon + \left(\mu_y - \mu_x\right) \epsilon + \left(\sigma_x +\sigma_y\right) \sqrt{\epsilon} \\ & \leq \frac{ 2\epsilon + \sqrt{\epsilon}\left(\sigma_x +\sigma_y\right)}{1-\epsilon} \\ & = O\left(\sqrt{\epsilon} (\sigma_x +\sigma_y)\right) \end{align*}

Answer 2

Let $(p_1,\dots,p_n)$ and $(q_1,\dots,q_n)$ be the probability vectors underlying trial vectors $X^n = (X_1,\dots,X_n)$ and $Y^n = (Y_1,\dots,Y_n)$, and let $X = \sum_i X_i$ and $Y = \sum_i Y_i$.

We have

\begin{align} |\mathbb E X - \mathbb E Y| = | \sum_i \mathbb E(X_i-Y_i)| &= | \sum_i (p_i - q_i)| \\ &\le \sum_i | p_i - q_i| \\ &= \sum_i d_{TV}(X_i,Y_i) \end{align}

Dealing with total variation of the product measure $d_{TV}(X^n,Y^n)$ is not easy (and perhaps the same holds for $d_{TV}(X,Y)$. Either the Hellinger distance or Kullback-Liebler divergence are better behaved under products.

It might be easier to bound everything in terms of $\| p - q\|_1 = \sum_i |p_i - q_i|$. Assume that this quantity is $\le \epsilon$, then we have $|\mathbb E X - \mathbb E Y| \le \epsilon$ and \begin{align} [d_{TV}(X^n,Y^n)]^2 \le 2 H^2(X^n,Y^n) \le 2 \sum_i H^2(X_i,Y_i) \le 2 \sum_i d_{TV}(X_i,Y_i) \le 2\epsilon. \end{align}

EDIT. Assume $d_{TV}(X^n,Y^n) \le \epsilon$. Then, $\alpha_j := \frac{p_j}{1-p_j} \prod_{i=1}^n (1-p_i)$ is the probability of $X_j = 1$ and $X_i = 0, i\neq j$. Similarly, define $\alpha := \prod_{i=1}^n (1-p_i)$ (the probability of all of them being zero) and $\beta_j = \frac{q_j}{1-q_j} \prod_{i=1}^n (1-q_i)$ and $\beta := \prod_{i=1}^n (1-q_i)$.

From the assumption it follows that $\sum_j |\alpha_j - \beta_j| \le \epsilon$ (the event that exactly one of them is equal to 1), and $|\alpha - \beta| \le \epsilon$. Then, \begin{align*} \sum_j \Big( \frac{p_j}{1-p_j} - \frac{q_j}{1-q_j} \Big) &= \sum_j \Big( \frac{\alpha_j}{\alpha} - \frac{\beta_j}{\beta} \Big) \\ &= \sum_j \Big( \frac{\alpha_j}{\alpha} - \frac{\alpha_j}{\beta} + \frac{\alpha_j}{\beta}- \frac{\beta_j}{\beta} \Big)\\ &= \Big( \frac1\alpha - \frac1\beta \Big)\sum_j\alpha_j + \frac1\beta \sum_j\big(\alpha_j- \beta_j \big) \end{align*} Assuming $\alpha,\beta \ge c^{-1}$ for some constant $c > 0$, we have $|\alpha^{-1} - \beta^{-1}| \le c^2 \epsilon$. We also have $|\sum_j \alpha_j| \le 1$. It follows that \begin{align*} \sum_j \Big| \frac{p_j}{1-p_j} - \frac{q_j}{1-q_j} \Big| \le 2 c^2 \epsilon + c \epsilon \end{align*} Consider the map $x \mapsto f(x):=x/(1+x)$ on $[0,1]$ which has derivative $(1+x)^{-2}$, hence Lipschitz with constant $1$ on $[0,1]$. We have \begin{align*} |p_j - q_j| = \Big| f\Big(\frac{p_j}{1-p_j}\big) - f\Big(\frac{q_j}{1-q_j}\Big) \Big| \le \Big| \frac{p_j}{1-p_j} - \frac{q_j}{1-q_j}\Big|. \end{align*} It follows that \begin{align*} \sum_j \big| p_j - q_j \big| \le 2 c^2 \epsilon + c \epsilon. \end{align*} The condition $\alpha,\beta \ge c^{-1}$ seems to hold if $p_j,q_j \approx 1/n$ in which case both $\alpha,\beta$ approach $\approx e^{-1}$ as $n \to \infty$.