|
Random Fibonacci sequences and the number
Author(s):
Divakar
Viswanath.
Journal:
Math. Comp.
69
(2000),
1131-1155.
MSC (1991):
Primary 15A52, 28A80, 60J05, 65G05
Posted:
June 10, 1999
Retrieve article in:
PDF
This article is available free of charge
Abstract |
Similar articles |
Additional information
Abstract:
For the familiar Fibonacci sequence (defined by , and for ), increases exponentially with at a rate given by the golden ratio . But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by , and for , , where each sign is independent and either or - with probability - it is not even obvious if should increase with . Our main result is that ![\begin{equation*}\sqrt[n]{\vert{t_n}\vert} \rightarrow 1.13198824\ldots\:\:\: \text{as}\:\:\: n \rightarrow\infty \end{equation*}](/mcom/2000-69-231/S0025-5718-99-01145-X/gif-abstract/img49.gif)
with probability . Finding the number involves the theory of random matrix products, Stern-Brocot division of the real line, a fractal measure, a computer calculation, and a rounding error analysis to validate the computer calculation.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(1991):
15A52, 28A80, 60J05, 65G05
Retrieve articles in all Journals with MSC
(1991):
15A52, 28A80, 60J05, 65G05
Additional Information:
Divakar
Viswanath
Affiliation:
Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, California 94720
Email:
divakar@cs.cornell.edu
DOI:
10.1090/S0025-5718-99-01145-X
PII:
S 0025-5718(99)01145-X
Received by editor(s):
November 17, 1997
Received by editor(s) in revised form:
July 14, 1998
Posted:
June 10, 1999
Additional Notes:
This work was supported in part by NSF Grant DMS-9500975CS and DOE Grant DE-FG02-94ER25199 to Lloyd N. Trefethen.
Copyright of article:
Copyright
2000,
American Mathematical Society
|