Proof. The insertion procedure follows a single displacement chain. Suppose \(x_i\) displaces \(x_{i+1}\) from slot \(z_i\). Then \(x_i\) comes earlier than \(x_{i+1}\) in the anti-Robin Hood order for \(z_i\). Hence \(x_i\) reaches \(z_i\) at displacement no larger than the displacement at which \(x_{i+1}\) reaches \(z_i\), so \[\rho_i^+\le \rho_{i+1}^-.\] After \(x_i\) is displaced from its old slot, its insertion search continues forward in its own probe sequence, so \[\rho_i^-\le \rho_i^+\] for every \(i\ge1\). Combining these inequalities gives the claim. ◻

Proof. Fix an insertion chain as in Claim 2.

First consider \(X\), the number of free slots in \(A\) in the \(K\)-reveal. In the full table, every occupied slot remains occupied after the insertion; only the final empty slot of the chain becomes newly occupied. Besides this final slot, in the \(K\)-reveal, a slot can newly become occupied only if its old occupant had displacement greater than \(K\) and its new occupant has displacement at most \(K\).

Consider the variables defined in Claim 2. At the slot \(z_i\) where \(x_i\) displaces \(x_{i+1}\), the old occupant had displacement \(\rho_{i+1}^-\), and the new occupant has displacement \(\rho_i^+\). By Claim 2, \[\rho_i^+\le \rho_{i+1}^-.\] Thus a slot occupied in the \(K\)-reveal before the insertion remains occupied afterward. Moreover, for any slot \(z_i\) besides the final one in the chain, the slot can go from unoccupied to occupied in the \(K\)-reveal only if \[\rho_i^+\le K<\rho_{i+1}^-. \label{eq:crossing}\tag{3}\] The monotonicity of the insertion chain allows at most one such crossing. The final slot \(z_q\) may also enter the \(K\)-reveal, but only if \(\rho_q^+\le K\), in which case 3 did not hold for any \(i<q\). Thus \(X\) can decrease by at most \(1\), and it cannot increase.

Now consider \(Y\), the number of keys with home position in \(A\) and displacement greater than \(K\). Existing keys only move forward in their probe sequences. Thus an existing key can enter the set counted by \(Y\) only if \[\rho_i^-\le K<\rho_i^+\] for some \(i\ge1\), and monotonicity permits this for at most one key. The new key \(x_0\) may itself be counted by \(Y\), but only if \(\rho_0^+>K\), in which case the monotonicity \[\rho_0^+\le \rho_1^-\le \rho_1^+\le\cdots\] prevents any existing key from crossing from displacement at most \(K\) to displacement greater than \(K\). Thus \(Y\) can increase by at most \(1\), and it cannot decrease. ◻

Proof. Let \(a₁,a₂,… ∈ [0,1]\) be independent and uniformly random, let \(A_k = \{a₁,…,a_k\}\) and let \(N \sim \operatorname{Poisson}(m)\). This realises \(A\) as \(A = A_N\). Define \(g(k) := \mathop{\mathrm{\mathbb{E}}}[f(A_k)]\) and note that \(g\) is \(1\)-Lipschitz because \(|f(A_{k+1})-f(A_k)| ≤ 1\). We divide \(|f(A)-\mathop{\mathrm{\mathbb{E}}}[f(A)]|\) into four parts as follows: \[|f(A)-\mathop{\mathrm{\mathbb{E}}}[f(A)]| ≤ \underbrace{|f(A)-g(N)|}_{D₁} + \underbrace{|g(N)-g(⌊m⌋)|}_{D₂} + \underbrace{|g(⌊m⌋)-\mathop{\mathrm{\mathbb{E}}}[g(N)]|}_{D₃} + \underbrace{|\mathop{\mathrm{\mathbb{E}}}[g(N)]-\mathop{\mathrm{\mathbb{E}}}[f(A)]|}_{D₄}.\] We show for each part separately that it is bounded by \(u/4\), except with the stated error probability. We trivially have \(D₄ = 0\) since \(g(N) = \mathop{\mathrm{\mathbb{E}}}[f(A) | N]\). As for \(D₃\), we have \[D₃ = |g(⌊m⌋)-\mathop{\mathrm{\mathbb{E}}}[g(N)]| ≤ \mathop{\mathrm{\mathbb{E}}}[|g(⌊m⌋)-g(N)|] \stackrel{\text{1-Lipschitz}}{≤} \mathop{\mathrm{\mathbb{E}}}[|⌊m⌋-N|] ≤ O(\sqrt{m})\] where the last step is a basic property of Poisson random variables. Note that the lemma’s claim is trivial for \(u = O(\sqrt{m})\) so by changing constants we can bound \(O(\sqrt{m})\) by \(u/4\).

To bound \(D₂\) we use a standard Chernoff bound for Poisson random variables which gives \[\mathop{\mathrm{Pr}}\mleft[D₂ ≥ u/4\mright] = \mathop{\mathrm{Pr}}\mleft[|g(N)-g(⌊m⌋)| ≥ u/4\mright] \stackrel{\text{1-Lipschitz}}{≤} \mathop{\mathrm{Pr}}\mleft[|N-\lfloor m\rfloor|\ge u/4\mright] \le \exp\mleft(-\Omega\mleft(\min\mleft\{\frac{u^2}{m},u\mright\}\mright)\mright).\] In particular we may assume \(N ≤ m+u\) also when bounding \(D₁\). We condition on \(N = k\) for any \(k ≤ m+u\). We may now use McDiarmid’s inequality to bound \(D₁\) as \(f(A) = f(A_k)\) is now a function of \(k\) independent random variables and replacing one point of \(A_k\) by another changes \(f(A_k)\) by at most \(2\). Hence: \[\begin{align} \mathop{\mathrm{Pr}}[D₁\ge u/4\mid N=k] &= \mathop{\mathrm{Pr}}[|f(A)-g(N)| \ge u/4\mid N=k] = \mathop{\mathrm{Pr}}[|f(A_k)-\mathop{\mathrm{\mathbb{E}}}[f(A_k)]| \ge u/4]\\ &\le 2\exp\mleft(-\Omega(u^2/k)\mright) \stackrel{k ≤ m+u}{≤} 2\exp\mleft(-\Omega\mleft(\min\mleft\{\frac{u^2}{m},u\mright\}\mright)\mright).\qedhere \end{align}\] ◻

Proof of Proposition 1. The \(K\)-reveal inside \(A\) depends only on keys whose home positions lie within displacement \(O(K)\) of \(A\). The number of relevant keys is Poisson with mean \(\Theta(K)\). By Lemma 1, adding or deleting one key changes either statistic by at most one. Applying Lemma 2 with \(m=\Theta(K)\), and encoding each relevant key’s home position and priority as a point in a bounded probability space, gives the claimed bounds. ◻

Proof. Fix \(j\in\{j_1,\ldots,j_2\}\) and suppose that \(r_{j_1},\ldots,r_{j-1}\) have already been revealed. A slot \(z\) is a \(j\)-opportunity for \(u\) if \[z\in u+I_j \qquad\text{and}\qquad z\text{ is free in the }(\alpha j^d-1)\text{-reveal}.\] Let \(T_j\) be the number of \(j\)-opportunities. These slots are determined before \(r_j\) is sampled.

If \(u+r_j\) is a \(j\)-opportunity and some key with home position \(u\) is still absent just before offset \(r_j\) is revealed, then the next absent key with home position \(u\) is placed at \(u+r_j\). Indeed, no offset of the common probe sequence lies between \(\alpha j^d\) and \(r_j\) before the \(j\)-th probe, and at offset \(r_j\) the only keys that can probe \(u+r_j\) are keys with home position \(u\).

Since \(r_j\) is uniform in \(I_j\), and since \(|I_j|\le C K_+^{(d-1)/d}\) for a constant \(C=C(d,\alpha)\), \[\mathop{\mathrm{Pr}}[u+r_j\text{ hits a }j\text{-opportunity} \mid r_{j_1},\ldots,r_{j-1}] = \frac{T_j}{|I_j|} \ge \frac{T_j}{C K_+^{(d-1)/d}} .\] Thus the opportunity hits stochastically dominate adaptive coin flips whose head probability at step \(j\) is \(T_j/(C K_+^{(d-1)/d})\).

Initially, fewer than \(\beta\) keys with home position \(u\) are absent from the \(K_-\)-reveal. Therefore, if some such key is still absent from the \(K_+\)-reveal, then fewer than \(\beta\) opportunity hits occurred during probes \(j_1,\ldots,j_2\).

Conversely, every slot \(z\in u+I\) that is free in the \(K_+\)-reveal lies in \(u+I_j\) for a unique \(j\in\{j_1,\ldots,j_2\}\), and it was already free in the \((\alpha j^d-1)\)-reveal. Hence the event in the lemma with \(S\) free slots implies \(\sum_{j=j_1}^{j_2}T_j\ge S\).

Applying 5 below with \(t=C K_+^{(d-1)/d}\) gives \[\mathop{\mathrm{Pr}}\mleft[ \#\{\text{opportunity hits}\}<\beta \text{ and } \sum_{j=j_1}^{j_2}T_j\ge S \mright] \le \exp\mleft(\beta-\Omega\mleft(S/K_+^{(d-1)/d}\mright)\mright),\] which proves the lemma. ◻

Proof. Let \(H_i\) be the number of heads among the first \(i\) flips, and let \[S_i=\sum_{r=1}^i t_r.\] Let \(\mathcal{F}_{i-1}\) be the history before \(t_i\) is chosen, and let \(\mathcal{G}_i\) be the history after \(t_i\) is revealed but before the \(i\)-th coin is flipped. For \(c=1-e^{-1}\), define \[M_i=\exp(cS_i/t-H_i).\] We verify that \((M_i)\) is a supermartingale. Conditional on \(\mathcal{G}_i\), the head probability is \(p_i=t_i/t\), so \[\mathop{\mathrm{\mathbb{E}}}\Bk*{e^{-\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK{\text{head at }i}}}\mid\mathcal{G}_i} = 1-p_i(1-e^{-1}) \le e^{-cp_i}.\] Hence \[\mathop{\mathrm{\mathbb{E}}}\Bk*{M_i\mid\mathcal{F}_{i-1}} = \mathop{\mathrm{\mathbb{E}}}\Bk*{M_{i-1}e^{ct_i/t} \mathop{\mathrm{\mathbb{E}}}\Bk*{e^{-\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK{\text{head at }i}}}\mid\mathcal{G}_i} \mid\mathcal{F}_{i-1}} \le M_{i-1}.\] Thus \(\mathop{\mathrm{\mathbb{E}}}\Bk*{M_\ell}\le1\). On the event in the lemma, \[M_\ell\ge \exp(cS/t-\beta),\] so Markov’s inequality gives the result. ◻

Proof. It suffices to prove the bound for a single home position \(u\), and then sum over \(u\in A\).

Fix \(u\). Condition on the offset sequence and on all keys with home position different from \(u\). The keys with home \(u\) form a Poisson point process on the priority interval \([0,1]\) of intensity at most \(1\), where larger priority means earlier placement among same-home keys.

Expose the part of the \(K\)-reveal involving home position \(u\). Since same-home keys are processed in decreasing priority order, this exposure either shows that no same-home key survives past displacement \(K\), or leaves exactly the unexposed Poisson points below some priority cutoff. Consequently, conditional on the exposed information, \[Y_u(K)\sim \operatorname{Poisson}(\lambda_u) \qquad\text{for some }\lambda_u\le1,\] or \(Y_u(K)=0\). Thus the lemma follows from the fact that, if \(Z\sim\operatorname{Poisson}(\lambda)\) with \(\lambda\le1\), then \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\Bk*{Z\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Z\ge\beta}}} \le{}& e^{-\Omega(\beta\log\beta)}\mathop{\mathrm{\mathbb{E}}}\Bk*{Z}. \qedhere \end{align}\] ◻

Proof of 3. Note that the lemma is trivial for any \(K = O(1)\), since we can take \(c\) large enough so that the if-statement in the lemma never goes into effect. We will therefore assume (WLOG) for the rest of the proof that \(K\) is large enough that every sampling interval intersecting \([K,5K]\) has length at most \(K\).

Let \[\delta=10^{-4}.\] Choose constants \(\beta\) and \(c\), where \(\beta\) is sufficiently large compared to \(\delta\) and \(c\) is sufficiently large compared to \(\beta\). Consider four consecutive intervals \[A,B,C,D,\] each of length \(K\). Define \[X_1=\#\{\text{free slots in }D\text{ in the }K\text{-reveal}\}, \qquad X_2=\#\{\text{free slots in }D\text{ in the }5K\text{-reveal}\},\] and \[Y_1=\#\{x:h(x)\in A\text{ and }\operatorname{disp}(x)>K\}, \qquad Y_2=\#\{x:h(x)\in A\text{ and }\operatorname{disp}(x)>5K\}.\] For \(u\in A\), let \[Y_u=\#\{x:h(x)=u\text{ and }\operatorname{disp}(x)>K\},\] and define \[Y_1^{(\beta)} = \sum_{u\in A}Y_u\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_u\ge\beta}}.\] Since the expected number of keys overall is \(n\), we have by symmetry that \[\mu_1:=\mathop{\mathrm{\mathbb{E}}}\Bk*{X_1}=\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1}.\] By assumption, \[\mu_1\ge c\max\{\sqrt K,K^{(d-1)/d}\},\] so in particular \(\mu_1\ge c\sqrt K\) and \(\mu_1\ge cK^{(d-1)/d}\).

Let \(\mathcal{R}\) be the still-random offsets with sampling intervals intersecting \((K,5K]\), and write \[\nu(\mathcal{R})=\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2\mid \mathcal{R}},\] where the expectation is over the Poisson keys. Conditional on \(\mathcal{R}\), symmetry gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{X_2\mid\mathcal{R}}=\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2\mid\mathcal{R}}=\nu(\mathcal{R}).\]

Suppose for contradiction that \[\mathop{\mathrm{\mathbb{E}}}_{\mathcal{R}}\Bk*{\nu(\mathcal{R})}>\delta\mu_1.\] Since \(0\le Y_2\le Y_1\), since \(Y_1\) is determined by offsets whose sampling intervals intersect \([0,K]\) and is therefore independent of \(\mathcal{R}\), and since \(\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1}=\mu_1\), we have \[0\le \nu(\mathcal{R})\le \mu_1.\] Hence \[\mathop{\mathrm{Pr}}_{\mathcal{R}}\mleft[\nu(\mathcal{R})\ge \frac{\delta}{2}\mu_1\mright] \ge \frac{\delta}{2}.\] Call such offset realizations \(\mathcal{R}\) good.

Fix a good \(\mathcal{R}\). Proposition 1, applied with the full offset sequence fixed and reveal parameter \(5K\) where needed, implies that, with probability at least \(0.9\) over the Poisson keys, \[Y_1\le2\mu_1, \qquad Y_2\ge \frac{\delta}{4}\mu_1, \qquad X_2\ge \frac{\delta}{4}\mu_1,\] provided \(c\) is large enough. Indeed, the proposition says that, for each of \(Y_1,Y_2,X_2\) conditioned on the offset sequence, the probability of deviating from the mean by at least \(\delta\mu_1/4\ge \delta c\sqrt K/4\) is at most, say, \(0.001\).

Choose \(\beta\) so large that Lemma 6 gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1^{(\beta)}}\le \frac{\delta^2}{1000}\mu_1.\] By Markov’s inequality, \[\mathop{\mathrm{Pr}}\mleft[Y_1^{(\beta)}>\frac{\delta}{16}\mu_1\mright]\le \frac{\delta}{50}.\] Thus the event \[\mathcal{G}= \mleft\{ \mathcal{R}\text{ is good},\, Y_1\le2\mu_1,\, Y_2\ge\frac{\delta}{4}\mu_1,\, X_2\ge\frac{\delta}{4}\mu_1,\, Y_1^{(\beta)}\le\frac{\delta}{16}\mu_1 \mright\}\] has probability at least \(\delta/4\).

Condition on what we will call the augmented \(K\)-data consisting of the \(K\)-reveal together with the counts \(Y_u\) for \(u\in A\). This fixes \(Y_1\), \(Y_1^{(\beta)}\), and the light home positions in \(A\) (the home positions with \(u \in A\) with \(Y_u < \beta\)), while leaving the offsets whose sampling intervals are disjoint from \([0,K]\) unrevealed.

Fix a light home position \(u\in A\), so \(1\le Y_u<\beta\). Let \(I_{j_1}\) be the first sampling interval that intersects the set of displacements \[D-u=\{z-u:z\in D\},\] and let \(I_{j_2}\) be the last such sampling interval. Since \(D-u\subseteq[2K,4K]\) and every sampling interval intersecting \([K,5K]\) has length at most \(K\), the intervals \(I_{j_1}, I_{j_1 + 1}, \ldots, I_{j_2}\) are disjoint from \([1, K]\). Critically, this means that the augmented \(K\)-data does not reveal any information about \(r_{j_1}, \ldots, r_{j_2}\). Let \(K_+=\alpha(j_2+1)^d\) be the right endpoint used in Lemma 4; the preceding sentence implies \(K_+\le5K\).

Since \(D-u\subseteq \bigcup_{j=j_1}^{j_2}I_j\), every slot of \(D\) that is free in the \(5K\)-reveal is also free in the \(K_+\)-reveal. Therefore, if \(X_2\ge\delta\mu_1/4\), then Lemma 4 applies with \(S=\delta\mu_1/4\) and \(K_+^{(d-1)/d}=O(K^{(d-1)/d})\), giving \[\mathop{\mathrm{Pr}}\mleft[ \text{some key with home position }u\text{ is absent from the }5K\text{-reveal} \text{ and }X_2\ge\frac{\delta}{4}\mu_1 \mid \text{augmented }K\text{-data} \mright] \le q,\] where \[q= \exp\mleft(O(\beta)-\Omega\mleft(\frac{\delta\mu_1}{K^{(d-1)/d}}\mright)\mright) \le \exp(O(\beta)-\Omega(\delta c)),\] and where the asymptotic notation hides constants that are independent of \(\beta\) and \(c\).

Let \(Z\) be the number of keys counted by \(Y_2\) whose home position was light at displacement \(K\), and that occur together with \(X_2\ge\delta\mu_1/4\). Conditioning on the augmented \(K\)-data and summing over light home positions, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Z\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_1\le2\mu_1}} \mid \text{augmented }K\text{-data}} \le qY_1\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_1\le2\mu_1}} \le 2q\mu_1.\] Thus, removing the conditioning on the augmented \(K\)-data, we have \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Z\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_1\le2\mu_1}}}\le 2q\mu_1.\]

On \(\mathcal{G}\), \[Z\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_1\le2\mu_1}} \ge Y_2-Y_1^{(\beta)} \ge \frac{\delta}{8}\mu_1.\] Therefore, by Markov’s inequality, \[\mathop{\mathrm{Pr}}[\mathcal{G}]\le \frac{16q}{\delta}.\] Choosing \(c\) large enough makes this smaller than \(\delta/4\), contradicting \(\mathop{\mathrm{Pr}}[\mathcal{G}]\ge\delta/4\). Therefore \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2}\le \delta\mu_1,\] as claimed. ◻

Proof. It suffices to prove the estimate for power-of-\(5\) values of \(K\); the bound for intermediate values then follows from monotonicity after increasing the constant by a factor depending only on \(d\). We prove by induction that, for a sufficiently large constant \(C\), \[P(K)\le CK^{-\chi_d} \label{eq:critical-tail-induction}\tag{4}\] for every power-of-\(5\) value \(K\le n/10\). The case \(K=1\) holds after taking \(C\ge1\).

Fix a power-of-\(5\) value \(K\) with \(5K\le n/10\), and assume 4 holds at scale \(K\). Let \(\rho\) be the sequence of all offset choices \(r_j\) whose sampling interval \(I_j\) intersects \([0,K]\), ordered by \(j\). For a fixed value \(\rho^*\) of this sequence, define the conditional tail density \[P_{\rho^*}(K)=\frac{1}{n} \mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>K\}\mid \rho=\rho^*}.\] The \(K\)-reveal is already determined once these offsets are fixed, so the expectation above is only over the Poisson keys. Moreover, conditioned on \(\rho=\rho^*\), translation invariance and the identity \(\mathop{\mathrm{\mathbb{E}}}[N]=n\) imply that every interval of length \(K\) has \[KP_{\rho^*}(K)\] free slots in expectation in the \(K\)-reveal. Indeed, all length-\(K\) intervals have the same expected number of free slots, and the expected total number of free slots in the \(K\)-reveal equals the expected number of keys with displacement greater than \(K\).

Set \[T_K=c\frac{\max\{\sqrt K,K^{(d-1)/d}\}}{K} =cK^{-\chi_d},\] where \(c\) is the constant from Lemma 3. If \(P_{\rho^*}(K)\ge T_K\), then the conditional form of the hypothesis of Lemma 3 holds for this fixed offset sequence. Applying the lemma and summing its conclusion over all length-\(K\) home intervals gives \[\frac{1}{n}\mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>5K\}\mid \rho=\rho^*} \le 10^{-4}P_{\rho^*}(K).\] If instead \(P_{\rho^*}(K)<T_K\), then monotonicity of the displacement threshold gives \[\frac{1}{n}\mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>5K\}\mid \rho=\rho^*} \le P_{\rho^*}(K)<T_K.\] Therefore, for every fixed offset sequence \(\rho^*\), \[\frac{1}{n}\mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>5K\}\mid \rho=\rho^*} \le 10^{-4}P_{\rho^*}(K)+cK^{-\chi_d}.\] Averaging over the random sequence \(\rho\) yields \[P(5K)\le 10^{-4}P(K)+cK^{-\chi_d}.\] By the inductive hypothesis, \[P(5K)\le (10^{-4}C+c)K^{-\chi_d}.\] Choosing \(C\) large enough that \[10^{-4}C+c\le 5^{-\chi_d}C\] gives \(P(5K)\le C(5K)^{-\chi_d}\), completing the induction. ◻

Proof. The proof follows the same template as the proof of 3; the load slack \(\varepsilon\) gives many genuinely empty slots, and the only additional work is to keep track of the rare event where this slack is not visible locally. By taking \(C_0\) sufficiently large, we may assume throughout that every sampling interval intersecting \([K,5K]\) has length at most \(K\).

Partition the table into intervals of length \(K\), and fix four consecutive intervals \[A,B,C,D.\] Define \[X_1=\#\{\text{free slots in }D\text{ in the }K\text{-reveal}\},\] and \[Y_1=\#\{x:h(x)\in A,\operatorname{disp}(x)>K\}, \qquad Y_2=\#\{x:h(x)\in A,\operatorname{disp}(x)>5K\}.\] For \(u\in A\), write \[Y_u=\#\{x:h(x)=u,\operatorname{disp}(x)>K\}.\] Since the expected load is \(1-\varepsilon\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{X_1}\ge \varepsilon K.\] By assumption and by symmetry across intervals of length \(K\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1}\le \eta\varepsilon K.\]

Let \(E\) be the length-\(6K\) interval consisting of \(D\) together with the five length-\(K\) intervals immediately preceding it, and let \[R=\#\{x:h(x)\in E\text{ and }\operatorname{disp}(x)>K\}.\] Then \[\mathop{\mathrm{\mathbb{E}}}\Bk*{R}\le 6\eta\varepsilon K.\] Choose \(\eta\) sufficiently small, and define the common-case event \[\mathcal{H}= \mleft\{ X_1\ge \frac{\varepsilon K}{2},\quad R\le \frac{\varepsilon K}{8},\quad Y_1\le \frac{\varepsilon K}{8} \mright\}.\] We first bound the contribution from \(\neg\mathcal{H}\). Since \(Y_2\le Y_1\), and setting \(T=\varepsilon K/8\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2\mathop{\mathrm{\mathbb{1}}}\nolimits_{\neg\mathcal{H}}} \le T\mathop{\mathrm{Pr}}\mleft[X_1<\frac{\varepsilon K}{2}\mright] + T\mathop{\mathrm{Pr}}\mleft[R>\frac{\varepsilon K}{8}\mright] + \mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_1>T}}}.\] Proposition 1 gives \[\mathop{\mathrm{Pr}}\mleft[X_1<\frac{\varepsilon K}{2}\mright] \le e^{-\Omega(\varepsilon^2K)}.\] Applying the same proposition to the six length-\(K\) intervals forming \(E\), and using \(\eta\) small, gives \[\mathop{\mathrm{Pr}}\mleft[R>\frac{\varepsilon K}{8}\mright] \le e^{-\Omega(\varepsilon^2K)}.\] Finally, by the following tail-summation argument, we get \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_1>T}}} &\le T\mathop{\mathrm{Pr}}[Y_1>T]+\sum_{\ell\ge0}2^{\ell+1}T\mathop{\mathrm{Pr}}[Y_1\ge 2^\ell T] \\ &\le \varepsilon K \sum_{\ell\ge0} 2^{\ell+1} \exp\mleft( -\Omega\mleft( \min\mleft\{\frac{(2^\ell\varepsilon K)^2}{K},2^\ell\varepsilon K\mright\} \mright) \mright) \\ &\le \varepsilon K e^{-\Omega(\varepsilon^2K)}. \end{align}\] Hence \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2\mathop{\mathrm{\mathbb{1}}}\nolimits_{\neg\mathcal{H}}} \le \varepsilon K e^{-\Omega(\varepsilon^2K)}.\]

We now bound \(\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2\mathop{\mathrm{\mathbb{1}}}\nolimits_{\mathcal{H}}}\). Set \[\beta=\mleft\lceil b_0\varepsilon K^{1/d}\mright\rceil,\] where \(b_0>0\) is a sufficiently small constant. Since \(K\ge C_0\max\{\varepsilon^{-2},\varepsilon^{-d}\}\), choosing \(C_0\) large ensures \(\beta\ge1\). Define \[Y_1^{(\beta)} = \sum_{u\in A}Y_u\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{Y_u\ge\beta}}.\] By Lemma 6, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1^{(\beta)}} \le e^{-\Omega(\beta)}\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1} \le \eta\varepsilon K e^{-\Omega(\varepsilon K^{1/d})}.\] Thus heavy home positions contribute negligibly to \(Y_2\), and it remains to control light home positions.

Suppose \(\mathcal{H}\) occurs, and condition on the augmented \(K\)-data for the intervals involved: the \(K\)-reveal, the counts \(Y_u\) for \(u\in A\), and the count \(R\). This fixes \(X_1,Y_1,R,Y_1^{(\beta)}\), and \(\mathcal{H}\), while leaving the offsets whose sampling intervals are disjoint from \([0,K]\) unrevealed. This is the same deferred-randomness setup used in the proof of 3: it fixes the surviving keys and their home-position multiplicities without exposing the future offsets that may place them. The difference is that the earlier proof worked with slots already known to be free in the \(5K\)-reveal, whereas here the load slack is visible only in the \(K\)-reveal. The additional count \(R\) controls how many of those currently free slots can be filled before the relevant future offsets are exposed.

Fix a light home position \(u\in A\), meaning that \(1\le Y_u<\beta\). Let \(I_{j_1}\) be the first sampling interval that intersects \(D - u\) and let \(I_{j_2}\) be the last such sampling interval. Since \(D-u\subseteq[2K,4K]\) and every sampling interval intersecting \([K,5K]\) has length at most \(K\), the intervals \(I_{j_1},I_{j_1+1},\ldots,I_{j_2}\) are disjoint from \([1,K]\). Thus the augmented \(K\)-data does not reveal \(r_{j_1},\ldots,r_{j_2}\). Let \(K_-=\alpha j_1^d-1\) and \(K_+=\alpha(j_2+1)^d\) be as in Lemma 4; then \(K_-\ge K\) and \(K_+\le5K\).

Among the \(X_1\) slots of \(D\) that are free in the \(K\)-reveal, any slot that is not free in the \(K_+\)-reveal must be occupied by a key with home position in \(E\) and displacement greater than \(K\); such keys are counted by \(R\). On \(\mathcal{H}\), at least \[X_1-R\ge \frac{3\varepsilon K}{8}\] slots of \(D\) are therefore free in the \(K_+\)-reveal. Since all of \(D-u\) is covered by \(I_{j_1},\ldots,I_{j_2}\), Lemma 4 gives \[\mathop{\mathrm{Pr}}\mleft[ \begin{array}{c} \text{some home-}u\text{ key is absent from the }5K\text{-reveal}\\ \mid \text{augmented }K\text{-data} \end{array} \mright] \le \exp\mleft(O(\beta)-\Omega\mleft(\frac{\varepsilon K}{K^{(d-1)/d}}\mright)\mright).\] Since \(\varepsilon K/K^{(d-1)/d}=\varepsilon K^{1/d}\), and since \(b_0\) is sufficiently small, the last display is \[q=\exp(-\Omega(\varepsilon K^{1/d})).\] Linearity of expectation over light home positions gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{(Y_2-Y_1^{(\beta)})_+\mathop{\mathrm{\mathbb{1}}}\nolimits_{\mathcal{H}} \mid \text{augmented }K\text{-data}} \le qY_1\mathop{\mathrm{\mathbb{1}}}\nolimits_{\mathcal{H}}.\] Taking expectations and using \(\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1}\le \eta\varepsilon K\) yields \[\mathop{\mathrm{\mathbb{E}}}\Bk*{(Y_2-Y_1^{(\beta)})_+\mathop{\mathrm{\mathbb{1}}}\nolimits_{\mathcal{H}}} \le \eta\varepsilon K e^{-\Omega(\varepsilon K^{1/d})}.\] Combining this with the bound on \(\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_1^{(\beta)}}\) gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2\mathop{\mathrm{\mathbb{1}}}\nolimits_{\mathcal{H}}} \le \varepsilon K e^{-\Omega(\varepsilon K^{1/d})}.\] Combining the estimates on \(\mathcal{H}\) and \(\neg\mathcal{H}\), we obtain \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2} \le \varepsilon K\exp\mleft(-a\min\{\varepsilon^2K,\varepsilon K^{1/d}\}\mright)\] for some constant \(a>0\). Since \(\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_2} = \frac{K}{n}\mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>5K\}}\), the lemma follows. ◻

Proof of [thm:anti-robinhood-expected-bounds]. We first prove the displacement bounds that will be used for queries. It is convenient to do this with a generic load parameter \(\theta\), and later we will take \(\theta=\varepsilon/2\).

For a Poissonized table containing \(\operatorname{Poisson}((1-\theta)n)\) keys, define \[P_\theta(K) = \frac{1}{n} \mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>K\}}.\] By monotonicity in the number of keys and Corollary 3, \[P_\theta(K)\le P_0(K)\le C_{\mathrm{crit}}K^{-\chi_d}\] for all \(K\le n/10\), where \(C_{\mathrm{crit}}\) is an absolute constant depending only on \(d\) and \(\alpha\).

Let \(\eta\) and \(C_0\) be the constants from Lemma 7. Choose \[K_\theta = L\max\{\theta^{-2},\theta^{-d}\},\] where \(L\) is a sufficiently large constant, depending only on \(d,\alpha,\eta,C_0\), so that \[C_{\mathrm{crit}}K_\theta^{-\chi_d}\le \eta\theta \qquad\text{and}\qquad K_\theta\ge C_0\max\{\theta^{-2},\theta^{-d}\}.\] Thus, whenever \(K_\theta\le n/10\), \[P_\theta(K_\theta)\le \eta\theta.\] The assumptions on \(\varepsilon\) in the theorem, with \(C_{\mathrm{fin}}\) large enough, ensure that this condition holds for \(\theta=\varepsilon/2\).

Since \(P_\theta(K)\) is nonincreasing in \(K\), the hypothesis of Lemma 7 holds at every scale \(K\ge K_\theta\). Therefore, applying Lemma 7 at scale \(K\) gives \[P_\theta(5K) \le \theta\exp\mleft(-a\min\{\theta^2K,\theta K^{1/d}\}\mright)\] for every \(K_\theta\le K\le n/10\). Equivalently, after changing the constant in the exponent, for every \[K\ge 5K_\theta\] in the range under consideration, \[P_\theta(K) \le \theta\exp\mleft(-\Omega\mleft(\min\{\theta^2K,\theta K^{1/d}\}\mright)\mright). \label{eq:ptheta1}\tag{5}\] In addition to this, for all \(K\), we can always use the load-one bound \[P_\theta(K)=O(K^{-\chi_d}) \label{eq:ptheta2}\tag{6}\] that comes from Corollary 3.

3.5.0.1 Transferring to fixed-load tables.

We next transfer these bounds 5 and 6 to a fixed-load table. Let \(P_\theta^{\mathrm{fix}}(K)\) denote the analogue of \(P_\theta(K)\) for a table with \((1-\theta)n\) keys (rather than a Poisson number of keys). Let \(N\sim\operatorname{Poisson}((1-\theta)n)\). There is an absolute constant \(\gamma>0\) such that \[\mathop{\mathrm{Pr}}[N\ge (1-\theta)n]\ge \gamma.\] On the event \(N\ge(1-\theta)n\), delete uniformly chosen keys from the Poissonized table until exactly \((1-\theta)n\) keys remain. The resulting key set has the fixed-load distribution, and deleting keys cannot increase displacements. Hence \[P_\theta^{\mathrm{fix}}(K)\le \gamma^{-1}P_\theta(K).\] Thus the two displacement-tail bounds 5 and 6 also hold in the fixed-load model.

3.5.0.2 Establishing query time bounds.

Finally, we translate our bound on displacement tails to bounds on query time. Set \[\theta=\varepsilon/2.\] We will bound both successful and unsuccessful queries using the fixed-load tail \(P_\theta^{\mathrm{fix}}\).

First consider a successful query to a fixed stored key in the table of load \(1-\varepsilon\). By history independence, and symmetry across keys, the query time has the same distribution as if we queried a uniformly random stored key. The probability that a uniformly random stored key has displacement greater than \(K\) is \[\frac{n}{(1-\varepsilon)n}\,P_\varepsilon^{\mathrm{fix}}(K) = O(P_\varepsilon^{\mathrm{fix}}(K)) \le O(P_\theta^{\mathrm{fix}}(K)).\]

Now consider an unsuccessful query for a key \(y\) (that is not present). The unsuccessful query stops no later than the position where \(y\) would be placed if inserted. The expected time is therefore at most the expected successful-query time in a table with \((1 - \varepsilon)n + 1\) keys. For all sufficiently large \(n\) in the theorem’s parameter range, \[(1-\varepsilon)n+1\le (1-\varepsilon/2)n=(1-\theta)n.\] Therefore, just as for successful queries, we have that the probability of the query searching to a displacement greater than \(K\) is at most \(O(P_\theta^{\mathrm{fix}}(K))\).

Let \(i_\star=\Theta(n^{1/d})\) be the largest probe index whose sampling interval intersects \([0,n/10]\). To control the remaining probes, we use the following expected completion bound.

The proof is deferred to 8. By definition, \(\tau_n\) depends only on offset variables whose sampling intervals are disjoint from \([0,n/10]\); it is therefore independent of the keys and of all offset variables that determine whether a query reaches displacement \(n/10\). The same independence holds for \(\tau_n(x)\) because it uses only activation bits at offsets at least \(n\). Once the relevant completion threshold is reached, the query has probed every physical slot, and the number of probes made before true displacement \(t\) is at most \(t+1\). Consequently, [lem:polynomial-completion] gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\text{query time}} \le O\mleft( 1+ \sum_{i=1}^{i_\star} P_\theta^{\mathrm{fix}}(\Theta(i^d)) + n^B P_\theta^{\mathrm{fix}}(n/10) \mright).\] Let \[i_0 = \Theta(K_\theta^{1/d}) = \Theta\mleft(\max\{\theta^{-2/d},\theta^{-1}\}\mright) = \Theta\mleft(\max\{\varepsilon^{-2/d},\varepsilon^{-1}\}\mright),\] where the hidden constant is chosen large enough that \(\Theta(i^d)\ge 5K_\theta\) for all \(i\ge i_0\).

We split the sum at \(i_0\). For \(i<i_0\), the load-one tail bound 6 gives \[P_\theta^{\mathrm{fix}}(\Theta(i^d)) = O\mleft((i^d)^{-\chi_d}\mright) = O(i^{-d\chi_d}).\] If \(1\le d<2\), then \(\chi_d=1/2\), so \[\sum_{i<i_0} i^{-d\chi_d} = \sum_{i<i_0} i^{-d/2} = O(i_0^{1-d/2}).\] In this range \(i_0=\Theta(\varepsilon^{-2/d})\), and hence \[i_0^{1-d/2} = O(\varepsilon^{1-2/d}).\] If \(d=2\), then \(d\chi_d=1\) and \(i_0=\Theta(\varepsilon^{-1})\), so the same sum is \[\sum_{i<i_0} i^{-d\chi_d} = \sum_{i<O(\varepsilon^{-1})} i^{-1} = O(\log\varepsilon^{-1}).\] If \(d>2\), then \(\chi_d=1/d\), so again \(d\chi_d=1\), while \(i_0=\Theta(\varepsilon^{-1})\), so the sum is again \[O(\log\varepsilon^{-1}).\]

For \(i\ge i_0\), on the other hand, we may use the bound 5 to deduce that \[P_\theta^{\mathrm{fix}}(\Theta(i^d)) \le O\mleft( \varepsilon \exp\mleft( -\Omega\mleft(\min\{\varepsilon^2 i^d,\varepsilon i\}\mright) \mright) \mright).\] Therefore \[\begin{align} \sum_{i\ge i_0} P_\theta^{\mathrm{fix}}(\Theta(i^d)) &\le O\mleft( \varepsilon\sum_{i\ge i_0} e^{-\Omega(\varepsilon^2 i^d)} \mright) + O\mleft( \varepsilon\sum_{i\ge i_0} e^{-\Omega(\varepsilon i)} \mright). \end{align}\] The final sum is at most \[\varepsilon\sum_{i\ge0}e^{-\Omega(\varepsilon i)}=O(1).\] To bound the second to final sum, comparison with an integral gives \[\sum_{i\ge0}e^{-\Omega(\varepsilon^2 i^d)} = O(\varepsilon^{-2/d}),\] so \[\varepsilon\sum_{i\ge i_0}e^{-\Omega(\varepsilon^2 i^d)} = O(\varepsilon^{1-2/d}).\] This is the desired bound when \(d<2\), and it is \(O(1)\) when \(d\ge2\).

Finally, we bound the polynomial-completion contribution. The tail bound at displacement \(n/10\) gives \[n^B P_\theta^{\mathrm{fix}}(n/10) \le n^B\cdot O\mleft( \varepsilon \exp\mleft( -\Omega\mleft(\min\{\varepsilon^2 n,\varepsilon n^{1/d}\}\mright) \mright) \mright).\] The theorem assumes \[\varepsilon \ge C_{\mathrm{fin}}\log n\cdot \max\{n^{-1/2},n^{-1/d}\}.\] Thus both \[\varepsilon^2n \qquad\text{and}\qquad \varepsilon n^{1/d}\] are at least a sufficiently large constant times \(\log n\), once \(C_{\mathrm{fin}}\) is chosen large enough in terms of \(B,d,\alpha\). Hence the polynomial-completion contribution is \(O(1)\).

Combining the estimates, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\text{query time}} = O(\varepsilon^{1-2/d}) \qquad (1\le d<2),\] and \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\text{query time}} = O(\log\varepsilon^{-1}) \qquad (d\ge2).\] This proves the theorem. ◻

Proof. The indices with \(X_i<1\) contribute at most \(j\) to the sum. We now control the maximal contiguous blocks of indices on which \(X_i\ge1\). Each such block begins with value at most \(3\): either the block starts at \(i=1\), or the previous value was below \(1\), and the growth condition gives \(X_i\le3X_{i-1}<3\).

Fix one block, and let \(M\) be the sum of the values of \(X_i\) in that block. If the block begins at the stopping time \(\tau\), let \(Y_r\) be the value of the process \(r\) steps after the beginning of the block, with \(Y_r=0\) after the block ends, and let \(\mathcal{H}_r=\mathcal{F}_{\tau+r}\). Thus \[M=\sum_{r\ge0}Y_r \qquad\text{and}\qquad Y_0\le3.\] For any \(r\) such that \(Y_r > 0\), the assumptions give \(0\le Y_{r+1}\le3Y_r\) and \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_{r+1}\mid\mathcal{H}_r} \le 10^{-3}Y_r.\] Therefore \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_{r+1}^4\mid\mathcal{H}_r} \le (3Y_r)^3\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_{r+1}\mid\mathcal{H}_r} \le 27\cdot10^{-3}Y_r^4.\] Hence, for some absolute constant \(\rho<1\), and for all \(r \ge 0\), we have \[\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_r^4}\le O(\rho^r).\] By Minkowski’s inequality, \[\mleft(\mathop{\mathrm{\mathbb{E}}}\Bk*{M^4}\mright)^{1/4} \le \sum_{r\ge0}\mleft(\mathop{\mathrm{\mathbb{E}}}\Bk*{Y_r^4}\mright)^{1/4} = O(1).\] Equivalently, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{M^4}=O(1).\] The same argument holds after conditioning on the entire history before the block begins.

There are at most \(j\) such blocks. Let their sums be \[M_1,M_2,\ldots,M_s, \qquad s\le j.\] Let \(\mathcal{G}_\ell\) be the history through the end of the \(\ell\)-th block. The conditional fourth-moment bound above gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{M_\ell^4\mid\mathcal{G}_{\ell-1}}\le C_1\] for an absolute constant \(C_1\). Define \[D_\ell=M_\ell-\mathop{\mathrm{\mathbb{E}}}\Bk*{M_\ell\mid\mathcal{G}_{\ell-1}}.\] Then the \(D_\ell\)’s are martingale differences. The conditional fourth-moment bound also gives the needed lower moments: Jensen’s inequality gives \(\mathop{\mathrm{\mathbb{E}}}\Bk*{M_\ell\mid\mathcal{G}_{\ell-1}}^4\le C_1\), and Cauchy–Schwarz gives \(\mathop{\mathrm{\mathbb{E}}}\Bk*{M_\ell^2\mid\mathcal{G}_{\ell-1}}\le C_1^{1/2}\). Using \((a-b)^2\le2a^2+2b^2\) and \((a-b)^4\le8a^4+8b^4\), we get \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D_\ell^2\mid\mathcal{G}_{\ell-1}}=O(1), \qquad \mathop{\mathrm{\mathbb{E}}}\Bk*{D_\ell^4\mid\mathcal{G}_{\ell-1}}=O(1).\]

We claim that \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\mleft(\sum_{\ell=1}^sD_\ell\mright)^4}=O(j^2).\] To see this, expand the fourth power. Since the \(D_\ell\)’s are martingale differences, every term in which some \(D_\ell\) appears to the first power has expectation zero. The only remaining terms are of the forms \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D_\ell^4} \qquad\text{and}\qquad \mathop{\mathrm{\mathbb{E}}}\Bk*{D_a^2D_b^2}\quad(a<b).\] The first type contributes \(O(j)\). For the second type, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D_a^2D_b^2} = \mathop{\mathrm{\mathbb{E}}}\Bk*{D_a^2\mathop{\mathrm{\mathbb{E}}}\Bk*{D_b^2\mid\mathcal{G}_{b-1}}} = O(\mathop{\mathrm{\mathbb{E}}}\Bk*{D_a^2}) = O(1),\] so the total contribution is \(O(j^2)\). This proves the claim.

Also, \[\sum_{\ell=1}^s\mathop{\mathrm{\mathbb{E}}}\Bk*{M_\ell\mid\mathcal{G}_{\ell-1}} = O(j),\] because \(s\le j\). Thus, for \(R\) sufficiently large, we can apply Markov’s inequality to get \[\begin{align} \mathop{\mathrm{Pr}}\mleft[\sum_{\ell=1}^sM_\ell>Rj\mright] &\le \mathop{\mathrm{Pr}}\mleft[\sum_{\ell=1}^sD_\ell>\Omega(Rj)\mright] \\ &\le \frac{\mathop{\mathrm{\mathbb{E}}}\Bk*{(\sum_{\ell=1}^sD_\ell)^4}}{\Omega(R^4j^4)} = O(R^{-4}j^{-2}). \end{align}\] Adding the deterministic contribution at most \(j\) from the indices with \(X_i<1\), and adjusting the constants as necessary proves the lemma. ◻

Proof. As in the proof of [thm:anti-robinhood-expected-bounds], we begin by considering a Poissonized table, i.e., a table with a Poisson random-variable number of keys. We will also, until the end of the proof, ignore the query-time contributions of keys with displacements greater than \(n / 10\), since these must be handled with a separate argument.

It suffices to consider load parameters of the form \[\varepsilon_j=2^{-j}, \qquad j=1,2,\ldots .\] Let \[K_i=5^iK_{\min},\] where \(K_{\min}\) is a sufficiently large constant. For each \(i\), define \[A_i = K_i^{1/d} \cdot \frac{1}{n} \mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>K_i\}},\] where the expectation is for the Poissonized table at expected load \(1\). Note that \(A_i\) is still a random variable, since it depends on the (still random) offset sequence being used. One can think of \(A_i\) as capturing, for a given offset sequence at load factor \(1\), the expected query cost spent traveling from displacement \(K_{i - 1}\) to \(K_i\). Whenever \(K_i\le n/10\), this quantity \(A_i\) is determined by the Poisson arrivals in a length-\((2K_i)\) interval and therefore does not depend on the choice of \(n\). Thus \(A_i\) may be viewed as a random variable depending only on the offset sequence, and not on \(n\).

We will now argue that the sequence \(A_i\) satisfies the conditions of Lemma 8, after division by a sufficiently large absolute constant. First, \[A_{i+1}\le5^{1/d}A_i\le3A_i,\] because \(d\ge2\) and the quantity \(\frac{1}{n} \mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>K\}}\) is nonincreasing in \(K\). Second, if \(A_i\) is larger than a sufficiently large constant, then the expected number of free slots in an interval of length \(K_i\) in the \(K_i\)-reveal is \[K_i\cdot \frac{1}{n} \mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>K_i\}} = K_i^{(d-1)/d}A_i.\] Thus 3 applies at threshold \(K_i\), giving \[\mathop{\mathrm{\mathbb{E}}}\Bk*{A_{i+1}\mid\text{offsets whose sampling intervals intersect }[0,K_i]} \le 10^{-4}5^{1/d}A_i \le 10^{-3}A_i.\] Therefore, by Lemma 8, for every \(R\ge R_0\) and every \(m\ge1\), \[\mathop{\mathrm{Pr}}\mleft[\sum_{i=1}^m A_i>Rm\mright]\le O(R^{-4}m^{-2}). \label{eq:drift}\tag{7}\]

Choose constants \(R\ge R_0\) and \(M\ge1\), both depending only on \(\delta,d,\alpha\), large enough for the union bounds below; as a slight abuse of notation, we will sometimes include \(R\) and \(M\) in asymptotic notation to indicate that the hidden constants are independent of \(R\) and \(M\).

Fix \(j\), and consider the Poissonized table at load factor \(1-\varepsilon_j\). We show that, except with probability \(O(j^{-2})\) over the offset sequence, its expected query time is \(O(j)\). We first control displacements up to a transition scale using the drift event, then use Lemma 7 for larger displacements up to \(n/10\), and finally handle displacements beyond \(n/10\) by the polynomial-completion bound.

3.6.0.1 Displacements up to the transition scale.

Since \[\varepsilon_j=2^{-j} \qquad\text{and}\qquad K_m^{1/d}=K_{\min}^{1/d}5^{m/d},\] let \(m_j\) be the least positive integer such that \[K_{m_j}^{1/d}\ge MR\frac{j}{\varepsilon_j}. \label{eq:mj-transition-scale}\tag{8}\] By minimality, \[K_{m_j}^{1/d} = \Theta\mleft(MR\frac{j}{\varepsilon_j}\mright),\] and taking logarithms shows that \(m_j=\Theta(j)\), where the implicit constants may depend on \(M,R,d\), and \(K_{\min}\), but not on \(j\) or \(n\). Since \(d\ge2\), choosing \(M\) and \(R\) sufficiently large also ensures \[K_{m_j} \ge C_0\max\{\varepsilon_j^{-2},\varepsilon_j^{-d}\},\] as required by Lemma 7.

Define \[\mathcal{C}_j = \mleft\{ \sum_{i=1}^{m_j}A_i\le Rm_j \mright\}.\] The bound 7 gives \[\mathop{\mathrm{Pr}}[\neg\mathcal{C}_j] \le O(R^{-4}m_j^{-2}) = O(R^{-4}j^{-2}). \label{eq:Cjprob}\tag{9}\]

Fix an offset sequence for which \(\mathcal{C}_j\) holds. Since lowering the load can only decrease displacement tails, the expected query-time contribution from displacement scales at most \(K_{m_j}\) in the table of load \(1-\varepsilon_j\) is bounded by the corresponding load-one quantities. Hence it is \[O\mleft(1+\sum_{i=1}^{m_j}A_i\mright) \le O(1+Rm_j) = O(Rj), \label{eq:Cjholds}\tag{10}\] where the expectation is over the keys and their hashes only.

3.6.0.2 Displacements from the transition scale to \(n/10\).

The event \(\mathcal{C}_j\) also supplies the starting condition for Lemma 7. To see this, fix the offsets whose sampling intervals intersect \([0,K_{m_j}]\) and suppose that they satisfy \(\mathcal{C}_j\). The definition of \(A_{m_j}\) is the load-one displacement tail for this fixed revealed prefix, multiplied by \(K_{m_j}^{1/d}\). Therefore, by monotonicity in the load, \[\frac{1}{n} \mathop{\mathrm{\mathbb{E}}}\Bk*{\#\{x:\operatorname{disp}(x)>K_{m_j}\}} \le \frac{A_{m_j}}{K_{m_j}^{1/d}} \le \frac{\sum_{i=1}^{m_j}A_i}{K_{m_j}^{1/d}} \le O\mleft(\frac{Rj}{K_{m_j}^{1/d}}\mright) = O\mleft(\frac{\varepsilon_j}{M}\mright).\] Here the expectation is over the keys; offsets beyond the revealed prefix do not affect whether a displacement exceeds \(K_{m_j}\). Taking \(M\) sufficiently large makes the last expression at most \(\eta\varepsilon_j\).

This bound is pointwise in every extension of the revealed prefix. Since the displacement tail is nonincreasing in its threshold, after revealing any additional offsets the hypothesis of Lemma 7 continues to hold at every scale \(K\ge K_{m_j}\). Moreover, \(K_{m_j}\ge\varepsilon_j^{-d}\) implies \[\varepsilon_j^2K \ge \varepsilon_jK^{1/d} \qquad\text{for every }K\ge K_{m_j},\] so the second term is the minimum in the exponent of Lemma 7. Consequently, for every \(s\ge0\) such that \(K_{m_j+s}\le n/10\), that lemma, followed by averaging over the revealed offsets conditioned on \(\mathcal{C}_j\), gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\frac{1}{n} \#\{x:\operatorname{disp}(x)>K_{m_j+s+1}\} \mid \mathcal{C}_j} \le \varepsilon_j \exp\mleft(-\Omega\mleft(\varepsilon_jK_{m_j+s}^{1/d}\mright)\mright).\] Because \(K_{m_j+s}=5^sK_{m_j}\) and 8 holds, \[\varepsilon_jK_{m_j+s}^{1/d} = \Theta(5^{s/d}MRj).\] It follows that the conditional expected query-time contribution from these scales is at most \[\begin{align} &\sum_{\substack{s\ge0:\\K_{m_j+s}\le n/10}} K_{m_j+s+1}^{1/d} \mathop{\mathrm{\mathbb{E}}}\Bk*{\frac{1}{n} \#\{x:\operatorname{disp}(x)>K_{m_j+s+1}\} \mid \mathcal{C}_j} \\ &\qquad\le \sum_{s\ge0} O(5^{s/d}MRj) \exp\mleft(-\Omega(5^{s/d}MRj)\mright) \le \exp(-\Omega(MRj)). \end{align}\] The infinite sum on the right dominates the finite sum for every table size \(n\), so this estimate holds simultaneously for all \(n\) for which \(K_{m_j}\le n/10\). By Markov’s inequality, conditioned on \(\mathcal{C}_j\), the probability over the remaining random offsets that the expected contribution of these displacement scales exceeds \(1\) is at most \[\exp(-\Omega(MRj)).\]

Combining this estimate with 9 and 10 , for a sufficiently large constant \(C'\) we obtain \[\mathop{\mathrm{Pr}}\mleft[ \mathop{\mathrm{\mathbb{E}}}\Bk*{\text{truncated query time}\mid\text{offset sequence}} > C'Rj \mright] \le O(R^{-4}j^{-2})+\exp(-\Omega(MRj)). \label{eq:prexpj}\tag{11}\] Here “truncated” means that only the contribution from displacements at most \(n/10\) is counted. The probability is over the random fixed-offset degree-\(d\) offset sequence, while the inner expectation is over the keys and their hashes.

3.6.0.3 Displacements beyond \(n/10\).

Suppose, as in the theorem statement, that the table size \(n\) satisfies \[\varepsilon_j \ge C_{\mathrm{sim}}\log n\cdot\max\{n^{-1/2},n^{-1/d}\}. \label{eq:epsjlower}\tag{12}\] Under this assumption, \(j=O(\log n)\). Together with \(K_{m_j}^{1/d}=O(MRj/\varepsilon_j)\), this shows that, after increasing \(C_{\mathrm{sim}}\) in terms of \(M,R,d\), we have \(K_{m_j}\le n/10\). Thus the preceding short- and intermediate-displacement estimates apply to every admissible \(n\).

Let \(\tau_n\) be the completion threshold from [lem:polynomial-completion]. It has expectation \(n^{O(1)}\) and, by its definition, is independent of the displacement tail at \(n/10\), which is determined by the keys and by offset variables whose sampling intervals intersect \([0,n/10]\). Moreover, every query has stopped by true displacement \(\tau_n\), after at most \(\tau_n+1\) probes. Therefore, averaging over both the offset sequence and the keys, the expected contribution of keys with displacement greater than \(n/10\) is at most \[n^B\cdot O\mleft( \varepsilon_j \exp\mleft( -\Omega\mleft( \min\{\varepsilon_j^2 n,\varepsilon_j n^{1/d}\} \mright) \mright) \mright). \label{eq:largedisp}\tag{13}\] The inequality 12 implies \[\min\{\varepsilon_j^2 n,\varepsilon_j n^{1/d}\} \ge \Omega(C_{\mathrm{sim}}\log n).\] Fix an integer \(q\ge3\), to be chosen below. Taking \(C_{\mathrm{sim}}\) sufficiently large in terms of \(q\) makes 13 at most \(n^{-q}\). Markov’s inequality then shows that, for this pair \((j,n)\), the probability that the completion contribution exceeds \(1\) is at most \(n^{-q}\). Every \(n\) satisfying 12 is at least \(\varepsilon_j^{-1}\), so a union bound over all admissible table sizes gives failure probability at most \[\sum_{n\ge\varepsilon_j^{-1}}n^{-q} = O(\varepsilon_j^{q-1}) = O(2^{-(q-1)j}).\] Combining this bound with 11 , the probability that there exists an admissible \(n\) for which the expected query time at load \(1-\varepsilon_j\) exceeds \(C'Rj+1\) is at most \[O(R^{-4}j^{-2}) + \exp(-\Omega(MRj)) + O(2^{-(q-1)j}).\] Choose \(R\), \(M\), and \(q\), and then \(C_{\mathrm{sim}}\), sufficiently large in terms of \(\delta,d,\alpha\). Summing the preceding display over all \(j\ge1\) then gives a total failure probability at most \(\delta\). Thus, with probability at least \(1-\delta\), every dyadic slack \(\varepsilon_j\) and every \(n\) satisfying 12 have expected query time \[O(j)=O(\log\varepsilon_j^{-1}).\]

To pass from dyadic to arbitrary slack, choose \(j\) so that \[\varepsilon_j\le\varepsilon<2\varepsilon_j.\] The table at slack \(\varepsilon\) has no larger expected query time than the table at the smaller slack \(\varepsilon_j\). After doubling the constant in the theorem’s lower bound on \(\varepsilon\), the admissibility of \((\varepsilon,n)\) implies the admissibility of \((\varepsilon_j,n)\). Since \(j=\Theta(\log\varepsilon^{-1})\), this proves the theorem for Poissonized tables.

Finally, since a table with \(\operatorname{Poisson}((1 - \varepsilon)n)\) keys has at least \(\lfloor(1 - \varepsilon)n\rfloor\) keys with probability \(\Omega(1)\), we can conclude that any expected-query-time bound on the Poissonized table also applies (up to constant factors) to a table with exactly \(\lfloor(1 - \varepsilon)n\rfloor\) keys. This completes the proof. ◻

Proof. Reveal the activation bits one offset at a time, for \(k=K_-+1,K_-+2,\ldots,K_+\). Just before the bits at offset \(k\) are exposed, call \(a+k\) a \(k\)-opportunity for \(a\) if it is free in the \((k-1)\)-reveal. Whether \(a+k\) is a \(k\)-opportunity is determined by the information already exposed.

Whenever a \(k\)-opportunity exists and at least one key with home position \(a\) is still absent, choose the highest-priority such key and reveal its activation bit at offset \(k\) first. This bit is independent of the past and equals \(1\) with probability \[p(k)\ge cK_+^{-(d-1)/d}\] for a constant \(c=c(d)>0\). If the bit equals \(1\), the chosen key is placed at \(a+k\): before offset \(k\) the slot is free, and at true offset \(k\) only keys with home position \(a\) can probe it. We may then reveal the remaining activation bits at offset \(k\) in any order.

Initially fewer than \(\beta\) same-home keys are absent. Hence, if one of them is still absent from the \(K_+\)-reveal, fewer than \(\beta\) successful opportunity activations occurred. Conversely, every slot in \(a+[K_-+1,K_+]\) that is free in the \(K_+\)-reveal was a \(k\)-opportunity at its corresponding offset \(k\). Thus the event in the lemma with \(S\) final free slots entails at least \(S\) adaptive trials, each with head probability at least \(cK_+^{-(d-1)/d}\), but fewer than \(\beta\) heads. Applying 5 with \(t=1\) and with \(t_k\) equal to the corresponding conditional head probability proves the claim. ◻

Proof. Write \(\lambda=(1-\varepsilon)n\), \(m=\floor*{\lambda}\), and \(\Delta=\varepsilon n/2\), and let \[\mathcal{E}=\{m\le N\le\lambda+\Delta\}.\] The assumption \(n\ge10\varepsilon^{-2}\) gives \(\Delta/\sqrt{\lambda}\ge\sqrt{5/2}\). A standard uniform local central-limit estimate for the Poisson distribution therefore gives \[\mathop{\mathrm{Pr}}[\mathcal{E}]\ge\frac{1}{3},\] with the integer endpoints rounded as above.

We next couple the two hash tables on \(\mathcal{E}\). The standard instance contains at most \(m\) keys other than \(x\). Fix a value of \(N\) in this event, generate the \(N\) other keys and all their probe sequences, and use the first required number of these keys for the standard instance. The Poissonized instance is obtained from the standard instance by adding keys. In the deferred-acceptance view from the proof of [lem:history-independence-of-rh-and-arh], adding proposals can only make slots more selective; it cannot move an old key to an earlier proposal in its probe sequence. Thus, under this coupling, \[\mathrm{disp}^{(\mathrm{Poi})}(x) \ge \mathrm{disp}^{(\mathrm{std})}(x).\] The same domination holds after averaging over \(N\) conditional on \(\mathcal{E}\). Therefore \[\begin{align} \mathop{\mathrm{Pr}}\Bk*{\mathrm{disp}^{(\mathrm{Poi})}(x)\ge L} &\ge \mathop{\mathrm{Pr}}[\mathcal{E}]\, \mathop{\mathrm{Pr}}\Bk*{\mathrm{disp}^{(\mathrm{Poi})}(x)\ge L\mid\mathcal{E}}\\ &\ge \frac{1}{3}\mathop{\mathrm{Pr}}\Bk*{\mathrm{disp}^{(\mathrm{std})}(x)\ge L}, \end{align}\] which proves the claim. ◻

Proof. By [lem:history-independence-of-rh-and-arh], we may insert the keys in increasing order of their hash values. Write \(\mathcal{E}_1\) and \(\mathcal{E}_2\) for the first and second events in the statement.

4.1.0.1 The coupling.

Up to the moment when a key first crosses slot \(n\), the standard cyclic table and the right-unbounded table use the same activation bits. In the right-unbounded table, once a key crosses slot \(n\), we mark it as overflowed and do not expose its later probes; those later probes cannot affect any slot in \([n]\) in the right-unbounded model.

We next specify the fresh randomness used by the standard table after a key wraps around to the left. Let \[p_0 \mathrel{\vcenter{:}}= p(3n/2) = (3n/2)^{-\frac{d-1}{d}}.\] For each wrap-around kicking chain, draw a fresh block \((B_1,\ldots,B_{n/2})\) of independent Bernoulli\((p_0)\) random variables, one for each slot in \([1,n/2]\). When the current key is tested at a slot \(j\le n/2\) during this chain, its cyclic displacement is at most \(3n/2\), so its true activation probability at that occurrence is at least \(p_0\). We use the monotone coupling in which \(B_j=1\) forces the true activation bit for the current key at slot \(j\) to be \(1\); if \(B_j=0\), the remaining activation randomness is filled in so that the marginal activation probability is correct.

4.1.0.2 The good event.

During a wrap-around chain, let \(E\subseteq[1,n/2]\) be the set of empty slots in \([1,n/2]\) just before the chain starts. The set \(E\) may depend on the right-unbounded process and on the pool blocks used by earlier wrap-around chains. Define \(\mathcal{G}\) to be the event that, for every wrap-around chain for which \(\abs{E}\ge \frac{\varepsilon n}{6}\), the fresh pool block for that chain has \(B_j=1\) for at least one \(j\in E\).

We bound the probability of \(\mathcal{G}\) conditional on \(\mathcal{E}_1\cap \mathcal{E}_2\). Fix any realization of the right-unbounded process satisfying \(\mathcal{E}_1\cap\mathcal{E}_2\), and expose the wrap-around pool blocks adaptively. Conditional on the past and on the current set \(E\) with \(\abs{E}\ge \frac{\varepsilon n}{6}\), the probability that the current chain fails the requirement in \(\mathcal{G}\) is at most \[(1-p_0)^{\frac{\varepsilon n}{6}} \le \exp\bk*{-\Omega\bk*{\varepsilon n^{\frac{1}{d}}}}.\] On \(\mathcal{E}_2\), there are at most \(\frac{\varepsilon n}{6}\) wrap-around chains. Hence a sequential union bound gives \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{G}^c \mid \mathcal{E}_1\cap\mathcal{E}_2} \le \frac{\varepsilon n}{6}\exp\bk*{-\Omega\bk*{\varepsilon n^{\frac{1}{d}}}} \le \exp\bk*{-\Omega\bk*{\varepsilon n^{\frac{1}{d}}}},\] where the last inequality uses \(n\ge100\varepsilon^{-10d}\). This proves the stated conditional probability bound.

4.1.0.3 Termination before \(n/2\).

We now work deterministically on \(\mathcal{E}_1\cap\mathcal{E}_2\cap\mathcal{G}\). We claim that every wrap-around kicking chain in the standard table terminates before reaching slot \(n/2\). Proceed by induction over the increasing-home insertion order. Suppose all previous wrap-around chains terminated inside \([1,n/2]\). Then the part of the standard table in \([n/2,n]\) is identical to the right-unbounded table, and every key that newly wraps around in the standard table is one of the overflowed keys in the right-unbounded table.

At the start of the current wrap-around chain, every occupied slot in \([1,n/2]\) contains either a key whose hash location lies in \([1,n/2]\), or one of the keys that overflowed past slot \(n\) in the right-unbounded table. By \(\mathcal{E}_1\) and \(\mathcal{E}_2\), the number of such occupied slots is at most \[\bk*{1-\frac{2\varepsilon}{3}}\frac{n}{2} + \frac{\varepsilon n}{6} = \frac{n}{2} - \frac{\varepsilon n}{6}.\] Thus there are at least \(\frac{\varepsilon n}{6}\) empty slots in \([1,n/2]\) at the start of the chain. Since \(\mathcal{G}\) occurs, the fresh pool block has \(B_j=1\) at one of these empty slots. That slot is activated for the current key when the chain reaches it, so the chain stops there. This proves the induction claim.

4.1.0.4 Comparing the displacement of \(x\).

If \(x\) does not overflow in the right-unbounded table, then all slots relevant to the placement of \(x\) lie in \([n/2,n]\), where the coupled tables are identical. Hence \(\mathrm{disp}^{(\mathrm{std})}(x)=\mathrm{disp}^{(\mathrm{Ru})}(x)\). If \(x\) overflows in the right-unbounded table, then \(h(x)=3n/4\) implies \(\mathrm{disp}^{(\mathrm{Ru})}(x)\ge \frac{n}{4}\). By the termination claim, the standard wrap-around chain of \(x\) terminates before slot \(n/2\), and in particular \(\mathrm{disp}^{(\mathrm{std})}(x)\le n\). Therefore \[\mathrm{disp}^{(\mathrm{std})}(x) \le n \le 4\mathrm{disp}^{(\mathrm{Ru})}(x).\] The desired comparison follows in both cases. ◻

Proof. Fix \(t\) and \(k\ge k_0\). We prove 14 and 15 simultaneously by induction on \(t\), assuming both estimates at every earlier slot and for every parameter at least \(k_0\). The base case \(t=0\) is immediate.

The proof follows the two mechanisms described above. First, the induction hypothesis bounds the number and displacement of the keys present sufficiently far in the past; each such key then has many independent opportunities to be placed, which controls the current maximum displacement. Second, once all frontier displacements are moderate, a large frontier supplies a probe at almost every slot. Since the mean number of new arrivals per slot is only \(1-\varepsilon\), the frontier size is then dominated by a random walk with drift \(-\varepsilon/2\).

4.2.0.1 Step 1: bounding the maximum displacement.

Let \[M\mathrel{\vcenter{:}}=\ceil*{4k\varepsilon^{-1}}.\] If \(t<M\), then every key in \(S_t\) has displacement less than \(M\), so the desired maximum bound is immediate. Suppose henceforth that \(t\ge M\). Since displacements are integers, the event \(\max(S_t)>4k\varepsilon^{-1}\) implies \(\max(S_t)\ge M\). Any key witnessing this event was already present in \(S_{t-M}\) and survived all of the next \(M\) slots. By the induction hypothesis with parameter \(2k\), \[\begin{align} \mathop{\mathrm{Pr}}\Bk*{\abs{S_{t-M}}>2k\varepsilon^{-1}} &\le \exp\bk*{-(2k)^{\frac{1}{d}}/100}, \tag{16}\\ \mathop{\mathrm{Pr}}\Bk*{\max(S_{t-M})>8k\varepsilon^{-1}} &\le \exp\bk*{-(2k)^{\frac{1}{d}}/100}. \tag{17} \end{align}\] For \(k_0\) sufficiently large, each right-hand side is at most \(\frac{1}{4}\exp(-k^{\frac{1}{d}}/100)\). Condition on the complementary good event and on the whole multiset \(S_{t-M}\).

Fix a key \(x\) represented in \(S_{t-M}\). Throughout the interval \(\{t-M+1,\ldots,t\}\), the relative Robin Hood priority of two keys already in \(S_{t-M}\) is fixed: the key with the smaller home slot has the larger displacement. Moreover, every key arriving after time \(t-M\) has lower priority than \(x\). Expose the probes in this interval of the keys in \(S_{t-M}\) that have higher priority than \(x\). Each such key can occupy at most one slot, so these keys block at most \(\abs{S_{t-M}}\le2k\varepsilon^{-1}\) of the \(M\) slots. Consequently, at least \[M-2k\varepsilon^{-1}\ge2k\varepsilon^{-1}\] slots remain at which \(x\) would be placed if it probed: each such slot is either empty or occupied only by a lower-priority key.

At every one of these available slots, the displacement of \(x\) is at most \[\max(S_{t-M})+M \le 16k\varepsilon^{-1},\] after increasing \(k_0\) to absorb rounding. The activation decisions of \(x\) at the available slots are independent of the probes exposed above, and each has probability at least \(p(16k\varepsilon^{-1})\). Hence, conditionally on the good event and on the higher-priority probes, \[\begin{align} \mathop{\mathrm{Pr}}\Bk*{x\in S_t} &\le \bk*{1-p(16k\varepsilon^{-1})}^{2k\varepsilon^{-1}} \\ &\le \exp\bk*{-(k\varepsilon^{-1})^{\frac{1}{d}}/16}. \end{align}\] A union bound over the at most \(2k\varepsilon^{-1}\) keys in \(S_{t-M}\) makes this conditional probability at most \[\frac{1}{2}\exp\bk*{-k^{\frac{1}{d}}/100}\] when \(k_0\) is sufficiently large. Combining this estimate with 16 and 17 proves 15 at time \(t\).

4.2.0.2 Step 2: coupling the size process to a negative-drift walk.

It remains to prove 14 at time \(t\). Put \[L\mathrel{\vcenter{:}}=\ceil*{10k\varepsilon^{-2}}, \qquad B\mathrel{\vcenter{:}}= 8k\varepsilon^{-1}\log^{2d}(k\varepsilon^{-1}).\] The guiding idea is that, while \(\max(S_{i-1})\le B\), a frontier of size at least \(\frac{1}{2}k\varepsilon^{-1}\) contains many keys, each with a nonnegligible chance to probe slot \(i\). With probability at least \(1-\varepsilon/2\), some old key is therefore placed. This service rate exceeds the mean arrival rate \(1-\varepsilon\) by \(\varepsilon/2\), creating negative drift.

For each slot \(i\), let \(Y_i\in\{0,1\}\) indicate that some key is placed into slot \(i\) during the transition from \(S_{i-1}\) to \(S_i\). Then \[\label{eq:frontier-size-transition-revised} \abs{S_i}=\abs{S_{i-1}}+X_i-Y_i.\tag{18}\]

Conditional on the past, let \(q_i\) be the probability that none of the keys already in \(S_{i-1}\) probes slot \(i\). Draw independent random variables \(U_i\sim\operatorname{Unif}[0,1]\), also independent of the arrivals, and use a monotone coupling in which the event that at least one old key probes slot \(i\) is realized as \(\{U_i\le1-q_i\}\). Define \[\widetilde{Y}_i\mathrel{\vcenter{:}}=\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{U_i\le1-\varepsilon/2}}, \qquad Z_i\mathrel{\vcenter{:}}=\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{q_i>\varepsilon/2}}, \qquad W_i\mathrel{\vcenter{:}}= X_i-\widetilde{Y}_i.\] If \(q_i\le\varepsilon/2\), then \(1-q_i\ge1-\varepsilon/2\), so \(\widetilde{Y}_i=1\) forces an old key to probe and therefore forces \(Y_i=1\). If \(q_i>\varepsilon/2\), subtracting \(Z_i=1\) makes the same lower bound trivial. Thus, in all cases, \[\label{eq:Yi-coupling-revised} Y_i\ge \widetilde{Y}_i-Z_i.\tag{19}\] The variables \(W_i\) are independent and satisfy \[\label{eq:Wi-mean-var-revised} \mathop{\mathrm{\mathbb{E}}}\Bk*{W_i}=-\varepsilon/2, \qquad \mathop{\mathrm{Var}}(W_i)\le2.\tag{20}\]

We next verify that the error term \(Z_i\) vanishes whenever the frontier is large and its maximum displacement is controlled. If \[\abs{S_{i-1}}\ge \frac{1}{2} k\varepsilon^{-1} \qquad\text{and}\qquad \max(S_{i-1})\le B,\] then every old key probes slot \(i\) with probability at least \(p(B+1)\), independently of the others. Consequently, \[\begin{align} q_i &\le \bk*{1-p(B+1)}^{\frac{1}{2} k\varepsilon^{-1}} \\ &\le \exp\bk*{-\frac{1}{2} k\varepsilon^{-1}(B+1)^{-\frac{d-1}{d}}} \\ &\le \exp\bk*{-(k\varepsilon^{-1})^{\frac{1}{2d}}} \le \varepsilon/2, \end{align}\] where the last two inequalities hold for \(k_0\) sufficiently large as a function of \(d\). Hence \(Z_i=0\), and 18 –19 give \[\abs{S_i}-\abs{S_{i-1}}\le W_i.\] Thus \(W_i\) is the promised negative-drift comparison increment whenever the frontier is both large and low-maximum.

4.2.0.3 Step 3: reducing a large frontier to four exceptional events.

Let \[a\mathrel{\vcenter{:}}=\max\{0,t-L\}, \qquad T\mathrel{\vcenter{:}}= t-a=\min\{t,L\}.\] We claim that \(\abs{S_t}>k\varepsilon^{-1}\) implies at least one of the following events: \[\begin{align} \mathcal{F}_1 &\mathrel{\vcenter{:}}= \BK*{\abs{S_a}>2k\varepsilon^{-1}}, \\ \mathcal{F}_2 &\mathrel{\vcenter{:}}= \BK*{\exists i\in\BK{a,\ldots,t-1}: \max(S_i)>B}, \\ \mathcal{F}_3 &\mathrel{\vcenter{:}}= \BK*{T=L\;\text{ and }\; \sum_{i=t-L+1}^{t} W_i>-k\varepsilon^{-1}}, \\ \mathcal{F}_4 &\mathrel{\vcenter{:}}= \BK*{\exists m\in\{1,\ldots,T\}: \sum_{i=t-m+1}^{t} W_i>\frac{1}{3} k\varepsilon^{-1}}. \end{align}\] The four events have a direct interpretation: the frontier is already too large at the start of the window, the maximum-displacement control fails somewhere in the window, the comparison walk does not realize its expected decrease over a full window, or a terminal segment of that walk has an unusually large upward excursion.

Suppose none of \(\mathcal{F}_1,\ldots,\mathcal{F}_4\) occurs. First assume that \[\abs{S_i}\ge \frac{1}{2}k\varepsilon^{-1} \qquad\text{for every }i\in\{a,\ldots,t-1\}.\] Since \(S_0=\varnothing\), this case forces \(a>0\) and hence \(T=L\). The failure of \(\mathcal{F}_2\) makes the comparison from Step 2 valid on every transition from \(a+1\) through \(t\). Therefore, using the failures of \(\mathcal{F}_1\) and \(\mathcal{F}_3\), \[\abs{S_t} \le \abs{S_a}+\sum_{i=a+1}^{t}W_i \le 2k\varepsilon^{-1}-k\varepsilon^{-1} =k\varepsilon^{-1}.\]

Otherwise, let \(s\) be the last index in \(\{a,\ldots,t-1\}\) with \(\abs{S_s}\le\frac{1}{2}k\varepsilon^{-1}\). For each transition \(i\in\{s+2,\ldots,t\}\), the previous frontier is larger than \(\frac{1}{2}k\varepsilon^{-1}\); the failure of \(\mathcal{F}_2\) again makes the comparison from Step 2 valid. At the first transition after \(s\), we use only \[X_{s+1}=W_{s+1}+\widetilde{Y}_{s+1}\le W_{s+1}+1.\] Since \(t-s\le T\), the failure of \(\mathcal{F}_4\) now gives \[\begin{align} \abs{S_t} &\le \abs{S_s}+1+\sum_{i=s+1}^{t}W_i \\ &\le \frac{1}{2}k\varepsilon^{-1}+1+\frac{1}{3}k\varepsilon^{-1} \le k\varepsilon^{-1}, \end{align}\] where the last inequality holds for \(k\varepsilon^{-1}\ge6\). This proves the claimed implication. In particular, it formalizes the drift intuition: a frontier that remains large for a whole window can stay large only if the walk fails to drift downward, while a frontier that became large more recently requires a large upward fluctuation after its last visit below the half-threshold.

4.2.0.4 Step 4: bounding the four exceptional events.

If \(a=0\), then \(\mathcal{F}_1\) is impossible. Otherwise, the induction hypothesis with parameter \(2k\) gives \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{F}_1} \le \exp\bk*{-(2k)^{\frac{1}{d}}/100} \le \frac{1}{4}\exp\bk*{-k^{\frac{1}{d}}/100}.\] For \(\mathcal{F}_2\), apply the induction hypothesis for the maximum tail at each fixed \(i<t\) with parameter \[2k\log^{2d}(k\varepsilon^{-1}).\] The corresponding maximum threshold is \(B\). Hence \[\mathop{\mathrm{Pr}}\Bk*{\max(S_i)>B} \le \exp\bk*{-(2k)^{\frac{1}{d}}\log^2(k\varepsilon^{-1})/100}.\] A union bound over at most \(L\) indices gives \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{F}_2} \le \frac{1}{4}\exp\bk*{-k^{\frac{1}{d}}/100}\] by the choice of \(k_0\).

If \(T<L\), then \(\mathcal{F}_3\) is empty. If \(T=L\), the sum in \(\mathcal{F}_3\) has mean at most \(-5k\varepsilon^{-1}\) and variance at most \(2L\). The standard Chernoff bound for a centered Poisson-minus-Bernoulli sum gives, for any interval \(I\) and any \(u\ge0\), \[\label{eq:poisson-bernoulli-chernoff-revised} \mathop{\mathrm{Pr}}\Bk*{\sum_{i\in I}(W_i-\mathop{\mathrm{\mathbb{E}}}\Bk*{W_i})>u} \le \exp\bk*{-\Omega\bk*{\min\{u^2/\abs{I},u\}}}.\tag{21}\] Taking \(I=\{t-L+1,\ldots,t\}\) and \(u\ge4k\varepsilon^{-1}\) yields \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{F}_3} \le \exp(-\Omega(k)) \le \frac{1}{4}\exp\bk*{-k^{\frac{1}{d}}/100}.\]

Finally, we bound \(\mathcal{F}_4\) by an exponential supermartingale. Let \(\theta\mathrel{\vcenter{:}}=\varepsilon/16\) and let \(W=X-\widetilde{Y}\), where \(X\sim\operatorname{Poisson}(1-\varepsilon)\) and \(\widetilde{Y}\sim\operatorname{Bernoulli}(1-\varepsilon/2)\) are independent. Then \[\begin{align} \log \mathop{\mathrm{\mathbb{E}}}\Bk*{e^{\theta W}} &=(1-\varepsilon)(e^\theta-1) +\log\bk*{\varepsilon/2+(1-\varepsilon/2)e^{-\theta}} \\ &\le -\varepsilon\theta/2+2\theta^2 \le0. \end{align}\] For \(m=0,1,\ldots,T\), define \[M_m\mathrel{\vcenter{:}}= \exp\bk*{\theta\sum_{j=1}^{m}W_{t-j+1}}\] and let \(\mathcal{H}_m=\sigma(W_t,W_{t-1},\ldots,W_{t-m+1})\). Independence of the \(W_i\)’s and the preceding moment bound show that \((M_m)_{m=0}^{T}\) is a nonnegative supermartingale with respect to \((\mathcal{H}_m)_{m=0}^{T}\), with \(M_0=1\). The bound of \(\mathcal{F}_4\) follows from the standard maximal inequality below.

Applying 3 at level \(\exp(\theta k\varepsilon^{-1}/3)\) gives \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{F}_4} \le \exp\bk*{-\frac{\theta k\varepsilon^{-1}}{3}} =\exp(-k/48) \le \frac{1}{4}\exp\bk*{-k^{\frac{1}{d}}/100}.\]

A union bound over \(\mathcal{F}_1,\ldots,\mathcal{F}_4\) proves 14 at time \(t\), completing the induction and the proof of the lemma. ◻

Proof. Expose the table formed by all keys except \(x\), and then insert \(x\) with an independent probe sequence. Same-home ties may be broken against \(x\), which can only increase its displacement and is therefore harmless for an upper bound. By 12, \[\mathop{\mathrm{Pr}}\Bk*{\abs{S_t}>k\varepsilon^{-1}} \le \exp\bk*{-k^{\frac{1}{d}}/100}.\] Condition on the complementary event and on the whole frontier \(S_t\). In the next \(\ceil*{2k\varepsilon^{-1}}\) slots, at most \(k\varepsilon^{-1}\) slots can be occupied by keys that have higher Robin Hood priority than \(x\). Thus there are at least \(k\varepsilon^{-1}\) slots in this interval where \(x\) would be placed if it probed the slot. At each such slot, the displacement of \(x\) is at most \(2k\varepsilon^{-1}\) up to rounding, so the activation probability is at least \(p(2k\varepsilon^{-1})\) after changing constants. Therefore \[\begin{align} \mathop{\mathrm{Pr}}\Bk*{\mathrm{disp}^{(\mathrm{Ru})}(x)>2k\varepsilon^{-1}\mid \abs{S_t}\le k\varepsilon^{-1},S_t} &\le \bk*{1-p(2k\varepsilon^{-1})}^{k\varepsilon^{-1}} \\ &\le \exp\bk*{-(k\varepsilon^{-1})^{\frac{1}{d}}/2} \le \exp\bk*{-k^{\frac{1}{d}}/100}, \end{align}\] for \(k_0\) sufficiently large. Combining the two estimates proves the claim. ◻

Proof. By symmetry of the cyclic table, we may condition on \(h(x)=3n/4\). Applying the Poissonization reduction 10 conditionally on this home slot, it is enough to control the corresponding Poissonized cyclic table up to a factor \(3\) in tail probabilities.

Couple the Poissonized cyclic table to the Poissonized right-unbounded table as in 11. Let \(\mathcal{E}_0\) be the event that the Poissonized number of keys is at most \(n\). Recall that \(\mathcal{E}_1\) is the event that at most \((1-2\varepsilon/3)n/2\) keys hash to \([1,n/2]\) in the right-unbounded model, and \(\mathcal{E}_2\) is the event that at most \(\varepsilon n/6\) keys travel beyond slot \(n\). Let \(\mathcal{G}\) be the good event from that lemma. Standard Chernoff bounds give \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{E}_0^c}+\mathop{\mathrm{Pr}}\Bk*{\mathcal{E}_1^c} \le \exp(-\Omega(\varepsilon^2 n)).\] Moreover, the number of keys traveling beyond slot \(n\) in the right-unbounded table is \(\abs{S_n}\), so 12 with \(k=\varepsilon^2 n/6\) gives \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{E}_2^c} \le \exp\bk*{-\Omega\bk*{(\varepsilon^2 n)^{\frac{1}{d}}}}.\] Finally, 11 gives \[\mathop{\mathrm{Pr}}\Bk*{\mathcal{G}^c\mid \mathcal{E}_1\cap\mathcal{E}_2} \le \exp\bk*{-\Omega\bk*{\varepsilon n^{\frac{1}{d}}}}.\] Write \[\eta_n \mathrel{\vcenter{:}}= \exp(-\Omega(\varepsilon^2 n)) +\exp\bk*{-\Omega\bk*{(\varepsilon^2 n)^{\frac{1}{d}}}} +\exp\bk*{-\Omega\bk*{\varepsilon n^{\frac{1}{d}}}}.\] On \(\mathcal{E}_0\cap\mathcal{E}_1\cap\mathcal{E}_2\cap\mathcal{G}\), the cyclic displacement is at most four times the right-unbounded displacement. Hence, for every \(T\ge8k_0\varepsilon^{-1}\), \[\label{eq:standard-rh-displacement-tail} \mathop{\mathrm{Pr}}\Bk*{\mathrm{disp}(x)>T} \le O\mleft( \exp\bk*{-\Omega\bk*{(\varepsilon T)^{\frac{1}{d}}}} +\eta_n \mright),\tag{22}\] where we used 4 with \(k=\Theta(\varepsilon T)\) and absorbed the constant factor from Poissonization. All hidden constants in this proof may depend on the fixed constant \(d\).

Although the comparison with the right-unbounded model is valid for the entire tail, the additive bad-event probability \(\eta_n\) in 22 cannot be summed over infinitely many values of \(T\). We therefore use a separate unconditional bound beyond one full cycle. Insert \(x\) last, which is allowed by history independence, and condition on the table formed by all other keys. There are at least \(\varepsilon n\) empty physical slots. For \(T\ge n\), the offsets at most \(T\) contain at least \(\frac{1}{2}\varepsilon T\) occurrences of these empty slots. If any such occurrence is activated, then \(x\) is placed no later than that offset. Since each occurrence has activation probability at least \(p(T)\) and the activation bits are independent, \[\label{eq:standard-crude-long-tail} \mathop{\mathrm{Pr}}\Bk*{\mathrm{disp}(x)>T} \le \exp\bk*{-\Omega\bk*{\varepsilon T^{\frac{1}{d}}}} \qquad(T\ge n).\tag{23}\]

Summing the tail probabilities, 22 contributes \(O(\varepsilon^{-1})\) over \(T\le n\), while the additive term contributes only \(n\eta_n=O(\varepsilon^{-1})\) under the assumption \(n\ge100\varepsilon^{-10d}\). A dyadic decomposition in 23 gives \[\sum_{T\ge n} \exp\bk*{-\Omega\bk*{\varepsilon T^{\frac{1}{d}}}} =O\mleft( n\sum_{\ell\ge0} 2^\ell \exp\bk*{-\Omega\bk*{\varepsilon(2^\ell n)^{\frac{1}{d}}}} \mright) =O(\varepsilon^{-1}),\] again using \(n\ge100\varepsilon^{-10d}\). Therefore \(\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)}=O(\varepsilon^{-1})\). Jensen’s inequality then gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)^{\frac{1}{d}}} \le \mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)}^{\frac{1}{d}} =O(\varepsilon^{-\frac{1}{d}}),\] completing the proof. ◻

Proof of [thm:rh-expected-bounds]. Fix a key \(x\) in the standard Robin Hood smoothed degree-\(d\) probing hash table with \(n\) slots at load \(1-\varepsilon\). 6 gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)}=O(\varepsilon^{-1}) \qquad\text{and}\qquad \mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)^{\frac{1}{d}}}=O(\varepsilon^{-\frac{1}{d}}),\] which is the first of the two claimed bounds. For the probe-complexity bound, [lem:displacement-and-probe-complexity] gives \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{pc}(x)} =\Theta\bk*{\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)^{\frac{1}{d}}}+1} =O(\varepsilon^{-\frac{1}{d}}),\] as desired. ◻

Proof. We view the slots cyclically and orient every edge from a slot to its successor in the probing direction. For an edge \(e_i\) from slot \(i\) to slot \(i+1\), let \(C_i\) be the number of keys whose displacement path crosses \(e_i\), counted with multiplicity if a key wraps around more than once. Then \[\label{eq:total-displacement-edge-crossings} \sum_x \mathrm{disp}(x)=\sum_{i=1}^{n} C_i.\tag{24}\]

Fix an integer \(L\le n/2\), and let \(I_i\) be the cyclic interval of \(L\) slots ending at \(i\). Let \(X_{i,L}\) be the number of keys whose home slots lie in \(I_i\). At most \(L\) of these keys can be stored in physical slots of \(I_i\). Every remaining key must leave \(I_i\) in the probing direction and therefore must cross the edge \(e_i\) at least once. Hence, deterministically, \[\label{eq:edge-overload-lower-bound} C_i\ge \bk*{X_{i,L}-L}_+.\tag{25}\]

Take \(L=\floor*{\varepsilon^{-2}}\); the assumption on \(n\) ensures \(L\le n/2\). For a fixed edge \(i\), the random variable \(X_{i,L}\) has binomial distribution \[X_{i,L}\sim \operatorname{Binomial}\bk*{(1-\varepsilon)n,\frac{L}{n}}.\] Its mean is \((1-\varepsilon)L=L-\Theta(\varepsilon^{-1})\) and its standard deviation is \(\Theta(\varepsilon^{-1})\). Consequently, \[\label{eq:binomial-overload-positive-part} \mathop{\mathrm{\mathbb{E}}}\Bk*{\bk*{X_{i,L}-L}_+}=\Omega(\varepsilon^{-1}).\tag{26}\] For completeness, when \(\varepsilon\) is below a sufficiently small constant, a uniform Berry–Esseen bound gives constants \(c_1,c_2>0\) such that \[\mathop{\mathrm{Pr}}\Bk*{X_{i,L}\ge L+c_1\varepsilon^{-1}}\ge c_2.\] This implies 26 . When \(\varepsilon\) is bounded away from zero, both \(L\) and \(\varepsilon^{-1}\) are bounded by constants, and the same conclusion follows by decreasing the implicit constant.

Combining 24 , 25 , and 26 , \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\sum_x\mathrm{disp}(x)} =\sum_{i=1}^{n}\mathop{\mathrm{\mathbb{E}}}\Bk*{C_i} \ge n\cdot\Omega(\varepsilon^{-1}) =\Omega(n\varepsilon^{-1}),\] as claimed. ◻

Proof. Let \(m=(1-\varepsilon)n\) be the number of keys, ignoring harmless rounding. By exchangeability of the keys and 13, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{disp}(x)} =\frac{1}{m}\mathop{\mathrm{\mathbb{E}}}\Bk*{\sum_y\mathrm{disp}(y)} =\Omega(\varepsilon^{-1}).\] Write \(D=\mathrm{disp}(x)\) and let \(c>0\) be such that \(\mathop{\mathrm{\mathbb{E}}}\Bk*{D}\ge c\varepsilon^{-1}\). The tail estimates in the proof of 6 imply that, for a sufficiently large constant \(k_0=k_0(d)\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D>k_0\varepsilon^{-1}}}} \le \frac{c}{2}\varepsilon^{-1}.\] Consequently, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D\le k_0\varepsilon^{-1}}}} \ge \frac{c}{2}\varepsilon^{-1}.\] On the event \(D\le k_0\varepsilon^{-1}\), \[D^{\frac{1}{d}} \ge \frac{D}{(k_0\varepsilon^{-1})^{\frac{d-1}{d}}}.\] Therefore \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D^{\frac{1}{d}}} \ge \mathop{\mathrm{\mathbb{E}}}\Bk*{D^{\frac{1}{d}}\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D\le k_0\varepsilon^{-1}}}} =\Omega(\varepsilon^{-\frac{1}{d}}),\] as desired. By [lem:displacement-and-probe-complexity], this also gives \(\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{pc}(x)}=\Omega(\varepsilon^{-1/d})\). ◻

Proof. As above, exchangeability and 13 give \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D}=\Omega(\varepsilon^{-1}), \qquad D\mathrel{\vcenter{:}}=\mathrm{disp}(x).\] Let \(c>0\) satisfy \(\mathop{\mathrm{\mathbb{E}}}\Bk*{D}\ge c\varepsilon^{-1}\). We claim that, for a sufficiently large constant \(k_0=k_0(d,\alpha)\), \[\label{eq:anti-rh-truncated-displacement} \mathop{\mathrm{\mathbb{E}}}\Bk*{D\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D>k_0\varepsilon^{-2}}}} \le \frac{c}{2}\varepsilon^{-1}.\tag{27}\] Indeed, the tail bounds 5 and 6 from [thm:anti-robinhood-expected-bounds], applied to a uniformly random key, imply that for \(k_0\varepsilon^{-2}\le K\le n/10\), \[\mathop{\mathrm{Pr}}[D>K] \le C\varepsilon\mleft(e^{-c_1\varepsilon^2K}+e^{-c_1\varepsilon K^{1/d}}\mright).\] Summing this tail from \(k_0\varepsilon^{-2}\) to \(n/10\) contributes at most \[C'\varepsilon^{-1}e^{-c_2k_0^{1/d}}.\] It remains to control displacements beyond \(n/10\). By 5 at \(K=n/10\), the theorem’s lower bound on \(\varepsilon\) makes \(\mathop{\mathrm{Pr}}[D>n/10]\) smaller than \(n^{-M}\) for any prescribed constant \(M\), after increasing \(C_{\mathrm{fin}}\). Let \(\tau_n\) be the completion threshold from [lem:polynomial-completion]. Its offsets visit every residue modulo \(n\), so the probe prefix of every key contains every physical slot by true displacement \(\tau_n\). The table has an empty slot, and hence \(D\le\tau_n\). By definition, \(\tau_n\) is independent of the keys and of the offset variables whose sampling intervals intersect \([0,n/10]\), which determine the event \(\{D>n/10\}\). Consequently, \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D>n/10}}} \le \mathop{\mathrm{\mathbb{E}}}\Bk*{\tau_n}\mathop{\mathrm{Pr}}[D>n/10] =n^{O(1)}n^{-M} =o(\varepsilon^{-1}),\] where the final equality follows by choosing \(M\) sufficiently large. Choosing \(k_0\) large now proves 27 .

It follows that \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D\le k_0\varepsilon^{-2}}}} \ge \frac{c}{2}\varepsilon^{-1}.\] On this event, \[D^{1/d} \ge \frac{D}{(k_0\varepsilon^{-2})^{(d-1)/d}}.\] Taking expectations yields \[\mathop{\mathrm{\mathbb{E}}}\Bk*{D^{1/d}} =\Omega\mleft( \frac{\varepsilon^{-1}}{(\varepsilon^{-2})^{(d-1)/d}} \mright) =\Omega\bk*{\varepsilon^{1-2/d}}.\] For random fixed-offset degree-\(d\) probing, \(\mathrm{pc}(x)=\Theta(D^{1/d}+1)\) pointwise, so this is also the required query-time lower bound. ◻

Proof. We first analyze a Poissonized table in which the numbers of keys at the \(n\) home positions are independent \(\operatorname{Poisson}(1-\varepsilon)\) random variables. Condition throughout on the shared offset sequence.

Anti-Robin Hood insertion has an exact synchronous description. In round \(j\), every home position that still has an unplaced key tries the slot \(a+r_j\). If the slot is free, one key from that home is placed; otherwise no key from that home is placed in this round. Indeed, proposals from earlier rounds have smaller displacement and hence higher anti-Robin Hood priority. Moreover, for fixed \(j\), the map \(a\mapsto a+r_j\pmod n\) is a permutation, so distinct home positions never compete in the same round.

Let \(U_j\) be the number of keys that remain unplaced after the first \(j\) probes, and let \(q_j\) be the expected fraction of slots that are free at that time. If \(N\) denotes the total number of Poisson keys, then exactly \(N-U_j\) slots are occupied. Therefore \[\label{eq:anti-rh-free-backlog-relation} \mathop{\mathrm{\mathbb{E}}}\Bk*{U_j}=n(q_j-\varepsilon).\tag{28}\] After the home probe, a slot is free exactly when no key hashes to it, and hence \[\label{eq:anti-rh-free-initial} q_1=e^{-(1-\varepsilon)}.\tag{29}\] In particular, \(1/3<q_1<2/3\) for \(0<\varepsilon\le1/2\).

We next derive a recurrence that no longer contains \(\varepsilon\). Fix a home position \(a\). As functions of the independent Poisson home counts, the event that \(a\) still has an unplaced key after \(j\) probes is increasing, whereas the event that \(a+r_{j+1}\) is free is decreasing. These monotonicities follow by coupling two inputs that differ by added keys: after every round, each home has at least as many unplaced keys in the larger input, and every slot occupied in the smaller input is also occupied in the larger input. With these monotonicities, we can apply the following Harris’s inequality.

By 6 and translation invariance, the expected number of placements in round \(j+1\) is at most \[\begin{align} & \mathop{\mathrm{\mathbb{E}}}\Bk*{\sum_{a\in[n]} \mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{a\text{ has an unplaced key after }j\text{ probes}}} \cdot \mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{a+r_{j+1}\text{ is free after }j\text{ probes}}}}\\ \le{}&\sum_{a\in[n]} \mathop{\mathrm{Pr}}\Bk*{a\text{ has an unplaced key after }j\text{ probes}} \mathop{\mathrm{Pr}}\Bk*{a+r_{j+1}\text{ is free after }j\text{ probes}}\\ \le{}& \mathop{\mathrm{\mathbb{E}}}\Bk*{U_j}\,q_j =n(q_j-\varepsilon)q_j \le nq_j^2. \end{align}\] Every placement fills one free slot, so \[\label{eq:anti-rh-free-recurrence} q_{j+1}\ge q_j-q_j^2=q_j(1-q_j).\tag{30}\]

The sequence \((q_j)\) is nonincreasing, and hence \(q_j<2/3\) by 29 . Taking reciprocals in 30 gives \[\frac{1}{q_{j+1}} \le \frac{1}{q_j(1-q_j)} = \frac{1}{q_j}+\frac{1}{1-q_j} \le \frac{1}{q_j}+3.\] Since \(1/q_1<3\), induction yields \[\label{eq:anti-rh-harmonic-free-tail} q_j\ge\frac{1}{3j} \qquad(j\ge1).\tag{31}\] Combining 28 and 31 , for every \(j\le1/(6\varepsilon)\) we obtain \[\label{eq:anti-rh-harmonic-poisson-tail} \mathop{\mathrm{\mathbb{E}}}\Bk*{U_j} =n(q_j-\varepsilon) \ge\frac{n}{6j}.\tag{32}\]

It remains to return to exactly \(m\) keys. Couple the Poissonized and fixed-load tables by taking the first \(N\) and the first \(m\) keys, respectively, from one infinite i.i.d. key sequence. Adding or deleting one key changes \(U_j\) by at most one. Indeed, the round-by-round coupling above shows that adding a key cannot reduce any home backlog and cannot make a previously occupied slot free. Since \(U_j\) equals the number of keys minus the number of occupied slots, its increase is therefore between \(0\) and \(1\). Since \(\mathop{\mathrm{\mathbb{E}}}\Bk*{N}=(1-\varepsilon)n\) and \(\abs{m-(1-\varepsilon)n}<1\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\abs{N-m}}\le\sqrt n+1.\] Therefore, for \(j\le1/(6\varepsilon)\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{U_j^{\mathrm{fix}}} \ge \frac{n}{6j}-\sqrt n-1.\] The theorem’s assumption and \(n\ge2\) imply \[\sqrt n+1\le\varepsilon n.\] Hence, for every integer \(1\le j\le1/(12\varepsilon)\), \[\sqrt n+1 \le \varepsilon n \le \frac{n}{12j},\] and therefore \[\mathop{\mathrm{\mathbb{E}}}\Bk*{U_j^{\mathrm{fix}}} \ge \frac{n}{12j}.\] The \(m\) fixed-load keys are exchangeable, and \(U_j^{\mathrm{fix}}\) counts exactly the keys with probe complexity greater than \(j\). Thus every fixed key \(x\) satisfies \[\mathop{\mathrm{Pr}}\Bk*{\mathrm{pc}(x)>j} =\frac{\mathop{\mathrm{\mathbb{E}}}\Bk*{U_j^{\mathrm{fix}}}}{m} \ge \frac{1}{12j}\] throughout this range, proving the stated tail. Finally, the tail-sum formula and the trivial bound \(\mathrm{pc}(x)\ge1\) give \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{pc}(x)} \ge 1+\frac{1}{12} \sum_{j=1}^{\floor*{1/(12\varepsilon)}}\frac{1}{j} =\Omega\bk*{\log\varepsilon^{-1}}. \qedhere\] ◻

Proof. The parameter range of the corollary implies the hypothesis of 5, whose expectation conclusion gives the claim directly. ◻

Proof of [lem:polynomial-completion]. We first consider random fixed-offset degree-\(d\) probing. Let \[m=\lceil Cn\log(2n)\rceil,\] where \(C\) is a sufficiently large constant, and partition the probe indices beginning at \(m\) into consecutive blocks of length \(m\). Consider a block \[J,J+1,\ldots,J+m-1, \qquad J\ge m.\] The sampling intervals in this block have comparable lengths, namely \(|I_J|=\Theta(J^{d-1})\), with this quantity interpreted as a constant when \(d=1\).

Fix a residue class \(a\) modulo \(n\). The union of the sampling intervals in the block has length \(\Theta(J^{d-1}m)\) and hence contains \(\Theta(J^{d-1}m/n)\) integer offsets congruent to \(a\) modulo \(n\). Each such integer belongs to one sampling interval, which selects it with probability \(\Omega(J^{1-d})\). Therefore \[\sum_{j=J}^{J+m-1}\mathop{\mathrm{Pr}}[r_j\equiv a\pmod n] \ge c\frac{m}{n} \ge cC\log(2n)\] for a constant \(c=c(d,\alpha)>0\). Independence within the block shows that the probability of missing \(a\) is at most \((2n)^{-cC}\). After a union bound over all residue classes and an appropriate choice of \(C\), every block covers all residues with probability at least \(1/2\), independently of the other blocks.

Let \(G\) be the index of the first successful block. Then \(G\) is stochastically dominated by a geometric random variable of constant mean. By the end of the first successful block, the offsets allowed in the definition of \(\tau_n\) have visited every residue class, and the largest exposed offset is \(O(((G+1)m)^d)\). Therefore \[\tau_n = O(((G+1)m)^d).\] A geometric random variable has a finite \(d\)-th moment, and hence \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\tau_n} = O(m^d) = n^{O(1)}.\] By its definition through indices \(j\ge s_n\), \(\tau_n\) is measurable only with respect to offset variables whose sampling intervals are disjoint from \([0,n/10]\).

Now consider smoothed degree-\(d\) probing for a fixed key \(x\). Choose \[T=\lceil(C'n\log(2n))^d\rceil\] for a sufficiently large constant \(C'\), and partition the offsets above \(T\) into dyadic blocks \([2^\ell T,2^{\ell+1}T)\), \(\ell\ge0\). For any residue class \(a\) modulo \(n\), \[\sum_{\substack{2^\ell T\le k<2^{\ell+1}T\\ k\equiv a\pmod n}}p(k) \ge c'2^{\ell/d}\frac{T^{1/d}}{n} = \Omega\Bk*{2^{\ell/d}C'\log(2n)}.\] Thus the probability that the \(\ell\)-th block fails to contain an activated representative of every residue class is at most \[\exp\Bk*{-\Omega(2^{\ell/d}\log(2n))}.\] Let \(L\) be the first successful dyadic block. The blocks use disjoint activation bits, and the preceding estimate implies \[\mathop{\mathrm{\mathbb{E}}}\Bk*{2^L} \le 1+ \sum_{\ell\ge0}2^{\ell+1}\mathop{\mathrm{Pr}}[L>\ell] = O(1).\] Since \(T>n\) and \(\tau_n(x)\le2^{L+1}T\), \[\mathop{\mathrm{\mathbb{E}}}\Bk*{\tau_n(x)} = O(T) = n^{O(1)}.\] Taking a common exponent \(B\) large enough proves both assertions. ◻

Proof of [lem:history-independence-of-rh-and-arh]. We use key-proposing deferred acceptance in the sense of Gale and Shapley [71], expressed in the matching-with-contracts framework of Hatfield and Milgrom [72]. Fix the set of keys, their base hashes, their realized probe sequences, and their tie-breaking values. For every occurrence of a true offset \(k\) in the probe sequence of a key \(x\), introduce a contract \((x,k)\) with the physical slot \[h(x)+k \pmod n.\] Contracts \((x,k)\) and \((x,k')\) remain distinct even if \(k\equiv k'\pmod n\). Each key ranks its contracts in probe order, equivalently by increasing true offset. Each slot ranks the contracts pointing to it according to the insertion rule: Robin Hood ordering prefers larger true offset, anti-Robin Hood ordering prefers smaller true offset, and equal offsets are ordered by the fixed tie-breaking values. All preference orders are therefore strict.

Run key-proposing deferred acceptance. An unmatched key proposes its next contract; the receiving slot keeps the contract it prefers and rejects the other one, if any; and a rejected key continues with its next contract. This is exactly the insertion-and-kicking algorithm. Choosing an insertion order merely determines when each key makes its first proposal and hence selects an asynchronous proposal schedule for the same deferred-acceptance instance.

We use the standard schedule-independence property of deferred acceptance with finite strict preference lists. Its proof is the usual Gale–Shapley proof, which has two steps. First, the rejection lemma says that no rejected contract belongs to a stable matching. Indeed, let \((x,s)\) be the earliest rejected contract in a purported stable matching. Slot \(s\) rejects it for a key \(y\) that it prefers to \(x\). Since \(y\) has proposed to \(s\), it has already been rejected from every contract it prefers to \(s\); by minimality, its purported match is not one of them. Thus \(y\) prefers \(s\) to its match, and \((y,s)\) blocks the purported matching. Second, a terminating fair schedule is stable, and each key has been rejected from every contract it prefers to its terminal one. The rejection lemma makes the terminal matching key-optimal; strict preferences make it unique. Hence the outcome is schedule independent.

Now compare two completed insertion executions. For each key, truncate its contract list after the largest index proposed in either execution. Both executions are terminating fair schedules for this finite instance, so both produce its unique key-optimal matching. They therefore accept the same contract \((x,k)\) for every key. Since a contract records both the physical slot and the true offset, the two executions have the same table state and displacements. Hence the table is history independent. ◻

Proof of [lem:displacement-and-probe-complexity]. By history independence, we may insert \(x\) last. Let \(D=\mathrm{disp}(x)\), and let \(A_{x,r}\) indicate that offset \(r\) is activated for \(x\), with \(A_{x,0}=1\). The probe complexity is exactly the number of activated offsets up to and including the final displacement, so \[\label{eq:pc-from-displacement} \mathrm{pc}(x)=\sum_{r\ge 0} A_{x,r}\mathop{\mathrm{\mathbb{1}}}\nolimits_{\BK*{D\ge r}}.\tag{33}\] Fix \(r\ge1\), condition on the table formed by the other keys, and expose all randomness of \(x\) except \(A_{x,r}\). Whether \(x\) advances past every offset smaller than \(r\) is decided before the bit \(A_{x,r}\) is examined, and this event is precisely \(\{D\ge r\}\). Hence \(A_{x,r}\) is independent of \(\{D\ge r\}\). Taking expectations in 33 and using \(p(0)=1\) gives \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\Bk*{\mathrm{pc}(x)} &= \sum_{r\ge 0} p(r)\mathop{\mathrm{Pr}}\Bk*{D\ge r} \\ &= \mathop{\mathrm{\mathbb{E}}}\Bk*{\sum_{r=0}^{D}p(r)}. \end{align}\] Since \(p(r)=\Theta(r^{-(d-1)/d})\) for \(r\ge1\), the claimed identity follows by substituting \(m=D\) into \[\sum_{r=0}^{m}p(r)=\Theta\bk*{m^{1/d}+1} \qquad\text{for every integer }m\ge0. \qedhere\] ◻