2025 大阪大学（理系）前期 第 5 問 - 確率漸化式

投げたときに表と裏の出る確率がそれぞれ $\frac{1}{2}$ のコインがある。A, B, C の 3 文字を BAC のように 1 個ずつすべて並べて得られる文字列に対して、コインを投げて次の操作を行う。

・表が出たら文字列の左から 1 文字目と 2 文字目を入れかえる。
・裏が出たら文字列の左から 2 文字目と 3 文字目を入れかえる。

例えば、文字列が BAC であるときに、2 回続けてコインを投げて表、裏の順に出たとすると、文字列は BAC から ABC を経て ACB となる。

最初の文字列は ABC であるとする。コインを $n$ 回続けて投げたあとの文字列が ABC である確率を $p_n$ とし、BCA である確率を $q_n$ とする。

(1) $k$ を正の整数とするとき、$p_{2k}-q_{2k}$ を求めよ。

(2) $n$ を正の整数とするとき、$p_n$ を求めよ。

状態の分類

A, B, C の並べ方は全部で 6 通りある。これらを「偶置換」と「奇置換」に分類しよう。

表の操作も裏の操作も「隣り合う 2 文字の交換」である。交換を 1 回行うと、偶置換は奇置換に、奇置換は偶置換に変わる。

したがって、ABC（偶置換）から出発すると次のことが言える。

この時点で、$n$ が奇数のとき $p_n=0$ であることがわかった。

解法1：漸化式による方法（高校レベル）

$n$ が偶数のとき、状態は ABC, BCA, CAB のいずれかになる。CAB である確率を $r_n$ とおくと、対称性から $q_n=r_n$ が成り立つ。3 つの確率の和は 1 なので

$$p_n+2q_n=1\cdots \text{①}$$

が成り立つ。

次に、2 回の操作で ABC からどの状態に遷移するかを調べる。

ABC から 2 回後に ABC になる確率は $\frac{1}{2}$、BCA になる確率は $\frac{1}{4}$、CAB になる確率は $\frac{1}{4}$ である。

同様に BCA からの遷移を調べると、ABC への確率は $\frac{1}{4}$、BCA への確率は $\frac{1}{2}$、CAB への確率は $\frac{1}{4}$ となる。

これより漸化式が立つ。

$$p_{n+2}=\frac{1}{2}{p}_n+\frac{1}{4}{q}_n+\frac{1}{4}{r}_n=\frac{1}{2}{p}_n+\frac{1}{2}{q}_n$$

$$q_{n+2}=\frac{1}{4}{p}_n+\frac{1}{2}{q}_n+\frac{1}{4}{r}_n=\frac{1}{4}{p}_n+\frac{3}{4}{q}_n$$

辺々を引くと

$$p_{n+2}-q_{n+2}=\frac{1}{4}(p_n-q_n)$$

となる。初期値は $p_0-q_0=1-0=1$ なので

$$p_{2k}-q_{2k}={\left(\frac{1}{4}\right)}^k$$

を得る。これが (1) の答えである。

(2) については、① より $q_n=\frac{1-p_n}{2}$ を漸化式に代入すると

$$p_{n+2}=\frac{1}{2}{p}_n+\frac{1}{2}\cdot \frac{1-p_n}{2}=\frac{1}{4}{p}_n+\frac{1}{4}$$

となる。これを変形すると

$$p_{n+2}-\frac{1}{3}=\frac{1}{4}\left(p_n-\frac{1}{3}\right)$$

である。初期値 $p_0-\frac{1}{3}=\frac{2}{3}$ より

$$p_{2m}-\frac{1}{3}=\frac{2}{3}\cdot {\left(\frac{1}{4}\right)}^m$$

$n=2m$ とおくと $4^m=2^n$ なので

$$p_n=\frac{1}{3}+\frac{2}{3\cdot 2^n}=\frac{2^n+2}{3\cdot 2^n}$$

となる。

解法2：行列による方法（大学レベル）

2 回ごとの遷移を行列で表すと

$$\left(\begin{array}{c}{p}_{n+2}\\ q_{n+2}\\ r_{n+2}\end{array}\right)=\left(\begin{array}{ccc}1/2& 1/4& 1/4\\ 1/4& 1/2& 1/4\\ 1/4& 1/4& 1/2\end{array}\right)\left(\begin{array}{c}{p}_n\\ q_n\\ r_n\end{array}\right)$$

となる。この行列を $M$ とおく。$M$ の固有値を求めよう。

$M$ は $\frac{1}{4}I+\frac{1}{4}J$ と書ける。ここで $J$ は全成分が 1 の行列である。$J$ の固有値は 3（固有ベクトル $(1,1,1{)}^T$）と 0（重複度 2）なので、$M$ の固有値は

$$\frac{1}{4}+\frac{1}{4}\cdot 3=1,\frac{1}{4}+\frac{1}{4}\cdot 0=\frac{1}{4}\text{（重複度 2）}$$

である。

ベクトル $(1,-1,0{)}^T$ は固有値 $\frac{1}{4}$ の固有ベクトルである。実際

$$M\left(\begin{array}{c}1\\ -1\\ 0\end{array}\right)=\left(\begin{array}{c}1/4\\ -1/4\\ 0\end{array}\right)=\frac{1}{4}\left(\begin{array}{c}1\\ -1\\ 0\end{array}\right)$$

となる。

初期状態は $(p_0,q_0,r_0)=(1,0,0)$ である。$(1,-1,0{)}^T$ との内積をとると $p_0-q_0=1$ である。$M$ を $k$ 回作用させると固有値が $k$ 乗されるので

$$p_{2k}-q_{2k}=1\cdot {\left(\frac{1}{4}\right)}^k=\frac{1}{4^k}$$

を得る。これが (1) の答えである。

$p_n$ の極限については、固有値 1 の固有ベクトル $(1,1,1{)}^T$ の方向に収束する。確率の和が 1 という条件から、$n\to \infty$ で $(p_n,q_n,r_n)\to \left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$ となる。

一般項は固有空間分解を用いて

$$p_{2m}=\frac{1}{3}+\frac{2}{3}\cdot {\left(\frac{1}{4}\right)}^m=\frac{2^n+2}{3\cdot 2^n}$$

と求まる。ここで $n=2m$ である。

答え

(1) $p_{2k}-q_{2k}=\frac{1}{4^k}$

(2) $n$ が奇数のとき $p_n=0$、$n$ が偶数のとき $p_n=\frac{2^n+2}{3\cdot 2^n}$

検算

$n\to \infty$ で $p_n\to \frac{1}{3}$ に収束する。これは 6 状態が均等になることを意味しており、直感とも合う。