How to calculate the the number of nonzero for Poisson binomial distribution

71 Views Asked by At

Suppose a sequence of random number $S$, each entry has probability $p_i$ to be 1, otherwise choose zero. The sequence of probability is not necessary identical. According to wiki, we can compute the mean and variance $\mu=\sum_{i=1}^{n} p_i, \sigma^2=\sum_{i=1}^{n}(1-p_i)p_i$. I know the expected number of nonzero variable is $\mu$ .

In order to get the upper bound of number of non-zero number with high probability, I apply Chernoff bound to get the upper tail bound $P(X\leq a)=e^{-sa}M_{X}(s)$ for all $s > 0$. By minimize the RHS, we can achieve upper bound of $X$ under high probability.

But according to wiki, the Chernoff bound will have the form: $Pr(S\geq s) \leq exp(s-\mu-slog\frac{s}{\mu})$. Here the RHS will monotonic decrease for all $s>\mu$. This will not given any useful upper bound. Further more, I think the number of nonzero entry must related to the length of sequence, since the longer sequence get, the more nonzero entry it will has.

How can I have the proper upper bound of this Chernoff bound?