事象が起こるまでの試行回数

POINT

  • 確率$0 < p < 1$で成功する試行を成功するまで繰り返すときの試行回数の期待値は$1/p$.
  • 確率$p$の$n$種類の当たりくじを全て当てるまでの試行回数の期待値は$\displaystyle \frac{1}{p}\sum_{k=1}^{n}\frac{1}{k}$.

様々な計算方法があります.中でも,条件付き期待値による方法は,直感を利用して計算を省略できるメリットがあります.

$n$種類の場合に拡張することも簡単です.これは,簡単なコンプガチャの問題に相当します.
【関連記事】

事象が起こるまでの試行回数

まずは,問題設定を整理します.
問題
確率$0 < p < 1$で成功する試行を成功するまで繰り返し,成功した時点で終了する.このとき,終了するまでの試行回数の期待値は?

$k$回で終了する場合は「$k-1$回失敗し,最後の1回で成功する」ということなので,その確率は$(1-p)^{k}p$です.

したがって,試行回数の期待値は

\begin{aligned}
\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}$を

\begin{aligned}
S_{n}
=\sum_{k=1}^{n} k (1-p)^{k-1} p
\end{aligned}
で定めると,求める期待値は$\displaystyle S = \lim_{n\to\infty}S_{n}$です.

$S_{n}$に対して,等比級数の和を求めるのと同じ操作をすると,

\begin{aligned}
&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$としたときの各項が計算できれば,期待値$\displaystyle S = \lim_{n\to\infty}S_{n}$がわかります.

$n\to\infty$で,(左辺)$\to p S$です.右辺第1項は等比級数の和で$|1-p| < 1$より

\begin{aligned}
\frac{1}{1- (1-p)}=\frac{1}{p} \quad (n\to\infty),
\end{aligned}
右辺第2項は$n\to\infty$でゼロになります.これは,例えば任意の自然数$n$に対して$\displaystyle \lim_{x\to \infty} x^{n}e^{-x}=0$であること(*1)を知っていれば,$|a| < 1$に対し
\begin{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$,すなわち

\begin{aligned}
S = 1/p
\end{aligned}
が示せました.//

【補足】
正項級数$\sum_{k=1}^{\infty} k (1-p)^{k-1} p$が収束するかだけを知りたい場合,ダランベールの収束判定法(ratio test)

\begin{aligned}
\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}
で確認できます(【正項級数】収束判定法と例 - Notes_JP).

【参考記事】

微分を使った計算

計算に慣れていると,$k (1-p)^{k-1} = -\dfrac{\mathrm{d}}{\mathrm{d}p}(1-p)^{k} $に気づきます.そこで,
\begin{aligned}
&\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$回目に初めて成功する確率を

\begin{aligned}
P(\text{$k$回目に初成功})
=(p-1)^{k} p
\end{aligned}
と表します.

確率変数$X(\omega)=$(初めて成功した回数$k$)に対して

\begin{aligned}
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}
が成り立ちます(関連記事[A]).ここで,$E[X | A]$は事象$A$が起きたときの$X$の条件付き期待値を表します.

ここで,直感的には

  • 1回目で成功すれば,成功するまでの回数は1回なので,$E[X| \text{1回目成功}] = 1$
  • 1回目で失敗すれば,1回試行を行うことは確定で,2回目は初期状態に戻っただけなので,$E[X| \text{1回目失敗}]=1 + E[X]$
が成り立ちます.これを認めれば
\begin{aligned}
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]$について解けば
\begin{aligned}
E[X] = 1/p
\end{aligned}
が得られます.//


以下で,直感とした部分を,(もう少し厳密な)計算でも確かめておきます.


①1回目に成功したときの条件付き期待値は

\begin{aligned}
&E[X | \text{1回目成功}] \\
&=\sum_{k=1}^{\infty} k P(\text{$k$回目に初成功}| \text{1回目成功})
\end{aligned}
です.ここで
\begin{aligned}
& P(\text{$k$回目に初成功}| \text{1回目成功}) \\
&=
\begin{cases}
\, 1 & (k=1)\\
\, 0 & (k\neq 1)
\end{cases}
\end{aligned}
なので,
\begin{aligned}
E[X| \text{1回目成功}]
&=1
\end{aligned}
です.

②1回目に失敗したときの条件付き期待値は

\begin{aligned}
&E[X| \text{1回目失敗}] \\
&=\sum_{k=1}^{\infty} k P(\text{$k$回目に初成功}| \text{1回目失敗})
\end{aligned}
となります.ここで
\begin{aligned}
& P(\text{$k$回目に初成功}| \text{1回目失敗}) \\
&=
\begin{cases}
\, 0 & (k=1)\\
\, P(\text{$k-1$回目に初成功}) & (k\neq 1)
\end{cases}
\end{aligned}
なので,
\begin{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$種類の試行を全て成功するまで繰り返すとき,試行回数の期待値は
\begin{aligned}
\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}
となります.
【証明】
具体的に確率変数を構成することはせずに,イメージ重視で説明します.

期待値を求める確率変数は

\begin{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$の期待値は

\begin{aligned}
&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$.
がわかります.よって,上式に代入すれば
\begin{aligned}
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}
となります.//


【参考記事】

参考文献/記事

各項目ごとに参考にしたものは,それぞれの項目のの末尾に記載しました.ここでは,記事全般で参考にしたものを載せます.
【全般】

【AtCoderでの利用例】

*1:$e^{x} > x^{n+1}/(n+1)!$から簡単に示せる.例えば参考文献[2](Rudin) 8.6 Theorem.