Probability · Repeated trials
Flip a coin 100 times, throw a die until a six appears, inspect 1000 light bulbs for defects: the same experiment is repeated many times, independently, and we count how often an event \(A\) happens. One formula, Bernoulli's, answers every question exactly. But for large numbers of trials it becomes impractical, and two approximations take over: the normal curve (de Moivre–Laplace) when \(A\) is reasonably likely, and the Poisson law when \(A\) is rare. This post covers all three and explains when to use which.
Suppose an event \(A\) can occur in each of \(n\) independent repetitions of an experiment, with the same probability \(p\) each time, and let \(q = 1 - p\). If \(\mu\) is the number of times \(A\) actually occurred, the ratio \(\frac\mu n\) is the relative frequency of \(A\) in the series.
Why: a particular sequence with \(m\) successes and \(n - m\) failures, say \(AA\bar A A\bar A\cdots\), has probability \(p^mq^{n-m}\) by independence. The number of such sequences is the number of ways to choose which \(m\) of the \(n\) positions are successes, \(\binom nm\) (the book writes \(C_n^m\)). The probabilities add up to \( (p + q)^n = 1 \) by the binomial theorem, which is where the name comes from.
"At least once" is the complement of "never", and the probability of "never" is \(q^n\). So \(A\) occurs at least once with probability \( 1 - (1 - p)^n \). Requiring this to be at least \(P\) and solving for \(n\) (dividing by \(\log(1 - p) < 0\) flips the inequality):
Compare consecutive probabilities:
\[ \frac{P_n(m + 1)}{P_n(m)} = \frac{n - m}{m + 1}\cdot\frac pq. \]This ratio is \(> 1\) (probabilities increasing) while \( m < np - q \), and \(< 1\) once \( m > np - q \). So the distribution rises to a peak and falls, and the peak is at
The binomial probabilities are the coefficients of \( (q + px)^n = \sum_mP_n(m)x^m \). The same idea works when the trials are independent but have different probabilities \(p_1, p_2, \dots, p_n\) of success:
Why: expanding the product, each term picks from every factor either \(q_i\) (trial \(i\) fails) or \(p_ix\) (trial \(i\) succeeds, contributing one power of \(x\)). The power of \(x\) counts the successes, and the coefficient is the probability of that particular pattern. Collecting equal powers adds up all patterns with \(m\) successes. For equal \(p_i = p\) this is \((q + px)^n\) again.
Suppose each trial has \(k\) mutually exclusive outcomes \(A_1, \dots, A_k\) forming a complete group, with \( P(A_i) = p_i \), \( \sum p_i = 1 \).
The reasoning is the same as for the binomial law; \( \frac{n!}{m_1!\cdots m_k!} \) is the number of ways to arrange the outcomes (a multinomial coefficient). For \(k = 2\) it is the binomial formula.
For large \(n\), the binomial coefficients become huge and the powers tiny, and computing \(P_n(m)\) directly is hard. But the shape of the distribution becomes simple: a bell curve centred at \(np\) with width \(\sqrt{npq}\).
Why the bell curve: \(np\) is the expected number of successes and \(\sqrt{npq}\) is the standard deviation, so \(x\) measures "how many standard deviations \(m\) is from the mean". Applying Stirling's formula \( k! \approx \sqrt{2\pi k}\,(k/e)^k \) to the three factorials in \(\binom nm\), and expanding the logarithm to second order in \(x\), gives exactly \( \frac{1}{\sqrt{2\pi npq}}e^{-x^2/2} \). The factor \(\frac{1}{\sqrt{npq}}\) converts the density \(\varphi(x)\) into the probability of one integer value of \(m\) (one step in \(m\) is a step of \(\frac{1}{\sqrt{npq}}\) in \(x\)).
Usually we need the probability of a range of values, e.g. "between 70 and 90 successes". Adding up the local approximations turns a sum into an integral:
In practice, with \( \Phi(z) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^ze^{-x^2/2}dx \) (tabulated), \( P(m_1 \le m \le m_2) \approx \Phi(x_2) - \Phi(x_1) \). This is the first version of the central limit theorem: the number of successes is approximately normally distributed.
The normal approximation needs \(npq\) to be large. If \(p\) is very small (defective items, misprints, radioactive decays per second) while \(np\) stays moderate, a different limit appears.
Why: with \( p = \frac an \),
\[ P_n(m) = \frac{n(n - 1)\cdots(n - m + 1)}{m!}\,\frac{a^m}{n^m}\Big(1 - \frac an\Big)^{n-m} = \frac{a^m}{m!}\cdot\underbrace{\frac{n(n - 1)\cdots(n - m + 1)}{n^m}}_{\to1}\cdot\underbrace{\Big(1 - \frac an\Big)^n}_{\to e^{-a}}\cdot\underbrace{\Big(1 - \frac an\Big)^{-m}}_{\to1}. \](The sum is \( e^{-a}\sum\frac{a^m}{m!} = e^{-a}e^a = 1 \). The book uses both \(P(m)\) and \(p(m)\) for the same numbers.)
| Situation | Formula |
|---|---|
| small \(n\), exact | \( P_n(m) = \binom nmp^mq^{n-m} \) |
| at least once | \( 1 - q^n \); \( n \ge \frac{\log(1 - P)}{\log(1 - p)} \) |
| most probable \(m\) | \( np - q \le m_0 \le np + p \) |
| different \(p_i\) | coefficients of \( \prod(q_i + p_ix) \) |
| \(k\) outcomes | \( \frac{n!}{m_1!\cdots m_k!}p_1^{m_1}\cdots p_k^{m_k} \) |
| large \(n\), \(npq\) large, one value | \( P_n(m) \approx \frac{1}{\sqrt{npq}}\varphi(x) \) |
| large \(n\), \(npq\) large, a range | \( \Phi(x_2) - \Phi(x_1) \) (+ continuity correction) |
| large \(n\), small \(p\), \(np\) moderate | \( P_n(m) \approx \frac{a^m}{m!}e^{-a} \), \(a = np\) |
Try each one before opening the solution. More solved problems from this topic are in Probability.
\( \binom84/2^8 = \frac{70}{256} \approx 0.273 \); \( 1 - \frac{1}{256} \approx 0.996 \).
\( np - q = 14 - 0.3 = 13.7 \), not an integer: \( m_0 = [21\cdot0.7] = [14.7] = 14 \).
\( n \ge \frac{\log0.05}{\log0.95} \approx 58.4 \): 59 tickets.
\( (0.9 + 0.1x)(0.8 + 0.2x) = 0.72 + 0.26x + 0.02x^2 \).
\( np = 5000 \), \( \sqrt{npq} = 50 \), \( x = \pm1 \): \( \Phi(1) - \Phi(-1) \approx 0.683 \) (about \(0.69\) with continuity correction, \(x = \pm1.01\)).
\( a = \frac{250}{500} = 0.5 \): \( p(0) = e^{-0.5} \approx 0.607 \).
Bernoulli's formula \( \binom nmp^mq^{n-m} \) is the exact answer for repeated independent trials, and its generating function \((q + px)^n\) extends it to unequal probabilities and, as \((p_1x_1 + \cdots + p_kx_k)^n\), to several outcomes. For many trials the binomial distribution takes one of two limiting shapes. When \(npq\) is large it approaches the normal curve (de Moivre–Laplace), the first appearance of the central limit theorem. When \(p\) is tiny and \(np\) moderate it approaches the Poisson law of rare events. Choosing the right one is half of the skill.
Related posts: the Gamma function and Stirling's formula, Hermite polynomials (orthogonal with respect to the Gaussian weight), and Bernoulli polynomials (generating functions).