トップ› 京都大学› 1987年› 理系第6問

京都大学 1987年理系第6問解説

方針・初手

札は全部で赤3枚、白3枚であり、各人は常に2枚ずつ札を持つ。したがって、各人が持っている札の組み合わせは「赤札の枚数」だけで完全に決まります。 (1) では、A, B, C が持つ赤札の枚数を $(a, b, c)$ とおき、あり得る組み合わせをすべて列挙して状態を定義する。 (2) では、定義した各状態について、誰がどの札を渡し、結果として誰の赤札が増減するかを丁寧に追跡し、遷移確率を求める。 (3) は(2)の結果を利用して漸化式を立てる。一見すると状態数が多くて複雑であるが、$F_0$ 以外の状態から $F_0$ へ戻る確率がすべて等しいという対称性に気づけば、2つの変数の漸化式（実質的には1変数の漸化式）に帰着できる。

解法1

(1)

A, B, C の3人が持つ赤札の枚数をそれぞれ $a, b, c$ とし、状態を $(a, b, c)$ で表す。赤札は全部で3枚であり、各人は常に2枚の札を持つため、$a+b+c=3$ かつ $0 \leqq a, b, c \leqq 2$ である。条件を満たす整数の組 $(a, b, c)$ をすべて書き上げると、以下の7通りになる。これらを $F_0, F_1, \dots, F_6$ とおく。

$F_0 : (1, 1, 1)$ （最初の状態）
$F_1 : (2, 1, 0)$
$F_2 : (0, 2, 1)$
$F_3 : (1, 0, 2)$
$F_4 : (2, 0, 1)$
$F_5 : (1, 2, 0)$
$F_6 : (0, 1, 2)$

(2)

$F_i$ から1回の移動で $F_j$ になる確率 $p_{ij}$ を求める。

・$F_0 (1, 1, 1)$ からの遷移

A, B, C はそれぞれ確率 $\frac{1}{2}$ で赤または白を無作為に渡す（渡し方は全 $2^3 = 8$ 通りで等確率）。全員が赤を渡す、または全員が白を渡すとき、各人の赤札の枚数は増減せず $F_0$ となる（$2$ 通り）。 1人が赤、2人が白を渡すとき（$3$ 通り）、赤を渡した人の赤札が1枚減り、その受け手の赤札が1枚増える。例えば、Aが赤、BとCが白を渡すとき、Aの赤は $-1+0=-1$、Bの赤は $0+1=+1$、Cの赤は $0+0=0$ の増減となり、変化後の赤札は $(0, 2, 1) = F_2$ となる。同様に調べると、1人が赤を渡す場合は $F_2, F_3, F_1$ へ遷移する。 2人が赤、1人が白を渡すとき（$3$ 通り）、同様の計算により $F_5, F_6, F_4$ へ遷移する。したがって、$F_0$ から各状態への遷移確率は以下の通り。

$$ p_{00} = \frac{2}{8} = \frac{1}{4} $$

$$ p_{01} = p_{02} = p_{03} = p_{04} = p_{05} = p_{06} = \frac{1}{8} $$

・$F_1 (2, 1, 0)$ からの遷移

Aは赤2枚、Cは白2枚であるため、Aは必ず赤を、Cは必ず白を渡す。Bは赤白1枚ずつなので、確率 $\frac{1}{2}$ で赤または白を渡す。 Bが赤を渡すとき、 Aは白を受け取り赤赤 $\to$ 赤白 Bは赤を渡し、赤を受け取り赤白 $\to$ 赤白 Cは白を渡し、赤を受け取り白白 $\to$ 赤白よって、全員が赤白となり $F_0$ に遷移する。 Bが白を渡すとき、 Aは白を受け取り赤赤 $\to$ 赤白 Bは白を渡し、赤を受け取り赤白 $\to$ 赤赤 Cは白を渡し、白を受け取り白白 $\to$ 白白よって、赤札は $(1, 2, 0)$ となり $F_5$ に遷移する。したがって、

$$ p_{10} = \frac{1}{2}, \quad p_{15} = \frac{1}{2} $$

であり、その他の $p_{1j}$ は $0$ である。

・他の状態からの遷移

対称性により、$F_2, F_3$ も $F_1$ と同様の遷移を行う。すなわち、確率 $\frac{1}{2}$ で $F_0$ に戻り、確率 $\frac{1}{2}$ で「赤札2枚」が時計回りに移動した状態に遷移する。 $F_2 (0, 2, 1) \to F_0 \left(\frac{1}{2}\right), \quad F_6 (0, 1, 2) \left(\frac{1}{2}\right)$ $F_3 (1, 0, 2) \to F_0 \left(\frac{1}{2}\right), \quad F_4 (2, 0, 1) \left(\frac{1}{2}\right)$ 一方、$F_4, F_5, F_6$ は、赤札2枚の人の「左隣」が赤札1枚である状態であり、これも確率 $\frac{1}{2}$ で $F_0$ に戻り、確率 $\frac{1}{2}$ で「赤札2枚」が反時計回りに移動した状態に遷移する。 $F_4 (2, 0, 1) \to F_0 \left(\frac{1}{2}\right), \quad F_1 (2, 1, 0) \left(\frac{1}{2}\right)$ $F_5 (1, 2, 0) \to F_0 \left(\frac{1}{2}\right), \quad F_2 (0, 2, 1) \left(\frac{1}{2}\right)$ $F_6 (0, 1, 2) \to F_0 \left(\frac{1}{2}\right), \quad F_3 (1, 0, 2) \left(\frac{1}{2}\right)$

以上を表にまとめると、以下のようになる（表の $(i, j)$ 成分が $p_{ij}$ を表す。空白は $0$）。

$i \setminus j$	$F_0$	$F_1$	$F_2$	$F_3$	$F_4$	$F_5$	$F_6$
$F_0$	$1/4$	$1/8$	$1/8$	$1/8$	$1/8$	$1/8$	$1/8$
$F_1$	$1/2$					$1/2$
$F_2$	$1/2$						$1/2$
$F_3$	$1/2$				$1/2$
$F_4$	$1/2$	$1/2$
$F_5$	$1/2$		$1/2$
$F_6$	$1/2$			$1/2$

(3)

$n$ 回移動した後に状態が $F_k$ である確率を $P_n(F_k)$ とおく。求める確率は $q_n = P_n(F_0)$ である。 (2)で求めた遷移確率より、$n \geqq 0$ に対して

$$ q_{n+1} = \frac{1}{4} q_n + \sum_{k=1}^6 \frac{1}{2} P_n(F_k) $$

が成り立つ。ここで、すべての状態の確率の和は $1$ であるから、

$$ \sum_{k=1}^6 P_n(F_k) = 1 - P_n(F_0) = 1 - q_n $$

である。これを代入すると、

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

$$ q_{n+1} = -\frac{1}{4} q_n + \frac{1}{2} $$

となる。この漸化式の特性方程式 $\alpha = -\frac{1}{4}\alpha + \frac{1}{2}$ を解くと $\alpha = \frac{2}{5}$ であるから、式は次のように変形できる。

$$ q_{n+1} - \frac{2}{5} = -\frac{1}{4} \left( q_n - \frac{2}{5} \right) $$

数列 $\left\{ q_n - \frac{2}{5} \right\}$ は、初項 $q_0 - \frac{2}{5} = 1 - \frac{2}{5} = \frac{3}{5}$、公比 $-\frac{1}{4}$ の等比数列である。したがって、

$$ q_n - \frac{2}{5} = \frac{3}{5} \left( -\frac{1}{4} \right)^n $$

$$ q_n = \frac{2}{5} + \frac{3}{5} \left( -\frac{1}{4} \right)^n $$

解説

確率遷移（マルコフ連鎖）の典型的な問題である。状態をどのように定義するかが一番のポイントになる。(1)で「全部書き上げ」という指示があるため、A, B, Cを区別して7つの状態を列挙する。一見すると $7 \times 7$ の複雑な推移になりそうであるが、(2)で丁寧に遷移を調べると、「$F_0$ 以外のどの状態からも、必ず確率 $\frac{1}{2}$ で $F_0$ に戻る」という非常に美しい対称性があることに気づく。 (3)ではこの性質を活かし、$P_n(F_1) \sim P_n(F_6)$ を個別に求めるのではなく、それらの和が $1 - q_n$ になることを利用して、一気に $q_n$ のみの2項間漸化式を作り出す。