背景 |
知人はそこで次のような問題を出しました。
「確率90%以上で全15種類を手にいれたいとき、何個買ったらよいで しょう？」
これについて、まとめることにします。
シミュレーションで答えを出そう |
そこで学生さんに相談して解いてもらうことにしました。彼は早速 シミュレーションをしてくれました。そうそう、問題を解 くときにはシミュレーションはいいですよね。つまりこうです。箱を n個買います。その中にはランダムで15種類のおまけが入っています。 箱を開けておまけをチェックして15種類全部あるか無いか調べます。 これを1000回、10000回くらいやって成功する回数と失敗する回数か ら成功確率を求めます。
簡単なプログラムで彼は「72個じゃないですか」と答えを出してくれ ました。私も別にプログラムを組んで 73個が正解 ではな いかという答えを出しました。
近似解が提出される |
知人が夜に「ふと思いついた式」というのは、
n 箱買って全１５種類揃う確率 = 1 - 15 * (14/15)^n
でした。この式の考え方は、
n 箱買ってそろう確率 = 1 - n 箱買ってもそろわない確率 「あと１個がゲットできない」の「１個」の選びかたは１５とおり。 その「１個」をはずしまくって n 個買う確率 = (14/15)^n
というものでした。
で、確かにこれで計算すると73個という答えが出てくるのですが、近 似式なので、nが小さくなるとだめで、40個とかだと破綻してきます。 さて次はどうするか。
大人買いと子供買い |
大人買い：一度にまるごと、つまり段ボールに箱がたくさん入ってい る状態で全部買込んで、やおら開けていく。
子供買い：一つ買っては開けて、また一つ買っては開けて、揃うまで頑張る。
これらって同じでしょうか。違うのでしょうか。同じだという意見で は大人買いしたところで、やっぱり一個一個開けていき、コンプリー トしたところで、オークションで売ってしまうから(笑)、ということ でした。
子供買いの時には、開けていってコンプリートしたところで買いませ んから、若干問題が異なっています。今回の解こうとしている問題の 場合には、きちんと言えば大人買いをした時に、ほしいおまけが揃っ ているかということになります。たとえば16個買って開けていって 15個開けたところで仮に全種類揃ったとしても、次の1個を開けると いう行為を入れて確率を計算しています。つまり16個買ったとして、 15個開けたところで揃う確率+16個目を開けて揃う確率が、16個開け て揃う確率になっています。
きちんとした漸化式の提案およびその解 |
おまけの種類 n種類 すでに手にいれている種類 m種類(＜n) 残りの開けていない箱の数 l個 として、全種類ゲットできる確率fは n-m>l -> f=0これを解く、プログラムは以下の通りです。n-m=0 -> f=1
f(n,m,l)= (n-m)/n*f(n,m+1,l-1) + m/n*f(n,m,l-1)
当たときの確率 + はずした時の確率
#include私も、最初に思いついた自分の漸化式を解くプログラムを使って、学 生さんと同じ結果が出ることを確認しました。これで一応きちんとし た解析解を得ることができるようになりました。さて、こうなるとこ んなプログラムを使わなくても解析解が出る式が欲しくなってきます ね。#define N 15 #define L 100 double Data[N+1][N+1][L+1]; double f(int n,int m,int l) { if(Data[n][m][l]>=0)return Data[n][m][l]; if(n-m>l)return 0; if(n==m)return 1; Data[n][m][l]=(double)(f(n,m+1,l-1)*(n-m)/n+f(n,m,l-1)*m/n); return Data[n][m][l]; } int main() { int i,j,k; int l; for(i=0;i<=N;i++)for(j=0;j<=N;j++)for(k=0;k<=L;k++) Data[i][j][k]=-1; for(l=15;l<=L;l++){ printf("%2d %2d %f\n",N,l,f(N,0,l)); } return 0; }
初めての解析解発表 |
そのうち知人の許可をもらってその考え方を載せたいと思い ます。えーと、もらいました。 ここに導出過程を置きます。
解析解から近似解が導出されることが示される |
ちなみに解析解と近似解の関係は次のようなグラフになります。
さらなる一般化へ |
つまり先ほどまではN個の欲しいおまけがあって、n箱買ったときにど のくらいの確率で全種類が手にはいるかという問題でした。
これを次のように一般化しました。N種類のおまけがあってすでにa種 類持っている。これからn箱買ったときに手元にm種類になる確率pを 求める式。
最後にはここまできました。N種類のおまけのうち、b種類欲しいのが ある。今、手元には、b種類のうち、a種類そろっている。これから n個のおかしを買い増ししたとき、手元に揃った種類数がmとなる確率 はどうなるか?(N>0,n>=0,N>=b>=m>=a>=0)
この問題についてもきちんとした解析解が示されました。
この問題のかなり一般的な解になっているでしょうね。
みんなが使えるようにしよう |
さきほどの学生さんにたのんでJava Scriptを組んでもらいました。
たとえば、おまけの種類の数15、これから欲しい数15、これから買 う数73を入力してもらうと手にはいる確率0.90556が出てきます。ち なみに買う数72では0.89906となりまして、90%をほんのちょっと切 ります。あるいは、これまで5種類はすでに手に入れていて、最終的には8種 類が欲しいときには、「これから欲しい数」を8-5=3にして確率計算 することができます。
さあ、みなさんこのページを利用して、コンプリートするまでの確率 を計算して、おまけをゲットしてください！！
(注) もし結果が変なときには、後に 別な計 算方法を実装した計算機や 計算機のページ がありますので、そちらを参照ください。
いろいろな情報 |
結果は...5個買って2種類のみ手にいれました。;_;
食玩ではひどいめや天国にいる気分になった方は多いようで、そのリ ンクを教えてもらいました。
確率論を展開する人も多いようです。
店頭での商品シャッフル問題（アソート）は、「均等」ではなく「ランダム」の ようです。
そうそう、現実には、公表されていない種類のおまけがあったり偏り があったりするので、なかなかコンプリートできないですよね。
どうしても欲しいけど、そんなにお金をかけるのには躊躇する、とい うのであれば、
やオークションを使う手がありますね。
まとめ |
また今回の、問題があってそれを解く過程が、本当に研究のやり方の典 型例だったからです。シミュレーションでまずとにかく答えを手にい れる。厳密解をもとめる。さらに効率を上げる。一般化する。みんな が使えるようにする。そういう意味もあってまとめました。何かの役 に立てば幸いです。
その後 |
白夜書房というところから発行している隔月間の雑誌「ハッカージャ パン」の2010年1月号のコラムに取り上げていただきました。執筆さ れた神戸大学大学院工学研究科の森井昌克先生に感謝申し上げます。 (2009/12/22)
AKB48の「 ワンダフルルーレッ ト」という最近終わった販促キャンペーンの解析に使ったとい うメールをいただきました。これは73日間、毎日1回、56個の賞品 から1つをルーレットで抽選するというものです。ところが、抽選 結果では、68日目で、56個すべてが出揃いました。このページをご 覧の方は分かるように、思ったよりも確率は低いです。実際の値は とんでもなく低く2.31E-14です。(2011/5/18)
実は、上の2.31E-14というのは最初の学生さんが作ってくれた JavaScriptのプログラムでは計算することができません。解析解を 数値的に解いていくと、計算機では桁落ちが起きて数値的に扱えな くなるからです。このことについて知人に相談したら、なんと漸化 式を使う計算解を使う方法を提案してくれました。下にある JavaScriptでは56個のおまけがあって、56個欲しくて、68回試して みたという計算ができます。
この考え方も工学っぽくて興味深いです。数学的には解析解を出す ことが重要ですが、工学ではそれを使えるようにすることが重要で す。この場合には計算機の性能が限られているから、解析解を直接 数値にするよりも、数学的には美しくないかもしれないけど漸化式 から数値化していくということを行うことに工学的な意味がありま す。
普通の問題では解析解が一番数値計算するのが楽で、計算時間も計 算に必要なメモリも計算量(CPU)も小さいです。計算解は解析解より も計算コストが大きいので使われないです。しかし今回の問題では 計算解では計算のコストはややかかるはずですが、逆に実用上はこ ちらで解いた方がスムーズです。
こう考えていくと、場合によってはもっと後退して、近似解や思い つきの解（モデル解）なんていうのが実用的になる場合だってある はずです。(2011/6/1)
「解析解」と「計算解」を両方比較してみたい方のために、 一つのページ にまとめました。お楽しみください。
また神戸大学大学院工学研究科の森井昌克先生に、この記事の紹介をいただきました。ありがとうございました。(2021/7/1)
Yahoo Newsの記事 「ガチャに騙されるな？！ ~数学センスで万事解決（第４回）~」