Teao 問題の解法

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

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

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

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

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

となり、1回あたりの確率 p の逆数となる。つまり、「サイコロの１の目を出すまでにはだいたい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=1^M (M/k)

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

ヒント１

集まったバッジの種類が k 種類のとき，Ｓk の状態にあるとします．
またバッジの種類はMとします．

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

ヒント２

n本Teaoを買ったときに Ｓk の状態にある確率を ｐk(n) とします．
ベクトル Ｐ(n) を考え，Ｐ(n)=(ｐ1(n), ｐ2(n),..., ｐM(n)) とします．
Ｐ(n+1) = Ａ Ｐ(n) となるような行列 Ａ を<ヒント1>で作った 状態遷移確率から求めてみましょう．

ヒント３

行列 Ａ の固有値・固有ベクトルを求めて，Ｐ(n) の一般項を求めましょう．

ヒント４

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

以上．

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