## 利用馬可夫鏈計算擲幣事件發生的機率

OXXXXXOXOOXOOXOOXOOX，

XXOXOOOXOOXOXXOOXXOO。

\begin{aligned} S_1&\xrightarrow{X}S_1,~S_1\xrightarrow{O}S_2\\ S_2&\xrightarrow{X}S_1,~S_2\xrightarrow{O}S_3\\ S_3&\xrightarrow{X}S_3,~S_3\xrightarrow{O}S_3\end{aligned}

$S_1\to S_2\to S_1\to S_1\to S_2\to S_3\to S_3$

Markov chain: Two heads in a row

\begin{aligned} P_1(k)&=qP_1(k-1)+qP_2(k-1)\\ P_2(k)&=pP_1(n-1)\\ P_3(k)&=pP_2(n-1)+P_3(n-1),\end{aligned}

$\begin{bmatrix} P_1(k)\\ P_2(k)\\ P_3(k) \end{bmatrix}=\begin{bmatrix} q&q&0\\ p&0&0\\ 0&p&1 \end{bmatrix}\begin{bmatrix} P_1(k-1)\\ P_2(k-1)\\ P_3(k-1) \end{bmatrix}$

$\mathbf{u}_k=\begin{bmatrix} P_1(k)\\ P_2(k)\\ P_3(k) \end{bmatrix},~A=\begin{bmatrix} q&q&0\\ p&0&0\\ 0&p&1 \end{bmatrix}$

$\mathbf{u}_k=c_1\lambda_1^k\mathbf{x}_1+c_2\lambda_2^k\mathbf{x}_2+c_3\lambda_3^k\mathbf{x}_3$

$\det(A-\lambda I)=\begin{vmatrix} q-\lambda&q&0\\ p&-\lambda&0\\ 0&p&1-\lambda \end{vmatrix}=(1-\lambda)(\lambda^2-q\lambda-pq)$

$\displaystyle\lambda_1=\frac{q+r}{2},~\lambda_2=\frac{q-r}{2},~\lambda_3=1$

$\mathbf{x}_1=\begin{bmatrix} \lambda_1\\ p\\ p^2/(\lambda_1-1) \end{bmatrix},~\mathbf{x}_2=\begin{bmatrix} \lambda_2\\ p\\ p^2/(\lambda_2-1) \end{bmatrix},~\mathbf{x}_3=\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}$

$\mathbf{u}_k=c_1\lambda_1^k\begin{bmatrix} \lambda_1\\ p\\ p^2/(\lambda_1-1) \end{bmatrix}+c_2\lambda_2^k\begin{bmatrix} \lambda_2\\ p\\ p^2/(\lambda_2-1) \end{bmatrix}+c_3\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}$

\displaystyle\begin{aligned} c_1\lambda_1^2+c_2\lambda_2^2&=q\\ c_1\lambda_1+c_2\lambda_2&=1\\ c_1p^2\frac{\lambda_1}{\lambda_1-1}+c_2p^2\frac{\lambda_2}{\lambda_2-1}+c_3&=0,\end{aligned}

$\displaystyle c_1=\frac{q-\lambda_2}{\lambda_1(\lambda_1-\lambda_2)}=\frac{\lambda_1}{\lambda_1r}=\frac{1}{r}$

$\displaystyle c_2=\frac{1}{\lambda_2}\left(1-\frac{\lambda_1}{r}\right)=\frac{r-\lambda_1}{\lambda_2r}=\frac{-\lambda_2}{\lambda_2r}=-\frac{1}{r}$

\displaystyle\begin{aligned} c_3&=\frac{p^2}{r}\left(\frac{\lambda_1}{1-\lambda_1}-\frac{\lambda_2}{1-\lambda_2}\right)\\ &=\frac{p^2}{r}\cdot\frac{\lambda_1-\lambda_2}{(1-\lambda_1)(1-\lambda_2)}\\ &=\frac{p^2}{1-\lambda_1-\lambda_2+\lambda_1\lambda_2}\\ &=\frac{p^2}{1-q-pq}=\frac{p^2}{p-pq}\\ &=\frac{p^2}{p(1-q)}=\frac{p}{1-q}=1\end{aligned}

\displaystyle\begin{aligned} P_1(k)&=\frac{1}{r}\left(\lambda_1^{k+1}-\lambda_2^{k+1}\right)\\ P_2(k)&=\frac{p}{r}\left(\lambda_1^k-\lambda_2^k\right)\\ P_3(k)&=\frac{p^2}{r}\left(\frac{\lambda_1^k}{\lambda_1-1}-\frac{\lambda_2^k}{\lambda_2-1}\right)+1\end{aligned}

$\displaystyle \lambda_1=\frac{1}{2}\left(\frac{1+\sqrt{5}}{2}\right),~\lambda_2=\frac{1}{2}\left(\frac{1-\sqrt{5}}{2}\right)$

\displaystyle\begin{aligned} P_1(n)&=\frac{1}{2^n}\cdot\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]=\frac{F_{n+1}}{2^n}\\ P_2(n)&=\frac{1}{2^n}\cdot\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]=\frac{F_n}{2^n},\end{aligned}

$F_{n+2}=F_{n+1}+F_{n}$

$\displaystyle P_3(n)=1-(P_1(n)+P_2(n))=1-\frac{F_{n+2}}{2^n}$

$\displaystyle 1-\frac{F^{(m)}_{n+2}}{2^n}$

0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,…。

OOOXO, OOOXX, XOOOX, OXOOO, XXOOO, OOOOX, XOOOO, OOOOO。

$\displaystyle 1-\frac{F^{(4)}_{22}}{2^{20}}=1-\frac{547,337}{1,048,576}=1-0.5220=0.4780$

$n=20$$m=5$，結果是

$\displaystyle 1-\frac{F^{(5)}_{22}}{2^{20}}=1-\frac{786,568}{1,048,576}=1-0.7501=0.2499$

$\displaystyle Q_k=\frac{1}{2}Q_{k-1}+\frac{1}{4}Q_{k-2},~~k>2$

$\displaystyle 2^kQ_k=2^{k-1}Q_{k-1}+2^{k-2}Q_{k-2},~~k>2$

$R_k=2^kQ_k$，就有

$R_k=R_{k-1}+R_{k-2}$

$\displaystyle P_n=1-\frac{F_{n+2}}{2^n}$

$\displaystyle P_n=1-\frac{F^{(m)}_{n+2}}{2^n}$

[1] Gary Belsky and Thomas Gilovich, Why smart people make big money mistakes and how to correct them, Fireside, pp 119, 1999.
[4] http://en.wikipedia.org/wiki/Markov_chain

This entry was posted in 機率統計 and tagged , , , , , , . Bookmark the permalink.

### 3 則回應給 利用馬可夫鏈計算擲幣事件發生的機率

1. pgcci7339 說：

老師您好~對於廣義費布納西數的定義，我可能還不是看的非常清楚~想請問您一下：)

當m=3時，$F^{(3)}_{n}$ 的前三項 0，1，1 是如何來的呢，第一個0我知道根據定義，那後面兩個1呢？
若m=4，前4個是否是0，1，1，2？
若m=5，前5個是否為0，1，1，2，3？

• ccjou 說：

不論是我們熟悉的傳統或廣義費布納西數的初始條件都是 $F_0=0$$F_1=1$。當 $m=4$$F_2$ 的計算方式為
$F_2=F_1+F_0+F_{-1}+F_{-2}$
我們另外定義 $F_k=0$，若 $k<0$，所以
$F_2=1+0+0+0=1$
$F_3=1+1+0+0=2$
$F_4=2+1+1+0=4$
$F_5=4+2+1+1=8$
$F_6=8+4+2+1=15$

• pgcci7339 說：

謝謝老師的講解~：)