ハッカタベタクナイー問題
過去ブログの転載です。
ガチャガチャの景品が種類あったとき、それをコンプリートするために回さないといけない回数を求めることをクーポンコレクター問題といいます。ガチャガチャは一度出た景品がまた出てきてしまうので、種類の景品を集めるのに回回せばいい、というわけには当然いかず、結構余計に回す必要があります。
では何回回せばいいかというと、次式で求めることができます:
クーポンコレクター問題
ガチャガチャの種類の景品がそれぞれすべて同じ確率で出るとき、全種類コンプリートするために回さなければいけないガチャガチャの回数の期待値は 回
※ は番目の調和数
例えば種類であれば、以下のようになります:
回
結構余分に回さないといけないんですね。確かに最後の1種類とかになると、残りの9種類はいらないので確率が低いです。
以上がクーポンコレクター問題で便利な公式なのですが、これは本記事の前置きです。似たような空気の、別の問題を考えてみます。
ハッカ食べたくないです
色んな種類が入ったチョコレート。アーモンドが好きじゃないので、つい避けて食べてしまうのですが、当然アーモンドが残っていくので、てきとうに取り出したものが
アーモンドになっちゃう確率が高くなってしまいます。
ドロップのハッカの方が分かりやすいと思いますけど、ハッカ味を食べようとして別の味ばっかり食べていってたら、そのうちハッカだらけになっちゃいますよね。そうしたら、どうしても後半になるとハッカを取り出してしまうことが多くなり、イライラしてしまうことになります。
ハッカ以外のドロップを完全に食べきるまでに、一体何個ハッカを取り出してしまうのか、期待値を知りたくなりますね。この期待値を求めることを、ハッカタベタクナイー問題*1と呼びます。
ハッカタベタクナイー問題
食べたいお菓子個と、食べたくないお菓子個の、個のお菓子が混在したお菓子袋の中からランダムに取り出し、食べたくないお菓子が出たら戻して再度取り出す、という操作を繰り返す。戻す回数の期待値は 回
式がクーポンコレクター問題にとてもよく似ており、実際としてやればまったく同じ式になるのですが、たぶん関係ないと思います。いや、あるのかなぁ。*2
例:ハッカを避けて食べる際の、ハッカを戻す回数期待値
この式を使うと、ドロップのハッカを避けて残りの味すべてを完食するまでに、ハッカを取り出しては戻す、という操作を何回ぐらいすればいいのかの期待値が求められます。実際に求めてみましょう。
参考:Taro's Page [Sakuma Drops vs. Sakuma-Shiki Drops]
実はサクマドロップスとサクマ式ドロップスの2種類があるそうです。それぞれの場合について、ハッカを食べずにそれ以外を完食するまでの、ハッカを取り出してしまう平均回数を求めてみましょう。
サクマドロップスの場合
ハッカが個、合計個、とのことなので、をそれぞれ代入して、平均回数は回となります。ハッカが結構多いので、回数もすごいことになっています……40回もしてたのか。
サクマ式ドロップスの場合
ハッカが個、合計個、とのことで、ハッカ率はとても低くなっています。をそれぞれ代入すると、平均回数は回となります。ハッカは3個しかないはずですけど、結構引いちゃうんですね。あたりがいくら多くても、最終的にはハッカだらけになってしまうためでしょう。
このように案外回数が多いので、本当にイライラしたくなければすべて取り出して選別したほうがいいと思います^^;
導出
ハッカタベタクナイー問題の公式を導出します。
まず、あたりが個、はずれが個の初期状態で考えます。
回目に取り出したものがあたりである確率はですね。逆に、回目ではずれになる確率はですから、回目がはずれで、回目にあたりになる確率は、になります。
同様に、回目であたるのはとなって、回目であたるのはとなります。
平均して何回目であたりを引くのかを求めるためには、回数に確率を掛けたものの総和を求めれば良いですね。期待値のことです。
この場合は無限に項があるので、無限級数になります:
ここで、
が成り立つことから、
回となります。これが初期状態での平均回数です。
例えばあたりが個、はずれが個の場合、はずれを引いたらやり直してあたりを個でも引く期待値を計算すると、を上式に代入して、回ということになります。平均回であたりを引けるということですね。
これはあたりを回引くまでの平均回数なので、あたり個目、個目、、個目の場合の期待値を計算し、全部足し算しましょう。*3
あたり個目を引く場面における回数の期待値をとすると、と表せます。前述の式において、あたりの個数が徐々に減っていくということで、こんな式になっています。
よって、すべてのあたりを引くまでの平均回数は次式で得られます。
これを求めればOKです。
のとき分母は、のとき分母は、となることから、範囲をひっくり返しても式は変わらず、
となります。(は調和数)
従って、として求めることができます。
この回数はあたりを引く回数を含めた総回数になるので、冒頭にあったようにはずれを引いたら戻すということを繰り返す回数は、あたりを引く回数であるを引いた、回となります。これがハッカタベタクナイー問題の答えです。
おまけ
自然数の逆数の和を調和数といいますが、計算は面倒です。よっぽど項が多いのでなければ、地道に足していくのが一番早いと思います。
一応、関数を使った表現も可能であり、近似計算も可能なのですが、その関数自体を計算するのが難しいので、それこそとかとかぐらいまで足さないといけない状況にならなければ使う必要ないでしょう。以下をご参照ください: