1993年(平成5年)東京大学前期-数学(理科)[5] - [別館]球面倶楽部零八式markIISR

2024.01.07記

[5] $1$ と $0$ を $5$ 個ならべた列 $10110$ をある人が繰返し書き写すとする．ただし，この列を $S$ で表し，これの第1回の写しを $S_1$ で表すとき，第2回目に書き写すときは $S_1$ を書き写す． $S_1$ の写しを $S_2$ とするとき，第3回目には $S_2$ を書き写す．以下同様に続ける．

この人が $0$ を $1$ に写しまちがえる確率は $p$ （ $0\lt p\lt 1$ ）であり， $1$ を $0$ に写しまちがえる確率は $q$ （ $0\lt q\lt 1$ ）であるが，それ以外の写しまちがいはないものとする．第 $n$ 回目の写し $S_n$ が $S$ に一致する確率を $C(n)$ とするとき，極限値 $\displaystyle\lim_{n\to\infty}C(n)$ を求めよ．

本問のテーマ

2元非対称通信路

2024.01.09記
通信することにより確率的に符号を誤って通信してしまうことから信号が劣化する，というモデルの1つが2元非対称通信路である．この通信を十分多数回行ったとしても， $S$ が正しく送られる確率には下限 $\dfrac{p^3q^2}{(p+q)^5}$ が存在する．つまり少なくとも $\dfrac{p^3q^2}{(p+q)^5}$ 以上の確率で符号が正しく送られていることが保証される．

ここで， $p=q=\dfrac{1}{2}$ のとき，書き写す度にランダムな文字列となるので $C(n)=\dfrac{1}{32}$ と $n$ によらない筈，と思えれば計算ミスに気付き易くなる（ $p=q$ ならば0が1になり易さと1が0になり易さが同じなので最終的には $\dfrac{1}{32}\$ に近づくはずとも思えれば尚良い）．

[大人の解答]
各桁独立に考えれば良い．
ある桁の文字が $k$ 回目に書き写したときに $0$ ， $1$ である確率を $p_k(0)$ ， $p_k(1)$ とし，
$A=\begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix}$ とおくと $\begin{pmatrix} p_{k+1}(0) \\ p_{k+1}(1) \end{pmatrix}$ $=A\begin{pmatrix} p_{k}(0) \\p_{k}(1) \end{pmatrix}$ が成立するので
$\begin{pmatrix} p_{n}(0) \\ p_{n}(1) \end{pmatrix}=A^n\begin{pmatrix} p_{0}(0) \\ p_{0}(1) \end{pmatrix}$
である．
$A\begin{pmatrix} 1 \\ -1\end{pmatrix}=(1-p-q)\begin{pmatrix} 1 \\ -1\end{pmatrix}$ ， $A\begin{pmatrix} q \\ p\end{pmatrix}=\begin{pmatrix} q \\ p\end{pmatrix}$
から
$A^n\begin{pmatrix} 1 & q \\ -1& p\end{pmatrix}$ $=\begin{pmatrix} 1 & q \\ -1& p\end{pmatrix}\begin{pmatrix} (1-p-q)^n & 0 \\ 0 & 1\end{pmatrix}$
が成立するので， $B:=\displaystyle\lim_{n\to\infty} A^n$ とおくと $-1\lt 1-p-q\lt 1$ から
$B\begin{pmatrix} 1 & q \\ -1& p\end{pmatrix}=\begin{pmatrix} 1 & q \\ -1& p\end{pmatrix}\begin{pmatrix} 0 & 0 \\ 0 & 1\end{pmatrix}$ $=\begin{pmatrix} 0 & q \\ 0& p\end{pmatrix}$
となり，
$B=\dfrac{1}{p+q}\begin{pmatrix} 0 & q \\ 0& p\end{pmatrix}\begin{pmatrix} p & -q \\ 1& 1\end{pmatrix}$ $=\dfrac{1}{p+q}\begin{pmatrix} q & q \\ p& p\end{pmatrix}$
となる．最初の文字が $1$ のとき， $\begin{pmatrix} p_{n}(0) \\ p_{n}(1) \end{pmatrix}=\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ であるから極限において $1$ である確率は $\dfrac{p}{p+q}$ ，最初の文字が $0$ のとき， $\begin{pmatrix} p_{n}(0) \\ p_{n}(1) \end{pmatrix}=\begin{pmatrix} 1 \\ 0\end{pmatrix}$ であるから極限において $0$ である確率は $\dfrac{q}{p+q}$ となるので，
$\displaystyle\lim_{n\to\infty}C(n)=\dfrac{p^3q^2}{(p+q)^5}$
となる．

[解答]
各桁独立に考えれば良い．

ある桁の文字が $k$ 回目に書き写したときに $0$ ， $1$ である確率を $p_k(0)$ ， $p_k(1)$ とすると
$p_{k+1}(0)=(1-p)p_k(0)+qp_k(1)$ $=(1-p)p_k(0)+q(1-p_k(0))$ $=(1-p-q)p_k(0)+q$
であるから，
$p_{k+1}(0)-\dfrac{q}{p+q}=(1-p+q)\left(p_{k}(0)-\dfrac{q}{p+q}\right)$
が成立し，よって
$p_{n}(0)=(1-p-q)^n\left(p_{0}(0)-\dfrac{q}{p+q}\right)+\dfrac{q}{p+q}$
が成立する．同様に
$p_{n}(1)=(1-p-q)^n\left(p_{0}(1)-\dfrac{p}{p+q}\right)+\dfrac{p}{p+q}$
も成立する（引数の0と1，pとqを交換すれば良い）．
よって最初の文字が $1$ のとき，第 $n$ 回目の写しで $1$ である確率は
$(1-p-q)^n\left(1-\dfrac{p}{p+q}\right)+\dfrac{p}{p+q}$ $(1-p-q)^n\dfrac{q}{p+q}+\dfrac{p}{p+q}$ ，
最初の文字が $0$ のとき，第 $n$ 回目の写しで $0$ である確率は
$(1-p-q)^n\dfrac{p}{p+q}+\dfrac{q}{p+q}$
となり，
$C(n)=\left\{(1-p-q)^n\dfrac{q}{p+q}+\dfrac{p}{p+q}\right\}^3\left\{(1-p-q)^n\dfrac{p}{p+q}+\dfrac{q}{p+q}\right\}^2$
となる． $-1\lt 1-p-q\lt 1$ から
$\displaystyle\lim_{n\to\infty}C(n)=\dfrac{p^3q^2}{(p+q)^5}$
となる．