令正面为H，背面为T

有4个状态，S1是开始或抛出反面（begin/T），S2是一个正面（H），S3:是连续抛出两个正面（HH），S4是连续抛出3个正面并结束（HHH）。

图来至

初始状态$x_0=[1,0,0,0]$，状态转移矩阵是

$$P=\begin{bmatrix}0.5 & 0.5 & 0 & 0\\0.5 & 0 & 0.5 & 0 \\ 0.5 & 0 & 0 & 0.5\\ 0 & 0 & 0 & 1\end{bmatrix}$$

$x_{t+1}=x_{t} P$

根据Markov Chain hitting time公式 定理1.3.5

$K_i^A $是状态i到状态A的步数的期望

$K_1^4 = 1 + \sum\limits_{j = 1,2,3} {{P_{1j}}K_j^4} =1+0.5K_1^4+0.5K_2^4$

$K_2^4 = 1 + \sum\limits_{j = 1,2,3} {{P_{2j}}K_j^4} =1+0.5K_1^4+0.5K_3^4$

$K_3^4 = 1 + \sum\limits_{j = 1,2,3} {{P_{3j}}K_j^4} =1+0.5K_1^4$

有$K_1^4=1+0.5K_1^4+0.5(1+0.5K_1^4+0.5(1+0.5K_1^4)$

最后$K_1^4=14$

提供两种解法：

1. 根据 http://sofasofa.io/forum_main_post.php?postid=1001963 的思路，得到公式

$(1-p)(x+1)+p(1-p)(x+2)+p^2(1-p)(x+3)+3p^3=x$

由 $p=1/2$ 得，$x=14$。

2. 根据 http://www.aquatutoring.org/ExpectedValueMarkovChains.pdf 的 Example 7 可直接得期望为 14。