読者です 読者をやめる 読者になる 読者になる

2重余事象

タイトルは造語。
http://q.hatena.ne.jp/1361848511

数学、確率の問題です。

1〜kまでの正の整数が書いてあるカードがm組あり、それぞれのカードの組からn枚ずつカードを引くとき、すべてのカードの組から、同じ数字のカードを、少なくとも1枚引く確率を求めよ。ただし、n < k * 1/2 とする。
この問題をとくにはどう考えれば良いのでしょうか。解法か、それに類する情報が掲載されているサイトでも結構です。

この問題,よくある問題かと思ってちょっと考えてみたけど案外難しい。思いつくのは数え上げによる方法。「少なくとも」には余事象の数え上げが有効ということで余事象を「どのカードもm組の内のいずれかの組では選ばれない」と考えてみると,これは「いずれのカードにしても,m組の内にはそのカードが選ばれない組が少なくとも1つある」ということにほかならず,また余事象を考えたくなる。それで余事象を考えてみるとこれは原文と全く同じことになってしまうように思う*1。何か変なドツボにはまってしまった。
求める確率をP(k,n,m)などとおいて漸化式を立てればうまくいくだろうか。
例えばすべてのm組で引かれるカードの枚数が1枚の時だと,P[1](k,n,m) = k * (1/k)^m * (1-P(k-1,n-1,m))
同じようにすべてのm組で引かれるカードの枚数がa枚の時だと,P[a](k,n,m) = kCa * (1-[k-a]Cn/kCn)^m * (1-P(k-a,n-a,m))
これはa=0からnまで正しい。ここでも2重の余事象を考えたい事情が現れてしまっているのかな。ひとまず原理的には,こうするとP(k,n,m)=Σ[a=1...n]P[a](k,n,m)=…となって,最終的にはP(k-n+1,1,m)だけで書けるはず。しかしこれはいかにも筋が悪い気がするし,数値的に解くならまだしも解析解は求まりそうにない。


何かの極限で正しいだろう解なら次で与えられるだろう。それぞれの数字があるカード組において選ばれる確率はn/kなので,m組の全部で選ばれるわけではない確率は 1-(n/k)^m。数字がk個あるので,これらの確率が独立に扱えるとするとk個の数字が各々m組のすべてにおいて選ばれるわけじゃない確率は {1-(n/k)^m}^k になる。なので余事象を考えると 1-{1-(n/k)^m}^kになる。これは各数字間の従属性を無視しているので正しくない。例えばk=5,n=1,m=10とかすると,
P(5,1,10) = 5 * 1/5^10
1-{1-(1/5)^10}^5 = 5 * 1/5^10 - 10 * (1/5)^20 + 10 * (1/5)^30 - 5 * (1/5)^40 + (1/5)^50
少し差がある。一般のnで比較するのは無理かな?


上の問題について何かアイディアがある人は俺も教えてほしいですね。

*1:なんか変な感じで,うまく余事象を考えられてないような