確率論の問題

遷移確率. 状態 $x$ から、確率 $\frac{1}{2}$ で $x$ にとどまり（選んだビットが第 $i$ 成分と同じとき）、各 $i$ について確率 $\frac{1}{2n}$ で第 $i$ 成分を反転した状態 $x\oplus e_i$ に移る。つまり $X$ は $n$ 次元超立方体上の「怠惰な（lazy）ランダムウォーク」である。

距離への射影. 目標を $b=(1,1,0,\dots ,0)$ とし、$D_t$ を $X_t$ と $b$ のハミング距離とする。1 ステップで、$X_t$ と $b$ が異なる $D_t$ 個の成分のどれかが選ばれて反転されれば距離は $1$ 減り、一致する $n-D_t$ 個のどれかが反転されれば $1$ 増える。よって $(D_t)$ は $\{0,1,\dots ,n\}$ 上のマルコフ連鎖で
$$P(d\to d-1)=\frac{d}{2n},P(d\to d+1)=\frac{n-d}{2n},P(d\to d)=\frac{1}{2}$$
である（エーレンフェスト型の出生死滅連鎖）。$D_0=2$ であり、$T$ は $D$ が初めて $0$ に達する時刻である。出生死滅連鎖なので、$2$ から $0$ に行くには必ず $1$ を通る。$k$ から出発して初めて $k-1$ に達するまでの期待時間を ${\tau }_k$ と書くと、強マルコフ性により
$$E[T]={\tau }_2+{\tau }_1$$
である。

定常分布. $X$ の遷移行列は対称なので一様分布 $2^{-n}$ が定常分布であり、したがって $D$ の定常分布は $\pi (d)=\left(\genfrac{}{}{0ex}{}{n}{d}\right)2^{-n}$ である。$D$ は可逆で、詳細つり合い $\pi (d)\frac{n-d}{2n}=\pi (d+1)\frac{d+1}{2n}$ が成り立つ（$\left(\genfrac{}{}{0ex}{}{n}{d}\right)(n-d)=\left(\genfrac{}{}{0ex}{}{n}{d+1}\right)(d+1)$ による）。

${\tau }_k$ の公式. $k$ 以上の状態の集合 $A_k=\{k,k+1,\dots ,n\}$ を考える。$k$ から出発して $k-1$ に達するまでの時間は、$A_k$ から外に出るまでの時間である。定常状態での $A_k$ の流出率（$A_k$ から $k-1$ への確率の流れ）は $\pi (k)\frac{k}{2n}$ で、$A_k$ の中に滞在する確率は $\pi (A_k)={\sum }_{j\ge k}\pi (j)$ である。$A_k$ に外から入るときは必ず $k$ に入るので、再生の議論により
$${\tau }_k=\frac{\pi (A_k)}{\pi (k)\frac{k}{2n}}=\frac{2n}{k\left(\genfrac{}{}{0ex}{}{n}{k}\right)}\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right).$$
（これは出生死滅連鎖の標準的な公式で、状態 $d$ から出発して $k-1$ に達するまでの期待時間 $h_d$ についての差分方程式を解いても得られる。）

計算.
$${\tau }_1=\frac{2n}{1\cdot n}\left(2^n-1\right)=2\left(2^n-1\right),$$
$${\tau }_2=\frac{2n}{2\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\left(2^n-1-n\right)=\frac{2n}{n(n-1)}\left(2^n-n-1\right)=\frac{2\left(2^n-n-1\right)}{n-1}.$$
よって
$$E[T]=2\left(2^n-1\right)+\frac{2\left(2^n-n-1\right)}{n-1}=\frac{2(n-1)\left(2^n-1\right)+2\left(2^n-n-1\right)}{n-1}.$$
分子は $2n\cdot 2^n-2\cdot 2^n-2n+2+2\cdot 2^n-2n-2=2n\cdot 2^n-4n=2n\left(2^n-2\right)$ なので
$$E[T]=\frac{2n\left(2^n-2\right)}{n-1}.$$

検算. ${\tau }_1$ は別の方法でも確かめられる。状態 $b$ への再帰時間の期待値は、カッツの定理より $1/2^{-n}=2^n$ である。$b$ から 1 ステップで、確率 $\frac{1}{2}$ で $b$ にとどまり、確率 $\frac{1}{2}$ で隣接頂点（距離 $1$）に移るので $2^n=1+\frac{1}{2}{\tau }_1$、すなわち ${\tau }_1=2(2^n-1)$ で一致する。また $n=2$ のとき、$X$ は 4 頂点の閉路上の怠惰なランダムウォークで、対角の頂点への到達時間は（怠惰でない場合の $2\cdot 2=4$ の 2 倍で）$8$ であり、公式の値 $\frac{2\cdot 2\cdot (4-2)}{1}=8$ と一致する。

目標状態を $x=(1,1,0,\dots ,0)$ とする。定常分布は $\{0,1{\}}^n$ 上の一様分布 $\pi (x)=2^{-n}$（遷移は対称）。既約ではないが、エルゴード的（非周期的かつ既約）なので、ヒッティング時間の公式 $E_0[T_x]=\frac{Z_{xx}-Z_{0x}}{\pi (x)}$、$Z_{yx}={\sum }_{t\ge 0}(P^t(y,x)-\pi (x))$ が使える。

時刻 $t$ までに一度でも選ばれた添字の集合を $R_t$、その大きさを $r_t$ とする。選ばれた成分は一様ランダムなビットになり、選ばれていない成分は初期値のまま。したがって
$P^t(x,x)=E[2^{-r_t}]$、$P^t(0,x)=E[2^{-r_t}1\{1,2\in R_t\}]$（$x$ と $0$ は成分 $1,2$ だけが異なる）。
$$E[T]=2^n\sum _{t\ge 0}E\left[2^{-r_t}1\{\{1,2\}⊈R_t\}\right].$$

添字が初めて選ばれる順序は $\{1,\dots ,n\}$ の一様ランダムな順列で、$r_t=k$ の状態に留まる期待時間は $\frac{n}{n-k}$（$k\le n-1$）。順列の最初の $k$ 個に $1,2$ がともには含まれない確率は $1-\frac{k(k-1)}{n(n-1)}$。よって
$$E[T]=2^n\sum _{k=0}^{n-1}{2}^{-k}\frac{n}{n-k}\left(1-\frac{k(k-1)}{n(n-1)}\right).$$
$j=n-k$ とおくと $1-\frac{(n-j)(n-j-1)}{n(n-1)}=\frac{j(2n-1-j)}{n(n-1)}$ だから
$$E[T]=\frac{1}{n-1}\sum _{j=1}^n{2}^j(2n-1-j).$$
${\sum }_{j=1}^n{2}^j=2^{n+1}-2$、${\sum }_{j=1}^{n}j{2}^j=(n-1)2^{n+1}+2$ を用いると
$$E[T]=\frac{(2n-1)(2^{n+1}-2)-(n-1)2^{n+1}-2}{n-1}=\frac{n{2}^{n+1}-4n}{n-1}=\frac{2n(2^n-2)}{n-1}.$$

検算: $n=2$ のとき公式は $\frac{2\cdot 2\cdot 2}{1}=8$。直接: $h_0=E_{00}[T]$, $h_1=E_{01}[T]$ とすると $h_0=1+\frac{1}{2}{h}_0+\frac{1}{2}{h}_1$, $h_1=1+\frac{1}{2}{h}_1+\frac{1}{4}{h}_0$。$h_1=2+\frac{1}{2}{h}_0$ を代入して $h_0=8$。一致する。