Exaltin’ Galton

The windows in my living room are covered in a lattice of adhesive strips. They’re meant to imitate leaded glasswork, in which individual panes of glass are suspended in a frame of lead cames.

The pattern the lattice forms is a plane of tessellating diamonds. I wondered: if I start somewhere near the top of the window and move downwards, travelling only along the lattice, how many different paths could I take to the bottom? Then I thought: if all paths are equiprobable, what is the probability that I end up at a particular position at the bottom of the window?

Consider the diagram below.

window

The picture shows part of the diamond lattice on the window. We’ll refer to the sides of the diamonds as ‘paths’ and points where they meet as ‘nodes’.

Bold paths are ones that are accessible – the dashed paths can never be reached.

Every accessible node is highlighted with a circle. The number inside the circle shows the number of ways that node can be reached. Inaccessible nodes (not displayed) automatically have the number 0, because they can never be reached. The very first node has the number 1, because your starting position is unique.

Let’s consider an example path, shown in brown in the diagram.

You start off at the top node. You then take the path to your right. You reach another node. The number in this node is 1, since you can only reach it having come from the top node.

You then take the path to your left, and reach another node. The number in this node is 2, because you could have got there having come from the node you just came from (accessible 1 way) or from another node (also accessible 1 way).

You then take the path to your left, and reach another node. The number in this node is 3, because you could have got there having from the node you just came from (accessible 2 ways) or from another node (accessible 1 way), and so on.

The general rule is that the number of ways of reaching a node is the sum of the number of ways the two nodes leading to it can be reached. What we’ve recreated is Pascal’s triangle.

pascal

The elements of Pascal’s triangle, called the binomial coefficients, are given by the formula

\displaystyle C_k^n=\frac{n!}{k!(n-k)!}

where n is the row the coefficient appears, k is how far along the row it appears, and ! represents the factorial function, defined by

a!=a\times(a-1)\times(a-2)\times...\times 3\times 2\times 1

The rows are labelled such that the very top node is in the 0th row.

For instance, the node at which the example path ends is accessible 15 different ways. This node is in the 6th row and 4 places from the left. So the expression for C_k^n predicts

\displaystyle C_4^6 = \frac{6!}{4!(6-4)!}=\frac{6\cdot5\cdot4\cdot3\cdot2}{4\cdot3\cdot2\cdot2}=\frac{6\cdot5}{2}=15

The expression for  C_k^n predicts perfectly the number of ways of reaching a particular node. What’s more, if all paths are equiprobable, then the probability of reaching a particular node in the nth row is simply the ratio of C_k^n to the total number of ways of reaching the nth row:

\displaystyle p(n,k)=\frac{C_k^n}{\sum_{k=0}^{n}C_k^n}

The denominator, you may have noticed, is equal to 2^n:

p(n,k)=2^{-n}C_k^n

\displaystyle p(n,k)=\frac{n!}{2^n k!(n-k)!}

\

The equation for p above predicts the way probability is distributed between the nodes in the nth row. The name for this particular distribution is the binomial distribution. The diagram below shows the distribution of probabilities for the 6th row.

6binom

The graph shows it is more likely you end up at a node near the centre of the lattice than at one near the edge. Why? Because there are many more ways of ending up near the middle of the lattice than near the edge. The reason for this is intuitive.

Consider the node corresponding to n=6, k=0. The path by which you reach this node is unique, since you have to turn right, right, right, right, right and right again – there are no other paths by which you may reach this node. Hence it is very unlikely that you end up at this node.

Now consider a node directly below the starting node, n=6, k=3. There are many paths by which you may reach this node – you can wiggle back and forth however you like and, so long as you don’t stray too far, can always work your way back to the middle. Hence you are much more likely to end up at this node.

I’m labouring the point, but it’s good to make sure we know why the distribution takes the shape it does.

\

Now we’re going to deduce something less obvious.

Let’s take the case where

  • there are an odd number of rows (meaning n is even), such that there exists a node directly below the starting node
  • there are very many rows (n\gg 1)

We’re going to work out the number of ways of reaching the node in the nth row displaced m nodes right of centre. That is, if m is 0, we reach the node at the centre corresponding to k=\frac{1}{2}n. If m is 1, we are one node to the right of the centre, and if m is -2, we are two nodes to the left of the centre.

Effectively, in place of the variable k we’re using a more useful variable m, defined by

\displaystyle k = \frac{n}{2}+m

The expression for the binomial coefficients tells us that the number of paths N reaching this node is

\displaystyle N(n,m) = \frac{n!}{\Big(\frac{n}{2}+m\Big)!\Big(n-(\frac{n}{2}+m)\Big)!}

\displaystyle N(n,m)=\frac{n!}{\Big(\frac{n}{2}+m\Big)!\Big(\frac{n}{2}-m\Big)!}

We’re going to manipulate this expression using Stirling’s approximationwhich says that

\ln a!\approx a\ln a - a

if a is a large number.

Things will get a little hairy, but terms cancel all over the place at the end, leaving a nice result.

\

First, take the logarithm of both sides:

\displaystyle \ln N=\ln\Bigg(\frac{n!}{\big(\frac{n}{2}+m\big)!\big(\frac{n}{2}-m\big)!}\Bigg)

\displaystyle \ln N=\ln n!-\ln \Big(\frac{n}{2}+m\Big)!-\ln\Big(\frac{n}{2}-m\Big)!

Next, use Stirling’s approximation. The full expression is too big to be accommodated by the page,  but after non-logarithmic terms cancel out we’re left with

\displaystyle \ln N=n\ln n - \Big(\frac{n}{2}+m\Big)\ln\Big(\frac{n}{2}+m\Big)-\Big(\frac{n}{2}-m\Big)\ln\Big(\frac{n}{2}-m\Big)

This assertion is valid provided \frac{n}{2}-m is not too small a number, or in other words, m\ll n.

We will use this condition again to carry out Taylor expansions of the logarithmic terms. These terms can be split up:

\displaystyle \ln\Big(\frac{n}{2}\pm m\Big)=\ln\Big(\frac{n}{2}\Big[1\pm\frac{2m}{n}\Big]\Big)

\displaystyle \ln\Big(\frac{n}{2}\pm m\Big)=\ln\Big(\frac{n}{2}\Big)+\ln\Big(1\pm\frac{2m}{n}\Big)

Taylor expand the logarithm:

\displaystyle \ln\Big(\frac{n}{2}\pm m\Big)=\ln\Big(\frac{n}{2}\Big)\pm\frac{2m}{n}-\frac{1}{2}\frac{4m^2}{n^2}

This expansion relies on the fact that m \ll n, or \frac{m}{n}\ll 1.

We substitute this expression for the logarithmic terms. Brackets are expanded, logarithms are broken up and stuck back together again. After the dust settles, only two terms have survived:

\displaystyle \ln N = n\ln 2 - \frac{2m^2}{n}

Exponentiating boths sides, we’re left with

\displaystyle N=2^n\exp\Bigg(-\frac{2m^2}{n}\Bigg)

Now recall that, because all paths are equiprobable, the probability of reaching a particular node p(n,m) is related to the number of ways of reaching that node N(n,m) by

\displaystyle p(n,m)=\frac{N(n,m)}{\sum_m N(n,m)}

just as before. Because the sum on the denominator is difficult to evaluate, we’ve going to approximate it with an integral:

\displaystyle \sum_{m=-\frac{n}{2}}^{\frac{n}{2}} N(n,m)\approx\int_{-\frac{n}{2}}^{\frac{n}{2}} N(n,m)\,dm

So

\displaystyle p(n,m)=\frac{2^n \exp\big(-\frac{2m^2}{n}\big)}{2^n \int_{-\frac{n}{2}}^{\frac{n}{2}}\exp\big(-\frac{2m^2}{n}\big)\,dm}

Since we’ve taken n to be a large number, we can extend the limits of integration to infinity without causing too much damage. After we evaluate the integral, our final expression for the probability distribution is

\displaystyle p(n,m)=\sqrt{\frac{2}{\pi n}}\exp\Bigg(-\frac{2m^2}{n}\Bigg)

So that’s the punchlinein the limit that n tends to infinity, the binomial distribution tends towards the normal distribution.

The diagram below compares the binomial distribution for n=30 in gold, and the Gaussian approximation in brown.

binorm

Pretty good.

\

To answer the questions originally asked,

  • the number of ways of reaching the nth row is 2^n
  • the probability p(n,m) of reaching a particular position in the nth row m nodes to the right of centre is given by a binomial distribution, which tends towards a normal distribution with mean \mu=0 and standard deviation \sigma=\frac{1}{2}\sqrt{n} in the limit that n\to\infty

We chose a special case where all paths are equiprobable. Another way of saying this is that, whenever you reach a node, you are just as likely to take the left path as the right path. This led to a probability distribution perfectly symmetric about 0. The more general case would include a probability q of choosing the left path, and 1-q of choosing the right path at any given node.  This would skew our distribution. But, this more general binomial distribution still tends towards a normal distribution in the limit that the window is very big.

For a very similar problem, take a look at the bean machine, also known as Galton’s board.

Return to top

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s