RPGツクールと数学のブログ

RPGツクールと数学についてのブログです。

ハッカタベタクナイー問題

過去ブログの転載です。

ガチャガチャの景品が \displaystyle n種類あったとき、それをコンプリートするために回さないといけない回数を求めることをクーポンコレクター問題といいます。ガチャガチャは一度出た景品がまた出てきてしまうので、 \displaystyle n種類の景品を集めるのに \displaystyle n回回せばいい、というわけには当然いかず、結構余計に回す必要があります。

では何回回せばいいかというと、次式で求めることができます:

クーポンコレクター問題

ガチャガチャの \displaystyle n種類の景品がそれぞれすべて同じ確率で出るとき、全種類コンプリートするために回さなければいけないガチャガチャの回数の期待値は \displaystyle n \cdot H_n = n \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) 回 

 \displaystyle H_n \displaystyle n番目の調和数

例えば \displaystyle 10種類であれば、以下のようになります:

 \displaystyle 10 \cdot H_{10} = 10 \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{10} \right) \fallingdotseq 29.29

結構余分に回さないといけないんですね。確かに最後の1種類とかになると、残りの9種類はいらないので確率が低いです。

以上がクーポンコレクター問題で便利な公式なのですが、これは本記事の前置きです。似たような空気の、別の問題を考えてみます。

ハッカ食べたくないです

f:id:fermiumbay13:20180212171529j:plain

色んな種類が入ったチョコレート。アーモンドが好きじゃないので、つい避けて食べてしまうのですが、当然アーモンドが残っていくので、てきとうに取り出したものが
アーモンドになっちゃう確率が高くなってしまいます。

ドロップのハッカの方が分かりやすいと思いますけど、ハッカ味を食べようとして別の味ばっかり食べていってたら、そのうちハッカだらけになっちゃいますよね。そうしたら、どうしても後半になるとハッカを取り出してしまうことが多くなり、イライラしてしまうことになります。

ハッカ以外のドロップを完全に食べきるまでに、一体何個ハッカを取り出してしまうのか、期待値を知りたくなりますね。この期待値を求めることを、ハッカタベタクナイー問題*1と呼びます。

ハッカタベタクナイー問題

食べたいお菓子 \displaystyle a個と、食べたくないお菓子 \displaystyle b個の、 \displaystyle (a + b)個のお菓子が混在したお菓子袋の中からランダムに取り出し、食べたくないお菓子が出たら戻して再度取り出す、という操作を繰り返す。戻す回数の期待値は \displaystyle b \cdot H_a = b \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{a} \right) 回 

式がクーポンコレクター問題にとてもよく似ており、実際 \displaystyle n = a = bとしてやればまったく同じ式になるのですが、たぶん関係ないと思います。いや、あるのかなぁ。*2

例:ハッカを避けて食べる際の、ハッカを戻す回数期待値

この式を使うと、ドロップのハッカを避けて残りの味すべてを完食するまでに、ハッカを取り出しては戻す、という操作を何回ぐらいすればいいのかの期待値が求められます。実際に求めてみましょう。

参考:Taro's Page [Sakuma Drops vs. Sakuma-Shiki Drops]

実はサクマドロップスサクマ式ドロップスの2種類があるそうです。それぞれの場合について、ハッカを食べずにそれ以外を完食するまでの、ハッカを取り出してしまう平均回数を求めてみましょう。 

サクマドロップスの場合

ハッカが\displaystyle 10個、合計\displaystyle 41個、とのことなので、\displaystyle a=41-10=31, b=10をそれぞれ代入して、平均回数は\displaystyle 10H_{31}=10 \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{31} \right) \fallingdotseq40.3 回となります。ハッカが結構多いので、回数もすごいことになっています……40回もしてたのか。

サクマ式ドロップスの場合

ハッカが\displaystyle 3個、合計\displaystyle 43個、とのことで、ハッカ率はとても低くなっています。\displaystyle a=43-3=40, b=3をそれぞれ代入すると、平均回数は\displaystyle 3H_{40}=3 \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{40} \right) \fallingdotseq12.8 回となります。ハッカは3個しかないはずですけど、結構引いちゃうんですね。あたりがいくら多くても、最終的にはハッカだらけになってしまうためでしょう。

このように案外回数が多いので、本当にイライラしたくなければすべて取り出して選別したほうがいいと思います^^;

導出

ハッカタベタクナイー問題の公式を導出します。

まず、あたりが\displaystyle a個、はずれが\displaystyle b個の初期状態で考えます。

\displaystyle 1回目に取り出したものがあたりである確率は\displaystyle \frac{a}{a+b}ですね。逆に、\displaystyle 1回目ではずれになる確率は\displaystyle \frac{b}{a+b}ですから、\displaystyle 1回目がはずれで、\displaystyle 2回目にあたりになる確率は、\displaystyle \frac{b}{a+b}\times\frac{a}{a+b}=\frac{ab}{(a+b)^{2}}になります。

同様に、\displaystyle 3回目であたるのは\displaystyle \frac{a}{a+b} \left( \frac{b}{a+b} \right) ^{2}となって、\displaystyle n回目であたるのは\displaystyle \frac{a}{a+b} \left(\frac{b}{a+b} \right) ^{n-1}となります。

平均して何回目であたりを引くのかを求めるためには、回数に確率を掛けたものの総和を求めれば良いですね。期待値のことです。

この場合は無限に項があるので、無限級数になります:

\displaystyle \frac{a}{a+b}+2\frac{ab}{(a+b)^{2}}+3\frac{a}{a+b} \left( \frac{b}{a+b} \right)^{2} + \cdots + n \frac{a}{a+b} \left( \frac{b}{a+b} \right)^{n-1} + \cdots
\displaystyle = \frac{a}{a+b} \sum_{k=1}^{\infty} k \left( \frac{b}{a+b} \right)^{k-1}

ここで、

\displaystyle \sum_{k=1}^{\infty} kr^{k-1}=\frac{1}{(1-r)^{2}}

が成り立つことから、

\displaystyle = \frac{a}{a+b} \frac{1}{\left(1-\frac{b}{a+b}\right)^{2}}
\displaystyle = \frac{a}{a+b} \frac{(a+b)^{2}}{a^{2}}
\displaystyle = \frac{a+b}{a}
\displaystyle = \left(1+\frac{b}{a}\right)回となります。これが初期状態での平均回数です。

例えばあたりが\displaystyle 8個、はずれが\displaystyle 4個の場合、はずれを引いたらやり直してあたりを\displaystyle 1個でも引く期待値を計算すると、\displaystyle a=8, b=4を上式に代入して、\displaystyle 1+\frac{4}{8}=1.5回ということになります。平均\displaystyle 1.5回であたりを引けるということですね。

これはあたりを\displaystyle 1回引くまでの平均回数なので、あたり\displaystyle 2個目、\displaystyle 3個目、\displaystyle \cdots\displaystyle a個目の場合の期待値を計算し、全部足し算しましょう。*3

あたり\displaystyle n個目を引く場面における回数の期待値を\displaystyle c_nとすると、\displaystyle c_n=1+\frac{b}{a-n+1}と表せます。前述の式において、あたりの個数が徐々に減っていくということで、こんな式になっています。

よって、すべてのあたりを引くまでの平均回数は次式で得られます。

\displaystyle \sum_{k=1}^{a} c_{k}

これを求めればOKです。

\displaystyle = \sum_{k=1}^{a} \left( 1 + \frac{b}{a - k + 1} \right)
\displaystyle = a + b\sum_{k=1}^{a} \frac{1}{a - k + 1}

\displaystyle k=1のとき分母は\displaystyle a\displaystyle k=aのとき分母は\displaystyle 1、となることから、範囲をひっくり返しても式は変わらず、

\displaystyle \sum_{k=1}^{a} \frac{1}{a - k + 1} = \sum_{k=1}^{a} \frac{1}{k} = H_{a} となります。( \displaystyle H_{a}は調和数)

従って、\displaystyle = a + b \cdot H_{a}として求めることができます。

この回数はあたりを引く回数を含めた総回数になるので、冒頭にあったようにはずれを引いたら戻すということを繰り返す回数は、あたりを引く回数である\displaystyle = aを引いた、\displaystyle b \cdot H_{a}回となります。これがハッカタベタクナイー問題の答えです。

おまけ

自然数の逆数の和を調和数といいますが、計算は面倒です。よっぽど項が多いのでなければ、地道に足していくのが一番早いと思います。

一応、関数を使った表現も可能であり、近似計算も可能なのですが、その関数自体を計算するのが難しいので、それこそ\displaystyle \frac{1}{1000}とか\displaystyle \frac{1}{2000}とかぐらいまで足さないといけない状況にならなければ使う必要ないでしょう。以下をご参照ください:

fermiumbay13.hatenablog.com

*1:私がなづけました許して

*2:式が似ているというだけの理由で、前置きにクーポンコレクター問題を提示しました。実は関係あるのかな?

*3:複数の事象を合わせた場合の期待値は、各々の期待値の和で表すことができます:E[X+Y]=E[X]+E[Y]