- 確率$0 < p < 1$で成功する試行を成功するまで繰り返すときの試行回数の期待値は$1/p$.
- 確率$p$の$n$種類の当たりくじを全て当てるまでの試行回数の期待値は$\displaystyle \frac{1}{p}\sum_{k=1}^{n}\frac{1}{k}$.
$n$種類の場合に拡張することも簡単です.これは,簡単なコンプガチャの問題に相当します.
【関連記事】
- [A]条件付き期待値の計算例 - Notes_JP
- [B]確率分布 - Notes_JP:初めて成功するまでの回数は,幾何分布に従う.
事象が起こるまでの試行回数
まずは,問題設定を整理します.$k$回で終了する場合は「$k-1$回失敗し,最後の1回で成功する」ということなので,その確率は$(1-p)^{k}p$です.
したがって,試行回数の期待値は
\sum_{k=1}^{\infty} k (1-p)^{k-1} p
\end{aligned}
以下では,いくつかの異なる方法で,この期待値が$1/p$になることを確かめます.
直感的には?
成功するまでのの期待値は,成功するまでの平均回数ということです.例えば,「確率$1/10$のくじを平均何回引いたら当たるか?」を考えると10回が答えになりそうです.
同様に,確率$p$のくじなら「$p\times$ (平均回数) = 1」が成り立ちそうなので,「(平均回数) =$1/p$」となりそう,と直感的に予想できます.
※ しかし,特に確率・統計の分野では,人の直感に反する例がよく現れるので注意が必要です!
等比級数的な計算
無限級数を,等比級数の和を求めるのと類似の方法で計算します.$S_{n}$を
S_{n}
=\sum_{k=1}^{n} k (1-p)^{k-1} p
\end{aligned}
$S_{n}$に対して,等比級数の和を求めるのと同じ操作をすると,
&S_{n} - (1-p)S_{n} \\
&=p\Biggl[\sum_{k=1}^{n-1}(1-p)^{k-1} - n(1-p)^{n} \Biggr]
\end{aligned}
$n\to\infty$で,(左辺)$\to p S$です.右辺第1項は等比級数の和で$|1-p| < 1$より
\frac{1}{1- (1-p)}=\frac{1}{p} \quad (n\to\infty),
\end{aligned}
na^{n} &= ne^{n\log a} \\
&= (n|\log a|) e^{- n |\log a|} /|\log a| \\
&\to 0 \quad (n\to\infty)
\end{aligned}
以上より,$pS = 1$,すなわち
S = 1/p
\end{aligned}
【補足】
正項級数$\sum_{k=1}^{\infty} k (1-p)^{k-1} p$が収束するかだけを知りたい場合,ダランベールの収束判定法(ratio test)
\frac{(k+1) (1-p)^{k} p}{k (1-p)^{k-1} p}
&=(1+1/k)(1-p) \\
&\to 1-p < 1 \quad(k\to \infty)
\end{aligned}
【参考記事】
微分を使った計算
計算に慣れていると,$k (1-p)^{k-1} = -\dfrac{\mathrm{d}}{\mathrm{d}p}(1-p)^{k} $に気づきます.そこで,&\sum_{k=1}^{\infty} k (1-p)^{k-1} p \\
&=\sum_{k=1}^{\infty} \biggl[-\frac{\mathrm{d}}{\mathrm{d}p}(1-p)^{k} \biggr] p \\
&=-p \frac{\mathrm{d}}{\mathrm{d}p}
\underbrace{\biggl[\sum_{k=1}^{\infty} (1-p)^{k} \biggr]}_{=\frac{1-p}{1-(1-p)}} \\
&=-p \frac{\mathrm{d}}{\mathrm{d}p} \biggl(\frac{1}{p} - 1\biggr) \\
&= \frac{1}{p}
\end{aligned}
【補足】
微分とlimを入れ替えて良いことは,べき級数$\sum_{k=1}^{\infty} z^{k}$が収束半径内($|z| < 1$)で広義一様収束することからわかります.微積分や複素関数論の本には大体載っていると思います(例えば,文献[2] 8.1 Theorem, 文献[3] 定理4.21).
【参考記事】
条件付き期待値による計算
条件付き期待値(+直感)を使うと,計算量をかなり減らすことができます.以下では,$k$回目に初めて成功する確率を
P(\text{$k$回目に初成功})
=(p-1)^{k} p
\end{aligned}
確率変数$X(\omega)=$(初めて成功した回数$k$)に対して
E[X]
&=\sum_{k=1}^{\infty} k P(\text{$k$回目に初成功}) \\
&=E[X| \text{1回目成功}]\cdot P(\text{1回目に初成功}) \\
& \qquad + E[X| \text{1回目失敗}]\cdot P(\text{1回目失敗})
\end{aligned}
ここで,直感的には
- 1回目で成功すれば,成功するまでの回数は1回なので,$E[X| \text{1回目成功}] = 1$
- 1回目で失敗すれば,1回試行を行うことは確定で,2回目は初期状態に戻っただけなので,$E[X| \text{1回目失敗}]=1 + E[X]$
E[X]
&=E[X| \text{1回目成功}]\cdot P(\text{1回目に初成功}) \\
& \qquad + E[X| \text{1回目失敗}]\cdot P(\text{1回目失敗}) \\
&=1\cdot p + (1 + E[X])\cdot (1-p) \\
&=1+(1-p)E[X]
\end{aligned}
E[X] = 1/p
\end{aligned}
以下で,直感とした部分を,(もう少し厳密な)計算でも確かめておきます.
①1回目に成功したときの条件付き期待値は
&E[X | \text{1回目成功}] \\
&=\sum_{k=1}^{\infty} k P(\text{$k$回目に初成功}| \text{1回目成功})
\end{aligned}
& P(\text{$k$回目に初成功}| \text{1回目成功}) \\
&=
\begin{cases}
\, 1 & (k=1)\\
\, 0 & (k\neq 1)
\end{cases}
\end{aligned}
E[X| \text{1回目成功}]
&=1
\end{aligned}
②1回目に失敗したときの条件付き期待値は
&E[X| \text{1回目失敗}] \\
&=\sum_{k=1}^{\infty} k P(\text{$k$回目に初成功}| \text{1回目失敗})
\end{aligned}
& P(\text{$k$回目に初成功}| \text{1回目失敗}) \\
&=
\begin{cases}
\, 0 & (k=1)\\
\, P(\text{$k-1$回目に初成功}) & (k\neq 1)
\end{cases}
\end{aligned}
&E[X| \text{1回目失敗}] \\
&=\sum_{k=2}^{\infty} k P(\text{$k-1$回目に初成功}) \\
&=\sum_{k=1}^{\infty} (k+1) P(\text{$k$回目に初成功}) \\
&=\sum_{k=1}^{\infty}P(\text{$k$回目に初成功}) \\
& \quad + \sum_{k=1}^{\infty} k P(\text{$k$回目に初成功}) \\
&=1 + E[X]
\end{aligned}
【参考記事】
コンプガチャ
確率$p$の$n$種類の試行を全て成功するまで繰り返すとき,試行回数の期待値は\frac{1}{p}\sum_{k=1}^{n}\frac{1}{k}
&=\frac{1}{p}\biggl(1+\frac{1}{2}+\frac{1}{3}+ \cdots + \frac{1}{n}\biggr)
\end{aligned}
【証明】
具体的に確率変数を構成することはせずに,イメージ重視で説明します.
期待値を求める確率変数は
&X(\omega) \\
&=(\text{事象$\omega$で$1\sim n$が当たるまでの回数}) \\
&=(\text{$1\sim n$コ目が当たるまでの回数}) \\
&=(\text{$1\sim (n-1)$コ目が当たるまでの回数}) \\
&\quad +(\text{←のあと$n$コ目が当たるまでの回数}) \\
&=(\text{$1$コ目が当たるまでの回数}) \\
&\quad +(\text{←のあと$2$コ目が当たるまでの回数}) \\
&\quad + \cdots \\
&\quad +(\text{←のあと$n$コ目が当たるまでの回数})
\end{aligned}
よって,$X$の期待値は
&E[X] \\
&=E[\text{$1$コ目が当たるまでの回数}] \\
&\quad + E[\text{←のあと$2$コ目が当たるまでの回数}] \\
&\quad + \cdots \\
&\quad + E[\text{←のあと$n$コ目が当たるまでの回数}]
\end{aligned}
ここで,上の結果から
- 1コ目が当たる確率は$np$なので,当たるまでの試行回数の期待値は$1/np$.
- 2コ目が当たる確率は$(n-1)p$なので,当たるまでの試行回数の期待値は$1/(n-1)p$.
- ・・・
- $(n-1)$コ目が当たる確率は$2p$なので,当たるまでの試行回数の期待値は$1/2p$.
- $n$コ目が当たる確率は$p$なので,当たるまでの試行回数の期待値は$1/p$.
E[X]
&=\frac{1}{np} + \frac{1}{(n-1)p} + \cdots \frac{1}{2p} + \frac{1}{p}\\
&=\frac{1}{p}\sum_{k=1}^{n}\frac{1}{k}
\end{aligned}
【参考記事】
- コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語
- Editorial - AtCoder Beginner Contest 194
- 「〜がすべて終わるまでの試行回数の期待値」を求める一般的なフレームワーク - けんちょんの競プロ精進記録
参考文献/記事
各項目ごとに参考にしたものは,それぞれの項目のの末尾に記載しました.ここでは,記事全般で参考にしたものを載せます.【全般】
- [1]確率論 (伊藤 清)
- [2]Principles of Mathematical Analysis (Walter Rudin)
- [3]微分積分学 (笠原 晧司)
- 条件付期待値 - Wikipedia
【AtCoderでの利用例】
*1:$e^{x} > x^{n+1}/(n+1)!$から簡単に示せる.例えば参考文献[2](Rudin) 8.6 Theorem.