Sum of Bernoulli random variables with different success probabilities 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$?
 A: 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).
