A Tail Bound For Poisson Binomial Distribution? Consider the Poisson-Binomial Distribution with two components. Let $Y_0\sim bin(n,p_0)$, $Y_1\sim bin(n,p_1)$, and let $Y=Y_0+Y_1$. For any $k>n(p_0+p_1)$,


*

*Can we upper bound the tail probability $Pr(Y\geq k)$? which decays exponentially when $k$ deviates away from the mean?

*Can we give a sharp bound on the partial expectation $\mathbb{E}[Y~ I_{\{Y\geq k\}}]$, where $I_{\{Y\geq k\}}$ is the indicator function?
Some possible directions:
I think Hoeffding inequality can give a fairly concise bound for the first part: 
\begin{equation}
Pr(Y\geq k) \leq \exp-4n\left[\frac{k}{2n}-n(p_0+p_1)\right].
\end{equation}
 A: I worked on a similar problem, and was able to show that the tail of the Poisson binomial distribution with $N$ events with probabilities $p_1,\dots,p_N$ is upper bounded by the tail of the binomial distribution with parameters $N$ and $\mu = \frac{1}{N}\sum_{k=1}^N p_k$.  I've applied my results to your question, if they are useful for you I can put the proof up (otherwise I don't want to clutter your question).
Assume that $p_0 \le p_1$. For $n >  \frac{2}{p_0}$ and $k \le n + 1 - \frac{2}{p_0}$, the probability mass function of the binomial distribution $bin\left(2n,\frac{p_0+p_1}{2}\right)$ upper bounds the probability mass function of $Y$ (note that you can get the other tail by using $1-p_1$ instead of $p_0$).  Suppose that $n = 1000$, then these conditions are met for $p_0 > 0.002$ and if $p_0 = 0.9$, then it applies for $k \le 998$. Any of the exponential tail bounds for the binomial will give exponential bounds for the Poisson binomial. Using Hoeffding's inequality gives a similar bound to what you had: $\exp\left(-\frac{1}{n}\left((p_0+p_1)n-k\right)^2\right)$. 
Hopefully this will also help you with the conditional expectation, since the Binomial distribution is much easier to analyze.
A: Let $Z_0 \sim {\rm Pois}(np_0)$ and $Z_1 \sim {\rm Pois}(np_1)$ be Piosson r.v.'s. Then, for any $j$,
$${\bf P}(Y_0=j)\le \frac{1}{1-p_0}{\bf P}(Z_0=j), \quad 
{\bf P}(Y_1=j)\le \frac{1}{1-p_1}{\bf P}(Z_1=j)$$
(see Borisov and Ruzankin https://projecteuclid.org/euclid.aop/1039548369 ).
Therefore,
$${\bf P}(Y=j)\le \frac{1}{(1-p_0)(1-p_1)}{\bf P}(Z_0+Z_1=j).$$
In its turn,  the tail of the Poisson distribution can be well approximated by a normal law, see the answer https://stats.stackexchange.com/a/376393/187064
Besides, you may see that paper https://projecteuclid.org/euclid.aop/1039548369 for bounds for Poisson approximation for expectations of unbounded functions, which is the case for ${\bf E}Y\ I(Y\ge k)$.
