How to approach nested experiments involving binomial distributions

Question

Problem

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

We have the following experiment. We're performing the following sub-experiment $k$ times:

• 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 sub-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?

Next you'll find my approach to formalize the problem, which does not seem to be of much help.

Formalization

Let $X$ the random variable for the whole experiment, and $Y_i$ the random variable for the $i$th sub-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}^{b}P[X=n]$$ where $b := \lfloor\frac{2}{3}kesp\rfloor$.

But how to compute this numerically (exactly or approximately), 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 1

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 of the binomial distribution. If $n$ is sufficiently large, you can also use the 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.