https://spherical-harmonics.hateblo.jp/entry/Kyodai/2015/Rikei

2025.05.10記

[6] 2つの関数を

$f_0(x)=\dfrac{x}{2}$ ， $f_1(x)=\dfrac{x+1}{2}$

とおく． $x_0=\dfrac{1}{2}$ から始め，各 $n=1$ ， $2$ ， $\cdots$ について，それぞれ確率 $\dfrac{1}{2}$ で $x_n=f_0(x_{n-1})$ または $x_n=f_1(x_{n-1})$ と定める．このとき， $x_n\lt \dfrac{2}{3}$ となる確率 $P_n$ を求めよ．

本問のテーマ

ベルヌーイ写像
2進数

2025.06.14記
ベルヌーイ写像
 パイこね変換 - 球面倶楽部零八式 mark II
を $y=B(x)$ とおくと， $2:1$ の写像となっているので逆写像を考えると2つの枝のいずれに戻るかわからない．それぞれの枝に戻る確率が $\dfrac{1}{2}$ である．という問題である．

ベルヌーイ写像が $0$ から $1$ までの二進小数から小数第一位を取り除く操作であるから，その逆写像として $0$ から $1$ までの二進小数の小数点の次に $0$ または $1$ を確率 $\dfrac{1}{2}$ で挿入するのが本問の $x_{n-1}\mapsto x_n$ の操作である．このとき $x_n$ は小数点以下が $n+1$ 桁(で末尾が1の)二進小数となるので， $\dfrac{2k-1}{2^{n+1}}$ が等確率で現れることになる．よってこれを $2^{n+1}$ 倍すると $1$ から $2^{n+1}-1$ までの奇数が等確率で現れることになる．

[うまい解答]
$x_{n-1}$ の二進数表示を $0.a_{n-1}a_{n-2}\cdots a_1 1$ （各 $a_0=1$ ， $a_1〜a_{n-1}$ は $0$ または $1$ ）とおくと，確率 $\dfrac{1}{2}$ で
$x_n=0.0a_{n-1}a_{n-2}\cdots a_1 1$ または $x_n=0.1a_{n-1}a_{n-2}\cdots a_1 1$
となる．よって帰納的に $x_n$ は等確率（確率 $\dfrac{1}{2^n}$ ）で小数第 $n+1$ 位が $1$ の二進小数
$0.\underbrace{0\cdots 0}_{n個} 1=\dfrac{1}{2^{n+1}}$
から
$0.\underbrace{1\cdots 1}_{n個} 1=\dfrac{2^{n+1}-1}{2^{n+1}}$
のいずれかとなる．よって $2^{n+1}\cdot x_n$ は等確率（確率 $\dfrac{1}{2^n}$ ）で
$1$ から $2^{n+1}-1$ までの奇数となる．これらの奇数 $2k-1$ （ $k\in\mathbb{N}$ ）のうち $\dfrac{2^{n+2}}{3}$ 未満のものは $\dfrac{\dfrac{2^{n+2}}{3}+1}{2}$ 未満の自然数の数 $\left\lfloor\dfrac{2^{n+2}+3}{6}\right\rfloor$ 個あるので求める確率は $P_n=\dfrac{1}{2^n} \left\lfloor\dfrac{2^{n+2}+3}{6}\right\rfloor$ となる．

ここで $n$ が奇数のとき $2^{n+2}$ を $6$ で割った余りが $4$ であることから
$\dfrac{1}{2^n} \left\lfloor\dfrac{2^{n+2}+3}{6}\right\rfloor$ $=\dfrac{1}{2^n} \cdot \dfrac{2^{n+2}+2}{6}=\dfrac{2}{3}+\dfrac{1}{3\cdot 2^n}$ となり， $n$ が奇数のとき $2^{n+2}$ を $6$ で割った余りが $2$ であることから
$\dfrac{1}{2^n} \left\lfloor\dfrac{2^{n+2}+3}{6}\right\rfloor$ $=\dfrac{1}{2^n} \cdot \dfrac{2^{n+2}-2}{6}=\dfrac{2}{3}-\dfrac{1}{3\cdot 2^n}$ となるので，床関数を用いずに表現すると
$P_n=\dfrac{2}{3}+\dfrac{(-1)^n}{3\cdot 2^n}$ となる．