Generating e through probability and hypercubes

This is a really beautiful solution to an interesting probability problem posed by fellow IB teacher Daniel Hwang, for which I’ve outlined a method for solving suggested by Ferenc Beleznay.  The problem is as follows:

On average, how many random real numbers from 0 to 1 (inclusive) are required for the sum to exceed 1?

1 number

Clearly if we choose only 1 number then we can’t exceed 1.

2 numbers

Here we imagine the 2 numbers we pick as x and y and therefore we can represent them as a coordinate pair.  The smallest pair (0,0) and the largest pair (1,1).  This means that the possible coordinates fit inside the unit square shown above.  We want to know for what coordinate pairs we have the inequality x + y > 1.  This can be rearrange to give y > 1-x.  The line y = 1-x is plotted and we can see that any coordinate points in the triangle BCD satisfy this inequality.  Therefore the probability of a random coordinate pair being in this triangle is 1/2.

3 numbers

This time we want to find the probability that we exceed 1 with our third number.  We can consider the numbers as x, y, z and therefore as 3D coordinates (x,y,z).  From the fact that we are choosing a third number we must already have x +y <1. We draw the line x+y = 1, which in 3D gives us a plane.  The volume in which our coordinate point must lie is the prism ABDEFG.

We now also add the constraint x+y+z >1.  This creates the plane as shown.  If our coordinate lies inside the pyramid ABDE then our coordinates will add to less than 1, outside this they will add to more than 1.

The volume of the pyramid ABDE = 1/3 (base area)(perpendicular height).

The volume of the prism ABDEFG =  (base area)(perpendicular height).

Given that they share the same perpendicular height and base area then precisely 1/3 of the available volume would give a coordinate point that adds to less than 1, and 2/3 of the available volume would give a coordinate point that adds to more than 1.

Therefore we have the following tree diagram:

Exceeds 1 with 2 numbers = 1/2

Does not exceed 1 with 2 numbers, exceeds 1 with 3 numbers = 1/2 x 2/3 = 1/3.

Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers = 1/2 x 1/3 = 1/6.

4 numbers

If you been following so far this is where things get interesting!  We can now imagine a 4 dimensional unit cube (image above from Wikipedia) and a 4D coordinate point (x,y,z,a).

Luckily all we care about is the ratio of the 4-D pyramid and the 4-D prim formed by our constraints x+y+z <1 and x+y+z+a >1.

We have the following formula to help:

The n-D volume of a n-D pyramid = 1/n (base)(perpendicular height).

Therefore:

The 4-D volume of a 4-D pyramid = 1/4 (base 3D volume)(perpendicular height).

The 4-D volume of the prism ABDEFG = (base 3D volume)(perpendicular height).

Given that the 2 shapes share the same base and perpendicular height,  the hyper-pyramid occupies exactly 1/4 of the 4-D space of the hyper-prism.  So the probability of being in this space is 1/4 and 3/4 of being outside this space.

We can now extend our tree diagram:

Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers, exceeds with 4 numbers = 1/2 x 1/3 x 3/4 = 1/8

Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers, does not exceed with 4 numbers = 1/2 x 1/3 x 1/4 = 1/24.

In general a hyper-pyramid in n dimensional space occupies exactly 1/n of the space of the hyper-prism – so we can now continue this tree diagram.

Expected value

We can make a table of probabilities to find how many numbers we expect to use in order to exceed one.

Which gives us the following expected value calculation:

Which we can rewrite as:

But we have:

Therefore this gives:

So on average we would need to pick numbers for the sum to exceed one! This is quite a remarkable result – e, one of the fundamental mathematical constants has appeared as if by magic on a probability question utilizing hyper-dimensional shapes.

Demonstrating this with Python

Running the Python code shown above will simulate doing this experiment.  The computer generates a “random” number, then another and carries on until the sum is greater than 1.  It then records how many numbers were required.  It then does this again 1 million times and finds the average from all the trials.

1 million simulations gives 2.7177797177797176.  When we compare this with the real answer for e, 2.7182818284590452353602874713527, we can see it has taken 1 million simulations to only be correct to 4sf.

Even 5 million simulations only gives 2.7182589436517888, so whilst we can clearly see that we will eventually get e, it’s converging very slowly.  This may be because we are reliant on a random number generator which is not truly random (and only chooses numbers to a maximum number of decimal places rather than choosing from all values between 0 and 1).

I think this is a beautiful example of the unexpected nature of mathematics – we started out with a probability problem and ended up with e, via a detour into higher dimensional space!  We can also see the power of computers in doing these kinds of brute force calculations.