Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

The Vibonacci Numbers

Brian Hayes

Rabbit Cannibalism

If the Fibonacci series describes rabbit breeding, what does the Vibonacci series describe? A cute answer might be the breeding of cannibalistic rabbits—animals that sometimes reproduce normally but at other times consume their own young or their own parents. But the inventor of the series had nothing so whimsical in mind. He was working on a problem in numerical analysis, the branch of mathematics concerned with large-scale computations.

The inventor is Divakar Viswanath, a young mathematician and computer scientist who earned his Ph.D. last year at Cornell University. He has spent the past academic year at the Mathematical Sciences Research Institute in Berkeley; in the fall he will take up a position in the departments of mathematics and computer science at the University of Chicago. His paper on random Fibonacci sequences will be published in Mathematics of Computation.

Figure 1. Vibonacci numbersClick to Enlarge Image

The most symmetric version of the Vibonacci series assigns randomly chosen signs to both of the preceding terms in the sequence; that is, the recurrence formula is v(n)v(n–2)±v(n–1). But if you are interested mainly in the absolute value of each term—ignoring the sign—the version with just a single random sign yields the same result. The main question in the study of the series is how fast the absolute value of v(n) grows as n increases. In other words, the aim is to find for the Vibonacci numbers a constant C that plays the same role as Φ does for the Fibonacci numbers. This hypothetical growth rate C is defined as the nth root of |v(n)|, where the notation |x| signifies the absolute value of x.

It is not immediately obvious that |v(n)| should be expected to grow at all in the long run. With equal numbers of random additions and subtractions, you might guess that the series would hover around some fixed average, so that the nth root of |v(n)| would converge to a value of 1, signifying no growth. Or, conversely, the Vibonacci numbers might bounce around so chaotically that the growth rate would never converge on any stable value; the limit of the nth root of |v(n)| might simply not exist.

Figure 2. Growth constantClick to Enlarge Image

The question of whether a limiting growth rate exists was settled 40 years ago by Harry Furstenberg and Harry Kesten, then both at Princeton University. For a broad class of random processes, including the one I'm calling the Vibonacci series, they showed that a limit does exist, given a few mild assumptions. Three years later Furstenberg proved that the growth rate is "almost surely" greater than 1. The "almost surely" disclaimer is needed because of the probabilistic nature of the system. Some sequences do fail to grow, and you cannot absolutely exclude the possibility of stumbling onto one. For example, a carefully chosen pattern of alternating plus and minus signs generates the cyclic Vibonacci series 1, 1, 0, 1, 1, 0, . . . . But such exceptional sequences are unlikely; indeed, in the limit as n goes to infinity, they have probability zero. They exist, but you have no chance of ever finding them. Thus Furstenberg's "almost surely" result is actually quite a strong statement. It implies not merely that almost all Vibonacci sequences grow but that any individual sequence grows with probability 1, if it is allowed to continue long enough.

Unfortunately, apart from showing that C must exist and be greater than 1, Furstenberg's theorem gives no information about the magnitude of C. The value 1 is merely a lower bound. There is a complementary upper bound: The value of C cannot be greater than 1.618 . . ., since that is the growth rate of the ordinary Fibonacci series, with all additions and no subtractions.

Numerical experiments provide estimates of C. For small n, it's easy to enumerate all possible n-step Vibonacci seqences and calculate their growth rates by taking the nth root of the final term. Since each of these series is equally likely, the arithmetic average is an estimate of C. For example, there are four Vibonacci series for n = 4, namely 1, 1, 0, –1; 1, 1, 0, 1; 1, 1, 2, 1; and 1, 1, 2, 3. Thus the final terms are –1, 1, 1, 3, and the average of the fourth roots of their absolute values is about 1.08. For n=20 the corresponding estimate of C is about 1.18. But tracing out the entire tree of Vibonacci sequences becomes impractical for large n. At n=20 there are already half a million branches to be tabulated.

Random sampling gives approximations to C for much larger values of n. Figure 1 shows the outcome of a single computer run generating Vibonacci numbers up to v(106). There is no question that this particular sequence is growing exponentially; it attains heights of greater than 1050,000. The value of C calculated from the series exhibits distinctive fluctuations, which appear to diminish in amplitude as n increases, but which also tend toward longer wavelengths at higher n. Convergence is slow. The growth rate appears to be somewhere near 1.13, but from these data it would be difficult to estimate C with greater precision.




comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Spotlight: Briefings

Technologue: Quantum Randomness

Letters to the Editors: Nautilus Biology

Subscribe to American Scientist