Let $X_{i} \in \{0,1\}$ be Bernouli random variable with probability of success $p_{i}$, i.e., $P(X_{i}=1) = p_{i}$ and $P(X_{i}=0) = 1-p_{i}$ and let $Y=\sum_{i=1}^{n}X_{i}$ for $n>0$. Is it relatively simple to estimate the pmf $P(Y=y)$ when $p_{i} \neq p_{j}$ for $i \neq j$?
Asked
Active
Viewed 1.4k times
13
-
Not quite iid, the $p_i$ are not the same. – André Nicolas May 15 '13 at 21:14
-
Answer: not in the general case. – Did May 15 '13 at 21:19
1 Answers
15
What you are describing is called a Poisson Binomial Distribution (PBD). In what sense do you want to estimate it?
If you are looking to some approximate learning of the distribution, based on samples drawn from it, you can have a look at this paper. It gives a (randomized) algorithm which, given access to i.i.d. draws from a PBD $p$ and a parameter $\varepsilon>0$, uses $\tilde{O}(\varepsilon^{-3})$ samples (no dependence on $n$), runs in polynomial time (in $\log n$ and $\varepsilon^{-1}$) and with high probability, outputs a representation of a probability distribution which is close (in terms of statistical distance — that is, $L_1$ distance, up to a factor 2) to the distribution $p$.
The distribution outputted by the algorithm is not a PBD, though; if you insist on getting a PBD, this is possible with the same number of samples, but a blowup in the running time of the algorithm (now superpolynomial in $\varepsilon^{-1}$).
Remarks: $\tilde{O}(\varepsilon^{-3})$ means $O(\varepsilon^{-3}\mathrm{poly}(\log(\varepsilon^{-1})))$ (the tilde "hides" the logarithmic factors).
Clement C.
- 67,323