Linear Hashing Is Poissonesque

The Poisson approximation theorem states that when m balls are tossed uniformly and randomly into n bins, the distribution of the bin loads can sometimes be approximated by n independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random F₂-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. Expected loads. We show that the expected value of the rth largest bin is governed by the rth largest value among n independent Poisson random variables of mean $m/n$. Specializing to the canonical setting of $m=n$ and $r=1$, our bounds show that the expected maximum load when n balls are hashed into n bins by a random F₂-linear map is no more than the corresponding expectation for a fully random map plus 32 + o(1). Specializing to m nlog n, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. Concentration. When m nlog (1/ρ) balls are tossed into n bins randomly, we expect with $0.99$ probability that every density-$ρ$ subset of bins will contain a (1± o(1) )ρ-fraction of the balls. We show that this remains the case if the m balls are tossed using a random linear map, and our bound matches the $o(1)$-factor produced by the fully random case. This gives a stronger version of the Leftover Hash Lemma for linear maps. An implication of this is that all bins have load m/n ± O(√(m/n)log n) with probability $0.99$. We obtain these results by showing that the average of a log-potential on the bin loads is upper bounded by the cumulant generating function of a Poisson random variable of mean $m/n$.