MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > July-August 1999 > Article Detail

COMPUTING SCIENCE

The Vibonacci Numbers

Brian Hayes

C = 1.13198824 . . .

Viswanath's approach to determining C is indirect, and indeed it takes a detour through some areas of the mathematical landscape that might seem to have no connection with Fibonacci-like series. But by transposing the problem into another realm, where more powerful tools can be brought to bear, he is able not merely to produce an empirical estimate of C but to prove that the value of the constant must lie in a certain narrow interval. The proof is not a simple one, and here I shall present only a hasty sketch; the details are in Viswanath's paper.

The first step is to recast the Vibonacci process in terms of matrices. The ordinary Fibonacci series can be defined by the matrix equation:

Click to Enlarge Image

Applying the rules for matrix multiplication confirms that the equation has the expected behavior. In the product on the left side of the equation the first row is given by the sum 0 x f(n–2)+1 x f(n–1), which of course is just f(n–1); the second row of the product is 1 x f(n–2)+1 x f(n–1), which is the definition of f(n).

Repeating the matrix multiplication generates successive terms of the Fibonacci sequence. For example, given the initial terms 1, 1, three matrix multiplications produce the terms 3, 5:

Click to Enlarge Image

Continuing in the same way generates every Fibonacci number in turn, and only those numbers.

The Vibonacci sequence can also be redefined as a matrix product, the only difference being that there are two matrices to choose from:

Click to Enlarge Image

At each step in generating the series, one of these matrices is selected at random with probability 1/2. Whenever the second matrix happens to be picked, the minus sign in the lower right corner has the effect of subtracting v(n–1) from v(n–2), rather than adding the two terms, just as in the more direct definition of the Vibonacci series.

Why bother with this elaborate reformulation of the problem if it merely reproduces the same result? Because the study of products of random matrices offers a handy toolkit of useful methods. It allows the Vibonacci process to be viewed in a geometrical context. Suppose that any two adjacent Vibonacci numbers, v(n–1) and v(n–2), represent the coordinates of a point in the x,y plane. Drawing a line from the origin at 0,0 to this point defines a direction in the plane, specified by an angle u or a slope m. The slope is simply y/x, so it is given directly by the coordinates of the point. Now multiply the pair of coordinates by one of the 2 x 2 Vibonacci matrices. What happens to the point? It is mapped into a new point—with coordinates v(n) and v(n–1)—which defines a new direction from the origin. Specifically, multiplying by one of the Vibonacci matrices causes a rotation to a new slope of either (1+1/m) or (1/m–1).

These transformations are easier to understand through a brief example. Starting with a slope of m=1 (equivalent to an angle of 45 degrees), the m→(1+1/m) transformation yields a new slope of 2 (about 63 degrees); applying the m→(1/m–1) transformation rotates the line to a slope of –1/2 (about 333 degrees). If you continue to iterate this process, always taking the last value of m and replacing it with a random choice of either (1+1/m) or (1/m–1), you create a kind of random walk through the space of possible slopes. The progression of slopes seems to have nothing in common with the Vibonacci series, and yet the connection through products of random matrices shows they are really just two manifestations of the same process. (And the connection isn't as mysterious as it might seem. Note that repeating the transformation m→(1+1/m) yields a series of numbers that converges to Φ for any starting m. Hidden in the mapping m→(1+1/m) is the equation 1/x=x–1 that defines Φ.)

The slope m in these formulas can take on any value along the real number line, from negative infinity to positive infinity, but not all slopes are equally likely. The key to understanding the random walk—and also to calculating the growth rate of the Vibonacci series—is identifying the probability distribution that determines the likelihood of every possible slope. Viswanath's main contribution was finding a way to estimate this distribution to any desired degree of accuracy.

The probability distribution is a peculiar one—not at all like the smooth Gaussian curve that describes so many random processes. Instead it has multiple spiky peaks and deep canyons, and if you look closer, you find that the spikes have spicules, and the canyons are creased by smaller canyons. Thus the distribution appears to be a fractal landscape that cannot be described by any continuous function. Viswanath sidestepped this problem by constructing an ingenious discrete partitioning of the real number line. The structure is called the Stern-Brocot tree, after the mathematician Moriz Stern and the watchmaker Achille Brocot, who discovered it more than a century before Viswanath did.

Figure 3. Stern-Brocot treeClick to Enlarge Image

The basic idea of the tree is to divide the set of real numbers into progressively finer—but not necessarily equal—intervals. Writing zero as 0/1 and representing infinity by the notation 1/0, all positive real numbers lie in the interval [0/1, 1/0]. This half of the number line is broken down into the subintervals [0/1, 1/1] and [1/1, 1/0], extending from zero to 1 and from 1 to infinity respectively. The left-hand subnode then splits into [0/1, 1/2] and [1/2, 1/1], and the right-hand subnode into [1/1, 2/1] and [2/1, 1/0]. The general rule is that an interval [a/b, c/d] splits into [a/b, (a+c)/(b+d)] and [(a+b)/(c+d), c/d]. All the numbers in the negative half of the real line are classified in the same way, and the two halves are joined by a special root node labeled [–1/0, 1/0].

The Stern-Brocot tree has a place in this story because there is a direct correspondence between the random walk among slopes m described above and paths traced out through the branches of the tree. Any such a path can be written as a sequence of left and right commands, giving directions for how to get from the root of the tree to a specific interior node. For example, from the [0/1, 1/0] node, a path of right, left, left brings you to the [1/1, 3/2] node. Suppose the current value of the slope m lies somewhere within this interval. After a transition from m to 1/m, the new slope must lie in the [2/3, 1/1] node, which is the mirror image of the original node; to reach it, you follow the opposite sequence of turns, left, right, right. Mapping the transformations m → (1 + 1/m) and m → (1/m – 1) into tree paths is only a little more complicated.Through this mapping, the intervals of the Stern-Brocot tree yield up an approximation to the probability distribution of the Vibonacci series.

Figure 4. Variant seriesClick to Enlarge Image

Viswanath tabulated all paths through the Stern-Brocot tree to a depth of 28 levels, where the tree has more than 50 million nodes. In this way he was able to calculate the value of C to eight decimal places. His result is C = 1.13198824 . . . . It has the same "almost surely" status as Furstenberg's proof; that is, every instance of the Vibonacci series will grow at this rate with probability 1 if it is continued long enough.

An unusual feature of Viswanath's proof is that it relies on floating-point computer arithmetic. Computer-aided proofs are no longer a novelty in mathematics, but few of them adopt floating-point methods because the results are not exact. Viswanath includes an error analysis showing that any arithmetic inaccuracies are much smaller than the uncertainty introduced by truncating the Stern-Brocot tree at a finite depth.





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Feature Article: Twisted Math and Beautiful Geometry

Perspective: Searching for Great Adventures

Letters to the Editors: Prime Beef

Subscribe to American Scientist