確率10-10
586 名前:132人目の素数さん[] 投稿日:2005/11/17(木) 12:06:40 商品を買うと,a種類の内b種類がランダムおまけとしてついてきます(1回でb種類が同じおまけになる事はない) おまけ全てをc個ずつ集めるには,平均いくつの商品を買えば良いか?
587 名前:132人目の素数さん[sage] 投稿日:2005/11/17(木) 12:20:09 >586 いまいち問題の内容がつかめない。 おまけは全部で a 種類あって、その中から b 個がランダムに選ばれる。 選ばれた b 個の中には同じ種類のおまけが二つ以上含まれることはない。 ってことかいな。
解答
590 名前:587[sage] 投稿日:2005/11/17(木) 13:24:32 うーん。 b = c = 1 のときは有名問題で aloga だけど、 b = 2, c = 1 のときですでに式がめちゃくちゃ汚くなってきた。 これ一般の a,b,c できれいに解けんのか?
591 名前:587[sage] 投稿日:2005/11/17(木) 13:31:24 q_k を * q_0=q_1=q_2=1, * q_k = (k-1)q_{k-1} + n(n-1)q_{k-2} (k>=3) を満たす数列として、 数列 p_k を * p_0=1,p_1=0,p_2=1 * p_k = k(k-1)(n-2)(n-3)・・・(n-k+1)q_k/{n(n-1)}^{k-1} (k>=3) #最初の二つだけが k になってるのは間違いではない として定義する で、期待値が a Σp_k k=1 になる。
592 名前:132人目の素数さん[] 投稿日:2005/11/17(木) 16:33:35 >>591 詳しくおながいしまつ
593 名前:132人目の素数さん[] 投稿日:2005/11/17(木) 18:43:34 詳しくあげ
594 名前:132人目の素数さん[] 投稿日:2005/11/18(金) 04:44:46 Sk を、おまけをk個持っている状態とする。 Pr{i,j} を状態 i から k へ遷移する確率とすると * Pr{k,k} = k(k-1)/n(n-1) * Pr{k,k+1} = k(n-k)/n(n-1) * Pr{k,k+2} = (n-k)(n-k-1)/n(n-1) 商品を買い始めてから全ての おまけを集めるまでに状態 k に到達する確率を Pr{k} とすると * Pr{k} = Pr{k-1}Pr{k-1,k} + Pr{k-2}Pr{k-2,k} * Pr{0} = 1 * Pr{1} = 0 Xk を状態 k での滞留時間とすると、 Sk にたどり着く確率が Pr{k} でその後 Sk->Sk のループを繰り返す 回数の期待値が 1/Pr{k,k} だから * E[Xk] = Pr{k}/Pr{k,k} これを計算すれば >587 の p_k になる。 でもとめるものは * ΣE[Xk] q_k は面倒なので求めなかった。 つーか初項がたぶん間違ってる。
595 名前:132人目の素数さん[sage] 投稿日:2005/11/18(金) 05:14:04 >>590 > うーん。 b = c = 1 のときは有名問題で aloga だけど、 aloga って何?
596 名前:132人目の素数さん[sage] 投稿日:2005/11/18(金) 05:16:57 a*log(a)
597 名前:587[sage] 投稿日:2005/11/18(金) 05:25:32 "coupon collector" でググってみると良い。 どうも、c=1の場合でも研究の対象になってるみたいだな。 c=1 の場合にすら一般式を出すのは seems impossible だそうだ。
598 名前:132人目の素数さん[sage] 投稿日:2005/11/18(金) 05:43:38 >>586に 1回で がなければ問題がはっきりするけどそのへん明らかにして再掲されては?
599 名前:132人目の素数さん[sage] 投稿日:2005/11/18(金) 06:06:03 >>598が再掲しろと言ってるぞ!
603 名前:132人目の素数さん[] 投稿日:2005/11/18(金) 22:58:15 >>586再括 ①商品を買うと,6種類の内1種類がランダムおまけとしてついてきます おまけ全てを2個ずつ集めるには,平均いくつの商品を買えば良いか? ②商品を買うと,6種類の内1種類がランダムおまけとしてついてきます おまけ全てをa個ずつ集めるには,平均いくつの商品を買えば良いか? 難し過ぎるからこれにしとく 因みに1個ずつ集めるには1+(6/5)+(6/4)+(6/3)+(6/2)+(6/1)=14.7個
604 名前:132人目の素数さん[sage] 投稿日:2005/11/18(金) 23:32:50 >>603 解ける?>>597の人によると一般には seems impossible という意見があるみたいだけど。 持ってる答えまちがいない?
654 名前:132人目の素数さん[sage] 投稿日:2005/11/23(水) 02:02:23 >>603 (1) あと、m 種類を1個ずつ、n 種類を2個ずつ集めればコンプという状態から、 コンプまでにかかる平均回数を a[m,n] とすると a[0,0] = 0, a[m,n] = (m*a[m-1,n] + n*a[m+1,n-1] + 6) / (m+n) が成立して、計算すると a[0,6] = 390968681/16200000 = 24.133… 平均 24個強買えば良いと