Linear Hashing Is Poissonesque
Abstract
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 𝔽2-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 𝔽2-linear map is no more than the corresponding expectation for a fully random map plus 3/2 + 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.
Related
- Polynomially larger deletion codes by linear hashing of substring counts
- List Decoding, Linear Hashing, and Furstenberg over 𝔽q
- Two-sided linear hashing and quadratic density bounds for smooth lattice coverings
- The probabilistic bound for perfect hashing is sharp only for binary alphabets
- Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding
BibTeX
@misc{kumar2026linear,
title = {{Linear Hashing Is Poissonesque}},
author = {Vinayak M. Kumar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34750},
eprint = {2610.34750},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34750},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Linear Hashing Is Poissonesque
AU - Vinayak M. Kumar
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34750
UR - https://arxiv.org/abs/2610.34750
AB - 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 𝔽_2-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 𝔽_2-linear map is no more than the corresponding expectation for a fully random map plus 3/2 + 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.
ER -