# Distribution of weighted sum of Bernoulli RVs

Let $x_1,...,x_m$ be drawn from independent Bernoulli distributions with parameters $p_1,...,p_m$.

I'm interested in distribution of $t=\sum_i a_ix_i,~a_i\in \mathbb{R}$

$m$ is not large so I can not use central limit theorems.

I have the following questions:

1- What is the distribution of $s=\sum_i x_i$?

2- What is the distribution of $t=\sum_i a_ix_i$ or $t=\sum_i a_ix_i-\sum_i a_i$ (to ensure non-negative support) for known $a_i$'s? can I approximate its distribution with a Gamma distribution? If yes, what would be the parameters (as a function of $p_i$'s and $a_i$'s)?

3- Is there a truncated Gamma distribution (or any other distribution (except normal)) that can approximately fits my problem?

However, $m$ is not very large, but it is still very large such that I can not calculate the distribution by convolution.

Thanks a bunch!

• Any kind of limitations of $a_i$'s? Without them, there isn't much you can say (for example take $a_i=2^{i-1}$ and $p_i=1/2$ to yield $t=U[0,2^m-1]$ or take $a_1=1$ to yield an almost normal). – A.S. Nov 28 '15 at 1:58
• For large $m$, you can use the Linderberg-Feller's central limit theorem, and approximate it with a normal. But, I would like to know if there is another any other distribution that can approximate it. Especially when $m$ is not very large. – Alt Nov 28 '15 at 2:37
• We know that $p_i$'s are relatively small (say less than $0.05$, and $a_i$'s have lower and upper bounds (which can be enforced if needed. However, it's better not restrict them.). – Alt Nov 28 '15 at 2:40
• Set all but one $a_i$ to zero. You'll get a scaled Bernoulli variable. Set all $a_i=1$ - you'll get $\approx Pois(\sum p_i)$. You must restrict $a_i$, $p_i$ and $a_ip_i$ further to get any kind of convergence results. Your question, as it is, is similar to asking if $\sum x_i$ converges without any additional info on $x_i$. Can you introduce some distribution on $a_i$'s as well? – A.S. Nov 28 '15 at 3:28
• @A.S., thanks! This is leading to something. So what restrictions on $a_i$, $p_i$, and $a_ip_i$ result in a common (actually I mean off-the-shelf) approximate distribution? (keeping in mind that $m$ is not very large). – Alt Nov 28 '15 at 3:51

I did some search and this is what I have found:

• Bounds for tail probabilities of a weighted sum of Bernoulli trials
This seminal paper of Raghavan in 1988: "Probabilistic Construction of Deterministic Algorithms: Approximating packing integer programs". In section 1.1 he derives some bounds, which seems to be important as part of an stochastic optimization technique called randomized rounding.
• Learning the distribution of a weigthed sum of Bernoulli trials
In this paper published this year by Daskalis et al.: "Learning Poisson Binomial Distributions". In theorem 2 they states that it's possible to construct an algorithm that learns the desired distribution in polynomial time.
• Code to compute the distribution of a weigthed sum of Bernoulli trials
This post in researchgate.net of Dayan Adoniel also asked the same and it seems that Dayan developed a code to compute the desired distribution and that he is willing to share it.

Unfortunately I do not have the time now to go over the details of the first two references but hopefully you can find them useful.

Edit 1: Bounds in the tails of the distribution of a weighted sum of independent Bernoulli trials [Raghavan, 1988]

Let $a_1, a_2, \ldots, a_r$ be reals in $(0, 1]$. Let $X_1, X_2, \ldots, X_r$ be independent Bernoulli trials with $E[X_j] = p_j$. Define $\Psi = \sum_{j=1}^r a_jX_j$ with $E[\Psi] = m$.

Theorem 1 (Deviation of $\Psi$ above its mean). Let $\delta > 0$ and $m = E[\Psi] > 0$. Then

$$\mathbf{P}(\Psi > m(1+\delta)) < \left[\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right]^m.$$

Theorem 2 (Deviation of $\Psi$ below its mean). For $\gamma \in (0,1]$,

$$\mathbf{P}(\Psi-m < -\gamma m) < \left[\frac{e^\gamma}{(1+\gamma)^{(1+\gamma)}}\right]^m.$$

• Thanks! Raghavan's paper, and Theorem 2 from Daskalis et al. are close to what I need. However my weights are not drawn from Rayleigh so the Dayan's code doesn't directly work here. (Although I might be wrong, and might actually be a good idea to assume that the weights also follow a distriution.) I appreciate it if you can fill in the details (from the theorems) as your time allows. – Alt Dec 4 '15 at 20:53
• There's a typo in the LHS of the Theorem 2 inequality: Raghavan's paper has $\mathbf{P}(\Psi-m < -\gamma m)$, not $\mathbf{P}(\Psi-\gamma < -\gamma m)$. – r.e.s. Nov 22 '16 at 14:46
• NICE paper (+1) – tired Nov 22 '16 at 22:17