クーポンコレクター問題を解き明かす！

この記事は物工/計数 Advent Calendar 2023 - Adventar の一部として書かれたものです。数式部分に興味のある方は前半を飛ばしてください。

導入

ずんどうねこって知ってますか？

この可愛すぎるキャラクターはずんどうねこと言い、とっとさんのTwitterで毎日更新されています！僕はずんどうねこを3年以上前からかなり推しているのですが、今年とても嬉しいことが起こりました。

10/22(日)発売開始♪#ずんどうネコぷっくりラバーマスコット

▼ラインナップ
ミケ×ハンバーガー
ミケ×エッグトースト
ミケ×ショートケーキ
ミケ×エビフライ
ミケ×マリトッツォ
ミケ×ミントアイス
1回300円🪙全6種

店舗情報を
下記YouTubeの概要欄に掲載中🐈

▼YouTube https://t.co/gTTiJez2Bo pic.twitter.com/Fnp2LfN5dH
— Qualia(クオリア)公式 (@Qualia_45_) 2023年10月20日

なんと、かわいすぎるラバーストラップ（全６種）が一回300円のガチャガチャに登場したんです！！！！！！！！これは集めるしかない！！！と僕と彼女は池袋へ繰り出しました。

ご飯屋さんの待ち時間に、全６種をコンプリートするのにかかるお金の期待値について考えていました。これはクーポンコレクター問題です。クーポンコレクター問題とは、N種類あるクーポンを全てコンプリートするために、何回購入しないといけないか？という問題です。詳しい定式化は後程します。かかるお金はコンプリートするのにかかる回数の期待値x300円で出せますね。ご飯屋さんの待ち時間の間に頭の中で解けて、期待回数は14.7回、かかるお金の期待値は、4410円となります。たった6個のガチャでも15回程度かかるんだ…ｶﾞﾁｬｺﾜｲってなりつつ、次のアイデアが湧いてきました。

「彼女と来てるんだから、お互いの出なかった分を分け合えば二人の期待回数の和は減るのでは？」というものです。これはクーポンコレクター問題の拡張版で、N種類のクーポンをmセット集めるときの回数についての問題となります。これはマルコフ連鎖で解けそうだなというところまで考察しましたが、その時は具体的な解を得られませんでした。

ここまで気持ちを準備して、いざガチャガチャ屋にいくと…

売り切れてました～～～～～～～～～～～～～～～～～うわあああああああああああああああああああああ

後でクーポンコレクター問題について調べていくと、確率論の基礎的な内容が詰まったおもしろい話だったのでここにまとめる次第です。

大まかな定式化

ここから数学パートです。

クーポンコレクター問題とは、 $N$ 種類のクーポンがそれぞれ、確率 $p_i$ で出現するときに、クーポンをコンプリートするまでに買う必要のある回数の確率や期待値について考える問題です。クーポンは以下、 ${1, 2, \dots, N}$ としてよく、 $\sum_{i=1}^N p_i = 1$ です。クーポン列が与えられるときにいくつまで見れば全て出現するかと言い換えることもできますね。

このクーポンコレクター問題はいくつかの種類にわけられます。

すべての確率が等確率の場合
確率がそれぞれ異なる場合 (レアなクーポンがある場合)

また、問題の拡張として

クーポンがいくつかのまとまりで来る場合
クーポンを1セットではなくmセット揃える場合

などが考えられます。以下ではそれぞれの場合について、期待値の証明などを与えます。

1セット、等確率の場合

$X$ を確率変数で、1セット揃うまでの購入回数とします。 $X_i$ を確率変数で、 $i-1$ 種類揃っている状態で、 $i$ 種類揃うまでの購入回数とします。

明らかに $X = X_1 + X_2 + \cdots + X_N$ ですね。

各 $X_i$ は独立なのは明らかです。 $X_i$ について、 $i$ 種類目を得る確率は $\frac{N-i+1}{N}$ ですので、 $X_i$ はパラメータ $\frac{N-i+1}{N}$ の幾何分布に従います。

よって、

$E[X] = E[X_1] + E[X_2] + \cdots + E[X_n] \\ = 1 + \frac{N}{N-1} + \frac{N}{N-2} + \cdots + \frac{N}{1} \\ = N \left(\sum_{i=1}^N \frac{1}{i}\right)$

となります。

他、マルコフ連鎖を用いても証明できますが、その場合方程式を解くのが面倒なのでこちらが楽です。

その他の話題として、 $\sum_{i=1}^N = \frac{1}{i}$ は $N \rightarrow \infty$ の時、

$\sum_{i=1}^N \frac{1}{i} = \log (N) + \gamma + \frac{1}{2N} + O\left(\frac{1}{N^2}\right)$

となるので、

$E[X] = N\log (N) + N\gamma + \frac{1}{2} + O\left(\frac{1}{N}\right) \qquad (n \rightarrow \infty)$

1セット、等確率ではない場合

$X_i$ を確率変数で、種類 $i$ 番目のクーポンを最初に得るまでに必要な購入回数とします。 $X$ を確率変数で、すべてのクーポンをそろえるのに必要な購入回数とします。明らかに、 $X = \max (X_1, X_2, \dots, X_N)$ ですね。また、 $X_i$ はパラメータ $p_i$ の幾何分布に従います。今問題なのは、各 $X_i$ は独立ではないということです。何故なら、例えば $X_i = 1$ なら最初にクーポン $i$ が出たということなので、他の $X_j$ は1になりえないからです。よってmaxを簡単にとれません。ここで重要な考察として、 $i \neq j のとき \min(X_i, X_j)$ はパラメータ $p_i + p_j$ の幾何分布に従う確率変数になります。3つ以上のminも同様になります。

ここで、Maximum-minimums identityという恒等式を紹介します。確率変数 $X_i$ について、以下の恒等式が成り立ちます。

$\max (X_1, X_2, \dots, X_n) = \sum_{i=1}^N X_i - \sum_{i < j} \min(X_i, X_j) + \sum_{i < j < k} \min(X_i, X_j, X_k) + \dots + (-1)^{n+1} \min(X_1, X_2, \dots, X_n)$

これ知りませんでした…。これを使って、maxをminに書き換えます。それぞれのminは幾何分布に従うことは説明しました。これでmaxの期待値をminを使って計算できますね！

$E[\max (X_1, X_2, \dots, X_n)] = \sum_{i=1}^N E[X_i] - \sum_{i < j} E[\min(X_i, X_j)]+ \sum_{i < j < k} E[\min(X_i, X_j, X_k)] - \dots + (-1)^{n+1}E[ \min(X_1, X_2, \dots, X_n)]\\ = \sum_i \frac{1}{p_i} - \sum_{i < j} \frac{1}{p_i + p_j} + \sum_{i < j < k} \frac{1}{p_i + p_j + p_k} - \dots + (-1)^{n+1} \frac{1}{p_1 + p_2 + \cdots + p_N}$

まだ汚いですね。ここからさらに変形していきます。

$\int_0^\infty e^{-px} dx = \frac{1}{p}$

と

$1 - \prod_{i=1}^N (1 - e^{-p_i x}) = \sum_i e^{-p_i x} - \sum_{i < j} e^{-(p_i + p_j)x} + \cdots + (-1)^{N+1} e^{-(p_1 + p_2 + \cdots + p_N)x}$

を使って

$E[X] = \int_0^\infty \left( 1 - \prod_{i=1}^N (1 - e^{-p_i x}) \right) dx$

となります。

これも、天下り的に指数分布とポアソン分布を使う天才的な証明もあるようなのですが、そちらは参考文献をご覧ください。

mセット、等確率の場合

m=2, N=6の場合が導入で述べた状況に相当しますね。

$p_i$ を $i$ 個購入したがmセット揃わない確率とします。 $X$ を確率変数で、mセット揃うのに必要な購入数とします。

すると、

$1 - \prod_{i=1}^N (1 - e^{-p_i x}) = \sum_i e^{-p_i x} - \sum_{i < j} e^{-(p_i + p_j)x} + \cdots + (-1)^{N+1} e^{-(p_1 + p_2 + \cdots + p_N)x}$

を使って

$E[X] = \sum_{i=1}^\infty i (p_{i-1} - p_i) = \sum_{i=0}^\infty p_i$

という関係が成り立ちます。

では、 $i$ 個購入したがmセット揃わない確率である $p_i$ はどう表せるでしょうか？ $p_i = i$ 個買ったが、どれかがmセットに満たない場合の数 / Nⁱ ですね。

$i$ 個買ったが、どれかがmセットに満たない場合の数は、

$(x_1 + x_2 + \cdots + x_n)^i$

の展開した後、どれかの指数の肩にm以上の数が乗っている項を消したあと、すべての $x_i$ に1をいれたもの。といえます。

後程の議論を楽にするために、以下に定義する記号を使います。

$\{P(x_1, x_2, \dots, x_n)\}$

これは多項式Pから全ての $i$ について、 $x_i$ の指数部分がm乗を超えるものを除いた多項式のことを表すことにします。

さて、 $S_m(t)$ を以下で定義します。

$S_m(t) = \sum_{k=0}^{m-1} \frac{t^k}{k!}$

そして、以下の式を考えます。

$F = e^{x_1+x_2+\cdots+x_n} - (e^{x_1} - S_m(x_1) \times \cdots \times (e^{x_N} - S_m(x_N))$

Fを $x_i$ の多項式だと思うと、Fは $x_i$ 全ての指数の肩がm以上の項を含まないことがわかります。しかし、Fはいくつかの $i$ について $x_i$ のm乗を超える項を含んでいます。つまり、

$F = \{e^{x_1+x_2+\cdots+x_n}\} = \sum_{i=0}^\infty \frac{\{(x_1+x_2+\cdots+x_n)^i\}}{i!}$

ですね。

最後のパーツとして、以下の式が成り立ちます。

$N \int_0^\infty \frac{t^i}{i!}e^{-Nt} dt = \frac{1}{N^i}$

これは部分積分して漸化式を解くと正しいことを示せます。

これらを用いて、

$E[X] = \sum_{i=0}^\infty p_i = \sum_{i=0}^\infty \frac{\{(x_1+x_2+\cdots+x_N)^i\}}{N^i} \\ = \sum_{i=0}^\infty \left( \{(x_1+x_2+\cdots+x_N)^i\} N \int_0^\infty \frac{t^i}{i!} e^{-Nt} dt \right) \\ = N \int_0^\infty \sum_{i=0}^\infty \left( \{(x_1+x_2+\cdots+x_N)^i\} \frac{t^i}{i!} \right) e^{-Nt} dt \\ = N \int_0^\infty \left[ e^{tx_1+tx_2+\cdots+tx_n} - (e^{tx_1} - S_m(tx_1) \times \cdots \times (e^{tx_N} - S_m(tx_N)) \right] e^{-Nt} dt$

さて、すべての $x_i$ に1をいれることを思い出して、1をいれて評価します。

$E[X] = N \int_0^\infty \left[ 1 - (1 - S_m(t)e^{-t})^N \right] dt$

が得られました！

これが答えなのですが、これだとどれくらい大きいかわかりずらいので、 $N \rightarrow \infty$ で評価をすると、 $E[X$ = N \left( \log(N) + (m-1)\log \log (N) + C_m + o(1) \right)] となるらしいです。逆に、 $m \rightarrow \infty$ で評価をすると $mN$ になります。これは直感的ですね！

では最後に具体的に計算してみます。導入で述べたN=6, m=2の場合だと、24.1回。一人当たりだと12回なので、N=6, m=1の場合の14.7回よりかなり改善しています。一人800円ほど安く済む計算になりました。

その他、マルコフ連鎖でも解けますが、m, Nが小さいときじゃないと難しそう…。

ここまで読んでくれた人、ありがとう！

参考文献

https://mat.uab.cat/matmat_antiga/PDFv2014/v2014n02.pdf

naoppyの日記

自分が欲しいなと思った記事を書きます。