[Σ]Sukarabe's Easy Living: ある期待値の問題(４)

« Kramnik vs Deep Fritz 戦、今日スタート | メイン | レンタル・サーバーの更新 »

2006年11月25日（土曜日）

ある期待値の問題(４) [ 数学 ]

以前、この問題の離散近似バージョンを作ったことがあるのだが、X+Yの密度関数がconvolutionになることに示唆されて、離散バージョンの別の解法を思いついた。

$n$ を正の整数として、 $n$ 個の数 $\frac{1}{n}$ , $\frac{2}{n}$ , $\ldots$ , $\frac{n}{n}$ からランダムに一つの数を選ぶ操作を考える。この操作を繰り返すとき、引いた数の和が初めて1を超えるまでの回数の期待値を求めよ、というのが離散近似バージョンになる。

連続バージョンからのアナロジーにより、 $1\leq k\leq n$ なる整数 $k$ に対して、最初の $r$ 回の和が $\frac{k}{r}$ 以下となる確率 $q_r(k)$ を考える。ここで、 $i$ 回目に引いた数を表す確率変数を $X_i$ とすれば、まず、
$q_1(k)=P\left( X_1\leq \frac{k}{n} \right) = \frac{k}{n}$
となる。次に、
$q_2(k)=P\left( X_1+X_2 \leq \frac{k}{n} \right) =\sum_{j=1}^{k} \frac{1}{n}\cdot\frac{k-j}{n} =\frac{k(k-1)}{2n^2}$
となる。ここで、離散変数についてのコンボリューションが出てきている。これを繰り返すと、一般に
$q_r(k)=P\left( X_1+X_2+\cdots+X_r \leq \frac{k}{n} \right) = \frac{_k{\rm C}_r}{n^r}$
となるだろう。多分・・・。ちゃんと計算してないけど、パスカルの三角形の性質から階差に書けるから、帰納法で示せると思う。

すると、これも連続バージョンと同様に、和が初めて $\frac{k}{n}$ を超えるまでの回数の期待値 $E(k)$ は
$E(k)=\sum \frac{_k{\rm C}_r}{n^r} = \left(1+\frac{1}{n} \right)^{k}$
のようになるのではなかろうか。だんだん自信なくなってきた(苦笑)。いや、 $k=n$ の場合、つまり、初めて和が１を超えるまでの回数の期待値が
$\left(1+\frac{1}{n} \right)^{n}$
になることは別の方法でチェック済みなのであるが。