0
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.