たくさんボールを投げて同じ箱に入る確率は?

たくさんボールを投げて同じ箱に入る確率は?

少なくとも 2 個のボールが同じ箱に入る確率は?

 $n$ 個の箱が並んでいて、そこに $a$ 個のボールを $1$ 個ずつ順番に投げ入れます。ボールは必ずどれかの箱に入り、どの箱に入る確率も等しいとします。すべてのボールを投げ終えたとき、少なくとも $2$ 個のボールが同じ箱に入る確率を $P$ とします。

[1] $P$ の表式を $a$ と $n$ で表してください。

[2] ボールの個数と箱の数を受け取って確率 $P$ を返す関数を Python で実装してください。

[3] $1000$ 個の箱に向けてボールを投げ入れるとき、少なくとも $2$ 個のボールが同じ箱に入る確率が $50$ % 以上になるには、最低何個のボールを投げる必要がありますか。
 

ヒント

 [1] では確率を計算する数式を考えます。[2] は for 構文などで記述すると比較的簡単に実装できますが、余裕のある人はループ以外で処理する方法も考えてみてください。NumPy を使えるのであれば配列演算機能を生かします。解答は広告の下です。
 

ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装

中古価格
¥2,818から
(2019/7/30 20:24時点)


 

解答

[1] すべてのボールが異なる箱に入る確率 $Q$ を求めることができれば、少なくとも $2$ 個のボールが同じ箱に入る確率は $P=1-Q$ で計算できます。

 たとえば、$3$ 個のボールを $5$ 個の箱に投げ入れて、すべて異なる箱に入る確率を考えてみましょう。最初に投げたボールが入る箱はどれでも構いません。敢えてどれかの箱に入る確率を記述するならば $5/5=1$ となります。

 続けて $2$ 個目のボールを投げます。最初に投げたボールが入っている箱を除いた、残り $4$ 個の箱のいずれかに入る確率は $4/5$ となります。同様に考えて、$3$ 個目のボールが残り $3$ 個の箱のどれかに入る確率は $3/5$ です。確率の乗法定理より、すべてのボールが異なる箱に入る確率は
 
\[Q=\frac{5}{5}\,\frac{4}{5}\,\frac{3}{5}=0.48\tag{1}\]
となるので、少なくとも $2$ 個のボールが同じ箱に入る確率は
 
\[P=1-Q=0.52\tag{2}\]
となります。一般化して、$a$ 個のボールを $n$ 個並ぶ箱に投げ入れるとき、すべて異なる箱に入る確率は
 
\[\begin{align*}Q&=\frac{n}{n}\,\frac{n-1}{n}\,\frac{n-2}{n}
\,\cdots\,\frac{n-(a-1)}{n}\\[6pt]
&=\frac{n(n-1)(n-2)\,\cdots\,(n-a+1)}{n^a}\end{align*}\tag{3}\]
となるので、得られた値を $1$ から引いて $P$ を得ます。
 
[2] それでは実装に進みましょう。最初の例は for を使った基本的なコードです。$Q$ の分子は range() 関数で計算できます。

# PYTHON_BALL_AND_BOX_00-1

def ball_box_0(a, n):
    k = 1
    for i in range(n-a+1, n+1):
        k *= i
    return 1 - k/n**a

 動作確認のために、$3$ 個のボールを $5$ 個の箱に向けて投げて、少なくとも2個のボールが同じ箱に入る確率を計算しておきます。

# PYTHON_BALL_AND_BOX_00-2

p = ball_box_0(3, 5)

print("{:.3f}".format(p))
0.520

 集約関数 functools.reduce() と乗算関数 operator.mul() を使って次のようなコードを書くこともできます。

# PYTHON_BALL_AND_BOX_01

from functools import reduce
from operator import mul

def ball_box_1(a, n):
    x = range(n - a + 1, n + 1)
    y = reduce(mul, x)
    return 1 - y / n**a

p = ball_box_1(3, 5)

print("{:.3f}".format(p))
0.520

 NumPy を活用したコードも掲載しておきます。
 numpy.arange() で n - a + 1 から n までの連番配列を作って、各要素を n で割り、numpy.prod() で総積を求めます。

# PYTHON_BALL_AND_BOX_02

import numpy as np

def ball_box_2(a, n):
    x = np.arange(n - a + 1, n + 1) / n
    return 1 - np.prod(x)

p = ball_box_2(3, 5)

print("{:.3f}".format(p))
0.520

[3] 引数 a に 1 から順に値を入れて確率を計算し、0.5 を超えたらプログラムを終了させます。for と break を用いた、Python の基本的なコードです。
 ball_box_2(a, n) を使う場合は以下のコードで計算できます。

# PYTHON_BALL_AND_BOX_03

import numpy as np

def ball_box_2(a, n):
    x = np.arange(n - a + 1, n + 1) / n
    return 1 - np.prod(x)

for i in range(100):
    p = ball_box_2(i, 1000)
    if p >= 0.5:
        print("{}個".format(i))
        print("p = {:.3f}".format(p))
        break
38個
p = 0.509

 $38$ 個のボールを投げたときに、確率は $0.5$ を超えます。
 

[補足] 処理速度の比較

 [2] で実装した関数の処理速度を比較しておきます。100 万個並ぶ箱に向けて 1 万個のボールを投げ入れるという設定で計算させます。以下のコードサンプルでは Jupyter Notebook の %timeit コマンドを使っていますが、Jupyter 以外の環境では timeit モジュールの timeit() 関数などを使ってください。

 ball_box_0() の処理速度を計測してみます。

%timeit -r 3 -n 10 ball_box_0(10**4, 10**6)
330 ms ± 4.55 ms per loop (mean ± std. dev. of 3 runs, 10 loops each)

 ball_box_1() も処理速度にほとんど差はありません:

%timeit -r 3 -n 10 ball_box_1(10**4, 10**6)
327 ms ± 1.54 ms per loop (mean ± std. dev. of 3 runs, 10 loops each)

 NumPy を活用した ball_box_2() は桁違いに高速です。

%timeit -r 3 -n 100 ball_box_2(10**4, 10**6)
156 µs ± 26.7 µs per loop (mean ± std. dev. of 3 runs, 100 loops each)