やりません。代わりにこれにかかるお時間を数学で推定しましょう。　

問題設定

とりあえず知りたいのは期待値ですよね。というわけで、次のような問題を考えます:

問題　ファイターの総数 $N (= 88)$、各ファイター $i$ が対戦相手になる確率 $p _ i$ 、各ファイター $i$ への勝率 $q _ i$ が与えられます。このとき、全ファイターに少なくとも 1 勝するまでの対戦数 $X$ の期待値 $\mathbb{E}[X]$ を計算せよ。

しかしよく考えるとわざわざ VIP に潜っておいて負けるなんて、そんな無駄なことをみなさまはしませんから、$q _ i = 1$ と仮定します。 ……というのは冗談として、$p _ i q _ i$ を改めて $p _ i$ とおくことでほぼ元の問題に帰着するので、ここではあまり本質と考えず、$q _ i = 1$ であると仮定しましょう。もちろんこれによって $\sum _ i p _ i \neq 1$ になってしまうことがありますが、これは一定確率で「マッチング失敗」になるのと同値ですから、たとえば期待値はスケーリングするだけでできます。

簡単な場合: $p$ が一様分布の場合

有名ですね。期待値は $N \left ( 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 N \right) \sim N \log N$ です。

たとえば $N = 88$ の場合は 445.2996712279478 になります。

一般の場合: 包除原理で O(2ᴺ ⋅ N) 時間

ファイター $i$ とマッチするまでの対戦数を $X _ i$ とすると、Maximum-minimums identity より

$$ \begin{aligned} X &= \max ( X _ 1, X _ 2, \dots, X _ N) \\ &= \sum _ { \emptyset \neq S \subseteq [n] } ( -1 ) ^ { |S| + 1 } \min _ { k \in S } X _ k \end{aligned} $$

ですから、期待値は

$$ \mathbb{E}[X] = \sum _ { \emptyset \neq S \subseteq [n] } ( -1 ) ^ { |S| + 1 } \frac 1 { \sum _ { k \in S } p _ k } $$

となります。スマブラがストリートファイター6や鉄拳8だった場合は、この式のまま厳密に計算できたかもしれないのですけれども、いかんせんファイターが88体もいるので、高速化を試みていきます。

数値積分により高速化

一般に正の実数 $a > 0$ に対して $\int _ 0 ^ \infty e ^ {-at} dt = 1 / a$ であることに注意すると、次のように変形できます。

$$ \begin{aligned} \mathbb{E}[X] = \sum _ { \emptyset \neq S \subseteq [n] } ( -1 ) ^ { |S| + 1 } \int _ 0 ^ \infty \prod _ { k \in S } e ^ { -p _ k t } dt \\ = \int _ 0 ^ \infty \left(1 - \prod _ { k = 1 } ^ N ( 1 - e ^ { -p _ k t } ) \right) dt \end{aligned} $$

被積分関数を $f(t)$ とおいて、これを数値積分していきましょう。

$f(t)$の観察

実データに対する $f(t)$ は次のような形になっています。

なおここでいう実データは

const X: [i64; 84] = [
    57, 45, 39, 38, 29, 27, 27, 25, 21, 19, 19, 19, 17, 16, 16, 15, 15, 15, 15, 14, 13, 13, 13, 13,
    13, 13, 13, 13, 13, 12, 11, 11, 11, 11, 10, 10, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 7, 7, 7, 7, 6, 6,
    6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1,
];

です。1000 戦して出会わなかったファイターが 4 体いたので、そのファイターは大変心苦しいですがスマブラに参戦できなかったものとして、$N = 84$ で計算してしましました。

数値積分の方法

積分区間の尾を $t = T$ でtruncate して有界区間にして、細かく分割してシンプソンの公式を適用することで近似的に積分を計算できます。

するとどこで tuncate するか、どれくらい細かく分割するか、そもそも一様な分割で良いのかという問題が生じてくるわけですが、今回は次のようにすることにしました。

最初は $T = 1$ かつ分割なしで計算し、1 ステップごとに誤差最大の区間を 2 等分するまたは $T$ を 2 倍にする（$[T, 2T]$ を push-back する）
シンプソンの公式の誤差は、2 等分したときの改善量の $16 / 15$ 倍とする（近似公式）
尾を truncate した分の誤差は $f(t)$ の上界 $\sum _ { k = 1 } ^ N e ^ { -p _ k t }$ を用いる

実装・計算

$([0, 1])$ から始めて 65536 ステップの改善を行うことで、

I = 2581.618398088767 (error ~ 0.000000000001600940014500234)

という結果を得ました。なお、参戦権を剥奪された 4 キャラは試合数 1 としてデータに無理やり push-back しました。（あんまりよくない処理）

計算コード

結論

VIP 2600 連勝くらいすればコンプですね。ロンさんよろしくお願いします！

逆にいうとまだ 2600 戦程度していない場合、まだ出会っていないファイターがいる可能性がけっこうあるわけです。すごい！

実データの代わりにモデルを用いる

正の実数 $s > 0$ を用いて、$r$ 番目に頻繁にマッチするファイターとマッチする確率が $r ^ { -s}$ であるというモデル（Zipf の法則）を仮定します。本来長い文章の中の単語の出現率に関する法則なのですが、スマブラで適用するのが適切なのかはあまりわかっていません。またファイター数は有限（$N = 88$）なので、truncated zeta function $\zeta _ N (s)$ で normalize しておきます。

最尤推定で $s$ を推定する

実データ（1 を 4 個 push-back する前のデータ）におけるファイター $r$ のマッチ回数を $x _ r$（ソート済み）とおき、その合計を $Y = \sum _ { r = 1 } ^ N x _ r = 1000$ とおくと尤度 $L(s)$ は、

$$ L(s) = \frac { Y ! } { \prod _ { r = 1 } ^ N x _ r ! } \prod _ { r = 1 } ^ N \left( \frac { r ^ { -s } } { \zeta _ N (s) }\right ) ^ { x _ r } $$

なので、対数尤度は定数倍を除くと

$$ l(s) = -s \sum _ { r = 1 } ^ N x _ r \log r - Y \log \zeta _ N ( s ) $$

となります。するとこの関数は多分きっと知らんけど上に凸になるはずなってくださいなので、黄金分割探索で最大化すると $s \sim 0.64$ がわかります。

実際に実データと並べてみると、下位だけ大きくずれているので、あまり適切なモデルではなかったかもという気持ちになってきます。

計算結果

全く同じ条件で計算した結果、こちらになりました。

I = 774.5587851886605 (error ~ 0.0000000000003155522278750538)

データ生成用コード:

    const S: f64 = 0.64;
    let xs = (1..=88).map(|r| (r as f64).powf(-S)).collect::<Vec<_>>();

結論

下位キャラの頻度が大事なのに、上位キャラの頻度が重点的にフィットする最尤推定なんかしたらそりゃズレるわけです。

おまけ: 一様分布の場合も数値計算でやってみる

すごい！最初の結果と同じですね。

I = 445.299671227953 (error ~ 0.0000000000007645371573390524)