初めて原点に戻る時刻

同義語：ランダムウォークの初回帰時刻first return time of a random walk

概要

初めて原点に戻る時刻（first return time of a random walk）とは、原点から出発し、確率 $\frac12$ ずつで独立に $+1$ か $-1$ 動く数直線上の点が、初めて原点に戻る回数 $T$ のことである。$2n$ 回目まで一度も原点に戻らない確率が $u_{2n}=\binom{2n}{n}\frac{1}{4^n}$ に等しいことから、差をとって $P(T=2n)=u_{2n-2}-u_{2n}=\frac{u_{2n}}{2n-1}=\frac{2C_{n-1}}{4^n}$（$C_m$ は Catalan 数）が得られる。$T$ は確率 $1$ で有限だが、$\sum_{k=1}^{N}2k\,P(T=2k)=2N\,u_{2N}\ge\sqrt N$ なので期待値は無限大である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ランダムウォークの原点への復帰, Catalan数（高校数学）, 無限級数の和と収束判定

高校での出発点：初めて原点に戻るまで待つ

数直線の原点に点を置き、硬貨を投げて、表なら右へ $1$、裏なら左へ $1$ 動かす。点が初めて原点に戻ったところでやめることにする。何回目にやめることになるだろうか。
ランダムウォークの原点への復帰 で見たように、点はいつかは原点に戻る。1 回目に右へ動いても、2 回目に左へ動けばすぐ戻る。一方で、点が片側に長くとどまることもある。まず、小さい回数で確率を数えてみる。

初めて原点に戻るのが 2 回目・4 回目・6 回目の確率

表を $+$、裏を $-$ と書く。原点に戻れるのは偶数回目だけである（ランダムウォークの原点への復帰 の命題「奇数回目には原点にいない」）。
(1) 2 回目に初めて戻るのは $+-$、$-+$ の 2 通りで、確率は $\dfrac2{4}=\dfrac12$ である。
(2) 4 回目に初めて戻るには、2 回目に原点にいてはいけないので、最初の 2 回は $++$ か $--$ である。$++$ の後、位置 $2$ から 2 回で原点に戻るのは $--$ だけである。よって $++--$、$--++$ の 2 通りで、確率は $\dfrac2{16}=\dfrac18$ である。
(3) 6 回目に初めて戻る並びは、同じように考えて
$$ {+}{+}{+}{-}{-}{-},\quad {+}{+}{-}{+}{-}{-},\quad {-}{-}{-}{+}{+}{+},\quad {-}{-}{+}{-}{+}{+} $$
の 4 通りで、確率は $\dfrac4{64}=\dfrac1{16}$ である。
(4) ここまでの和は $\dfrac12+\dfrac18+\dfrac1{16}=\dfrac{11}{16}$ である。残りの $\dfrac5{16}$ は、6 回目までに一度も原点に戻らない確率で、ランダムウォークの原点への復帰 の $u_6=\dfrac5{16}$ に等しい。

半分の確率で 2 回目に戻り、6 回目までに約 $69\%$ の確率で戻る。待ち時間はたいてい短い。それなのに、この記事で示すように、初めて戻るまでの回数の 期待値は無限大 になる。この記事の問いは次のとおりである。

  1. 初めて原点に戻るのが $2n$ 回目である確率はいくつか。→ thm-frt-dist
  2. 初めて戻る回数は、確率 $1$ で有限か。→ thm-frt-mean の (1)
  3. その期待値はいくつか。→ thm-frt-mean の (2)
  4. 「確率 $1$ で起こるなら期待値は有限」は正しいか。止まる所（壁）を置くと何が変わるか。→ ex-frt-cx-finite、ex-frt-cx-converse、ex-frt-walls
    高校の計算この記事の言葉大学の言葉
    余事象の確率の差$P(T>2n-2)-P(T>2n)$分布関数の差
    正しい括弧の列の数正の側にとどまって戻る歩みの数Catalan 数
    無限級数の発散期待値が無限大可積分でない確率変数
    幾何分布の待ち時間裾の確率の減り方裾の重い分布

言葉の準備：初めて原点に戻る時刻

この記事では、ランダムウォークの原点への復帰 の定義「1 次元のランダムウォーク」をそのまま使う。$X_1,X_2,\ldots$ は確率 $\dfrac12$ ずつで $+1$ か $-1$ をとる独立な動き、$S_n=X_1+\cdots+X_n$ は $n$ 回目の位置（$S_0=0$）である。$u_{2n}=P(S_{2n}=0)=\dbinom{2n}n\dfrac1{4^n}$（$u_0=1$）も同じ記事の記号である。

初めて原点に戻る時刻

$S_k=0$ となる最小の $k\ge1$ を $T$ と書き、初めて原点に戻る時刻 という。$n\ge1$ について、$T=2n$ となる確率、すなわち
$$ S_1\ne0,\ \ldots,\ S_{2n-1}\ne0,\quad S_{2n}=0 $$
となる確率を $f_{2n}=P(T=2n)$ と書く。この確率は長さ $2n$ の歩み $4^n$ 通りのうち、条件をみたすものの数を数えて求める。また、「$T>m$」は「$S_1,\ldots,S_m$ がどれも $0$ でない」ことを表す。

奇数回目には原点にいないので、$T$ は偶数の値しかとらない。したがって、「$T>2n-1$」と「$T>2n-2$」は同じ出来事である。

歩みと $T$ の値
  1. 歩み $(+1,+1,-1,+1,-1,-1,+1,\ldots)$ では、位置は $1,2,1,2,1,0,\ldots$ で、$T=6$ である。7 回目以降の動きは $T$ の値に関係しない。
  2. 歩み $(-1,+1,\ldots)$ では $S_2=0$ で、$T=2$ である。

$T$ の値は、初めて戻るまでの歩みだけで決まる。$T$ についての確率は、どれも長さが有限の歩みを数えて求められる。
ランダムウォークの原点への復帰 の定理「原点にいる確率と、原点に戻らない確率」の (2) は、この記号で
$$ P(T>2n)=u_{2n}\qquad(n\ge0) $$
と書ける（$n=0$ では $P(T>0)=1=u_0$）。$2n$ 回目まで一度も原点に戻らない確率は、$2n$ 回目に原点にいる確率に等しい、という等式であった。この記事の主定理は、すべてこの等式から出てくる。

主定理 1：初めて戻る時刻の分布

ex-frt-start の (4) で、$\dfrac12+\dfrac18+\dfrac1{16}$ と $u_6$ を足すと $1$ になった。これは「6 回目までに初めて戻る」と「6 回目まで戻らない」が余事象どうしだからである。同じ考え方で、1 回分ずつの差をとれば $f_{2n}$ が求まる。

初めて原点に戻る時刻の分布

$n\ge1$ について
$$ f_{2n}=u_{2n-2}-u_{2n}=\frac{u_{2n-2}}{2n}=\frac{u_{2n}}{2n-1} $$
である。$C_m=\dfrac1{m+1}\dbinom{2m}m$（Catalan 数）を使うと
$$ f_{2n}=\frac{2\,C_{n-1}}{4^n} $$
とも書ける。

方針：「$2n-2$ 回目まで戻らない」を「ちょうど $2n$ 回目に初めて戻る」と「$2n$ 回目まで戻らない」に分けて差をとり、$u_{2n}$ の漸化式で書きかえる。
段 1（差の形）。$T>2n-2$ のとき、$T$ は偶数なので $T=2n$ か $T>2n$ のどちらか一方である。逆に $T=2n$ でも $T>2n$ でも $T>2n-2$ である。2 つの出来事は重ならないので
$$ P(T>2n-2)=P(T=2n)+P(T>2n) $$
である。$P(T>2n-2)=u_{2n-2}$、$P(T>2n)=u_{2n}$ を代入して、$f_{2n}=u_{2n-2}-u_{2n}$ を得る。
段 2（漸化式で書きかえる）。ランダムウォークの原点への復帰 の命題「$u_{2n}$ の漸化式と積の形」より $u_{2n}=\dfrac{2n-1}{2n}u_{2n-2}$ である。よって
$$ f_{2n}=u_{2n-2}-\frac{2n-1}{2n}u_{2n-2}=\left(1-\frac{2n-1}{2n}\right)u_{2n-2}=\frac{u_{2n-2}}{2n} $$
である。同じ漸化式を $u_{2n-2}=\dfrac{2n}{2n-1}u_{2n}$ と書きかえて代入すると、$f_{2n}=\dfrac1{2n}\cdot\dfrac{2n}{2n-1}u_{2n}=\dfrac{u_{2n}}{2n-1}$ である。
段 3（Catalan 数の形）。$u_{2n-2}=\dbinom{2n-2}{n-1}\dfrac1{4^{n-1}}$ なので
$$ \frac{u_{2n-2}}{2n}=\frac1{2n}\binom{2n-2}{n-1}\frac{4}{4^n}=\frac2{4^n}\cdot\frac1n\binom{2n-2}{n-1}=\frac{2\,C_{n-1}}{4^n} $$
である（$C_{n-1}=\dfrac1{(n-1)+1}\dbinom{2(n-1)}{n-1}=\dfrac1n\dbinom{2n-2}{n-1}$）。$\square$

段 1 の差をとる考え方は、GS06 の第 12.1 節の練習問題 2 (a) にある。GS06 の Theorem 12.3 は、同じ式を母関数を使って導いている。

公式に数を入れる
$n$$1$$2$$3$$4$$5$
$u_{2n}$$\frac12$$\frac38$$\frac5{16}$$\frac{35}{128}$$\frac{63}{256}$
$f_{2n}=u_{2n-2}-u_{2n}$$\frac12$$\frac18$$\frac1{16}$$\frac5{128}$$\frac7{256}$
$C_{n-1}$$1$$1$$2$$5$$14$
$2C_{n-1}/4^n$$\frac24$$\frac2{16}$$\frac4{64}$$\frac{10}{256}$$\frac{28}{1024}$

たとえば $n=4$ では、$u_6-u_8=\dfrac5{16}-\dfrac{35}{128}=\dfrac{40-35}{128}=\dfrac5{128}$、$\dfrac{u_8}{7}=\dfrac{35}{128\cdot7}=\dfrac5{128}$、$\dfrac{2\cdot5}{256}=\dfrac5{128}$ で、3 つの形が一致する。$n=1,2,3$ の値は ex-frt-start の数え上げと一致する。

初めて原点に戻る時刻 T の分布。棒は T = 2n となる確率、折れ線は 2n 回目まで戻らない確率で、棒の高さは折れ線の 1 段ごとの下がり幅に等しい 初めて原点に戻る時刻 T の分布。棒は T = 2n となる確率、折れ線は 2n 回目まで戻らない確率で、棒の高さは折れ線の 1 段ごとの下がり幅に等しい
図 1 の棒の高さ $f_{2n}$ は、折れ線 $P(T>2n)=u_{2n}$ の 1 段ごとの下がり幅である。$f_{2n}$ は急に小さくなるが、折れ線はゆっくりとしか下がらない。
$f_{2n}=\dfrac{2C_{n-1}}{4^n}$ という形は、数え方からも直接分かる。これは前の証明とは別の、ランダムウォークの原点への復帰 の等式を使わない証明である。

（thm-frt-dist の Catalan 数の形の別証明）
方針：$2n$ 回目に初めて戻る歩みを、正の側にいる場合と負の側にいる場合に分け、正の側の歩みを正しい括弧の列に対応させる。
段 1（正の側と負の側）。$T=2n$ の歩みでは $S_1,\ldots,S_{2n-1}$ はどれも $0$ でない。位置は 1 回に $1$ ずつしか変わらないので、途中で符号を変えるには $0$ を通る必要があり、$S_1,\ldots,S_{2n-1}$ はすべて正か、すべて負である。すべての動きの符号を入れ替えると、2 つの場合が 1 対 1 に対応するので、すべて正の場合を数えて 2 倍すればよい。
段 2（最初と最後の 1 歩）。すべて正の場合、$S_1>0$ なので $X_1=+1$ で、$S_{2n-1}>0$、$S_{2n}=0$ なので $S_{2n-1}=1$、$X_{2n}=-1$ である。
段 3（間の $2n-2$ 歩）。間の動き $X_2,\ldots,X_{2n-1}$ について、$2\le k\le2n-1$ で $S_k=1+(X_2+\cdots+X_k)$ である。条件「$S_2,\ldots,S_{2n-1}$ がすべて $1$ 以上で $S_{2n-1}=1$」は、「$X_2+\cdots+X_k\ge0$（$2\le k\le2n-1$）で、全体の和が $0$」と同じである。$+1$ を「(」、$-1$ を「)」と読みかえると、これは「(」と「)」を $n-1$ 個ずつ並べ、どこまで読んでも閉じた数が開いた数を超えない列、つまり Catalan数（高校数学） の定義「正しい括弧の列とCatalan数」の括弧 $n-1$ 組の正しい列である（$n=1$ では間の動きはなく、空の列 1 つにあたる）。その個数は $C_{n-1}$ で、同じ記事の定理「Catalan数の公式」により $C_{n-1}=\dfrac1n\dbinom{2n-2}{n-1}$ である。
段 4（結論）。$T=2n$ の歩みは $2C_{n-1}$ 通りで、確率は $\dfrac{2C_{n-1}}{4^n}$ である。$\square$

括弧の列との対応を $n=3$ で見る

$n=3$ のとき、間の 4 歩は括弧 2 組の正しい列 (())、()() の 2 通り（$C_2=2$）である。前後に $+$ と $-$ を付けると、$+\,{+}{+}{-}{-}\,-={+}{+}{+}{-}{-}{-}$ と $+\,{+}{-}{+}{-}\,-={+}{+}{-}{+}{-}{-}$ になり、ex-frt-start の (3) の正の側の 2 通りと一致する。

主定理 2：確率 $1$ で戻るのに、期待値は無限大

$T$ は無限に続く歩みについての確率変数で、とる値 $2,4,6,\ldots$ は限りなく続く。そこで、次の意味で言葉を使う。

確率 $1$ で有限、期待値が無限大
  1. $\displaystyle\sum_{n=1}^\infty f_{2n}=1$ のとき（部分和 $f_2+f_4+\cdots+f_{2n}=P(T\le2n)$ が $1$ に近づくとき）、$T$ は 確率 $1$ で有限 であるという。
  2. $T$ の期待値は、無限級数 $\displaystyle\sum_{n=1}^\infty2n\,f_{2n}$ が収束するときはその和と定める。部分和 $\displaystyle\sum_{k=1}^N2k\,f_{2k}$ が $N$ とともに限りなく大きくなるとき、$T$ の 期待値は無限大 であるという。

値が有限個の確率変数なら、期待値は有限個の和で、いつでも有限の値になる（確率変数の期待値と分散）。値が限りなく続くときは、(2) の級数が収束するとは限らない。無限級数の和と収束判定 で見たように、項が $0$ に近づいても級数が発散することがある。

確率 $1$ で戻るが、期待値は無限大
  1. $n\ge1$ について $f_2+f_4+\cdots+f_{2n}=1-u_{2n}$ であり、$T$ は確率 $1$ で有限である。
  2. $k\ge1$ について $2k\,f_{2k}=u_{2k-2}$ であり、$N\ge1$ について
    $$ \sum_{k=1}^N2k\,f_{2k}=2N\,u_{2N}\ge\sqrt N $$
    である。したがって $T$ の期待値は無限大である。

方針：(1) は thm-frt-dist の差の形を足し合わせる（望遠鏡の和）。(2) は thm-frt-dist の $f_{2k}=\dfrac{u_{2k-2}}{2k}$ から $2kf_{2k}=u_{2k-2}$ とし、ランダムウォークの原点への復帰 の系の和の公式と補題の評価を使う。
段 1（(1) の和）。thm-frt-dist より $f_{2k}=u_{2k-2}-u_{2k}$ なので
$$ \sum_{k=1}^nf_{2k}=(u_0-u_2)+(u_2-u_4)+\cdots+(u_{2n-2}-u_{2n})=u_0-u_{2n}=1-u_{2n} $$
である（隣り合うかっこの間で $u_2,\ldots,u_{2n-2}$ が打ち消し合う）。
段 2（(1) の極限）。ランダムウォークの原点への復帰 の定理「いつかは原点に戻る」より $u_{2n}\to0$（$n\to\infty$）なので、$\displaystyle\sum_{n=1}^\infty f_{2n}=\lim_{n\to\infty}(1-u_{2n})=1$ である。
段 3（(2) の各項）。thm-frt-dist より $f_{2k}=\dfrac{u_{2k-2}}{2k}$ なので、両辺に $2k$ を掛けて $2k\,f_{2k}=u_{2k-2}$ である。
段 4（(2) の部分和）。段 3 より
$$ \sum_{k=1}^N2k\,f_{2k}=u_0+u_2+\cdots+u_{2N-2} $$
である。$N=1$ なら右辺は $u_0=1$ で、$2\cdot1\cdot u_2=1$ に等しい。$N\ge2$ なら、ランダムウォークの原点への復帰 の系「原点に戻る回数の期待値」の和の公式 $u_2+\cdots+u_{2n}=(2n+1)u_{2n}-1$ を $n=N-1$ で使って
$$ u_0+u_2+\cdots+u_{2N-2}=1+\bigl\{(2N-1)u_{2N-2}-1\bigr\}=(2N-1)u_{2N-2} $$
である。さらに漸化式 $u_{2N}=\dfrac{2N-1}{2N}u_{2N-2}$ から $(2N-1)u_{2N-2}=2N\,u_{2N}$ なので、部分和は $2N\,u_{2N}$ である。
段 5（下からの評価）。ランダムウォークの原点への復帰 の補題「$u_{2n}$ の上下の評価」の $u_{2N}\ge\dfrac1{2\sqrt N}$ から
$$ 2N\,u_{2N}\ge\frac{2N}{2\sqrt N}=\sqrt N $$
である。$\sqrt N$ は $N$ とともに限りなく大きくなるので、部分和も限りなく大きくなり、def-frt-infinite の (2) の意味で $T$ の期待値は無限大である。$\square$

段 3 の $2kf_{2k}=u_{2k-2}$ は、「期待値の級数の第 $k$ 項は、$2k-2$ 回目に原点にいる確率に等しい」と言っている。級数 $\sum u_{2k-2}$ の項は $0$ に近づくが、その近づき方が $\dfrac1{2\sqrt k}$ 以上で遅いので、和は発散する。

部分和の表
$N$$f_{2N}$$P(T>2N)=u_{2N}$$\sum_{k=1}^N2kf_{2k}=2Nu_{2N}$$\sqrt N$
$1$$0.5$$0.5$$1$$1$
$2$$0.125$$0.375$$1.5$$1.414$
$3$$0.0625$$0.3125$$1.875$$1.732$
$10$$0.00927$$0.176$$3.524$$3.162$
$100$$0.000283$$0.0563$$11.270$$10$
$1000$$0.00000892$$0.0178$$35.678$$31.623$

$N=2$ では、$2\cdot\dfrac12+4\cdot\dfrac18=1+\dfrac12=\dfrac32$ で、$4u_4=4\cdot\dfrac38=\dfrac32$ に等しい。$N=3$ では $\dfrac32+6\cdot\dfrac1{16}=\dfrac32+\dfrac38=\dfrac{15}8$ で、$6u_6=6\cdot\dfrac5{16}=\dfrac{15}8$ に等しい。部分和は、$N$ を $100$ 倍にすると約 $10$ 倍になり（$N=10$ から $N=1000$ で $3.52$ から $35.7$）、止まらずに増え続ける（図 2）。

期待値の級数の部分和（実線）と、下からの評価 √N（破線）。部分和は √N より上にあり、限りなく大きくなる 期待値の級数の部分和（実線）と、下からの評価 √N（破線）。部分和は √N より上にあり、限りなく大きくなる
ex-frt-start では、半分の確率で 2 回目に戻り、4 回目までに $\dfrac58$ の確率で戻った。待ち時間の大部分は短い。それでも期待値が無限大になるのは、まれに非常に長く待つことがあり、その重みが大きいからである。$2n$ 回目まで戻らない確率は、$n=50$（100 回）で $u_{100}\approx0.0796$、$n=500$（1000 回）でも $u_{1000}\approx0.0252$ ある。「1000 回待っても戻らない」ことが約 $2.5\%$ の確率で起こり、そのとき待ち時間は 1000 を超える。期待値の級数のうち $k>500$ の項の和は、$2k>1000$ と $\displaystyle\sum_{k>500}f_{2k}=P(T>1000)=u_{1000}$ から $1000\times u_{1000}\approx25$ 以上になる。
ランダムウォークの原点への復帰 の「$u_{2n}\sqrt{\pi n}\to1$」を使うと、thm-frt-mean の部分和 $2Nu_{2N}$ と $2\sqrt{N/\pi}$ の 比 は $1$ に近づく（$\dfrac{2Nu_{2N}}{2\sqrt{N/\pi}}=u_{2N}\sqrt{\pi N}$ だから）。部分和は $\sqrt N$ の程度の速さで、限りなく大きくなる。

幾何分布の待ち時間との比較

幾何分布と待ち時間（高校数学） では、毎回確率 $p$ で成功する試行を、初めて成功するまでくり返す回数 $X$ を考えた。そこでは $P(X>n)=(1-p)^n$ で、裾の確率は等比数列の速さで $0$ に近づき、期待値は $\dfrac1p$ と有限であった。初めて原点に戻る時刻 $T$ では、$P(T>2n)=u_{2n}\ge\dfrac1{2\sqrt n}$ で、裾の確率がずっとゆっくりとしか $0$ に近づかない。期待値が有限か無限大かは、この裾の重さで決まる。

状態が無限にあることの影響

期待値の漸化式と停止 の定理「止まることと期待値が有限であること」は、ある $k$ と $\delta>0$ があって、目標でないどの状態から出発しても $k$ 回以内に止まる確率が $\delta$ 以上なら、止まるまでの回数の期待値は有限であることを示している。ランダムウォークの位置を状態とみると、位置 $s$ からは原点に着くまでに少なくとも $\lvert s\rvert$ 回かかるので、$\lvert s\rvert>k$ の位置からは $k$ 回以内に止まる確率が $0$ になる。状態（位置）が限りなくあるので、この仮定はどの $k$ でも成り立たず、定理は使えない。thm-frt-mean は、その仮定がないと期待値が無限大になりうることを示している。
また、ギャンブラーの破産 の命題「上に止まる所がない公平な歩き方」は、正の整数 $s$ から出発して $0$ に着くまでの回数について、止まる確率が $1$ で期待値が無限大であることを、上に止まる所を置いて遠ざける方法で示している。$T$ は、1 回目に $\pm1$ へ動いた後、そこから $0$ に着くまでの回数に $1$ を足したものである。$+1$ へ動いた後の回数は命題の $s=1$ の場合の回数と同じ分布をもち、$-1$ へ動いた場合も左右を入れ替えれば同じなので、$T$ についても同じ結論になる。この記事では $T$ の分布を式で求めたので、期待値の部分和を正確に $2Nu_{2N}$ と計算できた。

例と反例：「確率 $1$」と「期待値が有限」は別のこと

外す条件反例成り立たなくなること
期待値の漸化式と停止 の定理の仮定（どの状態からも $k$ 回以内に確率 $\delta$ 以上で止まる。状態が有限個で、どの状態からも目標に着けるなら成り立つ）ex-frt-cx-finite：初めて原点に戻る時刻 $T$止まる確率は $1$ なのに、期待値は有限でない
（逆向きの予想）「期待値が無限大なら、止まらないことが正の確率で起こる」ex-frt-cx-converse：同じ $T$期待値は無限大なのに、止まる確率は $1$
thm-frt-mean の設定の「止まるのは原点に戻ったときだけ」（位置 $\pm m$ にも止まる所を置く）ex-frt-walls：$m=2,3,\ldots$期待値は無限大でなくなり、ちょうど $m$ になる
反例：止まる確率が $1$ でも、期待値が有限とは限らない

期待値の漸化式と停止 の定理「止まることと期待値が有限であること」は、仮定のもとで「止まる確率が $1$」と「期待値が有限」を同時に結論する。そのため、2 つはいつも一緒に成り立つと思いたくなる。しかし $T$ では、thm-frt-mean の (1) により止まる確率は $1$ で、(2) により期待値は無限大である。
$T$ がこの定理の仮定をみたさないことは、次のように確かめられる。$k$ をどんな正の整数にとっても、位置 $k+1$ から原点までは少なくとも $k+1$ 回かかるので、位置 $k+1$ から出発して $k$ 回以内に止まる確率は $0$ であり、$\delta>0$ 以上にはならない。仮定が崩れているので定理の結論も成り立たない、という関係である（rem-frt-states）。

反例：期待値が無限大でも、止まる確率は $1$

逆に、「期待値が無限大なら、いつまでも止まらないことがある」とも考えたくなる。確率変数の期待値と分散 の反例「値が無限個あって期待値が定まらない」（St. Petersburg の逆説）では、硬貨を表が出るまで投げ続け、$j$ 回目に初めて表が出たら $2^j$ 円もらう。$n$ 回投げても表が出ない確率は $\left(\dfrac12\right)^n$ で $0$ に近づくので、賭けは確率 $1$ で終わる。それなのに賞金の期待値は定まらない。$T$ も同じで、thm-frt-mean の (1) により $P(T\le2n)=1-u_{2n}\to1$ なので確率 $1$ で止まる。それでも (2) により期待値は無限大である。期待値が無限大であることは「止まらないことがある」ことを意味せず、「まれに非常に長くかかることの重みが大きい」ことを意味する。

例：両側に止まる所を置くと、期待値は有限になる

$m\ge2$ を整数とし、原点に戻るか、位置 $m$ か $-m$ に着いたところで止まることにする。止まるまでの回数を $T_m$ とすると、$T_m$ の期待値は $m$ である。
(1) 理由：1 回目に点は $+1$ か $-1$ に動く。$+1$ に動いたとすると、その後は「位置 $1$ から出発し、確率 $\dfrac12$ ずつで $\pm1$ 動き、$0$ か $m$ に着いたら止まる」歩き方で、これは ギャンブラーの破産 の設定で所持金 $i=1$、目標 $N=m$、$p=q=\dfrac12$ とした場合である。同じ記事の定理「終わるまでの回数の期待値」より、残りの回数の期待値は $i(N-i)=1\cdot(m-1)=m-1$ である。$-1$ に動いた場合も、左右を入れ替えれば同じである。1 回目の 1 回を足して、$T_m$ の期待値は $1+(m-1)=m$ である。
(2) $m=2$ では、1 回目の後の位置は $\pm1$ で、2 回目には必ず $0$ か $\pm2$ に着くので $T_2=2$ で、期待値は $2$ である。$m=3$ では、2 回目に原点に戻る（確率 $\dfrac12$）か位置 $\pm2$ に行き、そこから $\pm3$ に着くか $\pm1$ に戻る。式の値は $3$ である。
止まる所を $\pm m$ に置くと、位置は $-m,\ldots,m$ の有限個になり、期待値の漸化式と停止 の定理の仮定が成り立つ。$m$ を大きくすると期待値 $m$ も限りなく大きくなり、止まる所を置かない $T$ の期待値が無限大であることと整合する。

大学数学で見る：母関数と「再生」の式

GS06 の Theorem 12.2 は、$2n$ 回目に原点にいる歩みを、初めて原点に戻った時刻 $2k$ で分けて
$$ u_{2n}=f_2\,u_{2n-2}+f_4\,u_{2n-4}+\cdots+f_{2n}\,u_0\qquad(n\ge1) $$
を示している（初めて戻った後は、そこから新しく歩き始めたのと同じになる、という考え方）。Theorem 12.3 は、この式を母関数 $U(x)=\sum u_{2m}x^m$、$F(x)=\sum f_{2m}x^m$ の関係 $U(x)=1+U(x)F(x)$ に直し、$F(x)=1-\sqrt{1-x}$ を導いて $f_{2m}=\dfrac{u_{2m}}{2m-1}$ を得ている。この記事では母関数を使わず、「$2n$ 回目まで戻らない確率は $u_{2n}$」という等式から差をとって同じ式を得た。上の式を小さい $n$ で確かめることは、演習にした。

期待値が無限大の確率変数について開く

大学数学では、期待値を確率による積分として定める（確率変数の期待値と分散 の注意「期待値は確率による積分」）。値が無限個の確率変数では、期待値の無限和が絶対収束するかどうかを調べる必要がある（同じ記事の反例「値が無限個あって期待値が定まらない」）。$T$ は確率 $1$ で有限の値をとるが、$\sum 2n\,f_{2n}$（項はすべて正）が発散するので、有限の期待値をもたない確率変数の例になっている。

演習

再生の式を確かめる

$n=3$ のとき、$u_6=f_2u_4+f_4u_2+f_6u_0$ が成り立つことを数値で確かめよ。また、6 回目に原点にいる歩み $20$ 通りを、初めて原点に戻った時刻で分けて数えることで、この式の意味を説明せよ。

解答を開く

右辺は $\frac12\cdot\frac38+\frac18\cdot\frac12+\frac1{16}\cdot1=\frac3{16}+\frac1{16}+\frac1{16}=\frac5{16}=u_6$。歩みの数で言うと、初めて戻るのが 2 回目の歩みは、最初の 2 歩が $f_2\cdot4=2$ 通り、残り 4 歩で原点に戻るのが $u_4\cdot16=6$ 通りで $12$ 通り。4 回目なら $f_4\cdot16=2$ 通りと残り 2 歩の $u_2\cdot4=2$ 通りで $4$ 通り。6 回目なら $f_6\cdot64=4$ 通り。合計 $12+4+4=20=\binom63$ 通りで、これを $64$ で割ったものが上の式である。

戻らない確率が 5% 未満になるのは
  1. 10 回目までに初めて原点に戻る確率 $P(T\le10)$ を求めよ。(2) $P(T>2n)<0.05$ となる最小の $n$ について、ランダムウォークの原点への復帰 の補題「$u_{2n}$ の上下の評価」を使って $100< n\le200$ であることを示せ。（実際の値は $n=128$ である。）
解答を開く

(1) thm-frt-mean の (1) より $P(T\le10)=1-u_{10}=1-\frac{63}{256}=\frac{193}{256}\approx0.754$。

(2) $P(T>2n)=u_{2n}$ である。$n\le100$ なら $u_{2n}\ge\frac1{2\sqrt n}\ge\frac1{2\cdot10}=0.05$ なので、$u_{2n}<0.05$ にならない。$n=200$ なら $u_{400}\le\frac1{\sqrt{401}}<\frac1{20}=0.05$ である（$\sqrt{401}>20$）。よって最小の $n$ は $100$ より大きく $200$ 以下である。漸化式で計算すると $u_{254}\approx0.05001$、$u_{256}\approx0.04982$ で、最小の $n$ は $128$ である。

さらに先へ

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する

Mathpediaを支援する
初めて原点に戻る時刻