469:
475:
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
1245:
305:
967:
809:
1113:
1547:
1422:
1139:
820:
1655:
570:
653:
1328:
1125:
101:
660:
464:{\displaystyle f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{ with probability }}{\tfrac {1}{2}};\\f_{n-1}-f_{n-2},&{\text{ with probability }}{\tfrac {1}{2}}.\end{cases}}}
134:
978:
300:
1453:
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
1478:
231:
1341:
254:
158:
187:
657:
However, such patterns occur with vanishing probability in a random experiment. In a typical run, the terms will not follow a predictable pattern:
1589:
492:
137:
575:
1959:
1969:
471:
An instance of the random
Fibonacci sequence starts with 1,1 and the value of the each subsequent term is determined by a
1240:{\displaystyle A={\begin{pmatrix}0&1\\1&1\end{pmatrix}},\quad B={\begin{pmatrix}0&1\\-1&1\end{pmatrix}}.}
1670:, known as the Embree–Trefethen constant, and otherwise grows almost surely. They also showed that the asymptotic ratio
1551:
An explicit expression for this constant was found by
Divakar Viswanath in 1999. It uses Furstenberg's formula for the
962:{\displaystyle {f_{n-1} \choose f_{n}}={\begin{pmatrix}0&1\\\pm 1&1\end{pmatrix}}{f_{n-2} \choose f_{n-1}},}
1954:
1280:
41:
1802:
Makover, E.; McGowan, J. (2006). "An elementary proof that random
Fibonacci sequences grow exponentially".
1964:
104:
1560:
191:
177:
1855:
180:
showed that the growth rate of the random
Fibonacci sequence is equal to 1.1319882487943... (sequence
1870:
814:
110:
327:
1271:
813:
Similarly to the deterministic case, the random
Fibonacci sequence may be profitably described via
259:
36:
572:
If the signs alternate in minus-plus-plus-minus-plus-plus-... pattern, the result is the sequence
1886:
1851:
1829:
1811:
1784:
1767:
Oliveira, J. O. B.; De
Figueiredo, L. H. (2002). "Interval Computation of Viswanath's Constant".
1434:
1426:
It demonstrates that the
Fibonacci numbers grow at an exponential rate equal to the golden ratio
477:
173:
169:
32:
804:{\displaystyle 1,1,2,3,1,-2,-3,-5,-2,-3,\ldots {\text{ for the signs }}+,+,+,-,-,+,-,-,\ldots .}
1909:
1552:
1912:
1878:
1821:
1776:
1747:
209:
1254:
302:
and the subsequent terms are chosen randomly according to the random recurrence relation
1874:
1583:
1568:
1564:
1331:
239:
234:
143:
1108:{\displaystyle {f_{n-1} \choose f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \choose f_{2}},}
1948:
1833:
1471:
1335:
1890:
1788:
1863:
Proceedings of the Royal
Society A: Mathematical, Physical and Engineering Sciences
1542:{\displaystyle {\sqrt{|f_{n}|}}\to 1.1319882487943\dots {\text{ as }}n\to \infty .}
1438:
1275:
165:
1752:
1736:
1938:
1847:
1579:
1442:
20:
1934:
1825:
1780:
28:
1917:
472:
1882:
1417:{\displaystyle F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}.}
1454:
1816:
1261:
increases, the ratio of the successive terms of the Fibonacci sequence (
1691:
1678:) between consecutive terms converges almost surely for every value of
1556:
203:
161:
1930:
sequence A078416 (Decimal expansion of Viswanath's constant)
16:
Randomized mathematical sequence based upon the Fibonacci sequence
1926:
1563:. Moreover, Viswanath computed the numerical value above using
1441:
showed that for a general class of random matrix products, the
176:, but it is difficult to compute the rate explicitly. In 1999,
172:, random recurrent sequences of this kind grow at a certain
1929:
457:
182:
1555:
of a random matrix product and integration over a certain
1737:"Random Fibonacci sequences and the number 1.13198824..."
971:
where the signs are chosen independently for different
1200:
1154:
874:
440:
376:
115:
1592:
1481:
1344:
1283:
1142:
981:
823:
663:
578:
495:
308:
262:
242:
212:
146:
113:
44:
1126:
independent identically distributed random matrices
1650:{\displaystyle f_{n}=\pm f_{n-1}\pm \beta f_{n-2}}
1649:
1541:
1416:
1334:published an explicit formula, known today as the
1322:
1239:
1107:
961:
803:
647:
564:
463:
294:
248:
225:
152:
128:
95:
1096:
1069:
1018:
985:
950:
911:
860:
827:
1856:"Growth and decay of random Fibonacci sequences"
565:{\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots .}
1941:'s video about the random Fibonnaci sequence.
8:
648:{\displaystyle 1,1,0,1,1,0,1,1,0,1,\ldots .}
1567:arithmetic validated by an analysis of the
1323:{\displaystyle \varphi =(1+{\sqrt {5}})/2,}
194:that was later named Viswanath's constant.
975:with equal probabilities for + or −. Thus
1815:
1751:
1635:
1613:
1597:
1591:
1522:
1506:
1500:
1494:
1485:
1482:
1480:
1402:
1395:
1383:
1365:
1360:
1358:
1349:
1343:
1330:which is approximately 1.61803. In 1765,
1309:
1299:
1282:
1195:
1149:
1141:
1095:
1088:
1078:
1068:
1066:
1060:
1041:
1031:
1017:
1010:
994:
984:
982:
980:
949:
936:
920:
910:
908:
869:
859:
852:
836:
826:
824:
822:
742:
662:
577:
494:
439:
434:
417:
398:
375:
370:
353:
334:
322:
313:
307:
280:
267:
261:
241:
217:
211:
145:
114:
112:
81:
62:
49:
43:
96:{\displaystyle f_{n}=f_{n-1}\pm f_{n-2}}
1727:
1694:structure, with a global minimum near
206:random sequence given by the numbers
7:
103:, where the signs + or − are chosen
1533:
1073:
989:
915:
831:
202:A random Fibonacci sequence is an
14:
1586:showed in 1999 that the sequence
1469:| converges to a constant value
1188:
129:{\displaystyle {\tfrac {1}{2}}}
1663:is less than a critical value
1530:
1513:
1501:
1486:
1392:
1374:
1306:
1290:
1:
1753:10.1090/S0025-5718-99-01145-X
295:{\displaystyle f_{1}=f_{2}=1}
436: with probability
372: with probability
1913:"Random Fibonacci Sequence"
1475:, or with probability one:
1986:
1740:Mathematics of Computation
1826:10.1016/j.jnt.2006.01.002
744: for the signs
25:random Fibonacci sequence
1935:Random Fibonacci Numbers
1804:Journal of Number Theory
1659:decays almost surely if
1781:10.1023/A:1014702122205
1704:approximately equal to
107:with equal probability
1960:Mathematical constants
1883:10.1098/rspa.1999.0412
1735:Viswanath, D. (1999).
1651:
1543:
1418:
1324:
1241:
1136:with probability 1/2:
1109:
963:
805:
649:
566:
465:
296:
250:
227:
154:
130:
97:
1652:
1544:
1419:
1325:
1242:
1110:
964:
806:
650:
567:
466:
297:
251:
228:
226:{\displaystyle f_{n}}
192:mathematical constant
155:
131:
98:
1970:Stochastic processes
1690:) appears to have a
1590:
1479:
1342:
1281:
1140:
979:
821:
661:
576:
493:
306:
260:
240:
210:
144:
111:
42:
1875:1999RSPSA.455.2471T
1257:discovered that as
1124:) is a sequence of
37:recurrence relation
1910:Weisstein, Eric W.
1769:Reliable Computing
1746:(231): 1131–1155.
1647:
1539:
1435:Hillel Furstenberg
1414:
1320:
1237:
1228:
1179:
1105:
959:
902:
801:
645:
562:
478:Fibonacci sequence
461:
456:
449:
385:
292:
246:
223:
170:Hillel Furstenberg
150:
126:
124:
93:
33:Fibonacci sequence
1955:Fibonacci numbers
1561:Stern–Brocot tree
1553:Lyapunov exponent
1525:
1511:
1409:
1407:
1304:
1094:
1016:
948:
858:
745:
448:
437:
384:
373:
249:{\displaystyle n}
178:Divakar Viswanath
153:{\displaystyle n}
123:
1977:
1928:
1923:
1922:
1895:
1894:
1860:
1852:Trefethen, L. N.
1844:
1838:
1837:
1819:
1799:
1793:
1792:
1764:
1758:
1757:
1755:
1732:
1717:
1703:
1669:
1656:
1654:
1653:
1648:
1646:
1645:
1624:
1623:
1602:
1601:
1548:
1546:
1545:
1540:
1526:
1523:
1512:
1510:
1505:
1504:
1499:
1498:
1489:
1483:
1423:
1421:
1420:
1415:
1410:
1408:
1403:
1401:
1400:
1399:
1387:
1370:
1369:
1359:
1354:
1353:
1329:
1327:
1326:
1321:
1313:
1305:
1300:
1246:
1244:
1243:
1238:
1233:
1232:
1184:
1183:
1114:
1112:
1111:
1106:
1101:
1100:
1099:
1093:
1092:
1083:
1082:
1072:
1065:
1064:
1052:
1051:
1036:
1035:
1023:
1022:
1021:
1015:
1014:
1005:
1004:
988:
968:
966:
965:
960:
955:
954:
953:
947:
946:
931:
930:
914:
907:
906:
865:
864:
863:
857:
856:
847:
846:
830:
810:
808:
807:
802:
746:
743:
654:
652:
651:
646:
571:
569:
568:
563:
470:
468:
467:
462:
460:
459:
450:
441:
438:
435:
428:
427:
409:
408:
386:
377:
374:
371:
364:
363:
345:
344:
318:
317:
301:
299:
298:
293:
285:
284:
272:
271:
255:
253:
252:
247:
232:
230:
229:
224:
222:
221:
185:
174:exponential rate
159:
157:
156:
151:
135:
133:
132:
127:
125:
116:
102:
100:
99:
94:
92:
91:
73:
72:
54:
53:
31:analogue of the
1985:
1984:
1980:
1979:
1978:
1976:
1975:
1974:
1945:
1944:
1908:
1907:
1904:
1899:
1898:
1858:
1846:
1845:
1841:
1817:math.NT/0510159
1801:
1800:
1796:
1766:
1765:
1761:
1734:
1733:
1729:
1724:
1715:
1705:
1701:
1695:
1682:. The graph of
1664:
1631:
1609:
1593:
1588:
1587:
1577:
1557:fractal measure
1517:1.1319882487943
1490:
1484:
1477:
1476:
1468:
1391:
1361:
1345:
1340:
1339:
1279:
1278:
1269:
1255:Johannes Kepler
1252:
1227:
1226:
1221:
1212:
1211:
1206:
1196:
1178:
1177:
1172:
1166:
1165:
1160:
1150:
1138:
1137:
1123:
1084:
1074:
1067:
1056:
1037:
1027:
1006:
990:
983:
977:
976:
932:
916:
909:
901:
900:
895:
886:
885:
880:
870:
848:
832:
825:
819:
818:
659:
658:
574:
573:
491:
490:
488:
455:
454:
432:
413:
394:
391:
390:
368:
349:
330:
323:
309:
304:
303:
276:
263:
258:
257:
238:
237:
235:natural numbers
213:
208:
207:
200:
181:
142:
141:
109:
108:
77:
58:
45:
40:
39:
35:defined by the
17:
12:
11:
5:
1983:
1981:
1973:
1972:
1967:
1962:
1957:
1947:
1946:
1943:
1942:
1932:
1924:
1903:
1902:External links
1900:
1897:
1896:
1869:(1987): 2471.
1839:
1794:
1759:
1726:
1725:
1723:
1720:
1713:
1699:
1644:
1641:
1638:
1634:
1630:
1627:
1622:
1619:
1616:
1612:
1608:
1605:
1600:
1596:
1584:Nick Trefethen
1576:
1575:Generalization
1573:
1569:rounding error
1565:floating point
1538:
1535:
1532:
1529:
1524: as
1521:
1518:
1515:
1509:
1503:
1497:
1493:
1488:
1464:
1413:
1406:
1398:
1394:
1390:
1386:
1382:
1379:
1376:
1373:
1368:
1364:
1357:
1352:
1348:
1332:Leonhard Euler
1319:
1316:
1312:
1308:
1303:
1298:
1295:
1292:
1289:
1286:
1265:
1251:
1248:
1236:
1231:
1225:
1222:
1220:
1217:
1214:
1213:
1210:
1207:
1205:
1202:
1201:
1199:
1194:
1191:
1187:
1182:
1176:
1173:
1171:
1168:
1167:
1164:
1161:
1159:
1156:
1155:
1153:
1148:
1145:
1128:taking values
1119:
1104:
1098:
1091:
1087:
1081:
1077:
1071:
1063:
1059:
1055:
1050:
1047:
1044:
1040:
1034:
1030:
1026:
1020:
1013:
1009:
1003:
1000:
997:
993:
987:
958:
952:
945:
942:
939:
935:
929:
926:
923:
919:
913:
905:
899:
896:
894:
891:
888:
887:
884:
881:
879:
876:
875:
873:
868:
862:
855:
851:
845:
842:
839:
835:
829:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
484:
458:
453:
447:
444:
433:
431:
426:
423:
420:
416:
412:
407:
404:
401:
397:
393:
392:
389:
383:
380:
369:
367:
362:
359:
356:
352:
348:
343:
340:
337:
333:
329:
328:
326:
321:
316:
312:
291:
288:
283:
279:
275:
270:
266:
245:
220:
216:
199:
196:
149:
140:for different
122:
119:
90:
87:
84:
80:
76:
71:
68:
65:
61:
57:
52:
48:
15:
13:
10:
9:
6:
4:
3:
2:
1982:
1971:
1968:
1966:
1965:Number theory
1963:
1961:
1958:
1956:
1953:
1952:
1950:
1940:
1936:
1933:
1931:
1925:
1920:
1919:
1914:
1911:
1906:
1905:
1901:
1892:
1888:
1884:
1880:
1876:
1872:
1868:
1864:
1857:
1853:
1849:
1843:
1840:
1835:
1831:
1827:
1823:
1818:
1813:
1809:
1805:
1798:
1795:
1790:
1786:
1782:
1778:
1774:
1770:
1763:
1760:
1754:
1749:
1745:
1741:
1738:
1731:
1728:
1721:
1719:
1712:
1708:
1698:
1693:
1689:
1685:
1681:
1677:
1673:
1667:
1662:
1657:
1642:
1639:
1636:
1632:
1628:
1625:
1620:
1617:
1614:
1610:
1606:
1603:
1598:
1594:
1585:
1581:
1574:
1572:
1570:
1566:
1562:
1558:
1554:
1549:
1536:
1527:
1519:
1516:
1507:
1495:
1491:
1474:
1473:
1472:almost surely
1467:
1463:
1459:
1457:
1452:
1448:
1444:
1440:
1436:
1431:
1429:
1424:
1411:
1404:
1396:
1388:
1384:
1380:
1377:
1371:
1366:
1362:
1355:
1350:
1346:
1337:
1336:Binet formula
1333:
1317:
1314:
1310:
1301:
1296:
1293:
1287:
1284:
1277:
1273:
1268:
1264:
1260:
1256:
1249:
1247:
1234:
1229:
1223:
1218:
1215:
1208:
1203:
1197:
1192:
1189:
1185:
1180:
1174:
1169:
1162:
1157:
1151:
1146:
1143:
1135:
1131:
1127:
1122:
1118:
1102:
1089:
1085:
1079:
1075:
1061:
1057:
1053:
1048:
1045:
1042:
1038:
1032:
1028:
1024:
1011:
1007:
1001:
998:
995:
991:
974:
969:
956:
943:
940:
937:
933:
927:
924:
921:
917:
903:
897:
892:
889:
882:
877:
871:
866:
853:
849:
843:
840:
837:
833:
816:
811:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
655:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
487:
483:
479:
474:
451:
445:
442:
429:
424:
421:
418:
414:
410:
405:
402:
399:
395:
387:
381:
378:
365:
360:
357:
354:
350:
346:
341:
338:
335:
331:
324:
319:
314:
310:
289:
286:
281:
277:
273:
268:
264:
243:
236:
218:
214:
205:
197:
195:
193:
189:
184:
179:
175:
171:
167:
163:
147:
139:
138:independently
120:
117:
106:
88:
85:
82:
78:
74:
69:
66:
63:
59:
55:
50:
46:
38:
34:
30:
26:
22:
1916:
1866:
1862:
1842:
1807:
1803:
1797:
1772:
1768:
1762:
1743:
1739:
1730:
1710:
1706:
1696:
1687:
1683:
1679:
1675:
1671:
1665:
1660:
1658:
1578:
1550:
1470:
1465:
1461:
1455:
1450:
1446:
1439:Harry Kesten
1432:
1427:
1425:
1276:golden ratio
1266:
1262:
1258:
1253:
1133:
1129:
1120:
1116:
972:
970:
812:
656:
485:
481:
201:
166:Harry Kesten
24:
18:
1939:Numberphile
1716:) ≈ 0.89517
1668:* ≈ 0.70258
1580:Mark Embree
1250:Growth rate
198:Description
21:mathematics
1949:Categories
1848:Embree, M.
1775:(2): 131.
1722:References
1272:approaches
29:stochastic
1918:MathWorld
1834:119169165
1810:: 40–44.
1702:≈ 0.36747
1640:−
1629:β
1626:±
1618:−
1607:±
1534:∞
1531:→
1520:…
1514:→
1445:grows as
1433:In 1960,
1389:φ
1378:−
1372:−
1363:φ
1285:φ
1216:−
1054:…
1046:−
999:−
941:−
925:−
890:±
841:−
796:…
790:−
784:−
772:−
766:−
740:…
731:−
722:−
713:−
704:−
695:−
640:…
557:…
473:fair coin
422:−
411:−
403:−
358:−
339:−
105:at random
86:−
75:±
67:−
1891:16404862
1854:(1999).
1789:29600050
1449:, where
815:matrices
256:, where
1871:Bibcode
1692:fractal
1559:on the
1458:th root
1115:where (
204:integer
186:in the
183:A078416
162:theorem
160:. By a
1889:
1832:
1787:
23:, the
1887:S2CID
1859:(PDF)
1830:S2CID
1812:arXiv
1785:S2CID
190:), a
27:is a
1927:OEIS
1582:and
1460:of |
1443:norm
1437:and
1274:the
233:for
188:OEIS
168:and
1937:.
1879:doi
1867:455
1822:doi
1808:121
1777:doi
1748:doi
1714:min
1700:min
1132:or
489:),
164:of
19:In
1951::
1915:.
1885:.
1877:.
1865:.
1861:.
1850:;
1828:.
1820:.
1806:.
1783:.
1771:.
1744:69
1742:.
1718:.
1571:.
1430:.
1338:,
1270:)
817::
551:55
545:34
539:21
533:13
136:,
1921:.
1893:.
1881::
1873::
1836:.
1824::
1814::
1791:.
1779::
1773:8
1756:.
1750::
1711:β
1709:(
1707:σ
1697:β
1688:β
1686:(
1684:σ
1680:β
1676:β
1674:(
1672:σ
1666:β
1661:β
1643:2
1637:n
1633:f
1621:1
1615:n
1611:f
1604:=
1599:n
1595:f
1537:.
1528:n
1508:n
1502:|
1496:n
1492:f
1487:|
1466:n
1462:f
1456:n
1451:n
1447:λ
1428:φ
1412:.
1405:5
1397:n
1393:)
1385:/
1381:1
1375:(
1367:n
1356:=
1351:n
1347:F
1318:,
1315:2
1311:/
1307:)
1302:5
1297:+
1294:1
1291:(
1288:=
1267:n
1263:F
1259:n
1235:.
1230:)
1224:1
1219:1
1209:1
1204:0
1198:(
1193:=
1190:B
1186:,
1181:)
1175:1
1170:1
1163:1
1158:0
1152:(
1147:=
1144:A
1134:B
1130:A
1121:k
1117:M
1103:,
1097:)
1090:2
1086:f
1080:1
1076:f
1070:(
1062:3
1058:M
1049:1
1043:n
1039:M
1033:n
1029:M
1025:=
1019:)
1012:n
1008:f
1002:1
996:n
992:f
986:(
973:n
957:,
951:)
944:1
938:n
934:f
928:2
922:n
918:f
912:(
904:)
898:1
893:1
883:1
878:0
872:(
867:=
861:)
854:n
850:f
844:1
838:n
834:f
828:(
799:.
793:,
787:,
781:,
778:+
775:,
769:,
763:,
760:+
757:,
754:+
751:,
748:+
737:,
734:3
728:,
725:2
719:,
716:5
710:,
707:3
701:,
698:2
692:,
689:1
686:,
683:3
680:,
677:2
674:,
671:1
668:,
665:1
643:.
637:,
634:1
631:,
628:0
625:,
622:1
619:,
616:1
613:,
610:0
607:,
604:1
601:,
598:1
595:,
592:0
589:,
586:1
583:,
580:1
560:.
554:,
548:,
542:,
536:,
530:,
527:8
524:,
521:5
518:,
515:3
512:,
509:2
506:,
503:1
500:,
497:1
486:n
482:F
480:(
452:.
446:2
443:1
430:,
425:2
419:n
415:f
406:1
400:n
396:f
388:;
382:2
379:1
366:,
361:2
355:n
351:f
347:+
342:1
336:n
332:f
325:{
320:=
315:n
311:f
290:1
287:=
282:2
278:f
274:=
269:1
265:f
244:n
219:n
215:f
148:n
121:2
118:1
89:2
83:n
79:f
70:1
64:n
60:f
56:=
51:n
47:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.