https://spherical-harmonics.hatenablog.com/entry/2022/04/15/232104

Car Convoy Problem（その3） - 球面倶楽部零八式 mark II
の続き

$M$ 番目の車列の長さが $1$ となる確率が $\dfrac{1}{2^M}$ であることを示せ．

Car Convoy Problem（その2） - 球面倶楽部零八式 mark II
で導入した確率変数を用いよう．

確率変数 $X_i$ を， $i$ 台目の車が前の全ての車よりも遅い場合 $1$ ，そうでない場合は $0$ という値をとるように定めると
$\mathsf{P}(X_i=1)=\dfrac{1}{i}$ ， $\mathsf{P}(X_i=0)=\dfrac{i-1}{i}$
である．

(i) 1番目の車列の長さが1となる場合は $X_1=1$ かつ $X_2=1$ だから，その確率は $\mathsf{P}_1=1\cdot\dfrac{1}{2}=\dfrac{1}{2}$

(ii) $a_2$ 台目の車が $2$ 番目の車列となり，その長さが $1$ となる場合は
$X_2+\cdots +X_{a_2}=1$ かつ $X_{a_2}=X_{a_2+1}=1$
であるから，その確率は
$\mathsf{P}_2=1\cdot\dfrac{1}{2}\cdot\dfrac{2}{3}\cdots\dfrac{a_2-2}{a_2-1}\cdot\dfrac{1}{a_2}\cdot\dfrac{1}{a_2+1}$
$=\dfrac{1}{(a_2-1)a_2(a_2+1)}$ $=\dfrac{1}{2}\left\{\dfrac{1}{(a_2-1)a_2}-\dfrac{1}{a_2(a_2+1)}\right\}$
となるので，これを $a_2=2$ から無限大まで加えると $\dfrac{1}{4}$

(iii) $a_3$ （ $\geqq 3$ ）台目の車が $3$ 番目の車列となり，その長さが $1$ となる場合について考える．

1番目の車列の先頭は1である．2番目の車列の先頭が $a_2$ であり，3番目の車列の先頭が $a_3$ となる確率は
$\dfrac{1}{a_2-1}\cdot\dfrac{1}{(a_3-1)a_3(a_3+1)}$
であるから，求める確率は
$\mathsf{P}_3=\displaystyle\sum_{2\leqq a_2\lt a_3}\dfrac{1}{a_2-1}\cdot\dfrac{1}{(a_3-1)a_3(a_3+1)}$
$=\displaystyle\sum_{a_2=2}^{\infty}\dfrac{1}{a_2-1}\left(\sum_{a_3=a_2+1}^{\infty}\dfrac{1}{(a_3-1)a_3(a_3+1)}\right)$
$=\dfrac{1}{2} \displaystyle\sum_{a_2=2}^{\infty}\dfrac{1}{a_2-1}\cdot\dfrac{1}{a_2(a_2+1)}$ $=\dfrac{1}{2}\mathsf{P}_2$ $=\dfrac{1}{2}\cdot\dfrac{1}{4}$ $=\dfrac{1}{8}$

(iv) $a_M$ （ $\geqq M$ ）台目の車が $M$ 番目の車列となり，その長さが $1$ となる場合について考える．

1番目の車列の先頭は $a_1=1$ である． $m$ ( $2\leqq m\leqq M-1$ )番目の車列の先頭が $a_m$ であり， $M$ 番目の車列の先頭が $a_M$ となる確率は
$\dfrac{1}{a_2-1}\cdot\dfrac{1}{a_3-1}\cdot\cdots\cdot \dfrac{1}{a_{M-1}-1}\cdot\dfrac{1}{(a_M-1)a_M(a_M+1)}$
であるから，求める確率は
$\displaystyle\sum_{2\leqq a_2\lt a_3\lt\cdots\lt a_{M-1}\lt a_M}\dfrac{1}{a_2-1}\cdot\dfrac{1}{a_3-1}\times\cdots\times \dfrac{1}{a_{M-1}-1}\times\dfrac{1}{(a_M-1)a_M(a_M+1)}$
$=\displaystyle\sum_{2\leqq a_2\lt a_3\lt\cdots\lt a_{M-1}}\dfrac{1}{a_2-1}\cdot\dfrac{1}{a_3-1}\times\cdots\times \dfrac{1}{a_{M-1}-1}\left(\sum_{a_M=a_{M-1}+1}^{\infty}\dfrac{1}{(a_M-1)a_M(a_M+1)}\right)$
$=\dfrac{1}{2}\displaystyle\sum_{2\leqq a_2\lt a_3\lt\cdots\lt a_{M-1}}\dfrac{1}{a_2-1}\cdot\dfrac{1}{a_3-1}\times\cdots\times \dfrac{1}{a_{M-1}-1}\cdot\dfrac{1}{a_{M-1}}\cdot\dfrac{1}{a_{M-1}+1}$
$=\dfrac{1}{2}\textsf{P}_{M-1}$ $=\dfrac{1}{2^2}\textsf{P}_{M-2}$ $=\cdots$ $=\dfrac{1}{2^{M-3}}\textsf{P}_{3}$ $=\dfrac{1}{2^M}$

Car Convoy Problem は

作者:Williams, David
Cambridge University Press

の p.103 にあることを教えてもらって考え始めた。この本には既に解いた

・1番目の車列の長さが $n$ となる確率を求めよ
・1番目の車列の長さの期待値が無限大となることを示せ
・ $M$ 番目の車列の長さが1となる確率が $\dfrac{1}{2^M}$ となることを示せ
・最初の $N$ 台からできる車列の個数を $C(N)$ とするとき， $\dfrac{C(N)}{\log N}\to 1(N\to\infty)$ を示せ．以外に

$K$ 回のシミュレーションにおける1番目の車列の長さの平均値 $A_1(K)$ について　 $K\to\infty$ で $A_1(K)\to+\infty$ となることが確率1で起こることを示せ

いう問題があるが，これは1番目の車列の長さの期待値が無限大となることとボレル・カンテリの第二補題から従う．

Car Convoy Problem（その5） - 球面倶楽部零八式 mark II