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

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

math.stackexchange.com

I heard this problem, so I might be missing pieces. Imagine there are two cities separated by a very long road. The road has only one lane, so cars cannot overtake each other. $N$ cars are released from one of the cities, the cars travel at constant speeds $V$ chosen at random and independently from a probability distribution $P(V)$ . What is the expected number of groups of cars arriving simultaneously at the other city?

P.S.: Supposedly, this was a Princeton physics qualifier problem, if that makes a difference.

要は，

Car Convoy Problem の条件で，全部で $N$ 台の車があったときの車列の数 $M$ の期待値 $C(N)=\mathsf{E}(M)$ を求めよ

という問題．最初はこちらの問題を考えていた．

期待値 $\mathsf{E}(M)$ は受験数学で基本の「漸化式を作る」である． $N$ 台のときの車列の長さの期待値 $\mathsf{E}(M)$ を $m_N$ とするとき，一番速い車が 1台増えたとすると，それが先頭にあるとき(確率 $\dfrac{1}{N+1}$ )には車列の長さは1増えて，それ以外のときは車列の長さは増えないので，
$m_{N+1}=m_N+\dfrac{1}{N+1}$
が成立する． $L_1=1$ であるから，
$\mathsf{E}(M)$ $=m_N=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots +\dfrac{1}{N}$ $=\displaystyle\sum_{i=1}^N \dfrac{1}{i}$
となる．

参照した web page のAditya Bansai による解答と同じ考え方である．この値は調和数(harmonic number)である．

ja.wikipedia.org

調和数 $H_N$ は、 $\log N+\gamma$
（ $\gamma=0.57721\cdots$ はオイラーの定数）
と近似できるので，
$C(N)\approx \log N+\gamma$
が言え，
$\dfrac{C(N)}{\log N}\to 1(N\to\infty)$
が成立する．

調和数がクーポンコレクター問題で登場するので，Car Convoy Problem も対応づけることができるかと考えたが、よくわからない。またシープ問題にも調和数が登場するそうだ。
クーポンコレクター問題 - Wikipedia

Jeep problem - Wikipedia

エレガントだったのは，Andre Nicolas の

確率変数 $X_i$ を， $i$ 台目の車が前の全ての車よりも遅い場合 $1$ ，そうでない場合は $0$ という値をとるように定めると $\mathsf{P}(X_i=1)=\dfrac{1}{i}$ を利用して $\mathsf{E}(X_i)=\dfrac{1}{i}$ だから，車列の数 $M$ の期待値は
$\mathbf{E}(M)$ $=\mathsf{E}(X_1+X_2+\cdots+X_N)$ $=\mathsf{E}(X_1)+\mathsf{E}(X_2)+\cdots +\mathsf{E}(X_N)$ $=\displaystyle\sum_{i=1}^N \dfrac{1}{i}$

とう解法．自然だ．

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