解説

方針・初手

各回で $f_0$ または $f_1$ を選ぶことは、$0$ または $1$ のどちらかを確率 $\dfrac{1}{2}$ で選ぶこととみなせる。したがって、$x_n$ を選ばれた $0,1$ の列で表し、$x_n<\dfrac{2}{3}$ となる列の個数を数える。

解法1

$n$ 回目に $f_0$ が選ばれたとき $\varepsilon_n=0$、$f_1$ が選ばれたとき $\varepsilon_n=1$ とおく。このとき

$$ x_n=\frac{x_{n-1}+\varepsilon_n}{2}

$$

である。

これを繰り返すと、$x_0=\dfrac{1}{2}$ より

$$ x_n=\frac{x_0}{2^n}+\sum_{k=1}^{n}\frac{\varepsilon_k}{2^{n-k+1}}

$$

となる。両辺に $2^n$ をかけると

$$ 2^n x_n=\frac{1}{2}+\sum_{k=1}^{n}\varepsilon_k2^{k-1}

$$

である。

ここで

$$ m=\sum_{k=1}^{n}\varepsilon_k2^{k-1}

$$

とおく。$\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n$ の選び方は全部で $2^n$ 通りあり、$m$ は $0,1,2,\ldots,2^n-1$ をそれぞれちょうど1回ずつとる。

求める条件は

$$ x_n<\frac{2}{3}

$$

であるから、

$$ \frac{m+\frac{1}{2}}{2^n}<\frac{2}{3}

$$

すなわち

$$ m+\frac{1}{2}<\frac{2^{n+1}}{3}

$$

である。よって

$$ m<\frac{2^{n+1}}{3}-\frac{1}{2} =\frac{2^{n+2}-3}{6}

$$

を満たす整数 $m$ の個数を数えればよい。

$n\geqq 1$ において、$2^{n+2}$ を $6$ で割った余りは $2$ または $4$ である。したがって場合分けする。

**(i)**

$n$ が奇数のとき

このとき $n+2$ も奇数なので

$$ 2^{n+2}\equiv 2 \pmod{6}

$$

である。よって

$$ \frac{2^{n+2}-3}{6}

$$

は整数より $\dfrac{1}{6}$ だけ小さい数である。したがって条件を満たす $m$ の個数は

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

$$

である。

したがって

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

$$

となる。

**(ii)**

$n$ が偶数のとき

このとき $n+2$ も偶数なので

$$ 2^{n+2}\equiv 4 \pmod{6}

$$

である。よって

$$ \frac{2^{n+2}-3}{6}

$$

は整数より $\dfrac{1}{6}$ だけ大きい数である。したがって条件を満たす $m$ の個数は

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

$$

である。

したがって

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

$$

となる。

以上より、まとめて

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

$$

である。

解説

この問題の本質は、$f_0(x)=\dfrac{x}{2}$ と $f_1(x)=\dfrac{x+1}{2}$ が、$0$ または $1$ の情報を2進法的に付け加える操作になっている点である。

各回の選択列をそのまま追いかけると複雑に見えるが、

$$ m=\sum_{k=1}^{n}\varepsilon_k2^{k-1}

$$

とおけば、$m$ は $0$ から $2^n-1$ までの整数を一様に動く。したがって、確率の問題は整数の個数を数える問題に帰着する。

また、$x_n<\dfrac{2}{3}$ は厳密な不等号であるため、境界の扱いが重要である。ただしこの問題では、境界条件は

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

$$

となり、左辺は半整数、右辺は $3$ を分母にもつ数であるため、実際に等号が成立することはない。したがって、個数計算では $2^{n+2}$ の $6$ で割った余りに注意すればよい。

答え

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

$$

すなわち、

$$ \boxed{ \begin{cases} \displaystyle P_n=\frac{2}{3}-\frac{1}{3\cdot 2^n} & (n\text{ が奇数})\\[6pt] \displaystyle P_n=\frac{2}{3}+\frac{1}{3\cdot 2^n} & (n\text{ が偶数}) \end{cases} }

$$