랜덤 피보나치 수열

수학에서 무작위 피보나치 수열은 반복관계_n f = f_n−1 ± f에_n−2 의해 정의된 피보나치 수열의 확률적 아날로그로, 여기서 부호 + 또는 -는 서로 다른 n에 대해 독립적으로 동일한 확률 1/2로 무작위로 선택된다.해리 케스틴과 힐렐 푸르스텐베르크의 정리로는 이런 종류의 무작위 반복 시퀀스가 일정한 기하급수적인 비율로 증가하지만 그 비율을 명시적으로 계산하기는 어렵다.1999년 디바카르 비스와나트는 무작위 피보나치 수열의 증가율이 1.1319882487943…(OEIS의 후속 A078416)과 같다는 것을 보여주었는데, 이 상수는 나중에 비스와나스의 상수라고 명명되었다.^[1][2][3]

설명

무작위 피보나치 시퀀스는 정수 랜덤 시퀀스 {f_n}이며, 여기서 f₁ = f₂ = 1이고 이후 항은 무작위 반복 관계를 통해 결정된다.

${\displaystyle f_{n}={\displaysty}f_{n-1}+f_{n-2},>{\text{ 확률 1/2};\f_{n-1}-f_{n-2},&{\text{\text}.\end{case}}}$

무작위 피보나치 수열의 연속은 1,1로 시작하고 각 후속 기간의 값은 공정한 동전 던지기에 의해 결정된다: 순서의 두 가지 연속적인 요소를 감안할 때, 다음 원소는 이전에 행해진 모든 선택과는 별개로 그들의 합이거나 확률 1/2과의 차이다.무작위 피보나치 시퀀스에서 각 단계에서 플러스 기호가 선택되면 해당 런은 피보나치 시퀀스 {F_n}이다.

${\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots.}$

기호가 마이너스++마이너스+++++로 번갈아 나타나는 경우...패턴, 결과는 시퀀스

${\displaystyle 1,1,0,1,0,1,1,\ldots .}$

그러나 그러한 패턴은 무작위 실험에서 소멸 확률과 함께 발생한다.일반적인 실행에서 항은 예측 가능한 패턴을 따르지 않는다.

${\displaystyle 1,1,2,3,-2,-3,-3,-5,-2,-3,\ldots{{}+,+,+,+,-,+,+,-,-,-,-,-,\ldots.}$

결정론적 사례와 유사하게 무작위 피보나치 시퀀스는 행렬을 통해 유익하게 설명될 수 있다.

${\displaystyle {f_{n-1} \f_{n1}={\\pm 1&1\end{pmatrix}{pmatrix}}{f_{n-2}} \f_{n-1},} 선택$

여기서 기호는 + 또는 -에 대해 동일한 확률로 서로 다른 n에 대해 독립적으로 선택된다.그러므로

${\displaystyle {f_{n-1} \f_{n}}=M_{n-1}\ldots M_{3}{f_{1} \선택 f_{2}},}$

여기서 {M_k}은 확률 1/2로 A 또는 B 값을 취하며 동일한 분산 랜덤 행렬의 시퀀스입니다.

${\displaystyle A={\begin{pmatrix}0&1\1\end{pmatrix},\quad B={\begin{pmatrix}0&1\-1\end{pmatrix}}.}$

성장률

요하네스 케플러는 n이 증가함에 따라 피보나치 수열 {F_n}의 연속적인 항 비율이 황금 비율${\displaystyle }\phi {\displaystyle }$ =${\displaystyle }$(${\displaystyle 1\sqrt{\mathrm{}}}$+ 5${\displaystyle }$)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$, ${\displaystyle \varphi$ = $(1+{\sqrt{5})/2$에 근접한다는 것을 발견했는데$,$ 이는$$ 약 1.61803이다.1765년, 레온하르트 오일러는 오늘날 비넷 공식으로 알려진 명시적인 공식을 발표하였다.

${\displaystyle F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}}}}\over {\sqrt{5}}}.}$

피보나치 수치가 황금비율 φ과 같은 지수적인 비율로 증가한다는 것을 보여준다.

1960년에 힐렐 퍼스텐버그와 해리 케스틴은 일반 등급의 무작위 매트릭스 제품의 경우 n이 인자의 수인 λ으로ⁿ 표준이 성장한다는 것을 보여주었다.이들의 결과는 무작위 피보나치 수열을 포함하는 광범위한 무작위 시퀀스 생성 프로세스에 적용된다.결과적으로_n, f의 n번째 루트는 거의 확실히 일정한 값으로 수렴되거나 확률 1과 함께 수렴된다.

${\displaystyle {\sqrt[{n}]{f_{n}}}} }\to 1.1319882487943\propert{\text{{} \to }}$

이 상수에 대한 명시적인 표현은 1999년 디바카르 비스와나트에 의해 발견되었다.무작위 매트릭스 제품의 랴푸노프 지수 및 Stern-Brocot 트리의 특정 프랙탈 측정에 대한 통합을 위해 Furstenberg의 공식을 사용한다.더욱이 Viswanath는 반올림 오차의 분석에 의해 검증된 부동소수 산술학을 사용하여 위의 수치 값을 계산했다.

일반화

Mark Embree와 Nick Trefethen은 1999년에 그 순서가

${\displaystyle f_{n}=f_{n-1}\pm \fm f_{n-2}}$

β가 임계 값 β* ≈ 0.70258보다 작을 경우 거의 확실히 검출되며, 이는 Embree–로 알려져 있다.Trefethen 상수, 그리고 그렇지 않으면 거의 확실하게 자란다.그들은 또한 연속된 항 사이의 점근비 β(β)가 β의 모든 값에 대해 거의 확실하게 수렴된다는 것을 보여주었다.σ(β)의 그래프는 프랙탈 구조를 가지고 있는 것으로 보이며, 전지구적 최소치는 β_min 47 0.36747에 근접하여 σ(β_min) ≈ 0.89517과 거의 같다.^[4]

참조

외부 링크

• Weisstein, Eric W. "Random Fibonacci Sequence". MathWorld.
• OEIS 시퀀스 A078416(Viswanath 상수의 십진수 확장)
• 임의 피보나치 숫자.무작위 피보나시 수열에 대한 번호표시의 비디오.