MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > July-August 1999 > Article Detail

COMPUTING SCIENCE

# Variations and Generalizations

All the well-known variations on the Fibonacci series also have analogues in the randomized world of the Vibonacci numbers.

It was noted above that the Fibonacci recurrence has the same growth rate starting from any two initial terms. Does the Vibonacci series share this property? Numerical experiments quickly affirm that it does.

A randomized variant of the Tribonacci series defines each term as the sum of the previous three terms with randomly chosen signs. Not surprisingly, the absolute value of the three-term series grows faster than that of the two-term Vibonacci recurrence. Experiments suggest that the random Tribonacci growth constant is about 1.22. For the random-sign analogue of the Tetrabonacci series, with four terms included in each sum, the growth rate is roughly 1.27. It appears that the growth rate continues increasing slowly as more terms are included.

What happens in the limiting case, where all earlier terms are gathered up into the sum? In the pure Fibonacci version, without randomness, the first few terms of this series are 1, 1, 2, 4, 8, 16, 32, . . . . These are the successive powers of 2, and so the exponential growth rate is exactly 2. The random analogue of this series is actually the problem that got Viswanath started on his investigation of the Vibonacci numbers. Working with Lloyd N. Trefethen, his dissertation supervisor at Cornell, he was studying the series r(n)=±r(1)±r(2)± . . . ±r(n–1), where each term is calculated by giving random signs to all the preceding terms before taking the sum. Finding the asymptotic growth rate of this sequence would settle an outstanding question in the theory of random matrices, proposed by Trefethen. Viswanath was unable to find a rigorous solution and so turned to the two-term Vibonacci sum as a simpler model. Numerical experiments suggest that the growth rate for the random sum of all terms is about 1.32.

Another way of generalizing the Vibonacci process is to consider what happens when the probabilities of choosing plus or minus are not equal. Intuition suggests that any bias in the probabilities, favoring either plus or minus, ought to cause faster growth in the absolute value of v(n). In other words, the sequence with equal probabilities should have the minimum growth rate, with C increasing toward Φ in the extreme cases of all-plus or all-minus sequences. Experiments support these inferences, but the exact behavior of the series with skewed probabilities is unknown. The Stern-Brocot proof works only when plus and minus are chosen with equal probability.

Perhaps the most interesting Vibonacci variation has been studied by Mark Embree and Trefethen, who is now at the of the University of Oxford. Instead of skewing the probabilities, they scale one of the two terms in the random sum by an adjustable factor, which they denote β. That is, the recurrence relation is v(n)=v(n–1)±βv(n–2). If you try a value of β=1/2 in this equation, you will immediately see a dramatic change. The sequence no longer grows exponentially; on the contrary, it rapidly dwindles away. In other words, the exponential growth rate is less than 1; numerical evidence gives a value of about 0.929.

Setting β = 1 recovers the original Vibonacci sequence, where of course the growth rate is known to be 1.13198824 . . . . If the series decays for β = 1/2 and grows for β = 1, there must be some intermediate value of β where it is "neutrally buoyant," neither rising nor falling on average. Embree and Trefethen have searched for this point of equilibrium, designated β*, and they find the closest approximation at β*=0.70258.... Computer runs at this setting develop large and erratic fluctuations, but they seem not to veer off into unbounded growth or decay.

Searching for the value of β that minimizes the growth rate (or in other words maximizes the decay rate) turned up more surprises. The minimum cannot be at β=0, because that is another neutral point, where v(n)=1 for all n. Embree and Trefethen found the minimum at β=0.36747.... In the course of the search they discovered that the curve recording the variation of C as a function of b is not a smooth one. The dips and humps in the curve appear to have a fractal structure, similar to itself at all scales of magnification.

A final question: What is the meaning of numbers such as C = 1.13198824... and β* = 0.70258...? Where do they come from? The number f is given by a simple analytic expression, (1+√5)/2. Is there any similar formula for C or for β*? Probably not. Embree and Trefethen point out that C is 0.4 percent greater than the fourth root of Φ; it is even closer to four-fifths of √2, but these numerical coincidences are surely meaningless. Numbers are so plentiful that you can always find relations among them if you look hard enough, but C and β* will probably have to stand on their own as new constants of nature, or of mathematics. Embree and Trefethen suggest calling 1.13198824... Viswanath's constant.