京都大学 理学研究科 物理学・宇宙物理学専攻 2015年8月実施 II-3

标签：

• 京都大学
• 一维随机游走的首次返回时间

Author

祭音Myyura (refined with GPT 6 Astra)

Description

1次元のランダムウォークを考える。原点を出発点とするランダムウォークの $n$ ステップ後の位置 $S_n$ は確率変数で、以下のように与えられる。

$$S_n=\sum_{i=1}^nX_i.\tag{A}$$

ここで、確率変数 $X_i$ は、等確率で1か $-1$ をとる。ただし、$S_0$ は確率1で0をとるとする。また、$X_i\;(i=1,\ldots,n)$ は独立で、$X_i$ に対する平均を $\langle\ \rangle$ と表すとき、$\langle X_iX_j\rangle=\langle X_i\rangle\langle X_j\rangle\;(i\ne j)$ を満たすものとする。

(1) ランダムウォーク $S_n$ の平均 $\langle S_n\rangle$ と分散 $\langle(S_n-\langle S_n\rangle)^2\rangle$ を求めよ。

$S_n$ の個々の事象は、$i$ ステップ後の位置の値を $s_i$ とおくとき、$(s_1,s_2,\ldots,s_n)$ と表すことができる。これを $S_n$ の経路と呼ぶ。図1に $n=10000$ のときに得られた経路を示した。この経路では、$i>2k$ の全てで $s_i$ は正の値をとる。常識では $s_i$ の半分程度が正の値をとる確率が高いと思われるが、実際はそうではない。以下では、$s_i>0$ の割合が大きい経路は高い確率で実現されることを確かめる。

図1の経路は、$2k$ ステップ目に原点に戻る経路と原点を出た後 $n-2k$ ステップの間 $s_i>0$ となる経路に分けられる。ここで、原点を出た後 $2k$ ステップ目に原点に戻る経路の集合を事象 $S_{2k}^0$、原点を出た後 $k$ ステップの間 $s_i>0$ となる経路の集合を事象 $S_k^>$ とそれぞれ呼ぶ。

(2) 事象 $S_{2m}^0$ が実現される確率 $P(S_{2m}^0)=u_{2m}$ を求めよ。スターリングの公式 $n!\sim e^{-n}n^n\sqrt{2\pi n}$ を用いて $m\gg1$ の場合に、$u_{2m}$ の漸近形を求めよ。以下では、$P(S_0^0)=u_0=1$ とする。

原点を出た後 $k$ ステップの間 $s_i\ge0$ である経路の集合を事象 $S_k^\ge$ と呼ぶ。図2に事象 $S_6^\ge$（◆）、$S_6^>$（○）と $S_6^0$（□）に属する経路の例を示した。事象 $S_{2m}^\ge$ と事象 $S_{2m}^0$ に属する経路は1対1対応させることができるので、それぞれの事象に属する経路の総数は等しい。従って、実現確率は等しく $P(S_{2m}^\ge)=P(S_{2m}^0)$ である。この確率は $u_{2m}$ である。以下、この関係を既知として用いよ。

(3) 事象 $S_{2m}^>$ と事象 $S_{2m-1}^\ge$ に属する経路の総数が等しいことを示せ。また、$P(S_{2m}^\ge),P(S_{2m-1}^\ge)$ と $P(S_{2m}^>)$ の関係を求めよ。奇数回のステップでは原点に戻れないことに注意せよ。

図1の経路が属する、原点を出た後 $2k$ ステップ目に原点に戻り、その後の引き続く $2m-2k$ ステップの間は正となる事象 $S_{2k}^0+S_{2m-2k}^>$ が実現される確率 $P(S_{2k}^0+S_{2m-2k}^>)$ を求めよう。

(4) 事象 $S_{2k}^0$ と事象 $S_{2m-2k}^>$ は独立なので、事象 $S_{2k}^0+S_{2m-2k}^>$ の実現確率は以下の関係を満たす。

$$P(S_{2k}^0+S_{2m-2k}^>)=P(S_{2k}^0)P(S_{2m-2k}^>).$$

この実現確率を $\alpha_{2k,2m}$ とおく。このとき、$\alpha_{2k,2m}$ を適切な $j$ に対する $u_{2j}$ を用いて表せ。スターリングの公式を用いて、$m,k,m-k\gg1$ の場合に $\alpha_{2k,2m}$ の漸近形を求めよ。ただし、$x=k/m$ の関数として表せ。

ランダムウォーク $S_{2m}$ の中で、原点より上にあるステップ数が $2k\;(k\ge0)$ である事象を $Q_{2k,2m}$ と表す。ただし、$s_{2i}=0$ のとき、$s_{2i}$ の符号は $s_{2i-1}$ と同じとみなす。事象 $Q_{2k,2m}$ が実現される確率を $\beta_{2k,2m}$ とおくと、

$$P(Q_{2k,2m})=\beta_{2k,2m}=2\alpha_{2k,2m}\tag{B}$$

であることを示そう。

(5) 原点を出た後 $2i$ ステップ後に初めて原点に戻ってくる確率を $f_{2i}$ とおく。このとき、$u_{2m}$ を $f_{2i}$ と $u_{2j}\;(1\le i\le m,\ 0\le j<m)$ を用いて表せ。

(6) $Q_{2k,2m}$ の経路の中で初期の $2r$ ステップ目に初めて原点に到達するものは、$0<i<2r$ の全てで $s_i>0$ となる場合と $s_i<0$ となる場合の2通りある。その後、それぞれ $Q_{2k-2r,2m-2r}$ と $Q_{2k,2m-2r}$ に属する経路が後に続くことになる。この関係を用いて、$\beta_{2k,2m}$ を $f_{2a}$ と $\beta_{2b,2c}\;(a<m,c<m,b\le k)$ を用いて表せ。

(7) 式 (B) が成り立つことを示し、$\beta_{2k,2m}$ を適切な $j$ に対する $u_{2j}$ を用いて表せ。ただし、$b\le k,c<m$ の場合にも式 (B) が成り立つとして $\beta_{2b,2c}$ に代入せよ。

题目描述

考虑一维随机游走。以原点出发的随机游走在 $n$ 步后的位置 $S_n$ 是随机变量，定义为

$$S_n=\sum_{i=1}^nX_i.\tag{A}$$

随机变量 $X_i$ 等概率取1或 $-1$，$S_0$ 以概率1取0。各 $X_i\;(i=1,\ldots,n)$ 相互独立，用 $\langle\ \rangle$ 表示平均，满足 $\langle X_iX_j\rangle=\langle X_i\rangle\langle X_j\rangle\;(i\ne j)$。

(1) 求随机游走 $S_n$ 的均值 $\langle S_n\rangle$ 和方差 $\langle(S_n-\langle S_n\rangle)^2\rangle$。

将第 $i$ 步后的位置值记为 $s_i$，则 $S_n$ 的一次具体实现可以表示为 $(s_1,s_2,\ldots,s_n)$，称为 $S_n$ 的路径。图1显示 $n=10000$ 时得到的一条路径。该路径在所有 $i>2k$ 时都有 $s_i>0$。直觉上似乎约一半位置为正的概率较高，但实际并非如此。以下验证：正位置 $s_i>0$ 所占比例较大的路径，也会以较高概率出现。

图1的路径可分成第 $2k$ 步回到原点的路径，以及重新从原点出发后的 $n-2k$ 步内始终满足 $s_i>0$ 的路径。记从原点出发后第 $2k$ 步回到原点的路径集合为事件 $S_{2k}^0$，出发后 $k$ 步内始终满足 $s_i>0$ 的路径集合为事件 $S_k^>$。

(2) 求事件 $S_{2m}^0$ 的概率 $P(S_{2m}^0)=u_{2m}$。利用斯特林公式 $n!\sim e^{-n}n^n\sqrt{2\pi n}$，求 $m\gg1$ 时 $u_{2m}$ 的渐近形式。以下取 $P(S_0^0)=u_0=1$。

将出发后 $k$ 步内始终满足 $s_i\ge0$ 的路径集合记为事件 $S_k^\ge$。图2给出分别属于 $S_6^\ge$（◆）、$S_6^>$（○）和 $S_6^0$（□）的路径示例。事件 $S_{2m}^\ge$ 与 $S_{2m}^0$ 的路径可以一一对应，因而路径总数相等，概率也相等，即 $P(S_{2m}^\ge)=P(S_{2m}^0)=u_{2m}$。以下可以将此关系作为已知使用。

(3) 证明事件 $S_{2m}^>$ 与 $S_{2m-1}^\ge$ 的路径总数相等，并求 $P(S_{2m}^\ge),P(S_{2m-1}^\ge)$ 和 $P(S_{2m}^>)$ 的关系。注意奇数步后不可能回到原点。

考虑图1所属的事件：从原点出发后第 $2k$ 步回到原点，此后连续 $2m-2k$ 步位置均为正。将此事件记为 $S_{2k}^0+S_{2m-2k}^>$，求其概率。

(4) 由于 $S_{2k}^0$ 和 $S_{2m-2k}^>$ 相互独立，概率满足

$$P(S_{2k}^0+S_{2m-2k}^>)=P(S_{2k}^0)P(S_{2m-2k}^>).$$

记此概率为 $\alpha_{2k,2m}$。用适当下标 $j$ 的 $u_{2j}$ 表示 $\alpha_{2k,2m}$，再利用斯特林公式，求 $m,k,m-k\gg1$ 时的渐近形式，并写成 $x=k/m$ 的函数。

在随机游走 $S_{2m}$ 中，将位于原点上方的步数为 $2k\;(k\ge0)$ 的事件记为 $Q_{2k,2m}$。若 $s_{2i}=0$，则将其符号视为与 $s_{2i-1}$ 相同。记事件 $Q_{2k,2m}$ 的概率为 $\beta_{2k,2m}$，以下证明

$$P(Q_{2k,2m})=\beta_{2k,2m}=2\alpha_{2k,2m}.\tag{B}$$

(5) 将从原点出发后第 $2i$ 步首次回到原点的概率记为 $f_{2i}$。用 $f_{2i}$ 和 $u_{2j}\;(1\le i\le m,\ 0\le j<m)$ 表示 $u_{2m}$。

(6) 对 $Q_{2k,2m}$ 中首次在第 $2r$ 步回到原点的路径，有两种情况：在所有 $0<i<2r$ 时均有 $s_i>0$，或均有 $s_i<0$。之后分别接续属于 $Q_{2k-2r,2m-2r}$ 或 $Q_{2k,2m-2r}$ 的路径。利用这一关系，用 $f_{2a}$ 和 $\beta_{2b,2c}\;(a<m,c<m,b\le k)$ 表示 $\beta_{2k,2m}$。

(7) 证明式 (B) 成立，并用适当下标 $j$ 的 $u_{2j}$ 表示 $\beta_{2k,2m}$。可以假设在 $b\le k,c<m$ 时式 (B) 成立，并代入 $\beta_{2b,2c}$。

Kai

(1)

$\langle X_i\rangle=0$、$\langle X_i^2\rangle=1$、異なる増分は独立なので

$$\boxed{\langle S_n\rangle=0,\qquad\operatorname{Var}(S_n)=n}.$$

(2)

原点に戻るには正負のステップがそれぞれ $m$ 回必要である。

$$\boxed{u_{2m}=\frac1{2^{2m}}\binom{2m}{m}\sim\frac1{\sqrt{\pi m}}}.$$

(3)

厳密に正の経路から最初の $+1$ のステップを除き、高さを 1 下げれば、長さ $2m-1$ の非負経路になる。この操作は可逆なので経路数は等しい。分母となる全経路数は 2 倍違うから

$$P(S_{2m-1}^\ge)=2P(S_{2m}^>).$$

非負な奇数長経路の終点は少なくとも 1 なので、末尾にどちらのステップを加えても非負である。よって

$$\boxed{P(S_{2m}^\ge)=P(S_{2m-1}^\ge)=2P(S_{2m}^>)=u_{2m}}.$$

(4)

$0\le k<m$ に対して独立性と (3) から

$$\boxed{\alpha_{2k,2m}=\frac12u_{2k}u_{2(m-k)}}.$$

両区間が長いとき

$$\boxed{\alpha_{2k,2m}\sim\frac1{2\pi\sqrt{k(m-k)}} =\frac1{2\pi m\sqrt{x(1-x)}}}.$$

(5)

最初の帰還が $2i$ の経路を分けると、その後の $2m-2i$ ステップは独立な原点帰還経路なので

$$\boxed{u_{2m}=\sum_{i=1}^mf_{2i}u_{2(m-i)}}.$$

(6)

$0<k<m$ では、最初の帰還前が正なら正の滞在時間 $2r$ を使い、負なら正の滞在時間は使わない。両方の確率は $f_{2r}/2$ である。

$$\boxed{\beta_{2k,2m} =\frac12\sum_{r=1}^kf_{2r}\beta_{2(k-r),2(m-r)} +\frac12\sum_{r=1}^{m-k}f_{2r}\beta_{2k,2(m-r)}}.$$

端点では、全期間を正側または負側にいる確率は、零点の符号規約から非負経路の確率に等しく

$$\boxed{\beta_{0,2m}=\beta_{2m,2m}=u_{2m}}.$$

(7)

短い経路について $\beta_{2j,2\ell}=u_{2j}u_{2(\ell-j)}$ を仮定し (6) に代入すると

$$\begin{aligned} \beta_{2k,2m} &=\frac{u_{2(m-k)}}2\sum_{r=1}^kf_{2r}u_{2(k-r)} +\frac{u_{2k}}2\sum_{r=1}^{m-k}f_{2r}u_{2(m-k-r)}\\ &=\boxed{u_{2k}u_{2(m-k)}}. \end{aligned}$$

端点の結果と $m=0$ を初期条件として帰納法が成立する。したがって $0\le k<m$ では $\beta_{2k,2m}=2\alpha_{2k,2m}$。

$k=m$ では後半が空の区間であり、事象の通常の定義では $P(S_0^>)=1$、従って $\alpha_{2m,2m}=u_{2m}$ である。端点にも $\beta=2\alpha$ と書くには、$\alpha_{2m,2m}=u_{2m}/2$ という端点への延長規約が必要となる。滞在時間の確率 $\beta_{2k,2m}=u_{2k}u_{2(m-k)}$ は両端を含め成立する。

Reference

• 京都大学公式問題（2016年度、PDF 13–14ページ）