https://spherical-harmonics.hateblo.jp/entry/Todai/1983/Bunka

2023.08.23記

[4] 直線上に，赤と白の旗をもった何人かの人が，番号 $0$ ， $1$ ， $2$ ，…… をつけて並んでいる．
番号 $0$ の人は，赤と白の旗を等しい確率で無作為にあげるものとし，他の番号 $j$ の人は，番号 $j-1$ の人のあげた旗の色を見て，確率 $p$ で同じ色，確率 $1-p$ で異なる色の旗をあげるものとする．

このとき，番号 $0$ の人と番号 $n$ の人が同じ色の旗をあげる確率 $P_n$ を求めよ．

本問のテーマ

マルコフ過程

2020.11.28記
$p\neq 0,1$ なら十分大きい $n$ に対しては $P_n\approx \dfrac{1}{2}$ になるはずと考えると $P_n-\dfrac{1}{2}$ はすぐに見えます．

[解答]
$P_n=P_{n-1}\cdot p + (1-P_{n-1})(1-p)$ より
$P_n-\dfrac{1}{2}=(2p-1)\Bigl(P_{n-1}-\dfrac{1}{2}\Bigr)$ $=(2p-1)^n\Bigl(P_{0}-\dfrac{1}{2}\Bigr)$
となるので $P_0=1$ から
$P_n=\dfrac{1}{2}(2p-1)^n+\dfrac{1}{2}$

2023.08.23記
番号 $j$ の人が番号 $0$ の人と同じ色をあげる確率を $s_j$ ，異なる色をあげる確率を $d_j$ とする．

$A=\begin{pmatrix} p & 1-p \\ 1-p & p \end{pmatrix}$ とおくと
$\begin{pmatrix} s_j \\ d_j\end{pmatrix}=A\begin{pmatrix} s_{j-1} \\ d_{j-1}\end{pmatrix}$ $=A^{n}\begin{pmatrix} s_{0} \\ d_{0}\end{pmatrix}$ $=A^{n}\begin{pmatrix} 1 \\ 0\end{pmatrix}$
が成立する．ここで
$A=\dfrac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 2p-1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$
だから，
$A^n=\dfrac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & (2p-1 )^n\end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$
となる．よって $s_n$ は
$A^n\begin{pmatrix} 1 \\ 0\end{pmatrix}$ $=\dfrac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & (2p-1 )^n\end{pmatrix}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$
$=\dfrac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1 \\ (2p-1 )^n\end{pmatrix}$
$=\dfrac{1}{2}\begin{pmatrix} 1+(2p-1 )^n \\ 1-(2p-1 )^n\end{pmatrix}$
の第一成分の $\dfrac{1+(2p-1 )^n}{2}$ となる．

ちなみに
$A^n$ $=\dfrac{1}{2}\begin{pmatrix} 1+(2p-1 )^n & 1-(2p-1 )^n \\ 1-(2p-1 )^n & 1+(2p-1 )^n \end{pmatrix}$
である．