5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – A.S. Nov 28 '15 at 1:58
  • $\begingroup$ 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. $\endgroup$ – Alt Nov 28 '15 at 2:37
  • $\begingroup$ 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.). $\endgroup$ – Alt Nov 28 '15 at 2:40
  • $\begingroup$ 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? $\endgroup$ – A.S. Nov 28 '15 at 3:28
  • $\begingroup$ @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). $\endgroup$ – Alt Nov 28 '15 at 3:51
7
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Alt Dec 4 '15 at 20:53
  • 1
    $\begingroup$ 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)$. $\endgroup$ – r.e.s. Nov 22 '16 at 14:46
  • $\begingroup$ NICE paper (+1) $\endgroup$ – tired Nov 22 '16 at 22:17

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.