京都大学 2015年度
理系数学 第6問

解答

まず、$x_n$ の取り得る値を調べる。$n=0$ では $x_0=\frac{1}{2}=\frac{0+\frac{1}{2}}{2^0}$ である。$n$ 回後に $x_n=\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$ の形の値をそれぞれ等確率で取るとする。このとき $f_0(x_n)=\frac{x_n}{2}=\frac{j+\frac{1}{2}}{2^{n+1}}$ であり、$f_1(x_n)=\frac{x_n+1}{2}=\frac{j+2^n+\frac{1}{2}}{2^{n+1}}$ である。したがって $n+1$ 回後には $\frac{k+\frac{1}{2}}{2^{n+1}}(k=0,1,\dots ,2^{n+1}-1)$ の $2^{n+1}$ 個の値を等確率で取る。よって帰納法により、$n$ 回後の値は $\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$ の $2^n$ 個であり、すべて等確率である。

したがって $x_n<2/3$ となる確率は、$\frac{j+\frac{1}{2}}{2^n}<\frac{2}{3}$ を満たす整数 $j$ の個数を $2^n$ で割ればよい。この不等式は $j+\frac{1}{2}<\frac{2^{n+1}}{3}$ である。

$n$ が奇数のとき、$n+1$ は偶数なので $2^{n+1}\equiv 1(\mathrm{mod}3)$ である。よって $\frac{2^{n+1}}{3}=\frac{2^{n+1}-1}{3}+\frac{1}{3}$ であり、条件は $j<\frac{2^{n+1}-1}{3}-\frac{1}{6}$ となる。したがって条件を満たす $j$ の個数は $\frac{2^{n+1}-1}{3}$ である。

$n$ が偶数のとき、$n+1$ は奇数なので $2^{n+1}\equiv 2(\mathrm{mod}3)$ である。よって $\frac{2^{n+1}}{3}=\frac{2^{n+1}-2}{3}+\frac{2}{3}$ であり、条件は $j<\frac{2^{n+1}-2}{3}+\frac{1}{6}$ となる。したがって条件を満たす $j$ の個数は $\frac{2^{n+1}+1}{3}$ である。

以上より

である。これをまとめると $\boxed{P_n=\frac{2}{3}+\frac{(-1{)}^n}{3\cdot 2^n}}$ である。

別解。個数の漸化式から求める方法もある。$n$ 回後の $2^n$ 個の値のうち、$2/3$ 未満であるものの個数を $A_n$、$1/3$ 未満であるものの個数を $B_n$ とする。

$n+1$ 回後を作るとき、$f_0(x)=x/2$ を選んだ場合は、もとの $x$ がどの値でも $\frac{x}{2}<\frac{1}{2}<\frac{2}{3}$ となる。したがってこの分だけで $2^n$ 個ある。一方、$f_1(x)=(x+1)/2$ を選んだ場合は $\frac{x+1}{2}<\frac{2}{3}$ すなわち $x<\frac{1}{3}$ であることが必要十分である。よって $A_{n+1}=2^n+B_n$ である。

ここで $n$ 回後の値 $\frac{j+\frac{1}{2}}{2^n}(j=0,1,\dots ,2^n-1)$ は、$x$ が現れれば $1-x$ も現れるという左右対称な並びである。また $1/3,2/3$ と一致する値はない。したがって $1/3$ 未満の個数は $2/3$ より大きい個数に等しく、$B_n=2^n-A_n$ である。ゆえに $A_{n+1}=2^n+(2^n-A_n)=2^{n+1}-A_n$ を得る。

$P_n=A_n/2^n$ とおくと $P_{n+1}=1-\frac{P_n}{2}$ である。初期値は $P_0=1$ であり、$P_{n+1}-\frac{2}{3}=-\frac{1}{2}\left(P_n-\frac{2}{3}\right)$ だから

である。したがって $\boxed{P_n=\frac{2}{3}+\frac{(-1{)}^n}{3\cdot 2^n}}$ となる。