乱数斐波那契数列

乱数斐波那契数列是一个类似斐波那契数列的数列，由以下的递回关系式所定义：

f_n = f_n−1 ± f_n−2

其中正负号是依乱数决定，机率各是1/2，每次的正负号有统计独立性。

依照Harry Kesten及Hillel Fürstenberg的理论，这类的乱数递回关系式会依某种指数增长的方式增长，但其增长的速率很难具体的计算出来，1999年时Divakar Viswanath证明乱数斐波那契数列的增长速率为1.1319882487943…（OEIS数列A078416），此常数后来也被命名为Viswanath常数。

推广

马克·恩布里（英语：Mark Embree）及劳埃德·尼古拉斯·特雷费森（英语：Lloyd Nicholas Trefethen）发现以下的以下的递回关系式

${\displaystyle x_{n+1}=x_{n}\pm \beta x_{n-1}\,}$

在β小于临界值β* ≈ 0.70258后，几乎必定会衰减，此临界值称为恩布里-特雷费森常数（Embree–Trefethen constant），否则，此数列几乎必定会成长。他们也证明在两项之间的渐近比例σ(β)在每一个β都几乎确定收敛。σ(β)的图中存在碎形结构，全域最小值出现在β_min ≈ 0.36747附近，近似等于σ(β_min) ≈ 0.89517.^[1]。

参考资料

• Viswanath, Divakar, Random Fibonacci sequences and the number 1.13198824…, Mathematics of Computation, 1999, 69 (231): 1131–1155, doi:10.1090/S0025-5718-99-01145-X.

• Oliveira, J.B.; de Figueiredo, L.H., Interval computation of Viswanath's constant, Reliable Computing, 2002, 8 (2): 131–138., doi:10.1023/A:1014702122205

• Makover, Eran; McGowan, Jeffrey, An elementary proof that random Fibonacci sequences grow exponentially, Journal of Number Theory, 2006, 121 (1): 40–44, doi:10.1016/j.jnt.2006.01.002 arXiv:math.NT/0510159.