ある確率問題から現れる級数と連分数
はじめに
はじめまして。普段は絵を描いているk.a.256です。
次の自作問題を解説します。自信のある方は解いてみてください。
$(X_n)_{n\ge0}$ を $X_0=0$ から始まるランダムウォークとする。
すなわち、偏りのないコインを各回独立に投げ、表なら $X_{n+1}=X_n+1$、裏なら $X_{n+1}=X_n-1$ とする。
初期位置も含めて、$n$ 回目までに到達した最大の位置を $M_n$、最小の位置を $m_n$ とし、
$$
S_n=M_n+m_n
$$
とおく。
$S_n$ が初めて $2$ または $-1$ になる時刻を $T$ とする。
$S_T=2$ なら成功、$S_T=-1$ なら失敗とする。
(1) 成功確率を求めよ。
(2) $E[T]$ を求めよ。
(3) $M_n-m_n$ が初めて $r$ になる時刻を $T_r$ とし、$T_r< T$ のとき $S_{T-1}=S_{T_r}$ となる確率を $a_r$ とする。$a_r$ と $a_{r+1}$ の関係を求めよ。
(4) 次の一般化連分数が収束することを確認し、その値を求めよ。
$$
2+\cfrac2{
2+\cfrac3{
3+\cfrac4{
4+\cfrac5{
5+\ddots}}}}
$$
問題
解答
(1)
$M_n-m_n$ が初めて $r$ になる時刻を $T_r$ とします。
最初の一歩が $-1$ なら $(M_1,m_1)=(0,-1),\ S_1=-1$ となり、その場で終了します。一方、最初の一歩が $+1$ なら $(M_1,m_1)=(1,0),\ S_1=1$ となり、$T_1=1$ です。
ここから、終了せずに最大値か最小値が更新されたときの $(M_n,m_n)$ だけを順に並べると、
$$
(1,0),(1,-1),(2,-1),(2,-2),\ldots
$$
と進みます。
以下、$T_r< T$ の場合を固定して考えます。このとき、$S_{T_r}$ は $r$ が奇数のとき $1$、偶数のとき $0$ です。
時刻 $T_r$ から、その次に最大値か最小値が更新されるまでを考えます。この時点で $X_{T_r}$ は $M_{T_r}$ または $m_{T_r}$ のどちらかにあります。
次に記録が更新される位置の候補は $M_{T_r}+1$ と $m_{T_r}-1$ で、この二点の距離は $r+2$ です。また、現在地は一方の端から距離 $1$ の位置にあります。
破産の確率との接続
ここで、一次元ランダムウォークについて次の事実を使います。
$0,1,\ldots,N$ 上の単純対称ランダムウォークを考え、$0$ または $N$ に到達したら終了する。$i$ から出発したとき、$0$ より先に $N$ に到達する確率は $i/N$ である。
証明
$i$ から出発したとき、$N$ に先に到達する確率を $q_i$ とする。$q_0=0,\ q_N=1$ であり、$1\le i\le N-1$ では
$$
q_i=\frac{q_{i-1}+q_{i+1}}2
$$
を満たす。したがって $q_{i+1}-q_i=q_i-q_{i-1}$ なので $q_i$ は $i$ の一次関数であり、境界条件から $q_i=i/N$。
これはギャンブラーの破産問題の基本的な形です。
先ほどの二つの記録候補を両端とみなして平行移動し、必要なら左右反転すると、$i=1,\ N=r+2$ の場合になります。終了せずに次の段階へ進むには、現在いる側とは反対側の記録を先に更新する必要があるので、
$$
P(T_{r+1}< T\mid T_r< T)=\frac1{r+2}.
$$
ここで $p_r=P(T_r< T)$ とおきます。最初に $+1$ が出る必要があるので $p_1=1/2$ であり、$p_{r+1}=p_r/(r+2)$ です。したがって、
$$
p_r=\frac1{(r+1)!}.
$$
特に $p_r\to0$ なので、この過程は確率 $1$ で終了します。
成功するのは、ある $k\ge1$ について幅 $2k-1$ まで到達し、幅 $2k$ には到達せずに終了する場合です。したがって、
$$
\begin{aligned}
P(S_T=2)
&=\sum_{k=1}^{\infty}(p_{2k-1}-p_{2k})\\
&=\sum_{k=1}^{\infty}\left(\frac1{(2k)!}-\frac1{(2k+1)!}\right)\\
&=1-1+\frac1{2!}-\frac1{3!}+\frac1{4!}-\frac1{5!}+\cdots.
\end{aligned}
$$
指数関数のマクローリン展開 $e^x=\sum_{n=0}^{\infty}x^n/n!$ に $x=-1$ を入れると、これは $e^{-1}$ です。
$$
\boxed{P(S_T=2)=\frac1e}.
$$
この問題は、もともと $1/e$ をコイン1枚だけで表せないかと考えて作ったものです。
(2)
同じギャンブラーの破産問題について、$i$ から出発して $0$ または $N$ に到達するまでの平均歩数を $E_i$ とすると、$E_i=i(N-i)$ となります。
平均歩数の計算
境界条件は $E_0=E_N=0$ であり、$1\le i\le N-1$ では
$$
E_i=1+\frac{E_{i-1}+E_{i+1}}2
$$
を満たします。したがって $E_{i+1}-2E_i+E_{i-1}=-2$。一般解を $E_i=-i^2+Ai+B$ とおくと、境界条件から $B=0,\ A=N$ なので $E_i=i(N-i)$ です。
$T_r< T$ まで到達したとき、そこから次に最大値か最小値が更新されるまでの平均歩数は、$i=1,\ N=r+2$ として $r+1$ です。また、幅 $r$ まで到達してなお終了していない確率は $p_r=1/(r+1)!$ でした。
したがって、
$$ \begin{aligned} E[T] &=1+\sum_{r=1}^{\infty}p_r(r+1)\\ &=1+\sum_{r=1}^{\infty}\frac1{r!}\\ &=e. \end{aligned} $$
$$ \boxed{E[T]=e}. $$
コインを投げているだけで、成功確率に $1/e$、終了までの平均回数に $e$ が出てくるのはなんか凄いです。
(3)
(1) では、最後にどの幅まで到達するかを場合に分けました。今度は、先の部分を確率のまま残して考えます。
$T_r$ のあと、次の記録更新でそのまま終了する確率は $(r+1)/(r+2)$ です。この場合、$S_{T-1}=S_{T_r}$ です。
一方、終了せずに $T_{r+1}$ まで進む確率は $1/(r+2)$ です。このとき $S_{T_{r+1}}=1-S_{T_r}$ なので、最終的に $S_{T-1}=S_{T_r}$ となる確率は $1-a_{r+1}$ です。
よって、
$$
a_r=\frac{r+1}{r+2}+\frac1{r+2}(1-a_{r+1}),
$$
すなわち、
$$
\boxed{a_r=1-\frac{a_{r+1}}{r+2}}.
$$
(4)
(3) で得た
$$
a_r=1-\frac{a_{r+1}}{r+2}
$$
を使います。$t_r=a_r/(1-a_r)$ とおくと、$1-a_r=a_{r+1}/(r+2)$ なので、
$$
\boxed{t_r=(r+1)+\frac{r+2}{t_{r+1}}}.
$$
したがって、
$$
t_1=
2+\cfrac3{
3+\cfrac4{
4+\cfrac5{
5+\ddots}}}.
$$
まず、この連分数が収束することを確認します。
(3) の式と $0< a_{r+1}<1$ から、
$$
\frac{r+1}{r+2}< a_r<1
$$
です。また、同じ評価を $a_{r+1}$ に使うと $a_{r+1}>(r+2)/(r+3)$ なので、$a_r<(r+2)/(r+3)$ となります。したがって、
$$
r+1< t_r< r+2.
$$
ここで $F_r(x)=r+1+(r+2)/x$ とおくと、$t_r=F_r(t_{r+1})$ です。$x,y\ge r+2$ なら、
$$
|F_r(x)-F_r(y)|
=
\frac{(r+2)|x-y|}{xy}
\le
\frac{|x-y|}{r+2}.
$$
$t_1$ の連分数を有限で打ち切り、一番奥の値を $N+1$ としたものを $\tilde t_1^{(N)}$ とします。先の評価を $r=N$ に適用すると $N+1< t_N< N+2$ なので、実際の $t_N$ と打ち切った値との差は $1$ 未満です。
上の不等式を順に使うと、
$$
|t_1-\tilde t_1^{(N)}|
<
\frac1{3\cdot4\cdots(N+1)}
=
\frac2{(N+1)!}.
$$
右辺は $N\to\infty$ で $0$ に近づくので、$\tilde t_1^{(N)}$ は $t_1$ に収束します。
問題の一般化連分数を同じ位置で打ち切った値は $2+2/\tilde t_1^{(N)}$ です。$t_1>0$ なので、問題の一般化連分数も収束します。
ここで、その値を $C$ とすると、
$$
C=2+\frac2{t_1}.
$$
一方、$t_1=a_1/(1-a_1)$ なので、
$$
C=2+\frac2{t_1}=\frac2{a_1}.
$$
終了時には、成功なら $S_T=2$ なのでその直前は $S_{T-1}=1$、失敗なら $S_T=-1$ なのでその直前は $S_{T-1}=0$ です。
最初に $+1$ が出たあとは $S_{T_1}=1$ なので、$a_1$ はその時点から成功する確率です。全体の成功確率を $q$ とすると、最初に $+1$ が出る確率が $1/2$ なので $q=a_1/2$ です。したがって、
$$
C=\frac2{a_1}=\frac1q.
$$
(1) で $q=1/e$ と求めたので、
$$
\boxed{
2+\cfrac2{
2+\cfrac3{
3+\cfrac4{
4+\cfrac5{
5+\ddots}}}}
=e
}.
$$
この問題を作るまで、$e$ にこんな一般化連分数表示があるのは知りませんでした。とても綺麗です。
雑まとめ
級数と再帰の対応
(1) と (4) では、同じ確率をかなり違う形で扱いました。
$e^{-1}$ のマクローリン展開を途中から切り出して、
$$
U_r=\frac1{(r+1)!}-\frac1{(r+2)!}+\frac1{(r+3)!}-\cdots
$$
とおきます。さらに $b_r=(r+1)!U_r$ とすると、$U_r=1/(r+1)!-U_{r+1}$ なので、
$$
b_r=1-\frac{b_{r+1}}{r+2}.
$$
一方、ランダムウォークから得た $a_r$ も、
$$
a_r=1-\frac{a_{r+1}}{r+2}
$$
という、まったく同じ再帰を満たしていました。
この関係を繰り返すと、
$$
|a_r-b_r|
=
\frac{|a_{r+n}-b_{r+n}|}
{(r+2)(r+3)\cdots(r+n+1)}.
$$
$a_r$ は確率であり、$b_r$ も交代級数から $0< b_r<1$ なので、$n\to\infty$ とすれば $a_r=b_r$ です。したがって、
$$
\boxed{
U_r=\frac{a_r}{(r+1)!}
}.
$$
つまり、$e^{-1}$ の展開で $1/(r+1)!$ から始まる残り $U_r$ は、ランダムウォークで段階 $r$ 以降の終了の仕方を表す確率 $a_r$ と、階乗の係数を除いて一致しています。
さらに、連分数を作るために導入した $t_r=a_r/(1-a_r)$ について、(3) の関係から、
$$
t_r=(r+2)\frac{a_r}{a_{r+1}}
$$
なので、
$$
t_r=\frac{U_r}{U_{r+1}}.
$$
連分数の各段階に現れた $t_r$ は、マクローリン展開の隣り合う二つの残りの比になっています。
(1) では、最後にどの幅まで到達するかで場合分けし、その確率をすべて足したことでマクローリン展開が現れました。一方、(3)(4) では、段階 $r+1$ から先を $a_{r+1}$ という一つの確率のまま残し、その再帰を入れ子にしたことで一般化連分数が現れました。
この対応は、式の上でも同じ操作になっています。級数では先頭の項を取り出した残りを $U_{r+1}$ とし、確率では次の段階以降を $a_{r+1}$ という一つの確率にまとめています。
場合を最後まで展開すれば級数になり、先を再帰のまま残せば連分数になります。
おわりに
同じものに対してたくさんの表現を持てることは、数学の面白いところだと思います。
今回は $1/e$ という答えを先に決めて問題を作りましたが、そこから $E[T]=e$ や一般化連分数まで出てきました。
こうした再帰的な確率の規則を少し変えていくと、また別の数や級数が現れます。このあたりは、もう少しいろいろ試して、次回の記事でまとめるかもしれません。
