期待値の問題
問題
お仕事でこのような再帰関数を見ることがありました1。
def f(x)
t = rand()
if t > x
1 + f(t)
else
1
end
end
puts f(0)
気持ちとしてはこのような感じです。
(1) 0 以上 1 以下の実数の乱数を発生させる。
(2) その値が前に発生させた値 (初回は 0) より大きければ (1) に戻る。そうでなければ終了する。
このとき、f(0)
を実行したときに f
が呼ばれる回数、つまり f(0)
の値であり乱数を発生させる回数の期待値はいくらでしょうか?
解いてみる
とりあえず実験するとこのようになります。
irb(main):003:0> srand(42); n=1_000_000; n.times.map { f(0) }.sum.to_f / n
=> 2.716906
irb(main):004:0> srand(42); n=10_000_000; n.times.map { f(0) }.sum.to_f / n
=> 2.718093
irb(main):005:0> srand(42); n=100_000_000; n.times.map { f(0) }.sum.to_f / n
=> 2.71832571
$2.71832571$ という値が出てきました。なんだか見覚えのある数ですが、解析的に解いてみます。
rand
を $2$ 回呼んで後の方が大きい確率は $1/2$ です。同じように考えると、試行が $n$ 回以上続く確率は rand
を $n-1$ 回呼んでそれらの戻り値が昇順になる確率なので $1/(n-1)!$ です。なので、ちょうど $n$ 回となる確率は $1/(n-1)! - 1/n!$ です。したがって、求める期待値は次のような無限級数の和となります2。
$$ \sum_{n=1}^{\infty} n \left( \frac{1}{(n-1)!} - \frac{1}{n!} \right). $$
計算してみると…
$$ \begin{align*} \sum_{n=1}^{\infty} n \left( \frac{1}{(n-1)!} - \frac{1}{n!} \right) &= \sum_{n=2}^{\infty} n \left( \frac{1}{(n-1)!} - \frac{1}{n!} \right) \\ &= \sum_{n=2}^{\infty} \frac{n(n-1)}{n!} \\ &= \sum_{n=2}^{\infty} \frac{1}{(n-2)!} \\ &= \sum_{n=0}^{\infty} \frac{1}{n!} \\ &= e. \end{align*} $$
ということで、なんと $e$ となりました。実験で出てきた値とも一致します。このような計算は学生のときぶりなので Wolfram Alpha で確かめてみても、やはり $e$ となるので間違いなさそうです。なんとも不思議なものです。
これ以上のオチは無いのですが、偶然にも面白い極限に出会ったので記事にしたのでした。