# How to approach nested experiments involving binomial distributions

## 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}$$).

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.