Random Fibonacci sequence

In mathematics, the random Fibonacci sequence is a stochastic analogue of the Fibonacci sequence defined by the recurrence relation $f_{n}=f_{n-1}\pm f_{n-2}$ , where the signs + or − are chosen at random with equal probability ${\tfrac {1}{2}}$ , independently for different $n$ . By a theorem of Harry Kesten and Hillel Furstenberg, random recurrent sequences of this kind grow at a certain exponential rate, but it is difficult to compute the rate explicitly. In 1999, Divakar Viswanath showed that the growth rate of the random Fibonacci sequence is equal to 1.1319882487943... (sequence A078416 in the OEIS), a mathematical constant that was later named Viswanath's constant.^[1]^[2]^[3]

YouTube Encyclopedic

1/3
Views:
3 815 246
688
46 634

Transcription

Voiceover:Say [unintelligible], you're in math class and your teacher's talking about ... Well, who knows what your teacher's talking about. Probably a good time to start doodling. And you're feeling spirally today, so yeah. Oh, and because of overcrowding in your school, your math class is taking place in greenhouse number three. Plants. Anyway. You've decided there are three basic types of spirals. There's the kind where, as you spiral out, you keep the same distance. Or you could start big but make it tighter and tighter as you go around, in which case the spiral ends. Or you could start tight but make the spiral bigger as you go out. The first kind is good if you really want to fill up a page with lines. Or if you want to draw curled up snakes. You can start with a wonky shape to spiral around but you've noticed that, as you spiral out, it gets rounder and rounder. Probably something to do with how the ratio between two different numbers approaches one as you repeatedly add the same number to both. But you can bring the wonk back by exaggerating the bumps and it gets all optical illusiony. Anyway, you're not sure what the second kind of spiral is good for, but I guess it's a good way to draw snuggled up slug cats, which are a species you've invented just to keep this kind of spiral from feeling useless. This third spiral, however, is good for all sorts of things. You could draw a snail or a nautilus shell. And elephant with a curled up trunk, the horns of a sheep, a fern frond, a cochlea in an inner ear diagram, an ear itself. Those other spirals can't help but be jealous of this clearly superior kind of spiral. But I draw more slug cats. Here's one way to draw a really perfect spiral. Start with one square and draw another next to it that is the same height. Make the next square fit next to both together, that is each side is length two. The next square has length three. The entire outside shape will always be a rectangle. Keep spiraling around, adding bigger and bigger squares. This one has side length one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13. And now 21. Once you do that you can add a curve going through each square, arcing from one corner to the opposite corner. Resist the urge to zip quickly across the diagonal, if you want a nice smooth spiral. Have you ever looked at the spirally pattern on a pine cone and thought, "Hey, sure are "spirals on this pine cone?" I don't know why there's pine cones in your greenhouse. Maybe the greenhouse is in a forest. Anyway, there's spirals and there's not just one either. There's one, two, three, four, five, six, seven, eight going this way. Or you could look at the spirals going the other way and there's one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13. Look familiar? Eight and 13 are both numbers in the Fibonacci series. That's the one where you start by adding one and one to get two, then one and two to get three, two and three to get five. Three plus five is eight, five plus eight is 13, and so on. Some people think that instead of starting with one plus one you should start with zero and one. Zero plus one is one, one plus one is two, one plus two and three, and it continues on the same way as starting with one and one. Or, I guess you could start with one plus zero and that would work too. Or why not go back one more to negative one and so on? Anyway, if you're into the Fibonacci series, you probably have a bunch memorized. I mean, you've got to know one, one, two, three, five. Finish off the single digits with eight and, ooh with 13, how spooky. And once you're memorizing double digits, you might as well know 21, 34, 55, 89 so that whenever someone turns a Fibonacci number you can say, "Happy Fib Birthday." And then, isn't it interesting that 144, 233, 377? But 610 breaks that pattern, so you'd better know that one too. And oh my goodness, 987 is a neat number and, well, you see how these things get out of hand. Anyway, 'tis the season for decorative scented pine cones and if you're putting glitter glue spirals on your pine cones during math class, you might notice that the number of spirals are five and eight or three and five or three and five again. Five and eight. This one was eight and thirteen and one Fibonacci pine cone is one thing, but all of them? What is up with that? This pine cone has this wumpy weird part. Maybe that messes it up. Let's count the top. Five and eight. Now let's check out the bottom. Eight and 13. If you wanted to draw a mathematically realistic pine cone, you might start by drawing five spirals one way and eight going the other. I'm going to mark out starting and ending points for my spirals first as a guide and then draw the arms. Eight one way and five the other. Now I can fill in the little pine coney things. So there's Fibonacci numbers in pine cones but are there Fibonacci numbers in other things that start with pine? Let's count the spirals on this thing. One, two, three, four, five, six, seven, eight. And one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13. The leaves are hard to keep track of, but they're in spirals too. Of Fibonacci numbers. What if we looked at these really tight spirals going almost straight up? One, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21. A Fibonacci number. Can we find a third spiral on this pine cone? Sure, go down like this. And one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13 (muttering) 19, 20, 21. But that's only a couple examples. How about this thing I found on the side of the road? I don't know what it is. It probably starts with pine, though. Five and eight. Let's see how far the conspiracy goes. What else has spirals in it? This artichoke has five and eight. So does this artichoke looking flower thing. And this cactus fruit does too. Here's an orange cauliflower with five and eight and a green one with five and eight. I mean, five and eight. Oh, it's actually five and eight. Maybe plants just like these numbers though. Doesn't mean it has anything to do with Fibonacci, does it? So let's go for some higher numbers. We're going to need some flowers. I think this is a flower. It's got 13 and 21. These daisies are hard to count, but they have 21 and 34. Now let's bring in the big guns. One, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34. And one, two, three, four, five, six, seven, eight, nine, 10, 11, (muttering) 17, 24, (muttering) 42, 53, 54, 55. I promise, this is a random flower and I didn't pick it out specially to trick you into thinking there's Fibonacci numbers in things, but you should really count for yourself next time you see something spirally. There's even Fibonacci numbers in how the leaves are arranged on this stalk, or this one, or the Brussels sprouts on this stalk are a beautiful delicious three and five. Fibonacci is even in the arrangement of the petals on this rose, and sunflowers have shown Fibonacci numbers as high as 144. It seems pretty cosmic and wondrous, but the cool thing about the Fibonacci series and spiral is not that it's this big complicated mystical magical super math thing beyond the comprehension of our puny human minds that shows up mysteriously everywhere. We'll find that these numbers aren't weird at all. In fact, it would be weird if they weren't there. The cool thing about it is that these incredibly intricate patterns can result from utterly simple beginnings.

Description

A random Fibonacci sequence is an integer random sequence given by the numbers $f_{n}$ for natural numbers $n$ , where $f_{1}=f_{2}=1$ and the subsequent terms are chosen randomly according to the random recurrence relation

f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{ with probability }}{\tfrac {1}{2}};\\f_{n-1}-f_{n-2},&{\text{ with probability }}{\tfrac {1}{2}}.\end{cases}}

An instance of the random Fibonacci sequence starts with 1,1 and the value of the each subsequent term is determined by a fair coin toss: given two consecutive elements of the sequence, the next element is either their sum or their difference with probability 1/2, independently of all the choices made previously. If in the random Fibonacci sequence the plus sign is chosen at each step, the corresponding instance is the Fibonacci sequence (F_n),

1,1,2,3,5,8,13,21,34,55,\ldots .

If the signs alternate in minus-plus-plus-minus-plus-plus-... pattern, the result is the sequence

1,1,0,1,1,0,1,1,0,1,\ldots .

However, such patterns occur with vanishing probability in a random experiment. In a typical run, the terms will not follow a predictable pattern:

1,1,2,3,1,-2,-3,-5,-2,-3,\ldots {\text{ for the signs }}+,+,+,-,-,+,-,-,\ldots .

Similarly to the deterministic case, the random Fibonacci sequence may be profitably described via matrices:

{f_{n-1} \choose f_{n}}={\begin{pmatrix}0&1\\\pm 1&1\end{pmatrix}}{f_{n-2} \choose f_{n-1}},

where the signs are chosen independently for different n with equal probabilities for + or −. Thus

{f_{n-1} \choose f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \choose f_{2}},

where (M_k) is a sequence of independent identically distributed random matrices taking values A or B with probability 1/2:

A={\begin{pmatrix}0&1\\1&1\end{pmatrix}},\quad B={\begin{pmatrix}0&1\\-1&1\end{pmatrix}}.

Growth rate

Johannes Kepler discovered that as n increases, the ratio of the successive terms of the Fibonacci sequence (F_n) approaches the golden ratio $\varphi =(1+{\sqrt {5}})/2,$ which is approximately 1.61803. In 1765, Leonhard Euler published an explicit formula, known today as the Binet formula,

F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}.

It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio φ.

In 1960, Hillel Furstenberg and Harry Kesten showed that for a general class of random matrix products, the norm grows as λⁿ, where n is the number of factors. Their results apply to a broad class of random sequence generating processes that includes the random Fibonacci sequence. As a consequence, the nth root of |f_n| converges to a constant value almost surely, or with probability one:

{\sqrt[{n}]{|f_{n}|}}\to 1.1319882487943\dots {\text{ as }}n\to \infty .

An explicit expression for this constant was found by Divakar Viswanath in 1999. It uses Furstenberg's formula for the Lyapunov exponent of a random matrix product and integration over a certain fractal measure on the Stern–Brocot tree. Moreover, Viswanath computed the numerical value above using floating point arithmetic validated by an analysis of the rounding error.

Generalization

Mark Embree and Nick Trefethen showed in 1999 that the sequence

f_{n}=\pm f_{n-1}\pm \beta f_{n-2}

decays almost surely if β is less than a critical value $β * \approx 0.70258$ , known as the Embree–Trefethen constant, and otherwise grows almost surely. They also showed that the asymptotic ratio σ(β) between consecutive terms converges almost surely for every value of β. The graph of σ(β) appears to have a fractal structure, with a global minimum near $β min \approx 0.36747$ approximately equal to $σ (β min) \approx 0.89517$ .^[4]

References

^ Viswanath, D. (1999). "Random Fibonacci sequences and the number 1.13198824..." Mathematics of Computation. 69 (231): 1131–1155. doi:10.1090/S0025-5718-99-01145-X.
^ Oliveira, J. O. B.; De Figueiredo, L. H. (2002). "Interval Computation of Viswanath's Constant". Reliable Computing. 8 (2): 131. doi:10.1023/A:1014702122205. S2CID 29600050.
^ Makover, E.; McGowan, J. (2006). "An elementary proof that random Fibonacci sequences grow exponentially". Journal of Number Theory. 121: 40–44. arXiv:math.NT/0510159. doi:10.1016/j.jnt.2006.01.002. S2CID 119169165.
^ Embree, M.; Trefethen, L. N. (1999). "Growth and decay of random Fibonacci sequences" (PDF). Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 455 (1987): 2471. Bibcode:1999RSPSA.455.2471T. doi:10.1098/rspa.1999.0412. S2CID 16404862.

External links

Weisstein, Eric W. "Random Fibonacci Sequence". MathWorld.
OEIS sequence A078416 (Decimal expansion of Viswanath's constant)
Random Fibonacci Numbers. Numberphile's video about the random Fibonnaci sequence.

This page was last edited on 18 April 2023, at 23:15

From Wikipedia, the free encyclopedia