https://en.wikipedia.org/w/index.php?action=history&feed=atom&title=Random_Fibonacci_sequence Random Fibonacci sequence - Revision history 2025-06-09T19:45:45Z Revision history for this page on the wiki MediaWiki 1.45.0-wmf.4 https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1150580949&oldid=prev Blansheflur: /* Generalization */ 2023-04-18T23:15:03Z <p><span class="autocomment">Generalization</span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:15, 18 April 2023</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 41:</td> <td colspan="2" class="diff-lineno">Line 41:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Generalization==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Generalization==</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Mark Embree]] and [[Nick Trefethen]] showed in 1999 that the sequence</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Mark Embree]] and [[Nick Trefethen]] showed in 1999 that the sequence</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; f_n=<ins style="font-weight: bold; text-decoration: none;">\pm </ins>f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>decays almost surely if ''β'' is less than a critical value {{math|''β''* ≈ 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 {{math|''β''&lt;sub&gt;min&lt;/sub&gt; ≈ 0.36747}} approximately equal to {{math|''σ''(''β''&lt;sub&gt;min&lt;/sub&gt;) ≈ 0.89517}}.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T | s2cid = 16404862 }}&lt;/ref&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>decays almost surely if ''β'' is less than a critical value {{math|''β''* ≈ 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 {{math|''β''&lt;sub&gt;min&lt;/sub&gt; ≈ 0.36747}} approximately equal to {{math|''σ''(''β''&lt;sub&gt;min&lt;/sub&gt;) ≈ 0.89517}}.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T | s2cid = 16404862 }}&lt;/ref&gt;</div></td> </tr> </table> Blansheflur https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1135793065&oldid=prev Joel Brennan: added wikilinks 2023-01-26T22:04:41Z <p>added wikilinks</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:04, 26 January 2023</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Short description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{Short description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] &lt;math&gt;f_n=f_{n-1}\pm f_{n-2}&lt;/math&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability &lt;math&gt;\tfrac12&lt;/math&gt;, [[Independence (probability theory)|independently]] for different &lt;math&gt;n&lt;/math&gt;. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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...{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 | s2cid = 29600050 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = 40–44 | year = 2006 |arxiv=math.NT/0510159| s2cid = 119169165 }}&lt;/ref&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In <ins style="font-weight: bold; text-decoration: none;">[[</ins>mathematics<ins style="font-weight: bold; text-decoration: none;">]]</ins>, the '''random Fibonacci sequence''' is a <ins style="font-weight: bold; text-decoration: none;">[[</ins>stochastic<ins style="font-weight: bold; text-decoration: none;">]]</ins> analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] &lt;math&gt;f_n=f_{n-1}\pm f_{n-2}&lt;/math&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability &lt;math&gt;\tfrac12&lt;/math&gt;, [[Independence (probability theory)|independently]] for different &lt;math&gt;n&lt;/math&gt;. By a <ins style="font-weight: bold; text-decoration: none;">[[</ins>theorem<ins style="font-weight: bold; text-decoration: none;">]]</ins> of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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...<ins style="font-weight: bold; text-decoration: none;"> </ins>{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 | s2cid = 29600050 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = 40–44 | year = 2006 |arxiv=math.NT/0510159| s2cid = 119169165 }}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Description==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Description==</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>A random Fibonacci sequence is an integer random sequence given by the numbers &lt;math&gt;f_n&lt;/math&gt; for [[natural number]]s &lt;math&gt;n&lt;/math&gt;, where &lt;math&gt;f_1=f_2=1&lt;/math&gt; and the subsequent terms are chosen randomly according to the random recurrence relation</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>A random Fibonacci sequence is an <ins style="font-weight: bold; text-decoration: none;">[[</ins>integer<ins style="font-weight: bold; text-decoration: none;">]]</ins> random sequence given by the numbers &lt;math&gt;f_n&lt;/math&gt; for [[natural number]]s &lt;math&gt;n&lt;/math&gt;, where &lt;math&gt;f_1=f_2=1&lt;/math&gt; and the subsequent terms are chosen randomly according to the random recurrence relation</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>f_n = \begin{cases}</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>f_n = \begin{cases}</div></td> </tr> <tr> <td colspan="2" class="diff-lineno">Line 10:</td> <td colspan="2" class="diff-lineno">Line 10:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\end{cases}</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\end{cases}</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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]] <del style="font-weight: bold; text-decoration: none;">{</del>''F''&lt;sub&gt;''n''&lt;/sub&gt;<del style="font-weight: bold; text-decoration: none;">}</del>,</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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]] <ins style="font-weight: bold; text-decoration: none;">(</ins>''F''&lt;sub&gt;''n''&lt;/sub&gt;<ins style="font-weight: bold; text-decoration: none;">)</ins>,</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; 1,1,2,3,5,8,13,21,34,55,\ldots. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; 1,1,2,3,5,8,13,21,34,55,\ldots. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>If the signs alternate in minus-plus-plus-minus-plus-plus-... pattern, the result is the sequence</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>If the signs alternate in minus-plus-plus-minus-plus-plus-... pattern, the result is the sequence</div></td> </tr> <tr> <td colspan="2" class="diff-lineno">Line 19:</td> <td colspan="2" class="diff-lineno">Line 19:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\text{ for the signs } +, +, +, -, -, +, -, -, \ldots.&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\text{ for the signs } +, +, +, -, -, +, -, -, \ldots.&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Similarly to the deterministic case, the random Fibonacci sequence may be profitably described via matrices:</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Similarly to the deterministic case, the random Fibonacci sequence may be profitably described via <ins style="font-weight: bold; text-decoration: none;">[[matrix (mathematics)|</ins>matrices<ins style="font-weight: bold; text-decoration: none;">]]</ins>:</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;{f_{n-1} \choose f_{n}} = \begin{pmatrix} 0 &amp; 1 \\ \pm 1 &amp; 1 \end{pmatrix} {f_{n-2} \choose f_{n-1}},&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;{f_{n-1} \choose f_{n}} = \begin{pmatrix} 0 &amp; 1 \\ \pm 1 &amp; 1 \end{pmatrix} {f_{n-2} \choose f_{n-1}},&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>where the signs are chosen independently for different ''n'' with equal probabilities for + or −. Thus</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>where the signs are chosen independently for different ''n'' with equal probabilities for + or −. Thus</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;{f_{n-1} \choose f_{n}} = M_{n}M_{n-1}\ldots M_3{f_{1} \choose f_{2}},&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;{f_{n-1} \choose f_{n}} = M_{n}M_{n-1}\ldots M_3{f_{1} \choose f_{2}},&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>where <del style="font-weight: bold; text-decoration: none;">{</del>''M''&lt;sub&gt;''k''&lt;/sub&gt;<del style="font-weight: bold; text-decoration: none;">}</del> is a sequence of [[Independent and identically-distributed random variables|independent identically distributed random matrices]] taking values ''A'' or ''B'' with probability 1/2:</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>where <ins style="font-weight: bold; text-decoration: none;">(</ins>''M''&lt;sub&gt;''k''&lt;/sub&gt;<ins style="font-weight: bold; text-decoration: none;">)</ins> is a sequence of [[Independent and identically-distributed random variables|independent identically distributed random matrices]] taking values ''A'' or ''B'' with probability 1/2:</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; A=\begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 1 \end{pmatrix}, \quad</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; A=\begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 1 \end{pmatrix}, \quad</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>B=\begin{pmatrix} 0 &amp; 1 \\ -1 &amp; 1 \end{pmatrix}. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>B=\begin{pmatrix} 0 &amp; 1 \\ -1 &amp; 1 \end{pmatrix}. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Growth rate==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Growth rate==</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Johannes Kepler]] discovered that as ''n'' increases, the ratio of the successive terms of the Fibonacci sequence <del style="font-weight: bold; text-decoration: none;">{</del>''F''&lt;sub&gt;''n''&lt;/sub&gt;<del style="font-weight: bold; text-decoration: none;">}</del> approaches the [[golden ratio]] &lt;math&gt;\varphi=(1+\sqrt{5})/2,&lt;/math&gt; which is approximately 1.61803. In 1765, [[Leonhard Euler]] published an explicit formula, known today as the [[Binet formula]],</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Johannes Kepler]] discovered that as ''n'' increases, the ratio of the successive terms of the Fibonacci sequence <ins style="font-weight: bold; text-decoration: none;">(</ins>''F''&lt;sub&gt;''n''&lt;/sub&gt;<ins style="font-weight: bold; text-decoration: none;">)</ins> <ins style="font-weight: bold; text-decoration: none;">[[limit of a sequence|</ins>approaches<ins style="font-weight: bold; text-decoration: none;">]]</ins> the [[golden ratio]] &lt;math&gt;\varphi=(1+\sqrt{5})/2,&lt;/math&gt; which is approximately 1.61803. In 1765, [[Leonhard Euler]] published an explicit formula, known today as the [[Binet formula]],</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;F_n = {{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;F_n = {{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio ''φ''.</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio ''φ''.</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In 1960, [[Hillel Furstenberg]] and [[Harry Kesten]] showed that for a general class of random <del style="font-weight: bold; text-decoration: none;">[[</del>matrix<del style="font-weight: bold; text-decoration: none;"> (mathematics)|matrix]]</del> products, the [[matrix norm|norm]] grows as ''λ''&lt;sup&gt;''n''&lt;/sup&gt;, 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 ''n''th root of |''f''&lt;sub&gt;''n''&lt;/sub&gt;| converges to a constant value ''[[almost surely]]'', or with probability one:</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In 1960, [[Hillel Furstenberg]] and [[Harry Kesten]] showed that for a general class of random matrix products, the [[matrix norm|norm]] grows as ''λ''&lt;sup&gt;''n''&lt;/sup&gt;, 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 <ins style="font-weight: bold; text-decoration: none;">[[nth root|</ins>''n''th root<ins style="font-weight: bold; text-decoration: none;">]]</ins> of |''f''&lt;sub&gt;''n''&lt;/sub&gt;| converges to a constant value ''[[almost surely]]'', or with probability one:</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; \sqrt[n]{|f_n|} \to 1.1319882487943\dots \text{ as } n \to \infty. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; \sqrt[n]{|f_n|} \to 1.1319882487943\dots \text{ as } n \to \infty. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> </table> Joel Brennan https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1120995850&oldid=prev 77551enpassant: /* Growth rate */ arithmetics -> arithmetic 2022-11-09T23:35:36Z <p><span class="autocomment">Growth rate: </span> arithmetics -&gt; arithmetic</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:35, 9 November 2022</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 37:</td> <td colspan="2" class="diff-lineno">Line 37:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; \sqrt[n]{|f_n|} \to 1.1319882487943\dots \text{ as } n \to \infty. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; \sqrt[n]{|f_n|} \to 1.1319882487943\dots \text{ as } n \to \infty. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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|fractal measure]] on the [[Stern–Brocot tree]]. Moreover, Viswanath computed the numerical value above using [[floating point]] <del style="font-weight: bold; text-decoration: none;">arithmetics</del> validated by an analysis of the [[rounding error]].</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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|fractal measure]] on the [[Stern–Brocot tree]]. Moreover, Viswanath computed the numerical value above using [[floating point]] <ins style="font-weight: bold; text-decoration: none;">arithmetic</ins> validated by an analysis of the [[rounding error]].</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Generalization==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Generalization==</div></td> </tr> </table> 77551enpassant https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1088038287&oldid=prev Comp.arch at 21:36, 15 May 2022 2022-05-15T21:36:48Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:36, 15 May 2022</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>{{<del style="font-weight: bold; text-decoration: none;">short</del> description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>{{<ins style="font-weight: bold; text-decoration: none;">Short</ins> description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] &lt;math&gt;f_n=f_{n-1}\pm f_{n-2}&lt;/math&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability &lt;math&gt;\tfrac12&lt;/math&gt;, [[Independence (probability theory)|independently]] for different &lt;math&gt;n&lt;/math&gt;. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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...{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 | s2cid = 29600050 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = 40–44 | year = 2006 |arxiv=math.NT/0510159| s2cid = 119169165 }}&lt;/ref&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] &lt;math&gt;f_n=f_{n-1}\pm f_{n-2}&lt;/math&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability &lt;math&gt;\tfrac12&lt;/math&gt;, [[Independence (probability theory)|independently]] for different &lt;math&gt;n&lt;/math&gt;. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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...{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 | s2cid = 29600050 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = 40–44 | year = 2006 |arxiv=math.NT/0510159| s2cid = 119169165 }}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==<del style="font-weight: bold; text-decoration: none;"> </del>Description<del style="font-weight: bold; text-decoration: none;"> </del>==</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==Description==</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>A random Fibonacci sequence is an integer random sequence given by the numbers &lt;math&gt;f_n&lt;/math&gt; for [[natural number]]s &lt;math&gt;n&lt;/math&gt;, where &lt;math&gt;f_1=f_2=1&lt;/math&gt; and the subsequent terms are chosen randomly according to the random recurrence relation</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>A random Fibonacci sequence is an integer random sequence given by the numbers &lt;math&gt;f_n&lt;/math&gt; for [[natural number]]s &lt;math&gt;n&lt;/math&gt;, where &lt;math&gt;f_1=f_2=1&lt;/math&gt; and the subsequent terms are chosen randomly according to the random recurrence relation</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;</div></td> </tr> <tr> <td colspan="2" class="diff-lineno">Line 28:</td> <td colspan="2" class="diff-lineno">Line 28:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>B=\begin{pmatrix} 0 &amp; 1 \\ -1 &amp; 1 \end{pmatrix}. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>B=\begin{pmatrix} 0 &amp; 1 \\ -1 &amp; 1 \end{pmatrix}. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==<del style="font-weight: bold; text-decoration: none;"> </del>Growth rate<del style="font-weight: bold; text-decoration: none;"> </del>==</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==Growth rate==</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><br /></td> <td colspan="2" class="diff-empty diff-side-added"></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Johannes Kepler]] discovered that as ''n'' increases, the ratio of the successive terms of the Fibonacci sequence {''F''&lt;sub&gt;''n''&lt;/sub&gt;} approaches the [[golden ratio]] &lt;math&gt;\varphi=(1+\sqrt{5})/2,&lt;/math&gt; which is approximately 1.61803. In 1765, [[Leonhard Euler]] published an explicit formula, known today as the [[Binet formula]],</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Johannes Kepler]] discovered that as ''n'' increases, the ratio of the successive terms of the Fibonacci sequence {''F''&lt;sub&gt;''n''&lt;/sub&gt;} approaches the [[golden ratio]] &lt;math&gt;\varphi=(1+\sqrt{5})/2,&lt;/math&gt; which is approximately 1.61803. In 1765, [[Leonhard Euler]] published an explicit formula, known today as the [[Binet formula]],</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;F_n = {{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt;F_n = {{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}. &lt;/math&gt;</div></td> </tr> <tr> <td colspan="2" class="diff-lineno">Line 35:</td> <td colspan="2" class="diff-lineno">Line 34:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio ''φ''.</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio ''φ''.</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In 1960, [[Hillel Furstenberg]] and [[Harry Kesten]] showed that for a general class of random [[matrix (<del style="font-weight: bold; text-decoration: none;">math</del>)|matrix]] products, the [[matrix norm|norm]] grows as ''λ''&lt;sup&gt;''n''&lt;/sup&gt;, 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 ''n''th root of |''f''&lt;sub&gt;''n''&lt;/sub&gt;| converges to a constant value ''[[almost surely]]'', or with probability one:</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In 1960, [[Hillel Furstenberg]] and [[Harry Kesten]] showed that for a general class of random [[matrix (<ins style="font-weight: bold; text-decoration: none;">mathematics</ins>)|matrix]] products, the [[matrix norm|norm]] grows as ''λ''&lt;sup&gt;''n''&lt;/sup&gt;, 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 ''n''th root of |''f''&lt;sub&gt;''n''&lt;/sub&gt;| converges to a constant value ''[[almost surely]]'', or with probability one:</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; \sqrt[n]{|f_n|} \to 1.1319882487943\dots \text{ as } n \to \infty. &lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math display=block&gt; \sqrt[n]{|f_n|} \to 1.1319882487943\dots \text{ as } n \to \infty. &lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> </table> Comp.arch https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1087869153&oldid=prev David Eppstein: <math display=block>; some copyediting 2022-05-15T00:02:42Z <p>&lt;math display=block&gt;; some copyediting</p> <a href="//en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&amp;diff=1087869153&amp;oldid=1073285423">Show changes</a> David Eppstein https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1073285423&oldid=prev LaundryPizza03: /* Generalization */ now redirected here 2022-02-21T23:34:10Z <p><span class="autocomment">Generalization: </span> now redirected here</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:34, 21 February 2022</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 53:</td> <td colspan="2" class="diff-lineno">Line 53:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Generalization==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Generalization==</div></td> </tr> <tr> <td colspan="2" class="diff-empty diff-side-deleted"></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Mark Embree]] and [[Nick Trefethen]] showed in 1999 that the sequence</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><br /></td> <td colspan="2" class="diff-empty diff-side-added"></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The [[Embree–Trefethen constant]] describes the qualitative behavior of the random sequence with the recurrence relation</div></td> <td colspan="2" class="diff-empty diff-side-added"></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: &lt;math&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: &lt;math&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">for different values of ''β''. [[Mark Embree]] and [[Nick Trefethen]] showed in 1999 that this sequence </del>decays almost surely if ''β'' is less than a critical value {{math|''β''* ≈ 0.70258}}, 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 {{math|''β''&lt;sub&gt;min&lt;/sub&gt; ≈ 0.36747}} approximately equal to {{math|''σ''(''β''&lt;sub&gt;min&lt;/sub&gt;) ≈ 0.89517}}.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T | s2cid = 16404862 }}&lt;/ref&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>decays almost surely if ''β'' is less than a critical value {{math|''β''* ≈ 0.70258}}<ins style="font-weight: bold; text-decoration: none;">, known as the Embree–Trefethen constant</ins>, 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 {{math|''β''&lt;sub&gt;min&lt;/sub&gt; ≈ 0.36747}} approximately equal to {{math|''σ''(''β''&lt;sub&gt;min&lt;/sub&gt;) ≈ 0.89517}}.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T | s2cid = 16404862 }}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td> </tr> </table> LaundryPizza03 https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1073136879&oldid=prev LaundryPizza03: added Category:Stochastic processes using HotCat 2022-02-21T05:25:30Z <p>added <a href="/wiki/Category:Stochastic_processes" title="Category:Stochastic processes">Category:Stochastic processes</a> using <a href="/wiki/Wikipedia:HC" class="mw-redirect" title="Wikipedia:HC">HotCat</a></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 05:25, 21 February 2022</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 71:</td> <td colspan="2" class="diff-lineno">Line 71:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Mathematical constants]]</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Mathematical constants]]</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Number theory]]</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Number theory]]</div></td> </tr> <tr> <td colspan="2" class="diff-empty diff-side-deleted"></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Stochastic processes]]</div></td> </tr> </table> LaundryPizza03 https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1073092172&oldid=prev LaundryPizza03: /* Related work */ elaborate 2022-02-21T00:31:09Z <p><span class="autocomment">Related work: </span> elaborate</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:31, 21 February 2022</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 52:</td> <td colspan="2" class="diff-lineno">Line 52:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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|fractal measure]] on the [[Stern–Brocot tree]]. Moreover, Viswanath computed the numerical value above using [[floating point]] arithmetics validated by an analysis of the [[rounding error]].</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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|fractal measure]] on the [[Stern–Brocot tree]]. Moreover, Viswanath computed the numerical value above using [[floating point]] arithmetics validated by an analysis of the [[rounding error]].</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==<del style="font-weight: bold; text-decoration: none;">Related work</del>==</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==<ins style="font-weight: bold; text-decoration: none;">Generalization</ins>==</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The [[Embree–Trefethen constant]] describes the qualitative behavior of the random sequence with the recurrence relation</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The [[Embree–Trefethen constant]] describes the qualitative behavior of the random sequence with the recurrence relation</div></td> </tr> <tr> <td colspan="2" class="diff-lineno">Line 58:</td> <td colspan="2" class="diff-lineno">Line 58:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: &lt;math&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: &lt;math&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>for different values of β.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T | s2cid = 16404862 }}&lt;/ref&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>for different values of <ins style="font-weight: bold; text-decoration: none;">''</ins>β<ins style="font-weight: bold; text-decoration: none;">''. [[Mark Embree]] and [[Nick Trefethen]] showed in 1999 that this sequence decays almost surely if ''β'' is less than a critical value {{math|''β''* ≈ 0.70258}}, 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 {{math|''β''&lt;sub&gt;min&lt;/sub&gt; ≈ 0.36747}} approximately equal to {{math|''σ''(''β''&lt;sub&gt;min&lt;/sub&gt;) ≈ 0.89517}}</ins>.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T | s2cid = 16404862 }}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td> </tr> </table> LaundryPizza03 https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1053612663&oldid=prev Citation bot: Alter: title, pages. Add: s2cid. Formatted dashes. | Use this bot. Report bugs. | Suggested by Neko-chan | Category:Mathematical constants | #UCB_Category 84/89 2021-11-04T23:10:37Z <p>Alter: title, pages. Add: s2cid. Formatted <a href="/wiki/Wikipedia:ENDASH" class="mw-redirect" title="Wikipedia:ENDASH">dashes</a>. | <a href="/wiki/Wikipedia:UCB" class="mw-redirect" title="Wikipedia:UCB">Use this bot</a>. <a href="/wiki/Wikipedia:DBUG" class="mw-redirect" title="Wikipedia:DBUG">Report bugs</a>. | Suggested by Neko-chan | <a href="/wiki/Category:Mathematical_constants" title="Category:Mathematical constants">Category:Mathematical constants</a> | #UCB_Category 84/89</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:10, 4 November 2021</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{short description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{short description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] ''f''&lt;sub&gt;''n''&lt;/sub&gt; = ''f''&lt;sub&gt;''n''−1&lt;/sub&gt; ± ''f''&lt;sub&gt;''n''−2&lt;/sub&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability 1/2, [[Independence (probability theory)|independently]] for different ''n''. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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…{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences<del style="font-weight: bold; text-decoration: none;"> </del> and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = <del style="font-weight: bold; text-decoration: none;">40</del> | year = 2006 |arxiv=math.NT/0510159}}&lt;/ref&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] ''f''&lt;sub&gt;''n''&lt;/sub&gt; = ''f''&lt;sub&gt;''n''−1&lt;/sub&gt; ± ''f''&lt;sub&gt;''n''−2&lt;/sub&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability 1/2, [[Independence (probability theory)|independently]] for different ''n''. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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…{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205<ins style="font-weight: bold; text-decoration: none;"> | s2cid = 29600050</ins> }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = <ins style="font-weight: bold; text-decoration: none;">40–44</ins> | year = 2006 |arxiv=math.NT/0510159<ins style="font-weight: bold; text-decoration: none;">| s2cid = 119169165 </ins>}}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Description ==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Description ==</div></td> </tr> <tr> <td colspan="2" class="diff-lineno">Line 58:</td> <td colspan="2" class="diff-lineno">Line 58:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: &lt;math&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>: &lt;math&gt; f_n=f_{n-1}\pm \beta f_{n-2}&lt;/math&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>for different values of β.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T }}&lt;/ref&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>for different values of β.&lt;ref&gt;{{Cite journal | last1 = Embree | first1 = M. | author-link1 = Mark Embree| last2 = Trefethen | first2 = L. N. | author-link2 = Lloyd N. Trefethen| doi = 10.1098/rspa.1999.0412 | title = Growth and decay of random Fibonacci sequences | journal = Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume = 455 | issue = 1987 | pages = 2471 | year = 1999 | url = http://people.maths.ox.ac.uk/~trefethen/publication/PDF/1999_86.pdf|bibcode = 1999RSPSA.455.2471T<ins style="font-weight: bold; text-decoration: none;"> | s2cid = 16404862</ins> }}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==References==</div></td> </tr> </table> Citation bot https://en.wikipedia.org/w/index.php?title=Random_Fibonacci_sequence&diff=1009622703&oldid=prev Leschnei: /* top */ removed bold face 2021-03-01T13:59:19Z <p><span class="autocomment">top: </span> removed bold face</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Previous revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:59, 1 March 2021</td> </tr><tr> <td colspan="2" class="diff-lineno">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{short description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{short description|Randomized mathematical sequence based upon the Fibonacci sequence}}</div></td> </tr> <tr> <td class="diff-marker" data-marker="−"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] ''f''&lt;sub&gt;''n''&lt;/sub&gt; = ''f''&lt;sub&gt;''n''−1&lt;/sub&gt; ± ''f''&lt;sub&gt;''n''−2&lt;/sub&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability 1/2, [[Independence (probability theory)|independently]] for different ''n''. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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…{{OEIS|A078416}}, a [[mathematical constant]] that was later named <del style="font-weight: bold; text-decoration: none;">'''</del>Viswanath's constant<del style="font-weight: bold; text-decoration: none;">'''</del>.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = 40 | year = 2006 |arxiv=math.NT/0510159}}&lt;/ref&gt;</div></td> <td class="diff-marker" data-marker="+"></td> <td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In mathematics, the '''random Fibonacci sequence''' is a stochastic analogue of the [[Fibonacci sequence]] defined by the [[recurrence relation]] ''f''&lt;sub&gt;''n''&lt;/sub&gt; = ''f''&lt;sub&gt;''n''−1&lt;/sub&gt; ± ''f''&lt;sub&gt;''n''−2&lt;/sub&gt;, where the signs + or − are chosen [[Bernoulli distribution|at random]] with equal probability 1/2, [[Independence (probability theory)|independently]] for different ''n''. By a theorem of [[Harry Kesten]] and [[Hillel Furstenberg]], random recurrent sequences of this kind grow at a certain [[exponential growth|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…{{OEIS|A078416}}, a [[mathematical constant]] that was later named Viswanath's constant.&lt;ref&gt;{{Cite journal | last1 = Viswanath | first1 = D. | title = Random Fibonacci sequences and the number 1.13198824... | doi = 10.1090/S0025-5718-99-01145-X | journal = Mathematics of Computation | volume = 69 | issue = 231 | pages = 1131–1155 | year = 1999 | doi-access = free }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Oliveira | first1 = J. O. B. | last2 = De Figueiredo | first2 = L. H. | journal = Reliable Computing | volume = 8 | issue = 2 | pages = 131 |title=Interval Computation of Viswanath's Constant| year = 2002 | doi = 10.1023/A:1014702122205 }}&lt;/ref&gt;&lt;ref&gt;{{Cite journal | last1 = Makover | first1 = E. | last2 = McGowan | first2 = J. | doi = 10.1016/j.jnt.2006.01.002 | title = An elementary proof that random Fibonacci sequences grow exponentially | journal = Journal of Number Theory | volume = 121 | pages = 40 | year = 2006 |arxiv=math.NT/0510159}}&lt;/ref&gt;</div></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br /></td> </tr> <tr> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Description ==</div></td> <td class="diff-marker"></td> <td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Description ==</div></td> </tr> </table> Leschnei