確率pで起こる事象が起きるまでの試行回数の期待値~無限等比級数~

今回も競プロネタです。

今回は確率 $p$ で起こる事象が実際に起きるまでの期待値を求めてみましょう！
色々考え方はあると思いますが、無限級数の和を使ってゴリ押します。
必要になったんだけど思い出せなくてパニックになったときのために、覚えておこうと思って記事を書いておきます。

また、競プロ関連の記事は他にも書いています。今後必要なことを拡充していきたいと思いますので参考にしてみて下さい！
→「プログラミングコンテスト」一覧

無限等比級数の復習
確率 $p$ で起こる事象の試行回数の期待値
まとめ

無限等比級数の復習

まずは無限等比級数の公式を復習します。
(等比数列の定義からちゃんと勉強したい人はコチラ: 無限等比級数～収束・発散の条件、例題つき～)

収束のために公比 $r<1$ とし、級数

$\begin{equation} S = \sum_{i = 1}^{\infty}r^i \end{equation}$

を考えます。計算すると以下のようになります。

$\begin{equation} S = \frac{r}{1-r} \end{equation}$

以下、これを求めるための具体的な計算をしていきます。不要な方は飛ばしてください。
部分和

$\begin{equation} S_{n} = \sum_{i = 1}^{n}r^i \end{equation}$

を考えます。これは以下のように簡単に求まります。

$\begin{eqnarray} S_{n} &=& r+r^2+r^3+\cdots + r^n \\ rS_{n} &=& \,\,\,\,\,\,\,\,\,\,\, r^2+r^3+\cdots + r^n+r^{n+1} \end{eqnarray}$

より

$\begin{eqnarray} \left(1-r\right)S_{n} &=& r-r^{n+1} \\ &=& r\left(1-r^n\right) \\ S_{n} &=& \frac{r\left(1-r^n\right)}{1-r} \end{eqnarray}$

あとは $n \to \infty$ の極限を考えると $r<1$ より $r^n \to 0$ なので答えが求まりました。

確率 $p$ で起こる事象の試行回数の期待値

本題です。

今、確率 $p$ で起こる事象を考え、実際に起きるまでの試行回数の期待値を考えることにします。

先に答えを書いてしまうと、求める期待値を $E$ とすれば、

$\begin{equation} E = \frac{1}{p} \end{equation}$

となります。以下これを導出します。
試行回数の取りうる値としては1回から $\infty$ 回まであります。
通常の期待値の定義に従うと、

$\begin{eqnarray} E &=& 1\times p+2\times\left(1-p\right)p+3\times\left(1-p\right)^2 p+\cdots \\ &=& \sum_{k = 1}^{\infty}k\times\left(1-p\right)^{k-1}p \end{eqnarray}$

$k = 1$ とそれ以外で分けると

$\begin{eqnarray} E &=& p+\sum_{k = 2}^{\infty}k\left(1-p\right)^{k-1}p \end{eqnarray}$

2項目の添え字を1から振り直して項をバラすと

$\begin{eqnarray} E &=& p+\sum_{k = 1}^{\infty}\left(k+1\right)\left(1-p\right)^{k} p \\ &=& p+\sum_{k = 1}^{\infty}k\left(1-p\right)^{k} p+\sum_{k = 1}^{\infty}\left(1-p\right)^{k} p \\ &=& p+\left(1-p\right)\sum_{k = 1}^{\infty}k\left(1-p\right)^{k-1} p+\sum_{k = 1}^{\infty}\left(1-p\right)^{k} p \end{eqnarray}$

ここで2項目の総和部分はもともとの期待値の式とそっくり同じですから、 $E$ で置き換えます。

$\begin{eqnarray} E &=& p+\left(1-p\right)E+\sum_{k = 1}^{\infty}\left(1-p\right)^{k} p \end{eqnarray}$

3項目は単なる無限級数の和なので先ほどの公式から簡単に求めることができ、

$\begin{eqnarray} \sum_{k = 1}^{\infty}\left(1-p\right)^{k} p &=& p\times\frac{1-p}{1-\left(1-p\right)} \\ &=& p\times\frac{1-p}{p} \\ &=& 1-p \end{eqnarray}$

以上より、

$\begin{eqnarray} E &=& p+\left(1-p\right)E+\left(1-p\right) \\ &=& 1+\left(1-p\right)E \end{eqnarray}$

整理して

$\begin{equation} E = \frac{1}{p} \end{equation}$

を得ます。

ただ、そりゃそうだよねという感じもしなくありません。
例えば確率 $p = 1/n$ ( $n$ 回試行して1回起こる)で起こる事象は $n$ 回やれば起こる気がするし、 $p = 2/n$ は $n/2$ 回やれば起こりそうですからね。