Galton board

At the end of the 19th century, the English polymath Sir Francis C. Galton (1822–1911) developed an arrangement to demonstrate the so-called binomial distribution. This arrangement was later called the Galton board in his honor. A version of it is realized in MATHEMATICS ADVENTURE LAND:

Between two glass plates, several 50-cent coins are fixed with three pins each and arranged evenly so that — as an overall structure — an equilateral triangle of twelve “cascades” results (see Figure 1 below):

Figure 1: Schematic representation of the Galton board

If you now let a coin fall in vertically from above, each of these obstacles (i.e., the locked 50-cent coins) decides at random whether it falls to the right or to the left. The probability for this is p=0.5 in each case. Below the Galton board there are several compartments in which the inserted coins are stacked on top of each other. That is, in this way a kind of bar chart is created, which approximates the density of a normal distribution as the number of inserted coins increases. The shape of this density is a bell-shaped curve (“Gaussian bell curve”), as shown in Figure 2 below:

Figure 2: Gaussian bell curve

1-cent, 2-cent, … or 50-cent coins are suitable for carrying out the experiment in MATHEMATICS ADVENTURE LAND.

Note: The coins thrown in for an experiment at the Galton board will later benefit as a contribution to the work of the non-profit(!) association for the promotion of the work of the MATHEMATICS ADVENTURE LAND. This is how the name “money clay board” was created for this exhibit.


And now … the mathematics of it:

The Galton board in MATHEMATICS ADVENTURE LAND has a total of N=12 steps, i.e. the inserted coin has to “decide” for right or left exactly twelve times on its way down. It is reasonable to assume that all these decisions are stochastically independent of each other: Whether the coin decides one way or the other at an obstacle — it does not affect its behavior below. Thus, essentially the same random trial is run twelve times in a row. Accordingly, then, there are exactly

    \[2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2=2^{12}= 4.096\]

Possibilities of how the coin can behave. Each of these possibilities corresponds to exactly one path in the associated tree diagram. However, what is counted in the experiment is not how often a ball uses each of these (equally probable) paths, but how often it chooses right and left.

For this purpose, there are compartments F_0, F_1,\ldots, F_{12} below the Galton board N+1=13 which reflect this. The coin lands exactly in the compartment F_n if it decides exactly n times for the right (and accordingly (N-n)=(13-n) times for the left).

If one now performs this experiment with a sufficiently large number of coins, it can be observed that most of them collect in the middle compartments. The outer compartments, on the other hand, are rarely reached.

This, in turn, has a simple mathematical reason: the number of paths leading into the compartment F_n is exactly {N \choose n}={12 \choose n}, because it is necessary to select exactly n of the N=12 steps where the coin decides to go to the right. Accordingly, the probability of landing in the compartment F_n is exactly

    \[p_N(n) ={N \choose n}\cdot p^n\cdot(1-p)^{N-n}={N \choose n}2^{-N}={N \choose n}2^{-12}\]

where n=0,\ldots,12.

This probability distribution is called a binomial distribution with parameters p= 0.5 (the probability of a coin falling to the right at an obstacle) and N=12 (the number of stages of the random experiment). The p_N(n) is also called their individual probabilities.

The fact that the binomial distribution for “large” values N is approximated by the normal distribution, describes the so-called limit theorem of Moivre-Laplace:

    \[\sum_{n:a\leq\frac{n-\mu}{\sigma}\leq b}{p_N(n)}\to\frac{1}{\sqrt{2\pi}}\int_a^b{e^{-z^2/2}dz\]

for N\to\infty, a,b\in\mathbb R fixed and arbitrary, \mu=Np and \sigma=\sqrt{Np(1-p)}.

We sketch another proof of this theorem below:

First, we observe that the density function

    \[z\mapsto f(z)=\frac{e^{-z^2/2}}{\sqrt{2\pi}}\]

has the derivative -zf(z), thus satisfying the differential equation f'(z)=-z f(z). If we add that the integral

    \[\int_{z=-\infty}^\infty f(z)dz=1\]

we obtain the density function

    \[f(z)=\frac{e^{-z^2/2}}{\sqrt{2\pi}}\]

of the standard normal distribution as a unique solution of this differential equation. The assertion of Moivre-Laplace’s limit theorem is now that the (suitably rescaled) “density function” of the binomial distribution with parameters p and N converges to this function f(z). By “rescaling” we mean here that the x coordinate is first shifted to the left by \mu=pN and then the x axis is compressed by \sigma=\sqrt{Np(1-p)} and the y axis is stretched by \sigma. We thus obtain from the binomially-distributed random variable B_{N,p} with values in {0,\ldots,N}, the random variable B'_{N,p} which takes values in

    \[\left{\frac{-Np}{\sqrt{Np(1-p)}},\ldots,\frac{N(1-p)}{\sqrt{Np(1-p)}}\right}\]

assumes. This is a discrete random variable with distribution

    \[\sum_{k=0}^N{p_N(k)\delta_{\frac{k-\mu}{\sigma}},\]

Where \delta_x is the Dirac measure in x\in\mathbb R. Since the random variable B'{N,p} is discrete, it has no density function in the proper sense. However, we can replace the Dirac measure \delta_x in the formula just noted by a measure of mass one \lambda_x=\sigma\left.\lambda\rvert{[x-1/(2\sigma),x+1/(2\sigma)]} uniformly distributed on [x-\sigma/2,x+\sigma/2] (where \lambda denotes the Lebesgue measure). We obtain in this way another random variable B''{N,p}, which has a density function. It is easy to see that the distributions of B'{N,p} and B''{N,p} are weakly equivalent in the limit, i.e., their difference weakly converges to 0 for N\to\infty. Thus, we can work with B''{N,p} instead of B'{N,p}. To show that their distribution function weakly goes against f\lambda (\lambda the Lebesgue measure), we now simply show that it satisfies in the limit of the above differential equation f'(z)=-zf(z). So let us write f_0 for the density function of B''{N,p} and assume that z=\frac{k-\mu}{\sigma} for a k\in{0,\ldots,N}. This is certainly reasonable, since such values fill the whole axis as N increases, and are increasingly dense. Then we have

    \[-z=-\frac{k-\mu}{\sigma}\]

and

    \[f_0(z)=\sigma p_N(k).\]

But what is f_0'(z). In fact, f_0 is constant in a neighborhood of z, so f_0'(z)=0 should actually hold. But in the intercept 1/(2\sigma) of z, f_0 suddenly makes a jump; so there \lvert f_0'(z)\rvert=\infty would be. To account for both, we use a difference quotient instead of a differential quotient:

    \[f_0'(z)\approx\frac{f_0(z+1/\sigma)-f_0(z)}{1/\sigma}=\frac{\sigma p_N(k+1)-\sigma p_N(k)}{1/\sigma}=\sigma^2(p_N(k+1)-p_N(k)).\quad(\ast)\]

Thus, for the left side of the differential equation

    \[f_0'(z)=\sigma^2(p_N(k+1)-p_N(k))\]

and for the right side

    \[-zf_0(z)=-\frac{k-\mu}{\sigma}\sigma p_N(k)=-(k-\mu)p_N(k)\quad(\ast).\]

Thus, to check the above differential equation in the limit, it suffices — taking into account (\ast) and (\ast\ast) — the equation

    \[-\frac{f_0'(z)}{zf_0(z)}=-\frac{p_N(k+1)-p_N(k)}{p_N(k)}\cdot\frac{\sigma^2}{k-\mu}\to 1\]

for N\to\infty to be proved. We leave this calculation to the reader and refer to the proof on Wikipedia by carrying it out. Since also \int_{-\infty}^\infty f_0(z)dz=1, we are done. Of course, this sketch is not a rigorous proof — but it can be converted into one with some effort.


Literature

[1] Henze, N.: Stochastik für Einsteiger. Eine Einführung in die faszinierende Welt des Zufalls, Springer Spektrum, 10. Auflage, Wiesbaden, 2013.

[2] https://de.wikipedia.org/wiki/Satz_von_Moivre-Laplace.