Quasi-random Christmas Trees

When I studied mathematical finance at Oxford, one of the classes introduced me to a topic that still fascinates me: quasi-random numbers. Quasi-random numbers differ from the better-known pseudorandom numbers, and not just because of the hyphen. “Quasi” means “almost” while “pseudo” means “pretend.”

The “random” numbers generated by computers are usually only pseudorandom. While they appear to be unpredictable, pseudorandom numbers are set by rigid algorithms. A pseudorandom sequence can always be reproduced from the same “seed” number.

Pseudorandom numbers are widely used for many applications such as “Monte Carlo” financial analysis, but a drawback can be that they do not disperse themselves very well. For example, suppose you own the mineral rights to a huge parcel of land and want to explore for oil. You believe there is a good chance that there is valuable oil beneath the property (but have no detailed geological information). If you knew for certain how many holes you will be able to drill, you might work out a grid or other pattern for their placement that separates the holes from each other as much as possible, so that you could explore as efficiently as possible. You wouldn’t place them all close to each because then you would get no information about the other parts of the property.

But suppose you don’t how many holes you will end up drilling since you don’t know how much time or money will be available. You will want to explore carefully and never drill too closely to a prior location since that would be wasteful. How should you proceed? You might solve an optimization problem for each new location. If that’s too tricky, you might use pseudorandom numbers to select the latitude and longitude of each drilling site.

But pseudorandom (and truly random) points have no sense of personal space and often gather in clumps. Here’s what 100 holes might look if they were chosen by pseudorandom numbers. See how some of the holes bunch closely together while other regions are left unexplored:

It might be better to use quasi-random numbers. Quasi-random sequences tend to disperse themselves better than pseudorandom sequences. One kind of quasi-random sequence is the Halton sequence. With a Halton sequence, each dimension of the region to be explored is assigned a different number as a base. The bases should be primes, or at least relatively prime (no factors in common), to avoid synchronization of different dimensions. In our example, we could choose drilling locations by assigning base 2 to x (longitude) and base 3 to y (latitude). We’ll call this a 2,3 arrangement.

For each base, the first step is to write a sequence of numbers in that base. These are shown in the second column below for base 2 (binary). The digits are then reversed and placed behind a “decimal” point to form base 2 fractions, as shown in the third column. The last column writes these fractions in familiar form.  These are the x coordinates.

n	n (Base 2)	Reversed	x coordinates
1	1	0.1	1/2
2	10	0.01	1/4
3	11	0.11	3/4
4	100	0.001	1/8
5	101	0.101	5/8
6	110	0.011	3/8
7	111	0.111	7/8

The corresponding process in base 3 generates our y coordinates:

n	n (Base 3)	Reversed	y coordinates
1	1	0.1	1/3
2	2	0.2	2/3
3	10	0.01	1/9
4	11	0.11	4/9
5	12	0.21	7/9
6	20	0.02	2/9
7	21	0.12	5/9

So then the coordinates for the first seven locations are:

(1/2,1/3), (1/4,2/3), (3/4,1/9), (1/8, 4/9), (5/8, 7/9), (3/8, 2/9) and (7/8, 5/9).

If we continue the process for 100 pairs and plot them on a unit square we get:

The quasi-random points fill the square more evenly than the pseudorandom points did in the previous figure.

It occurred to me that quasi-random numbers could answer the problem of how to decorate a Christmas tree. Maybe you didn’t know there is such a problem, but if you lack common sense you might wonder what is a good procedure for arranging the ornaments  when you don’t know how many you have or how many more you might get later. If you want the ornaments to be distributed around the tree without any large gaps, then this problem is similar to that of drilling for oil.

We’ve seen how to use quasi-random to select points in a square, but how about points on a cone-shaped Christmas tree? First, imagine that the left and right sides of the square are curved back and brought together, forming a tube. Now shrink the top of the tube to a single point, forming a cone. The only problem is that too many ornaments will crowd the top of the cone. To make sure that the ornaments will be spaced evenly on the cone, we adjust their height with a little formula.

Here’s the same 2,3 quasi-random arrangement of 100 points, mapped onto a Christmas tree:

And now let’s cycle through five colors of ornaments as we place them on the tree:

And here it is with 300 ornaments:

Small bases such as 2 and 3 provide irregular arrangements and quickly fill in the gaps. Larger bases lead to more regular patterns but leave large gaps until enough ornaments have been placed. Heres are the first 150 ornaments from a 19,21 arrangement in five colors:

A large spiral band is left empty. But if we keep going to 420 ornaments, we get the design at the top of this post. Here is an aerial view:

All of these figures were rendered with MATLAB. I’m also working on an animation.

Related: Quasi-Random Christmas Trees:at the Movies

Copyright 2012.  All rights reserved.