2

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)$,

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

  2. 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}

Martin Zhang
  • 71

2 Answers2

1

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.

combo
  • 1,257
1

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

UPD. You may see some other publications as well:

https://dl.acm.org/doi/abs/10.1145/3460774

https://www.sciencedirect.com/science/article/abs/pii/S0167715220302042

https://www.mdpi.com/2227-7390/9/8/845

Pavel Ruzankin
  • 131