| 著作一覧 |
次の問題：
あるお菓子のおまけは3種類ある。お菓子1個につき1つのおまけが入っている。この時、3種類すべて揃うことが期待できる個数を求めよ。なお、おまけの数は同数とする。
食玩とかに応用させる問題だとは思うが、わからない。
最小は3個だということはわかる。最大（というか最悪）は、仮に1おまけにつき10000個製造されるとすれば20001個ということもわかる（ということは最大値はロットが不明な以上わからないということだし、それはしたがって設問に答えるのには考えなくても良いということだろう）。
ではどう考えるのか、がわからない。
答えはわかる。はず。
Target = ARGV.length == 0 ? 3 : ARGV[0].to_i
Try = ARGV.length < 2 ? 100000 : ARGV[1].to_i
Mask = (0...Target).inject(0) {|i, n| i |= 1 << n}
def buy
r = 0
c = 0
while r != Mask
r |= 1 << rand(Target)
c += 1
end
c
end
puts "avg = #{(1..Try).inject(0) {|total, n| total += buy } * 1.0 / Try}"
5.5になる(回数をどんどん増やせば)。したがって6個買えば良い。でも、どういう計算で5.5になるんだ？最終的な追記：できた。
Target = ARGV.length == 0 ? 3 : ARGV[0].to_i
puts "#{(1..Target).inject(0) {|n, i| n += (Target * 1.0) / i}}"
最後の追記：これが期待値なのか(完膚なきまでに忘れきっていた)。再発見してしまいましたよ。yowaさん、shinhさん、どうもありがとう。
蛇足：設問に期待って書いてあるね（期待値という言葉そのものを忘れてた）。
(1.0 - done_prob - 1.0/(3.0**(i-2))) / 3
まったくわからないのが困ったところ。
最初の1.0は必ずそうなるの1.0かな。done_probは名前から試し終わったやつ、最初のグラフの縦軸の値と同じなのか？ 次のはなんでi-2乗したもので割ってるのかわからないと書いたところで、これも引いているってことはiが現時点での値か。こういう式になるんだな。で、全体を3で割っているのは1つ当たりということか？
#注意：僕が種類を増やせるかな、と試しに変えてみたリスト。 #これは正しい値を出せない：shinhさんの解説参照 k = (ARGV.length == 0) ? 3 : ARGV[0].to_i T=1000 expect=0.0 done_prob = 0.0 for i in k..T prob = (1.0 - done_prob - 1.0/((k * 1.0)**(i-(k-1)))) / k done_prob += prob expect += prob * i end p expect
Taeo分布のLisp版の解説と読み合わせてなんとなくわかった気になる（が、わかってないから説明できないし、自分じゃ書けない）。
人生の後になったら読み直す。
ジェズイットを見習え |
Teao 分布と言うそうです。（ネタ）<br>http://chasen.org/~taku/teao/
えーと私のやろうとしたことですが…各試行の開始時に3つの状態がありますよね。1種類持っている状態、2種類持っている状態、3種類持っている状態です。3種類持ってる状態は既に終わっています。次に終わるには、2種類持った状態から、残った1種類をひけば終了、つまり1/3で終了です。<br>というわけで、 (1.0 - done_prob - 1.0/(3.0**(i-2))) / 3 は、 1.0 は必ずそうなるの 1.0 で、 done_prob は前回までに 3 種類そろったからやめたーとなっている確率、 1.0/(3.0**(i-2)) は1種類しか持ってない確率です。つまり (1.0 - done_prob - 1.0/(3.0**(i-2))) で、その時点で2種類持っている確率になっています。あとは 1/3 してやれば次にコンプリートできる確率が求まる、と。<br>で、この方法だと全然 k個のおまけに一般化できないので(ですから、私のコードの3をkに変えられたバージョンは正しい値を出してないと思います)、ちゃんと組み合わせでやらないとなぁと思っていたところ、 Teao の方にちゃんとした答えが載っていた、という感じです。プログラムが書けると、うまく解けないけど答えはわかる、っていうことが結構あって面白いですよね。
解説ありがとうございます。良く読み直して味わってみます。（kは上にメモが残っている4については一致したので、と思ってやり直したら確かに違うのか。循環する3333……が同じだったので合ってると思いこんでしまってました）
Teao のページのLispコードのコメントが間違ってます。<br>正しくは、<br><br>;;;<br>;;; n 回引いて k 種類集まっている組合せの数:<br>;;;<br>;;; k<br>;;; --- i n<br>;;; f(k,n) = > (-1) k C (k-i) (k-i)<br>;;; ---<br>;;; i=0<br>;;;<br>;;; Pr( n 回引いてちょうど k 種類集まる確率)<br>;;;<br>;;; = Pr( n-1 回引いて k-1 種類集まっている確率) * 1/k * k<br>;;;<br>;;; = f(k-1,n-1) / k^(n-1)<br>;;;<br><br>です。因みにこの式から得られた期待値がartonさんの<br><br> (1..Target).inject(0) {|n, i| n += (Target * 1.0) / i}<br><br>に等しいことは、純粋に計算で示せます。
あれ、スペースが飛んじゃった。書き換えたのは日本語のコメント部分だけです。
おお、（と最初に思ったのは）'shinh'と記述可能なお二人がツッコミ入れてくれているということ（うれしい）。<br>というのはさておき、「その時点で既に集まっている」数と読むわけですね。shinhさんのも同じだし。なるほど（解法を理解してなるほどと書いているのではまだなくて、別のことを考えている）なぁ、そういうふうに考えていくんですね（ここが越えられない壁なのだな、と「なるほど」と思った）。
僕も最初、もう一人の自分だと思いました。(^^;)<br>f(k,n)ですけど、これは「包除原理」を使った式です。<br><br>実はこれ、「Ｎ潟県数学選手権中学生(!)大会」の問題候補でした。難しすぎるのと、artonさんの出してきた式を証明なしで答えられた場合の採点をどうするかでもめてボツになりました。