解説

方針・初手

各回で $f_0$ を選ぶか $f_1$ を選ぶかを $0,1$ の列で表すと、$x_n$ はその列からできる二進数に対応する形で表せる。

したがって、$2^n$ 通りの選択列のうち、$x_n<\dfrac{2}{3}$ を満たすものを数えればよい。

解法1

第 $k$ 回目に $f_0$ を選んだとき $a_k=0$、$f_1$ を選んだとき $a_k=1$ とおく。各 $a_k$ は $0,1$ のどちらかであり、長さ $n$ の列は全部で $2^n$ 通り、すべて等確率である。

漸化式は

$$ x_k=\frac{x_{k-1}+a_k}{2}

$$

と書ける。これを繰り返し代入すると、

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

$$

である。$x_0=\dfrac{1}{2}$ より、

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

$$

となる。

ここで

$$ m=a_1+2a_2+\cdots+2^{n-1}a_n

$$

とおくと、$a_1,\dots,a_n$ がすべての $0,1$ の列を動くとき、$m$ は $0,1,\dots,2^n-1$ をちょうど一度ずつ動く。したがって

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

$$

と表せる。

求める条件は

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

$$

である。これを整理すると、

$$ 3(2m+1)<2^{n+2}

$$

すなわち

$$ 6m+3<2^{n+2}

$$

である。左辺と右辺は整数なので、

$$ 6m+3\leq 2^{n+2}-1

$$

と同値である。よって

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

$$

となる。

したがって条件を満たす $m$ の個数を $N_n$ とすると、

$$ N_n=\left\lfloor \frac{2^{n+1}-2}{3}\right\rfloor+1 =\left\lfloor \frac{2^{n+1}+1}{3}\right\rfloor

$$

である。

ここで、$2\equiv -1\pmod 3$ より、

$$ 2^{n+1}\equiv (-1)^{n+1}\pmod 3

$$

である。

**(i)**

$n$ が偶数のとき、$n+1$ は奇数なので

$$ 2^{n+1}\equiv 2\pmod 3

$$

である。したがって

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

$$

となる。

よって

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

$$

である。

**(ii)**

$n$ が奇数のとき、$n+1$ は偶数なので

$$ 2^{n+1}\equiv 1\pmod 3

$$

である。したがって

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

$$

となる。

よって

$$ P_n=\frac{N_n}{2^n} =\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}

$$

である。

解法2

区間への入り方から漸化式を作る。

$$ P_n=\Pr\left(x_n<\frac{2}{3}\right),\qquad Q_n=\Pr\left(x_n<\frac{1}{3}\right)

$$

とおく。$x_0=\dfrac{1}{2}$ であり、$f_0,f_1$ は $[0,1]$ を $[0,1]$ に写すので、すべての $n$ について $0\leq x_n\leq 1$ である。

まず、$x_n<\dfrac{2}{3}$ となる条件を考える。$f_0$ が選ばれた場合は

$$ x_n=\frac{x_{n-1}}{2}\leq \frac{1}{2}<\frac{2}{3}

$$

なので常に条件を満たす。

一方、$f_1$ が選ばれた場合は

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

$$

より

$$ x_{n-1}<\frac{1}{3}

$$

が必要十分である。したがって

$$ P_n=\frac{1}{2}+\frac{1}{2}Q_{n-1}

$$

である。

次に、$x_n<\dfrac{1}{3}$ となる条件を考える。$f_0$ が選ばれた場合は

$$ \frac{x_{n-1}}{2}<\frac{1}{3}

$$

より

$$ x_{n-1}<\frac{2}{3}

$$

である。$f_1$ が選ばれた場合は

$$ \frac{x_{n-1}+1}{2}<\frac{1}{3}

$$

より

$$ x_{n-1}<-\frac{1}{3}

$$

となるが、これは $x_{n-1}\geq 0$ に反するので起こらない。

よって

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

$$

である。これを用いると、$n\geq 2$ について

$$ P_n=\frac{1}{2}+\frac{1}{2}Q_{n-1} =\frac{1}{2}+\frac{1}{4}P_{n-2}

$$

となる。

初期値は

$$ P_0=1,\qquad P_1=\frac{1}{2}

$$

である。

この漸化式を

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

$$

と書き直す。

$n=2k$ のとき、

$$ P_{2k}-\frac{2}{3} =\left(\frac{1}{4}\right)^k\left(P_0-\frac{2}{3}\right) =\left(\frac{1}{4}\right)^k\cdot \frac{1}{3} =\frac{1}{3\cdot 2^{2k}}

$$

である。したがって

$$ P_{2k}=\frac{2}{3}+\frac{1}{3\cdot 2^{2k}}

$$

となる。

$n=2k+1$ のとき、

$$ P_{2k+1}-\frac{2}{3} =\left(\frac{1}{4}\right)^k\left(P_1-\frac{2}{3}\right) =\left(\frac{1}{4}\right)^k\left(-\frac{1}{6}\right) =-\frac{1}{3\cdot 2^{2k+1}}

$$

である。したがって

$$ P_{2k+1}=\frac{2}{3}-\frac{1}{3\cdot 2^{2k+1}}

$$

となる。

よって、解法1と同じく

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

$$

である。

解説

この問題では、確率過程そのものを追うよりも、$f_0$ と $f_1$ の選択列を $0,1$ の列として扱うのが自然である。$n$ 回の操作後の値 $x_n$ は、選択列からできる二進数に $x_0=\dfrac{1}{2}$ の寄与が加わった形になる。

解法1は、$x_n$ を明示的に表して個数を数える方法である。最も直接的で、境界 $2/3$ との大小を整数の不等式に帰着できる。

解法2は、区間 $[0,1/3)$ と $[0,2/3)$ の間の遷移に注目する方法である。こちらは漸化式が短く、なぜ答えが $2/3$ に近づくかも見えやすい。

答え

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

$$

すなわち

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

$$