容量Kの箱M個にN個のボールをランダムに入れていって箱からボールがあふれる確率

問題

https://twitter.com/kazuho/status/1604705858708836352

解法

余事象を考えると、すべての箱 (バケツ) についてボールが K 個以下になるようなボールの入れ方が何通りあるか分かればよいです。これはよく見る (?) タイプの DP で求められます。

import math


N = 200
M = 63
K = 16

# dp1[i][j] := バケツ i までに、各バケツ K 個以下、合計 j 個のボールを入れる場合の数
dp1 = [[0] * (N + 1) for _ in range(M + 1)]
# dp2[i][j] := バケツ i までに、合計 j 個のボールを入れる場合の数
dp2 = [[0] * (N + 1) for _ in range(M + 1)]
dp1[0][0] = 1
dp2[0][0] = 1
for i in range(M):
    for j in range(N + 1):
        for x in range(N + 1):
            if j + x <= N:
                c = math.comb(N - j, x)  # バケツ i+1 に入れる x 個のボールの選び方
                if x <= K:
                    dp1[i + 1][j + x] += dp1[i][j] * c
                dp2[i + 1][j + x] += dp2[i][j] * c

print(1.0 - dp1[M][N] / dp2[M][N])  # 1.8985225437306852e-06

シミュレーション

実際に N 個のボールをランダムに箱に入れる操作のシミュレーションをたくさんおこなってみます。

試行回数 T * U の小さいうちは (seedの選び方によって) ブレが目立ちますが「ボールがあふれた回数 / 試行回数」は 1.8985e-6 付近の値を取りました。

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"sync/atomic"
)

func main() {
	const T = 16
	const U = 6250000
	const N = 200
	const M = 63
	const K = 16

	var overflowCount uint64
	var wg sync.WaitGroup

	for t := 0; t < T; t++ {
		wg.Add(1)
		go func(seed int64) {
			r := rand.New(rand.NewSource(seed))
			for u := 0; u < U; u++ {
				var a [M]int
				overflow := false
				for j := 0; j < N; j++ {
					p := r.Int31n(M)
					a[p] += 1
					if a[p] > K {
						overflow = true
						break
					}
				}
				if overflow {
					atomic.AddUint64(&overflowCount, 1)
				}
			}

			wg.Done()
		}(int64(t))
	}

	wg.Wait()
	total := uint64(T) * uint64(U)
	fmt.Printf(
		"%v / %v = %.10f\n",
		overflowCount,
		total,
		float64(overflowCount)/float64(total),
	)

	// U = 6250000
	// 211 / 100000000 = 0.0000021100

	// U = 62500000
	// 1902 / 1000000000 = 0.0000019020

	// U = 625000000
	// 18897 / 10000000000 = 0.0000018897
}