Model

Balls in bins: the fullest partition

Throwing M balls at random into N bins: the fullest bin exceeds the mean.

i max n_{i} - \frac{M}{N} \approx 2 \frac{M}{N} ln N

$M$: Records; records placed at random
$N$: Partitions; partitions (bins)
$M / N$: Mean; records per partition on average

Recurring principle: Variance costs more than volume

How it behaves

One input on the horizontal axis, the others held fixed.

N = 10 partitionsN = 100

Data table

How far the fullest partition sits above the mean, by records
Records M	series	Fullest partition above the mean
100	N = 10 partitions	67.9%
119	N = 10 partitions	62.2%
141	N = 10 partitions	57.1%
168	N = 10 partitions	52.4%
200	N = 10 partitions	48%
237	N = 10 partitions	44.1%
282	N = 10 partitions	40.4%
335	N = 10 partitions	37.1%
398	N = 10 partitions	34%
473	N = 10 partitions	31.2%
562	N = 10 partitions	28.6%
668	N = 10 partitions	26.2%
794	N = 10 partitions	24.1%
944	N = 10 partitions	22.1%
1.12K	N = 10 partitions	20.3%
1.33K	N = 10 partitions	18.6%
1.58K	N = 10 partitions	17%
1.88K	N = 10 partitions	15.6%
2.24K	N = 10 partitions	14.3%
2.66K	N = 10 partitions	13.2%
3.16K	N = 10 partitions	12.1%
3.76K	N = 10 partitions	11.1%
4.47K	N = 10 partitions	10.2%
5.31K	N = 10 partitions	9.31%
6.31K	N = 10 partitions	8.54%
7.5K	N = 10 partitions	7.84%
8.91K	N = 10 partitions	7.19%
10.6K	N = 10 partitions	6.59%
12.6K	N = 10 partitions	6.05%
15K	N = 10 partitions	5.55%
17.8K	N = 10 partitions	5.09%
21.1K	N = 10 partitions	4.67%
25.1K	N = 10 partitions	4.28%
29.9K	N = 10 partitions	3.93%
35.5K	N = 10 partitions	3.6%
42.2K	N = 10 partitions	3.3%
50.1K	N = 10 partitions	3.03%
59.6K	N = 10 partitions	2.78%
70.8K	N = 10 partitions	2.55%
84.1K	N = 10 partitions	2.34%
100K	N = 10 partitions	2.15%
119K	N = 10 partitions	1.97%
141K	N = 10 partitions	1.81%
168K	N = 10 partitions	1.66%
200K	N = 10 partitions	1.52%
237K	N = 10 partitions	1.39%
282K	N = 10 partitions	1.28%
335K	N = 10 partitions	1.17%
398K	N = 10 partitions	1.08%
473K	N = 10 partitions	0.987%
562K	N = 10 partitions	0.905%
668K	N = 10 partitions	0.83%
794K	N = 10 partitions	0.761%
944K	N = 10 partitions	0.698%
1.12M	N = 10 partitions	0.641%
1.33M	N = 10 partitions	0.588%
1.58M	N = 10 partitions	0.539%
1.88M	N = 10 partitions	0.494%
2.24M	N = 10 partitions	0.454%
2.66M	N = 10 partitions	0.416%
3.16M	N = 10 partitions	0.382%
3.76M	N = 10 partitions	0.35%
4.47M	N = 10 partitions	0.321%
5.31M	N = 10 partitions	0.295%
6.31M	N = 10 partitions	0.27%
7.5M	N = 10 partitions	0.248%
8.91M	N = 10 partitions	0.227%
10.6M	N = 10 partitions	0.209%
12.6M	N = 10 partitions	0.191%
15M	N = 10 partitions	0.175%
17.8M	N = 10 partitions	0.161%
21.1M	N = 10 partitions	0.148%
25.1M	N = 10 partitions	0.135%
29.9M	N = 10 partitions	0.124%
35.5M	N = 10 partitions	0.114%
42.2M	N = 10 partitions	0.105%
50.1M	N = 10 partitions	0.096%
59.6M	N = 10 partitions	0.088%
70.8M	N = 10 partitions	0.081%
84.1M	N = 10 partitions	0.074%
100M	N = 10 partitions	0.068%
100	N = 100	303%
119	N = 100	278%
141	N = 100	255%
168	N = 100	234%
200	N = 100	215%
237	N = 100	197%
282	N = 100	181%
335	N = 100	166%
398	N = 100	152%
473	N = 100	140%
562	N = 100	128%
668	N = 100	117%
794	N = 100	108%
944	N = 100	98.8%
1.12K	N = 100	90.6%
1.33K	N = 100	83.1%
1.58K	N = 100	76.2%
1.88K	N = 100	69.9%
2.24K	N = 100	64.1%
2.66K	N = 100	58.8%
3.16K	N = 100	54%
3.76K	N = 100	49.5%
4.47K	N = 100	45.4%
5.31K	N = 100	41.7%
6.31K	N = 100	38.2%
7.5K	N = 100	35%
8.91K	N = 100	32.1%
10.6K	N = 100	29.5%
12.6K	N = 100	27%
15K	N = 100	24.8%
17.8K	N = 100	22.8%
21.1K	N = 100	20.9%
25.1K	N = 100	19.1%
29.9K	N = 100	17.6%
35.5K	N = 100	16.1%
42.2K	N = 100	14.8%
50.1K	N = 100	13.6%
59.6K	N = 100	12.4%
70.8K	N = 100	11.4%
84.1K	N = 100	10.5%
100K	N = 100	9.6%
119K	N = 100	8.8%
141K	N = 100	8.07%
168K	N = 100	7.41%
200K	N = 100	6.79%
237K	N = 100	6.23%
282K	N = 100	5.72%
335K	N = 100	5.24%
398K	N = 100	4.81%
473K	N = 100	4.41%
562K	N = 100	4.05%
668K	N = 100	3.71%
794K	N = 100	3.41%
944K	N = 100	3.12%
1.12M	N = 100	2.87%
1.33M	N = 100	2.63%
1.58M	N = 100	2.41%
1.88M	N = 100	2.21%
2.24M	N = 100	2.03%
2.66M	N = 100	1.86%
3.16M	N = 100	1.71%
3.76M	N = 100	1.57%
4.47M	N = 100	1.44%
5.31M	N = 100	1.32%
6.31M	N = 100	1.21%
7.5M	N = 100	1.11%
8.91M	N = 100	1.02%
10.6M	N = 100	0.932%
12.6M	N = 100	0.855%
15M	N = 100	0.785%
17.8M	N = 100	0.72%
21.1M	N = 100	0.66%
25.1M	N = 100	0.606%
29.9M	N = 100	0.555%
35.5M	N = 100	0.509%
42.2M	N = 100	0.467%
50.1M	N = 100	0.429%
59.6M	N = 100	0.393%
70.8M	N = 100	0.361%
84.1M	N = 100	0.331%
100M	N = 100	0.303%

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Data Movement
How do records cross between two systems that have independent rates, independent availability and independent lifetimes, and what are you willing to lose when the assumption underneath the crossing breaks?
$2 \cdot (M / N) \cdot ln N$
Read it in place →