2種類の味が入ったボトル入りのガム。
この所謂2色入りガムから、無作為に2つ取ったとき、いつも、2種類の味を1つずつ取っている気がした。
そこで、こんな疑問が浮かんだ。
「ガムを食べきるまでにどのぐらいの割合で、違う味のガムのペアが取り出せるのだろうか」
本日の問題
問1
マスカット味とグレープフルーツ味の2種類のガムが、それぞれ100個ずつ入っているボトル入りのガムがある。このボトルから、無作為に2個ずつ、無くなるまで取り出す。取り出した2個のガムの味が異なる回数は、無くなるまでの100回中平均何回だろうか。
実際にやってみる
こういった離散数学の問題は、実際にシミュレートすることができる。
from random import shuffle, randint
def random_pick(bottle):
x = randint(0, len(bottle) - 1)
return bottle.pop(x)
def test(n = 100):
bottle = [0] * n + [1] * n
shuffle(bottle)
result = 0
while len(bottle) >= 2:
a = random_pick(bottle)
b = random_pick(bottle)
if a == b:
result += 1
return result / n
※本当は、シャッフルして先頭から順に見ていくだけでいいのだが、見栄え上、取り出すときもランダムにしてみた。
以下が実行結果。
test()
0.5
test()
0.52
test()
0.58
test()
0.52
test()
0.5
test(10000)
0.4994
test(10000)
0.4972
test(10000)
0.4962
test(10000)
0.508
test(10000)
0.5014
見たところ、ほぼ2分の1、つまり100回中約50回の割合で、異なる味のガムのペアが取り出せると考えられる。いつも、異なる味が1つずつ取り出せたと思っていたのは、私のただの勘違いだったようだ。
ただ、厳密解については、きっちり2分の1、であるとは考えにくい。なぜなら、マスカット味とグレープフルーツ味がそれぞれ2個ずつ入っていた場合の、異なる味のペア数は、2/3の確率で2、1/3の確率で0、つまり2回中平均4/3回であるからだ。これは2分の1である2回中1回よりも多い。
一般化
問題を一般化して、厳密解を求める。
問2
マスカット味とグレープフルーツ味の2種類のガムが、それぞれx個、y個ずつ入っているボトル入りのガムがある（ただし、x+yは偶数）。このボトルから、無作為に2個ずつ、無くなるまで取り出す。取り出した2個のガムの味が異なる回数は、無くなるまでの$\dfrac{x+y}{2}$回中平均何回だろうか。
解く
確率漸化式に表せることは、すぐに察することができる。
答えの値を、$f(x,y)$とおく。任意の非負偶数$k$について、
$$ f(1,1)=1, f(k,0)=0, f(0,k)=0 $$
である。また、1以上で和が偶数の整数の組$x, y$について、
$$ \begin{align} \
f(x, y)&=\dfrac{x(x-1)}{(x+y)(x+y-1)}f(x-2, y)\\
&+\dfrac{y(y-1)}{(x+y)(x+y-1)}f(x,y-2)\\
&+\dfrac{2xy}{(x+y)(x+y-1)}\{1+f(x-1,y-1)\}\\
\end{align} $$
である。式の意味としては、味Aを2つ取った場合、味Bを2つ取った場合、味Aと味Bを1つずつ取った場合を足し合わせているだけである。$x$や$y$が1のときもあるが、その場合には、分子に0の因子が現れるため問題ない。
さて、漸化式には表せたが、拙者は特に数学に強いわけでは無いので、実際に$x, y$に代入して計算した結果をみて、答えの式を予想することにする。手作業で計算するのは面倒なので、また、Pythonの力を借りることにする。
from fractions import Fraction
memo = {}
def f(x, y):
assert (x + y) % 2 == 0
if x <= 0 or y <= 0:
return Fraction(0)
if (x, y) in memo:
return memo[x, y]
A = x * (x - 1) * f(x - 2, y)
B = y * (y - 1) * f(x, y - 2)
C = 2 * x * y * (1 + f(x - 1, y - 1))
memo[x, y] = Fraction(A + B + C) / ((x + y) * (x + y - 1))
return memo[x, y]
Pythonのfractionsモジュールというのは便利で、計算を、既約分数の形で行うことができる。これにより、小数の精度の問題をほとんど気にしなくて済むようになるので、お薦めである。
さて、実行結果は以下である。
f(100, 100)
Fraction(10000, 199)
f(200, 300)
Fraction(60000, 499)
かなり綺麗な値が出た。容易に、$f(x,y)=\dfrac{xy}{x+y-1}$であると予想できる。
証明
$f(x,y)=\dfrac{xy}{x+y-1}$を先ほどの漸化式に代入して証明する。
$$ \begin{align} \
\dfrac{xy}{x+y-1}&=\dfrac{x(x-1)}{(x+y)(x+y-1)}\dfrac{(x-2)y}{x+y-3}\\
&+\dfrac{y(y-1)}{(x+y)(x+y-1)}\dfrac{x(y-2)}{x+y-3}\\
&+\dfrac{2xy}{(x+y)(x+y-1)}\{1+\dfrac{(x-1)(y-1)}{x+y-3}\}.\\
\end{align} $$
両辺に$(x+y)(x+y-1)$を掛けて整理する。（以下は単なる式計算です）
$$ \begin{align} \
(x+y)xy&=x(x-1)\dfrac{(x-2)y}{x+y-3}\\
&+y(y-1)\dfrac{x(y-2)}{x+y-3}\\
&+2xy\{1+\dfrac{(x-1)(y-1)}{x+y-3}\}.\\
\end{align} $$
両辺に$x+y-3$を掛ける。
$$ \begin{align} \
(x+y-3)(x+y)xy&=xy(x-1)(x-2)\\
&+xy(y-1)(y-2)\\
&+2xy(x+y-3)+2xy(x-1)(y-1).\\
\end{align} $$
$xy \ne 0$の場合であると仮定して、両辺を$xy$で割る。
$$ \begin{align}\\
(x+y-3)(x+y)&=(x-1)(x-2)\\
&+(y-1)(y-2)\\
&+2(x+y-3)+2(x-1)(y-1).\\
\end{align} $$
展開して整理する。
$$ \begin{align} \\
(x+y-3)(x+y)&=x^2-3x+2\\
&+y^2-3y+2\\
&+2x+2y-6+2xy-2x-2y+2,\\
(x+y-3)(x+y)&=x^2-3x+2\\
&+y^2-3y+2\\
&+2x+2y-6+2xy-2x-2y+2,\\
(x+y-3)(x+y)&=x^2-3x+2xy-3y+y^2.\\
\end{align} $$
左辺を展開すれば、両辺が等しいことが分かる。よって、$f(x,y)=\dfrac{xy}{x+y-1}$が示された。
∎
考察
厳密に目的の答えを得た。たとえば、$f(100,100)=\dfrac{10000}{199}\approx 50.3$であり、200個入りのガムでは、100回中約半分の回数、異なる味のペアを取り出すと分かる。
しかし釈然としない点がある。
- これだけ簡単な式なら、直観的な解法が存在したのではないか
- 答えの式が、何かの式に似ている気がする
実の所、これらは、答えの式を、割合として直すと明らかになる。
つまり、$x+y$個入りなら、取り出す回数は$\dfrac{x+y}{2}$であるから、それで割れば割合が出てくる。異なるペアを取り出す割合を$g(x,y)$とおくと、
$$ g(x,y)=\dfrac{2}{x+y}f(x,y)=\dfrac{2xy}{(x+y)(x+y-1)} $$
となる。これは、一番最初に取り出す2つのガムが、異なる味のペアである確率に等しい。
要するに、1回あたりの異なるペアを取る確率を考えると、その値は、無くなるまで取り尽くす場合でも、最初の状態、つまり、取った2つを毎回戻す場合でも、同じ値なのである。
たとえば、考えてみてほしい。サイコロを2回振って、和が9になる確率と、「１」「２」……「６」までの6種のカードが10枚ずつ入った箱から、2枚ずつ、無くなるまで取り出した時の、和が9になる1回辺りの確率を。
これらが異なる確率になるとは到底考えられない。
つまり、こういうことが言えるのではないだろうか。或る条件の下で、
「離散的な事象の確率は、バッチにしても変わらない」
統計学の基礎定理に、こんな風なものがありそうな気がする。私は数学に特段強くないので分からないが。
応用
離散的な事象の確率が、バッチにしても変わらないとして、次のような応用がある。
それは、ぷよぷよテトリスでの応用である。
7種類あるテトリミノを考えたとき、ただ単に7分の1の確率で、Nextのテトリミノを決めた場合、極端に偏る可能性が生じる。たとえば、100回連続、縦長の棒が来ないといったことや、10回連続S字のブロックが来るなどいった可能性である。
そこでバッチ化を考える。というのは、例えば、14回の区間ごとに、各種のテトリミノはちょうど2個ずつ落ちてくるようにする、といった設定である。そうすれば、極端に偏った配牌を避けることができる。
その上、先ほどの、
「離散的な事象の確率は、バッチにしても変わらない」
が正しいとするなら、例えば、2つごとに見たテトリミノの組合せの出る確率は、単純に7分の1の確率で出現させる場合の確率と変わらない、のである。（ただし、3つごとの出現確率はもちろん変わる）
というわけで強引にまとめると、ガムの払底は、買い足しの区切りとともに、期待値的な区切りでもあったわけだ……。
まとめ
- 2色のガムが同数入ったボトルから無作為に2つ取ってゆくとき、同じ味のペアを取る回数と、異なる味のペアを取る回数は、ほとんど同じである。
- ただし、ほんの少しだけ、異なる味のペアを取る確率の方が大きい。
