確率が苦手なのを放置していたら刺されたので書いた。

普通のさいころ

$6$面を持ちそれらが等確率で出るさいころである。 このとき、結論としては$14.7$回がその期待値である。

まずはさいころを降り続けて1の目が出るまでにかかる回数の期待値を考えよう。 これは$6$回である。 直感的な説明としては、さいころを$1$回振るたびに1の目は$\frac{1}{6}$個出るので、合計$1$個でるには$6$回振る必要があるから、である。

さてこの期待値を計算しよう。 期待値$E = \frac{1}{6} + 2 \cdot \frac{1}{6} \cdot \frac{5}{6} + 3 \cdot \frac{1}{6} \cdot (\frac{5}{6})^2 + 4 \cdot \frac{1}{6} \cdot (\frac{5}{6})^3 + \dots$である。 $k$回目に始めて1が出るような確率は$\frac{1}{6} \cdot (\frac{5}{6})^{k-1}$であり、これにその重み$k$を掛けたものを全て足している。 この無限和$E = \frac{1}{6} \cdot \Sigma_{k=1}^{\infty} (k \cdot (\frac{5}{6})^{k-1})$はなんらかの実数に収束する。 この収束性は、線形的に増える$k$より指数的に減る$(\frac{5}{6})^{k-1}$のほうが強いから、としてここでは認めるものとする。 まじめに計算することもできるが、$E = \frac{1}{6} + \frac{5}{6} \cdot (1 + E)$とすれば$E = 6$。

一般に確率$p$で起こるものが起こるまで試行し続けるとき、その回数の期待値$E = \Sigma_{k=1}^{\infty} kp(1-p)^{k-1} = \frac{1}{p}$である。

$6$面全てがでるまでの回数の期待値を考えよう どの目も等確率で出るので目の数字は区別する必要はなく、まだ出ていない面の数だけを気にすればよいことを使う。 残り$1$種類の目だけがまだ出ていないときから始めて全て出るまでの回数の期待値$E_1$は、目1が出るまでのそれと等しいので、$E_1 = 6$である。 同様に、残り$2$種類の目だけがまだ出ていないときの$E_2$は、まだ出ていない目のひとつが出るまでの回数$\Sigma_{k=1}^{\infty} k\frac{2}{6}(\frac{4}{6})^{k-1} = (\frac{2}{6})^{-1} = 3$と、それ以降に振る必要のある回数$E_1 = 6$より、$E_2 = 9$。 同様に、$E_3 = (\frac{3}{6})^{-1} + E_2 = 2 + E_2 = 11$、$E_4 = 1.5 + E_3 = 12.5$、$E_5 = 1.2 + E_3 = 13.7$、$E_6 = 1 + E_5 = 14.7$である。 よって、期待値は$14.7$回。

一般化されたさいころ

さいころの面が$k$個あり、それぞれの出る確率$p_k$が必ずしも一様でない場合を考えよう。

$X$をまだ出ていない面の集合としそれらが全て出るまでの振る回数の期待値$e_X$を再帰的に計算する。 面の集合の部分集合$X$に対しても$p_X$を定義して、$e_X = (p_X + 2 p_X (1 - p_X) + 3 p_X (1 - p_X)^2 + 4 p_X (1 - p_X)^3 + \dots) + \Sigma_{y \in X} \frac{p_y}{p_X} e_{X \setminus \{y\}} = \frac{1}{P_X} + \Sigma_{y \in X} \frac{p_y}{p_X} e_{X \setminus \{y\}}$である。 $\frac{1}{P_X}$に収束する無限級数はまだ出ていない面が出るまでに振る回数を表し、続く$\Sigma_{y \in X} \frac{p_y}{p_X} e_{X \setminus \{y\}}$はその後に振る回数を表す。$P_X$として表現されていた新しく出る面を、$\frac{p_y}{P_X}$により切り分けている。

これを計算機で計算する際はbit-DPを回すことになるだろう。

注意であるが、期待値$e_X$の$X$はまだ出ていない面の集合であり、$e_X$はそのような出目の状況から初めそれらが全て出るまでに振る回数の期待値である。 もしこれを、$X$はすでに出た面の集合であり、$e_X$はそのような出目の状況から始め残りが全て出るまでに振る回数の期待値であると定義してしまうと、そのような出目の状況が発生する確率$q_X$も計算に使いたくなってしまう。本質的な差はないが、理由がなければ前者を考えるべきだろう。

実装

仕様: さいころの面の数$k \ge 1$、$i$番目の面がでる確率$\frac{a_i}{\Sigma_j a_j}$が標準入力から以下のように与えられる。このとき全ての目が出るまでさいころを振り続けたとき、振る回数の期待値を標準出力に出力する。

k
a_0 a_1 ... a_{k-1}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
double sq(double x) { return x * x; }
int main() {
    int k; cin >> k;
    vector<int> a(k); repeat (i,k) cin >> a[i];
    // calc
    int sum_a = accumulate(a.begin(), a.end(), 0);
    vector<double> p(k); repeat (i,k) p[i] = a[i] /(double) sum_a;
    vector<double> dp(1<<k);
    repeat_from (s,1,1<<k) {
        double p_s = 0;
        repeat (i,k) if (s & (1<<i)) {
            p_s += p[i];
        }
        dp[s] += 1 / p_s;
        repeat (i,k) if (s & (1<<i)) {
            int t = s & ~ (1<<i);
            dp[s] +=  (p[i] / p_s) * dp[t];
        }
    }
    // output
    printf("%.12lf\n", dp[(1<<k)-1]);
    return 0;
}