擲硬幣問題

重複擲一枚硬幣, 當出現連續兩次為正時停止, 平均要扔幾次?

第一種做法: 窮舉法

我們以正負號 (+ -) 代表正面反面.

觀察

假設花 $n$ 次才擲到連續兩次為正, $n \geq 2$.

我們發現, 可以從第 $n-1$ 次的結果進行窮舉法得到第 $n$ 次的結果。

• 當 $n = 2$, 只會有 1 種情況 : ++
• 要窮舉 $n = 3$, 要知道三次中的尾巴兩次必須是 $n=2$ 的所有情況. 由於 $n=2$ 的第一個為正, 因此要在前加一項只能為負, 因此 $n=3$ 只有 -++ 這情況
• 對 $n=4$, 尾巴三次必須是 $n=3$ 的所有情況. 由於 $n=3$ 的第一個為負, 因此要在前加正或負皆可, 因此 $n=4$ 有兩種情況: +-++, --++

小結論

對 $n=k+1$ 而言, 我們只需要考慮 $n=k$ 所有情況的第一個是正或負即可. 若為正則只能在前面再加個負, 若為負則可以在前面加正或負.

也就是說, 假設 $n=k$ 中有 $x_k$ 個情況第一個為正, 有 $y_k$ 個情況第一個為負, 那 $n=k+1$ 的所有情況中必有 $y_k$ 個情況第一個為正, $x_k+y_k$ 個情況第一個為負. 寫成矩陣型式就是 $$ \begin{bmatrix} x_{k+1} \\ y_{k+1}\end{bmatrix} = A \begin{bmatrix} x_{k} \\ y_{k}\end{bmatrix}, \quad A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} $$ 則我們有 $$ \begin{bmatrix} x_{k} \\ y_{k}\end{bmatrix} = A^{k-2} \begin{bmatrix} 1 \\ 0\end{bmatrix}, \quad k\ge 2. $$ 並且我們知道花 $k$ 次才達到連續兩次為正共會有 $x_k+y_k$ 種情況, 意即 $$ \begin{bmatrix} 1 & 1\end{bmatrix} A^{k-2} \begin{bmatrix} 1 \\ 0\end{bmatrix}. $$ 另外我們還知道丟硬幣 $k$ 次之任一情況的機率為 $\frac{1}{2^k}$.

計算期望值

利用以上結果我們可以知道期望值為 $$ E = \sum_{k=2}^\infty \left( \begin{bmatrix} 1 & 1\end{bmatrix} A^{k-2} \begin{bmatrix} 1 \\ 0\end{bmatrix} \right) \cdot \frac{k}{2^{k}} =\sum_{k=0}^\infty \left( \begin{bmatrix} 1 & 1\end{bmatrix} A^{k} \begin{bmatrix} 1 \\ 0\end{bmatrix} \right) \cdot \frac{k+2}{2^{k+2}}. $$

1. 對角化 $$ A = \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix} = \frac{1}{\sqrt{5}} \begin{bmatrix}1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\end{bmatrix} \begin{bmatrix}\frac{1+\sqrt{5}}{2} & 0 \\ 0 & \frac{1-\sqrt{5}}{2}\end{bmatrix} \begin{bmatrix}\frac{\sqrt{5}-1}{2} & 1 \\ \frac{1+\sqrt{5}}{2} & -1\end{bmatrix} $$

2. 可得 $$ A^k = \frac{1}{\sqrt{5}} \begin{bmatrix}1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\end{bmatrix} \begin{bmatrix}\left(\frac{1+\sqrt{5}}{2}\right)^k & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right)^k\end{bmatrix} \begin{bmatrix}\frac{\sqrt{5}-1}{2} & 1 \\ \frac{1+\sqrt{5}}{2} & -1\end{bmatrix} $$

3. 接著我們有 $$ \begin{bmatrix} 1 & 1\end{bmatrix} A^{k} \begin{bmatrix} 1 \\ 0\end{bmatrix} =\frac{1}{\sqrt{5}}\left[(\frac{1+\sqrt{5}}{2})^{k-1}\cdot\frac{3+\sqrt{5}}{2} - (\frac{1-\sqrt{5}}{2})^{k-1}\cdot\frac{3-\sqrt{5}}{2}\right] $$

4. 因此 $$ E = \frac{3+\sqrt{5}}{16\sqrt{5}} \underbrace{\sum_{k=0}^{\infty}(k+2)\cdot(\frac{1+\sqrt{5}}{4})^{k-1}}_{(a)} - \frac{3-\sqrt{5}}{16\sqrt{5}} \underbrace{\sum_{k=0}^{\infty}(k+2)\cdot(\frac{1-\sqrt{5}}{4})^{k-1}}_{(b)} $$

Recall Calculus

要算 (a) 與 (b) 我們先 recall 微積分裡的一個結果

$$ \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}, \quad |x| < 1. $$ 兩邊微分得到 $$ \sum_{n=0}^{\infty} n x^{n-1} = \frac{1}{(1-x)^2}, \quad |x| < 1. $$

利用這個我們可以算 (a) $$ \sum_{k=0}^{\infty}(k+2)\cdot(\frac{1+\sqrt{5}}{4})^{k-1} = 18 + 10\sqrt{5} $$ 也可以算 (b) $$ \sum_{k=0}^{\infty}(k+2)\cdot(\frac{1-\sqrt{5}}{4})^{k-1} = 18 - 10\sqrt{5} $$

最後, $$ E = \frac{3+\sqrt{5}}{16\sqrt{5}}\cdot (18+10\sqrt{5}) - \frac{3-\sqrt{5}}{16\sqrt{5}}\cdot (18-10\sqrt{5}) = 6 $$

結論

重複擲一枚硬幣, 當出現連續兩次為正時停止, 平均要扔六次.

第二種做法:

我們可以用 Markov chain 來想這問題

觀察

假設目前連續投擲出 0 個正, 那下一投有 $0.5$ 機率是正以及 $0.5$ 機率是負. 也就是 $0.5$ 機率會是到 1正 這狀態以及 $0.5$ 機率回到 0正 這狀態.

假設目前連續投擲出 1 個正, 那下一投則 $0.5$ 機率會是到 2正 這狀態以及 $0.5$ 機率回到 0正 這狀態.

根據這些觀察我們可以做出以下的 diagram:

graph LR;
A[0 正] -- 0.5 -->B(1 正)
  B -- 0.5 --> C(2 正)
  A -- 0.5 --> A
  B -- 0.5 --> A

接著我們假設從 0正 這狀態需要投 $k_0$ 次才會到 2正, 而從 1正 這狀態需要投 $k_1$ 次才會到 2正.

對 0正 狀態而言, 投一次有 $0.5$ 機會到1正狀態, 然後再需要 $k_1$ 次到2正, 所以這樣總共投 $1+k_1$ 次. 而 0正 投一次也有 $0.5$ 機會會回到自己原始 0正 狀態, 然後再需要 $k_0$ 次到2正, 所以這樣總共投 $1+k_0$ 次. 如此可以列式: $$ k_0 = 0.5(1+k_1) + 0.5(1+k_0) $$

同理, 對 1正 狀態而言我們有以下式子 $$ k_1 = 0.5(1) + 0.5(1+k_0) $$

這樣我們有兩個未知數兩個方程式, 解出來得到 $$ k_0=6, \quad k_1=4. $$

所以, 從 0正 狀態到出現連續兩次為正平均要投 $6$ 次.