期待値の問題

問題

お仕事でこのような再帰関数を見ることがありました¹。

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!$ です。したがって、求める期待値は次のような無限級数の和となります²。

$$ \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$ となるので間違いなさそうです。なんとも不思議なものです。

これ以上のオチは無いのですが、偶然にも面白い極限に出会ったので記事にしたのでした。