数学が出来る人は既に予想できると思うんですが，
なにぶん，自分は全く数学ができないので・・・←
シミュレーションを行うプログラムを作成し，
おおよその数を得ることにしました．
以下，結果から得られた図です．
両対数のグラフで，横軸がx，縦軸が試行回数を表しています．
xは10, 100, 1000, 10000, 100000, 1000000, 10000000で
各10回ずつシミュレーションを行いました．
プロットされているのはその平均です．
擬似乱数生成器はmt19937を使いました．
点線はgnuplotのfit（設定はデフォルト）により得られたもの．
線形．なんていうかほぼ線形関係みたいですね．
なるほど・・・．← 全然わかっていない
だいたいxの10倍の数だけ乱数を生成すれば，区間すべての整数が得られるみたいです．
重複組み合わせなどを用いて考えると10倍すれば，
まぁ，得られるんじゃね？ってことは想像できるんですが・・・ orz
例えば，n種類ある整数をm個取り出す(重複組合せの数)をnHmとすれば，
m個取り出す内，各種類必ず1つ以上選択したときの重複組合せの数はnHm-nになる．
また，nHm-n/nHmってmを大きくするとだんたん1に近づくじゃないですか．←
この値が1に近いほどそのm個取り出したときに各整数が少なくとも1つ以上含まれている
組み合わせの割合が大きくなると考えられます．
分子に注目するとnHm-nとなっていますが，m>>nになるとだんだんと
nを無視できるようになります．
このことから，ｍがnの10倍らへんで値が大幅に上昇するんじゃないかなと思います．
うん．自分の数学力ではここまでです．(´・ω・｀)
数学ができる方，教えて下さい．←
// 以下 2012年12月19日追記
おうふ
この問題はクーポン収集問題っていうらしいですね．
大学生にもなって知らないとかまじわろす・・・．
っで，全部の整数が少なくとも1回は選択されるまでの回数の期待値なんか簡単に求まるみたいですね．ちょっと詳しく書くと，0からx-1までの整数において少なくとも1回選択されている整数の数の各状態を考え，その状態に要する選択回数の期待値を足せばいいそうです．これにもたどり着けないとかまじ俺の数学力わろす・・・．具体的には，今回の問題設定の場合には期待値nは以下の式により求まります．
また近似式[1]が良い感じらしいです．ここでγはオイラーの定数（約0.5772）です．
期待値を求めてみたところ以下のようになりました．
凄い見にくいんですが，実験で得られた値と期待値はおおよそ同じ値（なんだそれ）をとっています．なるほどでした．
[1] 岩沢宏和，続確率パズルの迷宮 確率クイズ，数学セミナー，Vol.51，No.6，pp.50-55，2012．
0 件のコメント:
コメントを投稿