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

方針・初手

• $x_n < \dfrac{2}{3}$ となる確率を求めるために、状態の推移に注目して漸化式を立てる。
• $x_n = f_0(x_{n-1})$ の場合と $x_n = f_1(x_{n-1})$ の場合で $x_{n-1}$ が満たすべき条件を逆算すると、新たに「$x_{n-1} < \dfrac{1}{3}$」という条件が出現する。
• したがって、$P_n = P\!\left(x_n < \dfrac{2}{3}\right)$ と $Q_n = P\!\left(x_n < \dfrac{1}{3}\right)$ の連立漸化式を立てて解く方針が有効である。

解法1（連立漸化式）

まず、$x_0 = \dfrac{1}{2} \in [0, 1]$ であり、$0 \leq x \leq 1$ のとき $0 \leq f_0(x) \leq \dfrac{1}{2}$、$\dfrac{1}{2} \leq f_1(x) \leq 1$ となるため、数学的帰納法によりすべての $n$ に対して $0 \leq x_n \leq 1$ が成り立つ。

$P_n = P\!\left(x_n < \dfrac{2}{3}\right)$、$Q_n = P\!\left(x_n < \dfrac{1}{3}\right)$ とおく。

各ステップにおいて確率 $\dfrac{1}{2}$ で $f_0,\, f_1$ のいずれかが選ばれるため、

$$ P_n = \frac{1}{2} P\!\left(f_0(x_{n-1}) < \frac{2}{3}\right) + \frac{1}{2} P\!\left(f_1(x_{n-1}) < \frac{2}{3}\right) $$

それぞれの条件は、

$$ f_0(x_{n-1}) < \frac{2}{3} \iff \frac{x_{n-1}}{2} < \frac{2}{3} \iff x_{n-1} < \frac{4}{3} $$

$$ f_1(x_{n-1}) < \frac{2}{3} \iff \frac{x_{n-1}+1}{2} < \frac{2}{3} \iff x_{n-1} < \frac{1}{3} $$

常に $0 \leq x_{n-1} \leq 1$ であるから、$x_{n-1} < \dfrac{4}{3}$ となる確率は $1$ である。よって $n \geq 1$ のとき、

$$ P_n = \frac{1}{2} \cdot 1 + \frac{1}{2} Q_{n-1} = \frac{1}{2} + \frac{1}{2} Q_{n-1} \quad \cdots \textcircled{1} $$

同様に、

$$ Q_n = \frac{1}{2} P\!\left(f_0(x_{n-1}) < \frac{1}{3}\right) + \frac{1}{2} P\!\left(f_1(x_{n-1}) < \frac{1}{3}\right) $$

$$ f_0(x_{n-1}) < \frac{1}{3} \iff x_{n-1} < \frac{2}{3}, \qquad f_1(x_{n-1}) < \frac{1}{3} \iff x_{n-1} < -\frac{1}{3} $$

常に $x_{n-1} \geq 0$ であるから、$x_{n-1} < -\dfrac{1}{3}$ となる確率は $0$ である。よって $n \geq 1$ のとき、

$$ Q_n = \frac{1}{2} P_{n-1} \quad \cdots \textcircled{2} $$

初期値は $x_0 = \dfrac{1}{2}$ より $P_0 = 1$、$Q_0 = 0$。

$\textcircled{1} + \textcircled{2}$：$P_n + Q_n = \dfrac{1}{2}(P_{n-1} + Q_{n-1}) + \dfrac{1}{2}$ より、

$$ P_n + Q_n - 1 = \frac{1}{2}(P_{n-1} + Q_{n-1} - 1) $$

初項 $P_0 + Q_0 - 1 = 0$ であるから、すべての $n \geq 0$ に対して

$$ P_n + Q_n = 1 \quad \cdots \textcircled{3} $$

$\textcircled{1} - \textcircled{2}$：$P_n - Q_n = -\dfrac{1}{2}(P_{n-1} - Q_{n-1}) + \dfrac{1}{2}$ より、

$$ P_n - Q_n - \frac{1}{3} = -\frac{1}{2}\!\left(P_{n-1} - Q_{n-1} - \frac{1}{3}\right) $$

初項 $P_0 - Q_0 - \dfrac{1}{3} = \dfrac{2}{3}$ であるから、

$$ P_n - Q_n = \frac{1}{3} + \frac{2}{3}\!\left(-\frac{1}{2}\right)^{\!n} \quad \cdots \textcircled{4} $$

$\textcircled{3}, \textcircled{4}$ を足して $2$ で割ると、

$$ P_n = \frac{2}{3} + \frac{1}{3}\!\left(-\frac{1}{2}\right)^{\!n} $$

解法2（二進展開による直接計算）

確率変数 $a_k \in \{0, 1\}$ を独立に等確率 $\dfrac{1}{2}$ でとるものとし、$x_k = \dfrac{x_{k-1} + a_k}{2}$ と表す。$x_0 = \dfrac{1}{2}$ より繰り返し代入すると、

$$ x_n = \frac{a_n}{2} + \frac{a_{n-1}}{2^2} + \cdots + \frac{a_1}{2^n} + \frac{1}{2^{n+1}} = \frac{2X + 1}{2^{n+1}} $$

ただし $X = \displaystyle\sum_{k=1}^n a_k \cdot 2^{k-1}$（$0 \leq X \leq 2^n - 1$）は $0$ から $2^n - 1$ の各整数を等確率 $\dfrac{1}{2^n}$ でとる。

$x_n < \dfrac{2}{3}$ となる条件を整数 $X$ で表す。

$$ \frac{2X+1}{2^{n+1}} < \frac{2}{3} \iff 6X + 3 < 2^{n+2} \iff 3X < 2^{n+1} - \frac{3}{2} $$

$X$ は整数であるから、これは $3X \leq 2^{n+1} - 2$、すなわち $X \leq \left\lfloor\dfrac{2^{n+1}-2}{3}\right\rfloor$ と同値である。

（i）$n = 2m$（偶数）のとき

$2^{n+1} - 2 = 2(4^m - 1)$。$4 \equiv 1 \pmod{3}$ より $4^m - 1 \equiv 0 \pmod{3}$ なので、$2^{n+1} - 2$ は $3$ の倍数。

条件を満たす最大の $X$ は $\dfrac{2^{n+1}-2}{3}$ であり、個数は

$$ K = \frac{2^{n+1}-2}{3} + 1 = \frac{2^{n+1}+1}{3} $$

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

（ii）$n = 2m - 1$（奇数）のとき

$2^{n+1} - 2 = 4^m - 2$。$4^m \equiv 1 \pmod{3}$ より $4^m - 2 \equiv 2 \pmod{3}$。

条件を満たす最大の $X$ は $\dfrac{2^{n+1}-4}{3}$ であり、個数は

$$ K = \frac{2^{n+1}-4}{3} + 1 = \frac{2^{n+1}-1}{3} $$

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

（i）, （ii）をまとめると、$P_n = \dfrac{2}{3} + \dfrac{1}{3}\!\left(-\dfrac{1}{2}\right)^{\!n}$。

解説

マルコフ連鎖のように推移していく確率モデルの問題である。「$\dfrac{2}{3}$ 未満」という条件を 1 ステップ遡ると「$\dfrac{1}{3}$ 未満」という新たな条件が派生するため、2 つの確率を変数に置く連立漸化式に帰着させるのが最も自然な解法（解法1）となる。

解法2は $n$ 回操作した後の値が「$[0, 1]$ 区間を $2^n$ 等分した各区間の中点」に等確率で配置されるという構造に着目し、二進展開の和として $x_n$ を直接表現する方針である。剰余による場合分けが必要になるが、最終的に 1 本の式に統一できる。

答え

$$ P_n = \frac{2}{3} + \frac{1}{3}\!\left(-\frac{1}{2}\right)^{\!n} $$