大好き Teao 問題の解法

Teao 問題とは?

かつて、アサヒ飲料の「Teao」という紅茶飲料に「広末バッジ」というおまけが付いていたことがありました。このバッジは全部で12種類あり、全種類を集めるために多くの日本国民が大枚をはたいて Teao を飲みまくり、Teao に含まれている糖アルコールの作用によって多くの人々が下痢に悩まされたものでした。

このような「おまけ商法」はペプシのキャップやチョコエッグなど、今日様々な商品で行なわれていますが、これらのおまけを蒐集するにあたっては、その商品をだいたい何個買えばおまけを全部集めることができるかを見積もることが非常に大事です。このような事前分析をしておけば、おまけの価値以上の金銭を費やしてしまって後悔したり、商品の食べ過ぎや飲み過ぎで健康を害することを未然に防ぐことができます。

そこでここでは、この「何個商品を買えば全種類集まるか」を確率論に基づいて評価してみましょう。

この問題は以下のように一般化することができます。

商品を n 本買ったところでちょうどおまけが M 種類全て集まったとすると、この時までに買った商品の数 n の期待値 <n>(M) はいくらか。

私が考えたいい加減な解

途中ちょっとあやしいですが、こんなふうに解けます。

求めたい期待値は、「ある事象が起こるまでに必要な試行回数の期待値」である。まず、一般にこのような期待値がいくらになるかを求めよう。期待値の定義によれば、この値は

1×(1回で起こる確率) + 2×(2回で起こる確率) + 3×(3回で起こる確率)
+ … + ∞×(無限回で起こる確率)

という無限和になる。問題にしている試行を、考えている事象の起こる確率が1回あたり p の反復試行とすると、この和は

1*p + 2*(1-p)p + 3*(1-p)2p + … +∞*(1-p)∞-1p
= Σk=1 k(1-p)k-1p
= [1/{1-(1-p)}2]*p = 1/p(∵ 等比級数の項別微分)

となり、1回あたりの確率 p の逆数となる。つまり、「サイコロの1の目を出すまでにはだいたい6回振ればいい」という、至極自然な結論になる。

ここで Teao 問題に戻る。例えば、3種類のおまけを持っている時、新たに1種類を得て4種類になるまでに必要な試行回数の期待値は、3種類から4種類に増える確率が 9/12 なのだから、先ほどの結論を用いて、確率の逆数の 12/9 回ということになる。

従って、おまけが全12種類集まるまでに要する試行回数の期待値は、これを1種類から12種類になるまで加えれば良い(ほんとかな?)。すなわち

1 + 12/11 + 12/10 + 12/9 + … + 12/2 + 12/1
= 12*(1/12 + 1/11 + 1/10 + … + 1/2 + 1) ≒ 37.2385(回)

となる。ゆえに、一般に M 種類のおまけを全て集めるまでに必要な回数の期待値は、

Σk=1M (M/k)

となる。実際、答はこれで合っているらしい。(まいっか、というわけでおしまい)■

たった一つじゃないかも知れないけどもっと冴えたやり方

以下に示すまっとうな解法は、古川徹生さんにご教示頂いた方法です。ありがとうございました。

ヒント1

集まったバッジの種類が k 種類のとき,Sk の状態にあるとします.
またバッジの種類はMとします.

今,Sk の状態にあるとして,ここで一本の Teao を買うと,次の 状態は "(1) Sk の状態で留まる" あるいは "(2) Sk+1の状態になる" のどちらかです.さあここで状態遷移確率を図に書いてみましょう.

ヒント2

n本Teaoを買ったときに Sk の状態にある確率を pk(n) とします.
ベクトル P(n) を考え,P(n)=(p1(n), p2(n),..., pM(n)) とします.
P(n+1) = A P(n) となるような行列 A を<ヒント1>で作った 状態遷移確率から求めてみましょう.

ヒント3

行列 A の固有値・固有ベクトルを求めて,P(n) の一般項を求めましょう.

ヒント4

n本Teaoを買ったときに初めてM種類のバッジがそろう確率を q(n) とすると, q(n)=pM(n)-pM(n-1) という関係が成り立ちます.P(n) の一般項がわかって いるのですから,これは簡単ですね.

以上.

追伸,大学1年生の線形代数の試験問題としてちょうど良さそうですね.

上記の方法についての私の感想

P(n) = An-1 P(1) ということで、P(n) を求めるために行列Aの冪を求める必要があります。Aの固有値と固有ベクトルを求めれば、B-1AB でAを対角化できるような行列Bが求まり、これによってAnも求まる…はずなのですが、固有ベクトルを求めるのがめんどくさいです。単純作業ですが労力を要します。かつて親から「ものぐさ太郎」と呼ばれた私にはなかなか計算する気になれません。あと、B-1を求めるのも大変そう… M 次行列だし…。というわけで保留してます。

備考

この問題は「クーポンコレクターの問題 coupon collector's problem」という名前で呼ばれている有名な数学の問題だそうです。『サイアス』2000年10月号の記事「清水義範の「サイエンス言誤学」」でも様々な解法が紹介されています。

関連リンク

がしゃぽん問題
名古屋大学の服部哲弥さんのページ。問題をさらに一般化して、「各種類について N 個ずつ集める場合の期待値」についても述べられています。確かにコレクターは「遊ぶ用」と「保存用」で2個買ったりするよなあ。
Teao 分布
NAIST の工藤拓さんのページ。同じ研究室の助手の方が、この問題を一瞬で解いてしまったそうです。すごいと思う。

只今の戦果

こんな感じ。一つへんなのが混じってますね。

戻る


Taro Zzz (taro@hauN.org)