ランダムなフィボナッチ数列

数学において、ランダム フィボナッチ数列は、再帰関係によって定義されるフィボナッチ数列の確率的類似物であり、異なる に対して独立に、符号 + または − が等しい確率 でランダムに選択される。ハリー ケステンとヒレル ファーステンバーグの定理によれば、この種のランダム再帰数列は一定の指数関数的速度で増加するが、その速度を明示的に計算することは困難である。1999 年、ディヴァカール ヴィシュワナートは、ランダム フィボナッチ数列の増加率が 1.1319882487943... ( OEISの数列A078416 ) に等しいことを示しました。これは後にヴィシュワナートの定数と名付けられた数学定数です。 ^{[1] [2] [3]} ${\displaystyle f_{n}=f_{n-1}\pm f_{n-2}}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle n}$

ランダム フィボナッチ数列は、自然数の数値によって与えられる整数ランダム数列で、 であり、後続の項はランダム再帰関係に従ってランダムに選択される。 ランダム フィボナッチ数列のインスタンスは 1,1 から始まり、後続の各項の値は公平なコイントスによって決定される。数列の連続する 2 つの要素が与えられると、次の要素は、それまでに行われたすべての選択とは無関係に、確率 1/2 でそれらの和または差のいずれかになる。ランダム フィボナッチ数列で各ステップでプラス記号が選択される場合、対応するインスタンスはフィボナッチ数列( F _n ) である。 符号がマイナス-プラス-プラス-マイナス-プラス-プラス-... のパターンで交互になる場合、結果は数列になる。 ${\displaystyle f_{n}}$ ${\displaystyle n}$${\displaystyle f_{1}=f_{2}=1}$$${\displaystyle f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{ 確率 }}{\tfrac {1}{2}};\\f_{n-1}-f_{n-2},&{\text{ 確率 }}{\tfrac {1}{2}}.\end{cases}}}$$$${\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots .}$$$${\displaystyle 1,1,0,1,1,0,1,1,0,1,\ldots .}$$

しかし、このようなパターンはランダムな実験ではゼロ確率で発生します。典型的な実行では、項は予測可能なパターンに従いません。 $${\displaystyle 1,1,2,3,1,-2,-3,-5,-2,-3,\ldots {\text{ 記号については }}+,+,+,-,-,+,-,-,\ldots 。}$$

決定論的な場合と同様に、ランダムなフィボナッチ数列は行列を介して効果的に記述できます。 $${\displaystyle {f_{n-1} \choose f_{n}}={\begin{pmatrix}0&1\\\pm 1&1\end{pmatrix}}{f_{n-2} \choose f_{n-1}},}$$

ここで、符号は異なるnに対して独立して選択され、+または-の確率は等しい。したがって 、( M _k )は、確率1/2で値AまたはBを取る独立した同一分布のランダム行列のシーケンスです。 $${\displaystyle {f_{n-1} \choose f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \choose f_{2}},}$$$${\displaystyle A={\begin{pmatrix}0&1\\1&1\end{pmatrix}},\quad B={\begin{pmatrix}0&1\\-1&1\end{pmatrix}}.}$$

ヨハネス・ケプラーは、 nが増加すると、フィボナッチ数列の連続項の比率（F _n）が黄金比（約1.61803）に近づくことを発見しました。1765年にレオンハルト・オイラーは、今日ビネーの公式として知られる明確な公式を発表しました。 ${\displaystyle \varphi =(1+{\sqrt {5}})/2,}$$${\displaystyle F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}.}$$

これは、フィボナッチ数が黄金比φに等しい指数関数的に増加することを示しています。

1960 年、ヒレル・ファーステンバーグとハリー・ケステンは、ランダム行列積の一般的なクラスでは、ノルムがλ ⁿ（nは因数の数）に比例して増加することを示しました。彼らの結果は、ランダムなフィボナッチ数列を含む、ランダムな数列を生成するプロセスの広いクラスに適用されます。結果として、| f _{n | の}n乗根はほぼ確実に、つまり確率 1 で定数に収束します。 $${\displaystyle {\sqrt[{n}]{|f_{n}|}}\to 1.1319882487943\dots {\text{ as }}n\to \infty .}$$

この定数の明示的な表現は、1999 年に Divakar Viswanath によって発見されました。これは、ランダム行列積のLyapunov 指数に対する Furstenberg の公式と、 Stern–Brocot 木上の特定のフラクタル測度での積分を使用しています。さらに、Viswanath は、丸め誤差の分析によって検証された浮動小数点演算を使用して上記の数値を計算しました。

マーク・エンブリーとニック・トレフェセンは1999年に、 $${\displaystyle f_{n}=\pm f_{n-1}\pm \beta f_{n-2}}$$

β が臨界値β * ≈ 0.70258（エンブリー・トレフェゼン定数として知られる）より小さい場合、ほぼ確実に減少し、そうでない場合はほぼ確実に増加する。彼らはまた、連続する項間の漸近比σ ( β ) があらゆるβの値に対してほぼ確実に収束することを示した。 σ ( β )のグラフはフラクタル構造を持っているように見え、 β _min ≈ 0.36747付近で大域的最小値がσ ( β _min ) ≈ 0.89517にほぼ等しい。^[4]

• ワイスタイン、エリック W.「ランダム フィボナッチ数列」。マスワールド。
• OEISシーケンス A078416 (ヴィシュワナート定数の 10 進展開)
• ランダムなフィボナッチ数列。 ランダムなフィボナッチ数列に関するNumberphileのビデオ。