【期待値マスター講座26】"クーポンコレクター問題"も指示関数で攻略！！

この記事では、確率の古典的な題材「クーポンコレクター問題」の前半を扱います。

${n}$ 種類のクーポンがあり、独立に ${m}$ 回引いたとき集まる種類数の期待値を、指示関数で出します。第IV部の「6種類のカード」の問題を、 ${n}$ 種類に一般化したものです。

公式LINEでテキスト配布中
公式LINE追加→ 期待値テキスト と送信
で120ページ超えのテキストを自動送信！
ㅤ
無料勉強相談も受付中
学習相談も受け付けています。
ゴウカライズは情報の少ない獣医学部や医学部受験にも精通しています。
一般入試はもちろん、総合型選抜や推薦など、なんでもお問い合わせください！

シリーズ全体の流れを先に見たい方は、まず 期待値マスター講座の導入記事 からどうぞ。全56回の構成と読み進め方をまとめています。

https://note.com/goukalize/n/n9de4e3c6c4fb

問題設定

$${n}$$ 種類のクーポンがあり、1回の試行で各クーポンが等確率 $${\frac{1}{n}}$$ で得られる。独立に $${m}$$ 回試行したとき、集まったクーポンの種類数を $${X}$$ とする。 $${E(X)}$$ を求めよ。

「種類数」と言われたら、指示関数の出番です。第IV部の記事20で「6種類のカードを $${n}$$ 回引く」場合を扱いましたが、それを「 $${n}$$ 種類のクーポンを $${m}$$ 回引く」に書き換えただけです。

指示関数で分解

クーポン $${k\in{1, 2, \ldots, n}}$$ について

$$
I_k = \begin{cases} 1 & (m \text{ 回中に少なくとも1回 } k \text{ が出た}) \\ 0 & (\text{それ以外}) \end{cases}
$$

とおきます。 $${X}$$ は

$$
X = \sum_{k=1}^{n} I_k.
$$

$${k}$$ が1回も出ない確率は、毎回 $${k}$$ 以外の $${n-1}$$ 通りが出る確率を $${m}$$ 回独立に掛けて $${\bigl(1 - \frac{1}{n}\bigr)^m}$$ なので

$$
P(I_k = 1) = 1 - \Bigl(1 - \frac{1}{n}\Bigr)^m.
$$

線形性により

$$
E(X) = n\left(1 - \Bigl(1 - \frac{1}{n}\Bigr)^m\right).
$$

これがクーポンコレクター問題の前半（集まる種類数の期待値）の答えです。

$${m}$$ と $${n}$$ の関係を読む

公式を眺めると、 $${m}$$ が大きいほど $${\bigl(1 - \frac{1}{n}\bigr)^m}$$ が小さくなり、 $${E(X)}$$ が $${n}$$ に近づきます。直観的に「たくさん引けば、全種類が揃いやすい」のと一致します。

数値で見ると、 $${n = 6}$$ の場合（さいころ）

• $${m = 6}$$ ： $${E(X) = 6\bigl(1 - (\frac{5}{6})^6\bigr) = 6\cdot 0.665 \approx 3.99}$$
• $${m = 12}$$ ： $${E(X) = 6\bigl(1 - (\frac{5}{6})^{12}\bigr) \approx 4.66}$$
• $${m = 24}$$ ： $${E(X) \approx 5.42}$$
• $${m = 60}$$ ： $${E(X) \approx 5.94}$$

「6種類全部集めるには、6回引いても平均4種類くらい」「12回でやっと5種類弱」「全部揃うまではかなり時間がかかる」ことが見えます。

クーポンコレクター問題の後半（予告）

「逆向き」の問題、つまり

全 $${n}$$ 種類を集めるのに必要な試行回数の期待値はいくつか

を求めるのが、クーポンコレクター問題の後半です。答えは

$$
n\Bigl(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\Bigr) = n H_n
$$

ここで $${H_n}$$ は $${n}$$ 番目の調和数。 $${n = 6}$$ なら $${6\cdot(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}) = 6\cdot 2.45 \approx 14.7}$$ 回が平均、という結果になります。

詳しい導出は第IX部の漸化式編で扱います。 「すでに $${k}$$ 種類集まっているとき、次の新種が出るまでの平均試行回数」が幾何分布の期待値で出る のを使います。

包除原理を経由する正攻法

別ルートとして、 $${P(X = k)}$$ を直接書き下す方法もあります。 $${X = k}$$ となる確率は

$$
P(X = k) = \binom{n}{k}\sum_{j=0}^{k}(-1)^j\binom{k}{j}\Bigl(\frac{k - j}{n}\Bigr)^m
$$

で、包除原理を経由した式になります。これに $${k}$$ を掛けて和を取れば期待値は出ますが、 指示関数の発想を使うと2行で同じ答えに到達する ところが大きな利点です。

包除原理の式は「ちょうど $${k}$$ 種類」を直接数えるためのものなので、 $${P(X = k)}$$ の分布まで欲しい場合は便利です。期待値だけ欲しいなら、 「種類ごとに『出たか?』を見る」だけで十分 、というのが今回のメッセージです。

練習問題

1から100までの番号が書かれたカードが各1枚、合計100枚入った袋がある。1枚引いて番号を見て戻すという試行を200回繰り返したとき、出た番号の種類数 $${X}$$ の期待値を求めよ。

公式に $${n = 100, m = 200}$$ を入れて

$$
E(X) = 100\left(1 - \Bigl(\frac{99}{100}\Bigr)^{200}\right).
$$

$${\bigl(\frac{99}{100}\bigr)^{200} = \bigl(1 - \frac{1}{100}\bigr)^{200}\approx e^{-2}\approx 0.135}$$ なので

$$
E(X)\approx 100\cdot (1 - 0.135) \approx 86.5.
$$

200回も引けば100種類中86種類くらいは集まる、という見立てです。逆に言うと、 100種類全部集めるには200回でも足りない 、というのがクーポンコレクター問題の感覚的な厳しさです。後半で扱う「全種類集めるまでの試行回数」 $${100\cdot H_{100}\approx 519}$$ 回、というのが平均像です。

補足：$${n}$$ が大きいときの近似

$${n}$$ が大きく $${m = cn}$$（ $${c}$$ は定数）とすると

$$
E(X) = n\left(1 - \Bigl(1 - \frac{1}{n}\Bigr)^{cn}\right)\approx n(1 - e^{-c}).
$$

「 $${cn}$$ 回引いたら、約 $${1 - e^{-c}}$$ の割合の種類が集まる」というスケーリング則です。 $${c = 1}$$ なら約 $${63}$$ %、 $${c = 2}$$ なら約 $${86}$$ %、 $${c = 3}$$ なら約 $${95}$$ %、…という具合に、 試行回数を $${n}$$ の倍数で増やしても収穫逓減 していくのが見えます。

入試レベルでは近似式までは出ませんが、公式の振る舞いを直観的に掴むときに役立ちます。

次に読む記事

次回は、別のタイプの応用として「じゃんけんの勝者数」を扱います。 $${n}$$ 人が一斉にじゃんけんをして、勝者の人数の期待値を出す問題です。場合分けで処理すると面倒ですが、 「人 $${i}$$ が勝つ事象」を指示関数で見れば対称性で一気に処理 できます。

【無料相談受付中】学習マネジメントはゴウカライズにおまかせを！

「成績が伸び悩んでいるけどどうやって打破すればいいかわからない…」
「塾・予備校に行ってるけど、全体の成績が思ったように上がらない…」

そんな悩みをお持ちの受験生・保護者の皆様、ゴウカライズにご相談ください！

入試を突破するため、私たちはあなたの志望校や受験方式に必要なすべてをトータルサポートします。

【一般入試】完全オーダーメイドの学習計画 ：
入試は、わずかな失点が合否を分けることもあります。
あなたの現状と志望校の出題傾向を分析し、合格ラインに到達するための最短ルートを設計。
日々の進捗管理で、学習の遅れも見逃しません。

【推薦・総合型選抜】面接・小論文もプロが対応 ：
推薦入試や総合型選抜で必須となる「面接・小論文・志望理由書」の対策もお任せください。
医学部や獣医系特有のテーマ（動物倫理や獣医療時事など）に対応できるプロ講師が、合格レベルの答案作成と受け答えを指導します。

プロ講師・優秀学生講師の個別指導 ：
学習管理だけでなく、経験豊富なプロ講師や、高倍率から選抜された優秀な学生講師による完全個別指導も提供。
苦手科目の克服や過去問解説など、あなたのニーズに合わせた1対1の指導が可能です。

【医学部・獣医学部対策】特殊な対策に完全対応 ：
医学部入試、獣医学部入試は特殊な対策が必要です。
面接などがある入試形式の場合、面接対策も侮れません。
そんな入試に精通したプロがゴウカライズには多数在籍しています。
ゴウカライズ代表の大北も医学部・獣医学部受験の指導経験は15年を超える大ベテランです。

まずは無料相談で、あなたの合格までのロードマップを一緒に描きませんか？
無理な勧誘は一切ありません。
予備校選びに迷っているなどの相談でも、客観的にアドバイスを行います。

公式LINEでいつでも無料相談を受け付けています！

https://goukalize.com/

https://goukalize-official-line-harness.tiny-atlas.workers.dev/r/Expected-Value

#オンライン予備校 #大学受験 #数学 #指示関数 #クーポンコレクター