# Another question (related to binomial distributions)

## Problem

Let $s,e,k\in \mathbb{N}^*$ and $p\in[0,1]$.

We have the following experiment. $k$ times we're doing the following:
* we're drawing $s$ times a random biased coin with probability $p$ to get heads
* let $n$ be the number of heads
* the output of the experiment is $ne$

The output of the whole experiment is the sum of outputs of the $k$ sub-experiments.

Question: what is the probability that the output is smaller than $\frac{2}{3}kesp$, that is, two thirds of the expected output?

## Formalization

Let $X$ the random variable for the whole experiment, and $Y_i$ the random variable for the $i$th inner experiment.

We have $E[X] = \sum_{i=1}^k E[Y_i] = k \cdot e\cdot sp$.

The probability that the output is $n$ is
$$P[X=n]=\sum_{n_1+\dots+n_{k}=n}\prod_{i=1}^kP[Y_i=n_i]$$
And we have:
* $P[Y_i=ne] = \binom{s}{n}p^n(1-p)^{s-n}$,
* $P[Y_i=m]=0$ for $m$ not a multiple of $e$.

We need to compute
$$\sum_{n=0}^{u}P[X=n]$$
where $u := \lfloor\frac{2}{3}kesp\rfloor$.

But how to compute this numerically (exactly or approximatively), or get a reasonably good upper bound? Values for $s$ and $k$ would be in the thousands (say $2^{13}$), and $e$ would be rather smaller, say $2^i$ with $0\leq i \leq 6$, and $p$ also small (say $p=10^{-5}$).

## Answer

The answer from [stackexchange](https://math.stackexchange.com/questions/4598522/how-to-approach-nested-experiments-involving-binomial-distributions/):

> Assuming sub-experiments are performed independently, the result $X$ of the complete experiment is $e$ times the number of heads in $s·k$ independent coin flips, so $X/e$ is $b(sk, p)$ (i.e. binomially) distributed. Then
$$ \mathbb{P}[X \leq \frac{2}{3}kesp] = \mathbb{P}[X/e \leq \frac{2}{3}ksp] = \mathbb{P}[b(sk,p) \leq \frac{2}{3}ksp]$$

> Since you are interested in large values of $s·k$ and relatively small $p$, this probability can be estimated well by the [Poisson approximation](http://www.stat.yale.edu/~pollard/Courses/241.fall97/Poisson.pdf) of the binomial distribution. If $n$ is sufficiently large, you can also use the [Normal approximation](https://en.wikipedia.org/wiki/Binomial_distribution#Normal_approximation) of the binomial distribution, and this would give an estimate in terms of the CDF $Φ$ of $\mathcal{N}(0,1)$ in a relatively closed form.

A says:

> My distribution would be approximated by $N(skp,skp(1-p))$, and then the desired probability would be approximately $P(Z<\frac{1}{3}\sqrt{\frac{skp}{(1-p)}})$, where $Z$ is the standard normal distribution.