Source-linked AI summary
Linear Hashing Is Poissonesque
Vinayak M. Kumar
TL;DR
The paper asks whether coarse load statistics under random linear hashing can be described using Poisson variables, even though correlations can make exact Poisson tail bounds fail. The authors bound the expected log-average-exp of centered bin loads by the cumulant generating function of a centered Poisson variable, then use the potential to derive expectation and tail bounds. In the sparse regime where t/µ grows sufficiently fast, t is within 3/2 + o(1) of the expected max load of a fully random map.
Problem
The paper asks whether coarse load statistics under random linear hashing can be described using Poisson variables, even though correlations can make exact Poisson tail bounds fail.
Source: §1 · p. 2Method
The authors bound the expected log-average-exp of centered bin loads by the cumulant generating function of a centered Poisson variable, then use the potential to derive expectation and tail bounds.
Source: §1.1 · p. 3Results
In the sparse regime where t/µ grows sufficiently fast, t is within 3/2 + o(1) of the expected max load of a fully random map.
Source: §5.1 · p. 17Takeaways & Limitations
The potential inequality simplifies and unifies several load-distribution analyses, and its derived bounds also apply to hash families for which the inequality holds.
Source: §1.2 · p. 3The approach gives optimal concentration bounds down to m = n log n but works only over F2; prior exponential potentials give stronger tails when m = o(n log n).
Source: §1.3 · p. 7
Abstract
from arXiv · showhide
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 $\mathbb{F}_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. $\textbf{Expected loads.}$ We show that the expected value of the $r$th largest bin is governed by the $r$th 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 $\mathbb{F}_2$-linear map is no more than the corresponding expectation for a fully random map $\textit{plus}$ $\frac{3}2 + o(1)$. Specializing to $m\gg n\log n$, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. $\textbf{Concentration.}$ When $m\gg n\log (1/\rho)$ balls are tossed into $n$ bins randomly, we expect with $0.99$ probability that $\textit{every}$ density-$\rho$ subset of bins will contain a $(1\pm o(1) )\rho$-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 \pm O(\sqrt{(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$.
1 Introduction
The paper asks whether coarse load statistics for random F2-linear hashing can retain a Poisson-like description despite correlations that rule out exact Poisson tail behavior. It bounds a log-potential by a Poisson cumulant generating function and uses that inequality to derive expected-load and concentration results.
1 Introduction
- A random linear map induces correlations among outputs of linearly dependent inputs, so exact Poisson tail bounds can fail even though coarser statistics may remain synchronized.For linearly independent inputs, hashing reduces to fully random hashing; for a subspace, a fixed-bin load can have exponentially worse tails than a Pois(1) variable.Source: §1 · p. 2
1.1 A Potential-Poisson Inequality
- For every real λ and input set S of size m, the expected log-average-exp of centered bin loads is bounded by the cumulant generating function of a centered Pois(m/n) variable.The inequality governs coarser load statistics and provides the basis for expectation and tail bounds.Source: §1.1 · pp. 2–3
1.2.1 Expected Loads
- For m = n, the expected maximum load under a random F2-linear map exceeds the fully random expectation by at most 3/2 + o(1); for m ≫ n log n, expected maximum and minimum loads lie within second-order corrections of the mean.The expected-load bounds also govern the average of the r heaviest and lightest bins by corresponding quantities for n independent Pois(m/n) variables.Source: §1.2.1 · p. 4
1.2.2 Concentration Bounds
- For constant ε and m > n log n, linear hashing’s deviation has the same order in m and n as fully random hashing, but achieves probability 0.99 versus 1 − n^−Ω(1).Its ε^−1/2 dependence is necessary for random linear maps.Source: §1.2.2 · p. 6
1.3 Proof Technique
- Taking the logarithm of the exponential potential makes its conditional recurrence composable in expectation, yielding the potential bound and expected maximum-load bounds.The paper notes that directly composing the conditional-squaring recurrence for the exponential potential can fail.Source: §1.3 · p. 7
- The potential argument also applies to hash families built by repeatedly pseudorandomly grouping and merging bins, but the k > 2 family does not capture Fk-linear maps.For k = 2, this framework includes load distributions of uniformly random surjective F2-linear maps.Source: §1.3 · p. 7
2 Preliminaries
The preliminaries define bin loads and load-order statistics used throughout. A transfer lemma lifts bounds for random surjective linear maps to general random linear maps without parameter loss.
2 Preliminaries
- For a map f and a set S, a bin's load is the number of elements of S mapped to it; the ordered loads define the lightest and heaviest bins.The averages of the r heaviest and r lightest bins are key quantities used later.Source: §2 · p. 8
- The paper denotes a Poisson random variable of mean μ by Pois(μ), and defines D(ν, μ) as the Kullback-Leibler divergence between Pois(ν) and Pois(μ).The convention 0 log 0 := 0 is used.Source: §2 · p. 8
2.1 Removing Surjectivity For Free
- The transfer lemma lifts bounds on functions of the load vector from random surjective linear maps to general random linear maps without parameter loss.It applies to nonnegative functions of the entire load vector, including expected order statistics, moments, and tail probabilities.Source: §2.1 · p. 9
- Earlier variants of the surjectivity-transfer lemma incurred parameter losses; this proof combines prior ingredients with a new limit trick.Source: §2.1 · p. 9
3 The Potential Function Bound
The paper bounds a logarithmic potential of centered bin loads by the cumulant generating function of a centered Poisson variable. Taking logarithms and centering the loads are key to tighter bounds, especially in the dense regime.
3 The Potential Function Bound
- The potential is the logarithm of an average exponential of centered bin loads, capturing coarser load-distribution statistics.The loads are centered by the average load.Source: §3 · p. 10
- Taking logarithms yields quantitatively tighter results with a simpler argument, while centering the loads tightens concentration bounds when balls greatly outnumber bins.Source: §3 · p. 10
- The expected log-potential of the bin loads is bounded above by the cumulant generating function of a centered Poisson variable with mean μ = m/n.The paper identifies this inequality as the engine behind its results.Source: §3 · p. 10
- The proof tracks the potential while revealing kernel vectors one at a time, then removes the surjectivity assumption using the transfer lemma.The log-potential is the final potential in this sequence; linearity of expectation composes the recurrence to bound it.Source: §3 · pp. 11–12
4 Following the Recipe
The section turns the potential bound into load-statistic bounds by extracting statistics, applying expectation and tail inequalities, and optimizing the free parameter. The resulting Poisson thresholds control top- and bottom-bin averages for linear hashing.
4 Following the Recipe
- The recipe is to extract load statistics from ϕ, apply expectation and tail bounds, and optimize λ.Together, these steps yield information about load distributions under random F2-linear hashing.Source: §4 · p. 12
4.1 Extracting Statistics out of ϕ
- The method extracts top-r and bottom-r load averages as statistics controlled by a linear function of the potential.Expectation and tail bounds on the potential are then used to bound these statistics.Source: §4.1 · p. 12, §4.2 · p. 13
4.3 Optimizing λ
- The rth largest and smallest loads, and the averages of the top-r and bottom-r loads, are bounded using the corresponding Poisson thresholds.The section gives both expectation bounds and tail bounds for these load statistics.Source: §4.3 · pp. 14–15
- The Poisson thresholds represent load levels at which Poisson Chernoff bounds predict r heavy or light bins, and the linear-hashing bounds use these same thresholds.The lower threshold is zero when μ ≤ log(n/r); otherwise it is defined by the corresponding divergence equation.Source: §4.3 · p. 14
- For m = n, the upper Poisson threshold is characterized by t log t − t + 1 = log n and can be expanded using the Lambert W function.The text says similar calculations apply for other m and n and to any fixed asymptotic order.Source: §4.3 · p. 16
4.4 On Finding the Optimal λ
- The free parameter λ is optimized through the Cramér transform of the centered Poisson cumulant generating function.The section applies this optimization to derive the expectation and tail thresholds.Source: §4.4 · p. 16
5 Applications
The applications bound the expected maximum load of linear hashing near that of fully random hashing and establish concentration for subsets of bins in the dense regime. They also give tight two-sided load bounds for individual bins and examine how the concentration guarantee depends on the failure probability.
5.1 Additively Optimal Expected Max Load
- In the sparse regime, the Chernoff threshold is within 3/2 + o(1) of the expected maximum load for fully random hashing, supporting an additive comparison for linear hashing.The section applies this bound in the canonical setting of n balls into n bins; it also notes the same gap for sufficiently small m relative to n under the stated limit condition.Source: §5.1 · pp. 17–18
5.2 Concentration
- For m > n log(1/ρ), Theorem 10 bounds the fraction of balls mapped into every density-ρ subset of bins, simultaneously with probability at least 1 − ε.The theorem applies to an arbitrary input set A and a uniformly random linear map; the supplied passage does not state the bound's deviation formula.Source: §5.2 · pp. 19–20
- When m > n log n, the section derives tight two-sided bounds on individual bin loads by applying Theorem 10 to singleton bin sets.The corollary applies to arbitrary input sets and a uniformly random linear map.Source: §5.2 · p. 20
- For constant failure probability, Theorem 10 matches fully random hashing, and a constructed input set shows its dependence on ε^-1/2 is tight up to a logarithmic factor.The construction uses k linearly independent translates of one vector space of size m/k.Source: §5.2 · pp. 21–22
AI Methodology
The author reports using ChatGPT 6 after the initial draft to verify proofs, copyedit prose, and help interpret results in Lund’s manuscript [Lun26].
AI Methodology
- After the initial draft, ChatGPT 6 was used to verify proofs, copyedit prose, and help interpret results in Lund’s manuscript [Lun26].Source: AI Methodology · p. 22