Upper Bound on Difference of Expected Values of Poisson Binomial Distributions 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. 
 A: 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$.
A: 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*}
