« 2009年05月 | メイン | 2009年07月 »

2009年06月 アーカイブ

2009年06月06日

Coupon collector's problem

問1:おまけとしてフィギュアか何かが入っているお菓子があるとする。おまけは全m種類あり、お菓子の購入時にはどれが入っているかわからないとし、m種類は同じ確率で入っているとする。このお菓子をn回買うと、おまけが全種類揃う確率はいくらか?


これはTV東京の「ミネルヴァの法則」という昔の番組で出てきた問題のアレンジである。番組での問題は、おまけは10種類だと、100回買うと99%以上の確率で全種類揃うか(○/×)、という感じだったと思う。これの正解発表の時に、全種類揃う確率が99%になるのは66回であると、計算方法抜きで出てきた。

大学を卒業し、数式の類から遠ざかって10年以上、数学力はすっかり鈍っていたとはいえ、大学は理系卒で、高校時代は確率が得意中の得意だった身である。たかがテレビに出てくる確率の問題が解けないはずが無いと思って、その66を計算で求めようとしたが、やり方がわからず、その番組を見た日からのべ10時間以上考えて降参した。

三十半ばで再び数学に目覚めて1年、紙の上で数式をぐりぐりする右手を取り戻して、やっと解けた。


答1:
P¥left( m,n¥right) =¥sum_{k=1}^{m}{¥left( -1¥right) }^{m-k}¥,¥pmatrix{m¥cr k}¥,{¥left( ¥frac{k}{m}¥right) }^{n}
または
P¥left( m,n¥right) =¥sum_{k=0}^{m-1}{¥left( -1¥right) }^{k}¥,¥pmatrix{m¥cr k}¥,{¥left( ¥frac{m-k}{m}¥right) }^{n}
(これらはΣを展開すると同じ式、(m k)が縦に並んでるのは組み合わせ(mCkと書くのと同じ))


解説を試みる。

n個買うと、結果のパターンはmn通りである。この内、m種類揃っているのは、(m-1)種類以下しか無い場合を引いたものである。
(m-1)種類しか無いパターンは、(無い1種類のパターンmC1)×((m-1)種をn回選ぶパターン(m-1)n)、(m-2)種類しか無いパターンは、(無い2種類のパターンmC2)×((m-2)種をn回選ぶパターン(m-2)n)、…のように計算できると簡単なのだが、そうはならない。例えば(m-1)nパターンの中にも(m-2)種類以下しか無いパターンが含まれてしまうからだ。

この問題には「包除原理」(Inclusion-exclusion principle)というのが使えて、正しくは、(m-1)種類以下しか無いパターンの数は
¥pmatrix{m¥cr 1}(m-1)^n - ¥pmatrix{m¥cr 2}(m-2)^n + ¥pmatrix{m¥cr 3}(m-3)^n - ¥ldots - (-1)^{m-1}¥pmatrix{m¥cr m-1}1^n
であり、従ってm種類あるパターンの数はm^n(=mC0 m^n)からこれを引いたもの、
¥pmatrix{m¥cr 0}m^n - ¥pmatrix{m¥cr 1}(m-1)^n + ¥pmatrix{m¥cr 2}(m-2)^n - ¥ldots + (-1)^{m-1}¥pmatrix{m¥cr m-1}1^n
という+と−が交互に出てくる和になる。これを全てのパターンの数m^nで割ってΣ記号で整理したのが上記の答である。

この問題に「包除原理」が使えることを理解するには、勘が冴えてれば何も要らないかも知れないが、勘が鈍い日は次のように考えてはどうだろうか。
包除原理とは、例えばn人の人がいて、A,B,Cの3つの特徴を調べ、1人の人が複数の特徴を持つことができる時、いずれの特徴も持たない人の数が、
全体の人数−(Aの人数+Bの人数+Cの人数)+(AかつBの人数+BかつCの人数+CかつAの人数)−(AかつBかつCの人数)
となるようなことを言うものである。なぜそのようになるかというと、

この図の白い部分が求める人数だが、全体から1つの特徴を満たす人数を引くと2つの特徴を持つ人を2回引くことになり、引き過ぎた分を足すために2つの特徴を満たす人数を足すと3つの特徴を持つ人を3回足すことになり(m個の特徴を持つ人は(m-1)個の特徴を持つ人としてm回数えられるため)、以下同様に全ての特徴を満たす人数まで相殺する必要があるからである。
話を戻して、m種類のおまけが揃うパターンの数を求めるには、おまけ1が欠けてる場合をA、おまけ2が欠けてる場合をB、おまけ3が欠けてる場合をC、…と考えると、AとBが同時に起こることもあるから、A,B,…は上の図のように重なるので、どれも欠けていない場合、すなわち上の図の白い部分の数を数えようとすると、必然的に包除原理のような計算になるのである。


さて、現実的には、何個買った時にコンプリートしてる確率がいくらになるかより、大体何個買ったらコンプリートできるか、すなわち、コンプリートするまでの回数の期待値の方が興味があるのではなかろうか。

問2:おまけが全種類揃うまでのnの期待値は?

この問題は、"Coupon collector's problem"と呼ばれるらしい。日本語訳は不明だが、「食玩問題」とか「クーポン収集問題」とか呼ばれることがあるようだ。
確率分布がP(X)の確率変数Xの期待値E(X)を求める公式はΣ(X P(X))であり、上のP(m,n)より、n回目にm個揃う確率がP(m,n)-P(m,n-1)なので、nの期待値E(N,m)(以降、E(m)と省略する)はΣ(n (P(m,n)-P(m,n-1)))である。コンピューターでそれなりに大きなnまで計算すると正しい値に近づくので、一応正しい式のようであるが、これを解こうとするとひどい目に遭う。
しかし、違う発想で解くと、かなり簡単に求められる。


答2:
E(m)=m¥left(¥frac{1}{1}+¥frac{1}{2}+¥frac{1}{3}+¥ldots+¥frac{1}{m}¥right)


k-1種類まで揃ってから、k種類目が得られるまでに、平均何回かかるかと考える。
まだ得られてないのは(m-k+1)種類なので、1回買ってまだ得られてないのが得られる確率pは、p=(m-k+1)/mである。当たりの確率がpの時、当たりを引くまでの回数は、幾何分布に従う。すなわち、x回目で当たる確率はP(x)=(1-p)^(x-1) pである。このxの平均はΣxP(x)であり、等比級数の和を求める要領で解くと、ΣxP(x)=1/pとなる。従って、k種類まで揃ってからk+1種類目が得られるまでの回数の期待値はm/(m-k+1)である。
E(m)はこれを1種類目からm種類目まで足したものだから、
E(m)=m/m + m/(m-1) + m/(m-2) + ... + m/(m-m+1) = m(1/1 + 1/2 + ... + 1/m)
となる。

続きを読む "Coupon collector's problem" »

2009年06月09日

37%の法則

問:n個の箱にそれぞれ異なる額のお金が入っており、どれか1つの箱のお金をもらえるとする。最大の金額は不明である。1つ箱を開けたら、そのお金をもらって終了する(残りの箱は開けない)か、そのお金をパスするかを決めないといけない。1度パスしたお金はもらえない。最高額を得る確率を最大にするには、どのように箱を選択すれば良いか。


前項と同じく、「ミネルヴァの法則」の問題のアレンジである。番組の問題では、n=20だった。正解は、最初の37%(=7個)の箱は開けても選択せず、次に出てきた、それまでの最高額より大きい金額を選択するというものである。

前項の問題と同様、たかがテレビに出てくる確率の問題が解けないはずが無いと思って、その37%を(中略)降参した。
この度、やっと解けた。


答:最初のn/e個(eは自然対数、小数点以下切り捨て)の箱の中身をパスして、次に出てきた、それまでの最高額より大きいものを選択する。


解説する。
考えられる手順は、最初のr個の箱の中身をパスして、次に出てきた、それまでの最高額より大きいものを選択する、という手順に帰着する。これ以外を考えても無駄であることは容易にわかる(注:ここでの問題では最高額以外は全て外れである)。従って、その適切なrを選ぶのが問題である。

r個をパスして最高額が得られる確率をP(r)とする。最高額がx番目(x>r)にあり、それを選択できる確率は、
・最高額がx番目にある確率=1/n
・1〜r番目の最大より大きな額が(r+1)〜(x-1)番目には無い確率=1〜(x-1)番目の最大が1〜r番目に出てくる確率=r/(x-1)
の積である。P(r)はそれを全てのxについて足し合わせたものなので、
P(r)=¥sum_{x=r+1}^n ¥frac{1}{n}¥frac{r}{x-1}
となる。

P(r)が最大になるrを求める前に、P(r+1)-P(r)を計算して、P(r)の増減を調べてみる。

なので、上から下を引いて、
P(r+1)-P(r)=¥frac{1}{n}(-1+¥frac{1}{r+1}+¥frac{1}{r+2}+¥cdots+¥frac{1}{n-1})...(1)
である。これはよく見るとrが大きくなると項が減る一方で、どこかで0より小さくなる。従って、P(r)が最大になるのは、P(r)が減り始める直前のr、すなわちP(r+1)-P(r)<0となるrである。(1)の右辺の括弧内に注目すると、
¥frac{1}{r+1}+¥frac{1}{r+2}+¥cdots+¥frac{1}{n-1}<1...(2)
となる最小のrとも言える。

さらに、nが十分大きいとして、(2)の左辺を計算し易い積分に近似する。区分求積法より、
¥sum_{k=1}^{n}¥frac{1}{n}f(¥frac{k}{n})¥simeq¥int_0^1f(x)dx
なので、f(x)=1/xとして積分範囲を調節すると、
¥sum_{k=r+1}^{n-1}¥frac{1}{k}¥simeq¥int_¥frac{r}{n}^1¥frac{1}{x}dx
と近似できる。右辺<1を計算すると、-log(r/n)<1であり、r/n>1/eすなわちr>n/eが求まる。n/eは整数ではなく、r>n/eの整数だとP(r)がちょっと減るので、n/eを超えない整数がP(r)を最大にするrである。(nが小さい時は(2)で検算した方が良いかも知れない)


37%とは、1/e(≒0.368)のことであった。
なお、この問題は(classical) secretary problemと呼ばれ、問題の解は37%の法則とか37%ルールとかと呼ばれるらしい。

続きを読む "37%の法則" »

2009年06月28日

秘書問題の考察(2) 期待最高順位による停止戦略

「秘書問題」(secretary problem)というのは、非常に奥深い問題で、数理科学の「最適停止理論」における1つの重要な分野となっており、未解決の問題も少なくないらしい。
前のエントリーに書いた、37%の法則が成り立つ問題は、秘書問題の最も単純なものである。秘書問題に倣って秘書を面接で選ぶという表現に変えると、前のエントリーの問題は、応募者の中の最高の人以外は外れという条件の問題であるが、現実の問題としては、できるだけ最高の人を選ぶことだけを考えればいいとは限らない。誰か1人を選ばないといけない場合、最後の応募者まで採用を見送ると、最後の人はどんな人でも選ばないといけない。その1つ前の、残り1人(まだ面接していない応募者が1人)の時点で、前回の37%の法則の戦略に従うと、今面接している人がこれまでの中の2位であっても、残りの1人が1位である可能性に期待して見送るのであるが、なるべくいい人を選びたい場合は、残り1人で暫定2位であれば、残りの1人が2位以内に入る確率は(応募者が十分多いとすると)極めて低いので、暫定2位の人を採用するのが当然である。
このことからも直感的にわかる通り、1位の人を選ぶ確率を最大化するのとなるべく上位の人を選ぶのとは一般に両立しない。なるべく上位の人を選ぶ、というのを、順位の期待値を最小化する、と定義すると、1位の人を選ぶ確率を最大化するのと順位の期待値を最小化するのを同時に満たす最適停止戦略は存在しないことが数学的に示されているらしい。

という訳で、今回は次のような問題を考える。
・n人の応募者から1人を選ぶ。
・1人ずつ面接し、その場で採用するかどうかを伝える。採用したら、残りの人は面接しない。採用しなければ、その人は2度と選べない。
・応募者の良し悪しは、既に面接した応募者と比べてどうかでしか判断できない。絶対評価で何点というのは無く、あの人と比べてどうか、しかわからない。また、優劣は必ず付けられ、必ず順位付けが可能である。
・結果としてなるべく順位の高い人が選べるようにする。

必ず誰か1人は選ばないといけないということと、最後の1点以外は、前のエントリーの問題と同じである。
この問題は既に解かれていて、nを大きくすると順位の期待値の最小が約3.87に収束する(期待順位がそれより小さい戦略は存在しない)という摩訶不思議な定理になっているのだが、あまりにも難しいので、今回は単純な方法で考えてみる。


xを残りの応募者の数(まだ面接していない人数)とする。
x=0(今面接している人が最後の応募者)の時、その人を選ぶしか無い。
x=1の時、今面接している人を含むn-1人を1位〜n-1位に並べ、残りの人がその間または1位の上、n-1位の下のどこかに入ると考えると、入る場所はnヶ所なので、これを0.5位、1.5位、…、(n-0.5)位とすると、残りの人の順位の期待値はn/2なので、今面接している人の順位がn/2より小さければ選ぶ。(n/2以下なら、としても良い)
x=2の時、同様にこれまでの1位〜n-2位に対して残りの2人が0.5位、1.5位、…、(n-2+0.5)位の(n-1)ヶ所のどこかに入ると考えると、残りの2人のいい方の順位の期待値は、1人目の順位をkとすると
(2人目がkよりいい確率)*(2人目の順位の期待値)+(1 - 2人目がkよりいい確率)*k
であり、1人目の順位がkである確率は1/(n-1)なので、
¥frac{1}{n-1}¥sum_{k=1}^{n-1}¥left¥{¥frac{k-1}{n-1}¥,¥frac{k}{2}+¥left(1-¥frac{k-1}{n-1}¥right)k¥right¥}-¥frac{1}{2}
¥frac{n}{3}-¥frac{1}{2}+¥frac{1}{6-¥frac{6}{n}}
と計算できるので、今面接している人の順位がそれより小さければ選ぶ。

x>2の時、残りのx人の最高順位の期待値を同様に求めるのは難しいので、代わりに一様分布に従うx個の標本の最小値を求めてみる。
標本が0-1の一様分布に従う時、n個の標本の最大値がyより小さい確率は、全ての標本がyより小さい確率だから、ynである。これは最大値がyになる確率の累積密度だから、確率密度関数はそれを微分してn yn-1である。従って、最大値の期待値は、
¥int_{0}^{1}y¥,ny^{n-1}dy=n¥int_{0}^{1}y^ndy=¥frac{n}{n+1}
である。標本を全て(1-標本)にすると、最小値の期待値は1 - n/(n+1) = 1/(n+1)ということになる。
これを使うと、x>2の時、残りのx人の最高順位の期待値は、0.5+(0〜(n-x)の値を取るx個の標本の最小値の期待値)=0.5+(n-x)/(x+1)と概算できるので、今面接している人の順位がこれより小さければその人を選べば良い、と考えられる。


上の計算に沿って、n=10で残りがx人の時、今面接している人が何位以内ならその人を選べば良いかを表にしてみる。

xrank
15
23.17
32.25
41.7
51.33
61.07
70.88

x=1の時(9人目)は暫定5位以内なら採用、x=2の時(8人目)は暫定3位以内なら採用、x=3の時は暫定2位以内なら採用すれば良く、x=7の時(3人目)は暫定1位でもパスすべしということになる。

n=20についてもやってみる。

xrank
110
26.5
34.75
43.7
53
62.5
72.13
81.83
91.6
101.41
111.25
121.12
131
140.9

x=1の時は10位以内なら採用、x=2の時は6位以内なら採用、(中略)x>13の時は1位でもパスすべしということになる。

続きを読む "秘書問題の考察(2) 期待最高順位による停止戦略" »

About 2009年06月

2009年06月にブログ「Weblog on mebius.tokaichiba.jp」に投稿されたすべてのエントリーです。過去のものから新しいものへ順番に並んでいます。

前のアーカイブは2009年05月です。

次のアーカイブは2009年07月です。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

Powered by
Movable Type 3.35