Patterns from Randomness

May 18, 2017

The worldwide gambling industry has a market size of more than half a trillion dollars, with the US share being about $50 billion. It's expected to reach a trillion dollars within the next five years, fueled in part by online gambling opportunities. Since I'm a scientist well versed in statistics, I never gamble. One engineer I know does buy lottery tickets, two at a time, since he says buying the second one doubles his chance of winning.

Sports betting is exciting to many people, as the popularity of office basketball pools attest, but much gambling is built on the concept of randomness, as in dice throws, roulette spins, and slot machine pulls. These are example of physical randomness; and, in electronic versions of these, computer-generated randomness.

Computer-generated randomness was problematic in the past, since computer-generated pseudorandom numbers are produced by algorithms. As computer pioneer, John von Neumann, said

"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method."

John von Neumann on a 1992 Hungarian postage stamp. Von Neumann was one of the "Martians," the group of Hungarian scientists who were so skilled that they appeared to be of extraterrestrial origin. (Via Wikimedia Commons.)

Worn and loaded dice are examples that physical randomness is not always what we would wish; so, many computer programs are likely better sources of random numbers. One of these is the Mersenne twister, which I discussed in a previous article (Random Coprimes and Pi, October 10, 2016). This program gets high scores in the Diehard test of randomness devised by American mathematician and computer scientist, George Marsaglia (1924-2011). The source code for my C programming language version of the Mersenne Twister can be found here, and other versions are scattered on the Internet.

As I discussed in a a previous article (The Normality of Pi, September 5, 2016), there's an interesting connection between randomness and the mathematical constant, pi. It's conjectured that pi is a normal number; that is, an irrational number whose digits occur with the same likelihood. The digits of pi look like random numbers, not just in our commonly used base 10, but in every number base.

It's possible to use physical randomness to estimate a value of pi. This is called the millet seed method, named after the tiny seed of this plant. The millet seed is the object of one of the paradoxes of Zeno that asked the question of why dropping a handful of these seeds makes a sound when dropping a single seed does not. In this method, a handful of millet seed is dropped onto a circle inscribed in a square (see figure). The ratio of the number of seeds inside the circle to the total number is equal to π/4.

Estimating pi using physical randomness by dropping millet seeds onto a circle inscribed in a square. The ratio of the number of seeds inside the circle to the total number is equal to π/4. (Result of a computer simulation.)

The always instructive Numberphile people have recently published a YouTube video featuring mathematician, Ben Sparks. In this video, described as the "Chaos Game," Sparks demonstrates a simple random process for producing a Sierpinski triangle, also called a Sierpinski gasket and Sierpinski Sieve because of its sieve-like structure.[1] The Wikipedia page for chaos game shows some other variations of this process.[2]

An image of the Sierpinski triangle. In analogy to images of the Mandelbrot set, triangles appear no matter how far you zoom into the image. (Wikimedia Commons image by Beojan Stanislaus.)

The Sierpinski triangle is usually constructed by an iterative process involving repeated removal of triangular pieces, as follows:

•  Draw an equilateral triangle.
•  Divide the triangle into four smaller, congruent equilateral triangles and remove the one in the center.
•  Repeatedly do the last process on the remaining smaller triangles.

The chaos game construction is an additive process, rather than the subtractive process described above. A random point is chosen in a plane containing an equilateral triangle, a die is rolled to select one of the vertices of the triangle, and another point is drawn halfway between the first point and the vertex. The process is repeated using the last point. I wrote a generating program in C (source code here), and the results of 50,000 iterations are shown in the following figure.

A Sierpinski triangle generated by the 'chaos game' after 50,000 iterations. (Output of the simulation program.)

While reproducing prior results is entertaining, and it allows me to maintain my programming skills, it's better to attempt to extend known results in some way. Everyone knows about the butterfly effect, in which a small change in initial conditions will cause a huge change in a simulation. What would happen if we traveled a little more, or less, than half way towards a vertex from each point?

As the following figure shows, the process is somewhat robust to such a change in condition, although many more iterations would likely yield a completely filled triangle in any case.

Sierpinski triangles generated by the 'chaos game' with variation in the process condition. Left, the process is modified to travel just 45% of the way from the focus point to a vertex; middle, 40%; and, right 35%. The image is blurred, but recognizable, after 50,000 ieterations. The central triangle shrinks, but it is still clear of points. (Output of the simulation program. Click for larger version.)

References:

1. Chaos Game, Numberphile YouTube video by Brady Haran, April 27, 2017.
2. Wikipedia page on the chaos game. The simulation program can be simply modified to produce such different shapes.