0. プロローグ

期待値にまつわる有名事実として、以下のことが一般によく知られていて、競プロでも過去何度も出題例がある！！！

確率 $p$ で成功する試行を成功するまで続けたとき、成功するまでの回数の期待値は $\frac{1}{p}$ である
$n$ 個の品物がランダムに出力されるコンプガチャにおいて、コンプできるまでガチャを引く回数の期待値は $n(1 + \frac{1}{2} + \dots + \frac{1}{n})$ で与えられる

これらを統一する統合フレームワークを構築する。以下のことが成り立つ！！！！！！！

$n$ 個のクリアすべきミッションがある。 $n$ 個のミッションの部分集合 $S$ に対して、

$r_{S}$ := 一度のトライにおいて $S$ に含まれるミッションについてはすべて失敗する確率 (他のミッションについては問わない)

とする。このとき、 $n$ 個のミッションがすべて完了するまでのトライ回数の期待値は

$1 + \sum_{S \neq \emptyset} (-1)^{|S|-1} \frac{r_{S}}{1 - r_{S}}$

で与えられる。

1. 一般化になっていることの確認

確率 $p$ のチャレンジ回数 $\frac{1}{p}$ について

特に $n = 1$ とすると、 $S$ として考えられるのは $S = (1)$ のみであり、上の公式にしたがって期待値を求めると

$1 + (-1)^{1 - 1} \frac{1 - p}{1 - (1 - p))} = \frac{1}{p}$

となって一致する。

コンプガチャについて

各 $k$ に対して、 $k$ 個の品物がすべて失敗する確率とは、 $k$ 個の中に「当たり」が含まれない確率なので $\frac{n-k}{n}$ となる。よって求める期待値は

$1 + \sum_{k = 1}^{n} (-1)^{k-1} C(n, k) × \frac{\frac{n-k}{n}}{1 - \frac{n-k}{n}}$
$= 1 + \sum_{k = 1}^{n} (-1)^{k-1} C(n, k) × \frac{n-k}{k}$

となる。割と俄かに信じがたいのだけど、 $n = 1, 2, 3, 4, 5$ で手計算すると確かに合っている^^;;

合っていると思えばこれが $n(1 + \frac{1}{2} + \dots + \frac{1}{n})$ に一致することは数学的帰納法によって示せる (略)。

2. 証明

まずこの記事にも書いた通り、「成功するまでの回数の期待値」は、

$Q_k$ := 成功までに $k$ 回以上かかる確率

として $E = 1 + Q_2 + Q_3 + \dots$ と表せることを利用する。 $k = 2, 3, \dots$ に対して $Q_k$ を求める。 $Q_k$ を言い換えると

$k-1$ 回目までには少なくとも 1 つのミッションはクリアしない確率

となる。これは包除原理により、

(1 個以上を $k-1$ 回目までにクリアしない確率)
-(2 個以上を $k-1$ 回目までにクリアしない確率)
+(3 個以上を $k-1$ 回目までにクリアしない確率)
-(4 個以上を $k-1$ 回目までにクリアしない確率)
+(5 個以上を $k-1$ 回目までにクリアしない確率)

という感じになる。すなわち、ミッションの部分集合をなす各 $S$ に対して

$r_{S}$ := 一度のトライで $S$ に含まれるミッションについてはすべて失敗する確率

とおくと、

$Q_k = \sum_{S \neq \emptyset} (-1)^{|S|-1} r_{S}^{k-1}$

となる。ゆえに求める期待値は

$E = 1 + Q_2 + Q_3 + \dots$
$= 1 + \sum_{k = 2}^{\infty} \sum_{S \neq \emptyset} (-1)^{|S|-1} r_{S}^{k-1}$
$= 1 + \sum_{S \neq \emptyset} \sum_{k = 2}^{\infty} (-1)^{|S|-1} r_{S}^{k-1}$
$= 1 + \sum_{S \neq \emptyset} (-1)^{|S|-1} \frac{r_{S}}{1 - r_{S}}$