Galton Board Simulation

From bounces to the binomial distribution

A ball passing r rows makes r independent left-or-right choices, going right with probability p. Its final bin K is the number of right bounces, and the order does not matter: every path with k rights ends in bin k. There are C(r, k) such paths — the numbers in Pascal’s triangle — each with probability p^k(1 − p)^r−k:

On the default board with 12 rows, 924 of the 4,096 equally likely paths end in the middle bin, 22.6%, and only one path reaches each edge. Because K is a sum of independent bounces, its mean is rp and its variance rp(1 − p): 6 and 3 on the default board.

Step drops a single ball and draws its path. Tilting the board (changing p) shifts the pile and, for p far from ½, makes it lopsided.

When the normal curve fits

The de Moivre–Laplace theorem says that as the number of rows grows, the binomial distribution approaches a normal curve with the same mean and variance. The dashed line in the histogram is that curve, N(rp, rp(1 − p)), evaluated as a density; the readout max pmf error is the largest gap between it and the exact binomial probabilities.

For a level board with 12 rows the gap is under half a percentage point. With 5 rows and p = 0.1 it reaches 14 points: the binomial is piled against the left wall while the normal curve spills below zero. A common rule of thumb asks for rp and r(1 − p) both to be at least 5 before trusting the approximation. The same effect, in general form, is the central limit theorem.

Francis Galton described the device, which he called a quincunx, in Natural Inheritance (1889).

How the simulation works

1. For each ball, draw r uniform numbers; a number below p is a bounce to the right. The bin is the count of right bounces, and the sequence of bounces is kept for drawing the path.
2. Add the ball to its bin and compare the bin frequencies with the binomial probabilities: mean, variance and total variation distance (half the summed absolute gaps).

Seen from above, each ball’s horizontal position is a random walk of r steps, and the bins record where such walks end.

Example result

With seed 42, 1,000 balls through 12 rows with p = 0.5 landed with a mean bin of 6.059 (theory 6.000) and a variance of 2.810 (theory 3.000). The total variation distance between the bin frequencies and Binomial(12, 0.5) was 0.0296; the normal curve differs from the binomial probabilities by at most 0.0047.

Implementation

The page runs simulation.js from the package below; the Python file is a line-by-line port with the same random-number generator, so a given seed produces the same result in both languages. The excerpts show the core of each.

// One ball: at each of r rows it bounces right with probability p. The bin it
// lands in is the number of right bounces, so bins follow Binomial(r, p).
// path has bit i set when the ball went right at row i (used for drawing).
export function dropBall(r, p, rng) {
  let bin = 0, path = 0;
  for (let i = 0; i < r; i++) {
    if (rng.uniform() < p) { bin++; path |= 1 << i; }
  }
  return { bin, path };
}

// Binomial(r, p) probabilities by the ratio P(k+1)/P(k) = (r − k)/(k + 1) · p/q.
export function binomialPmf(r, p) {
  const q = 1 - p;
  let p0 = 1;
  for (let i = 0; i < r; i++) p0 *= q;
  const pmf = [p0];
  for (let k = 0; k < r; k++) pmf.push((pmf[k] * (r - k)) / (k + 1) * (p / q));
  return pmf;
}

// Normal approximation N(rp, rp(1 − p)) evaluated at the bin centers.
export function normalDensity(x, mu, variance) {
  return Math.exp(-((x - mu) * (x - mu)) / (2 * variance)) / Math.sqrt(2 * Math.PI * variance);
}

def drop_ball(r, p, rng):
    """Bounce right with probability p at each of r rows; the bin is the number
    of right bounces, so bins follow Binomial(r, p)."""
    b = 0
    for _ in range(r):
        if rng.uniform() < p:
            b += 1
    return b


def binomial_pmf(r, p):
    """P(k) for k = 0..r via P(k+1)/P(k) = (r - k)/(k + 1) * p/q."""
    q = 1 - p
    p0 = 1
    for _ in range(r):
        p0 *= q
    pmf = [p0]
    for k in range(r):
        pmf.append(pmf[k] * (r - k) / (k + 1) * (p / q))
    return pmf


def normal_density(x, mu, variance):
    return math.exp(-((x - mu) * (x - mu)) / (2 * variance)) / math.sqrt(2 * math.pi * variance)

Run the full model from a terminal:

node simulation.js --rows 12 --balls 1000 --seed 42
python simulation.py --rows 12 --balls 1000 --seed 42

Download the model

Assumptions & limitations

• Independent, identical bounces. Every peg sends the ball right with the same probability p, regardless of its earlier bounces. On a physical board balls carry momentum, can skip a peg and collide with each other, so their bounces are not independent.
• One peg per row. A ball meets exactly one peg in each row; bins have no capacity limit.
• The animation is for display. Balls in flight are drawn along their precomputed paths; the statistics count every ball once it is dropped, and the numbers do not depend on the animation speed.
• Sample variance. The simulated variance divides by n − 1.

Related simulations

• OS-011Central limit theoremAverage n draws from almost any distribution and the means turn normal — at a speed you can measure.
• OS-007Dice rollRoll k dice with s sides and check the histogram of sums against the exact distribution.
• OS-012Random walkCoin-flip steps on a line or grid: distance grows like √n, and in 1-D and 2-D every walker comes back.
• OS-006Coin flipFlip a fair or biased coin: the share of heads settles down, and long streaks keep happening.

Background: Pseudo-Random Numbers and Seeds in Simulation

References

1. Galton, F. (1889). Natural Inheritance. Macmillan.
2. Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. Wiley.
3. Grinstead, C. M. & Snell, J. L. (1997). Introduction to Probability, 2nd ed. American Mathematical Society. math.dartmouth.edu/~prob/prob/prob.pdf