# Two-Way Linear Probing Revisited
## Appendix A Lemmas Needed for Theorem 10  
For completeness, we prove the lemmas used in the proof of Theorem 10. Lemma 1: _Let \(D\) denote the event that the number of blocks in WalkFirst\((n,m)\) with load of at least \(\xi\), after termination, is at most \(n/\left(a\beta_{3}\xi\right)\), for some constant \(a>0\). For \(k\in\llbracket m\rrbracket\), let \(A_{k}\) be the event that after the insertion of \(k\) keys, none of the blocks is fully loaded. Then for any positive integers \(h,w\) and \(k\geq h+\xi\), and a non-negative integer \(b\leq w\), we have_  
\[\sup_{W_{k}(h)\in\mathcal{W}_{k}(h,w,b)}\mathbb{P}\{W_{k}(h)\text{ occurs }|\text{ }A_{k-1}\cap D\}\leq\frac{4^{w}P_{3}^{a \Rightarrow b-1}}{(a\xi)^{w-b+1}n^{w+b-1}}.\]  
Proof. : Notice first that given \(A_{k-1}\), the probability that any fixed key in the set \(\llbracket k\rrbracket\) chooses a certain block is at most \(2\beta_{3}/n\). Let \(W_{k}(h)\in\mathcal{W}_{k}(h,w,b)\) be a fixed witness tree. We compute the probability that \(W_{k}(h)\) occurs given that \(A_{k-1}\) is true, by looking at each node in bfs order. Suppose that we are at an internal node, say \(u\), in \(W_{k}(h)\). We would like to find the conditional probability that a certain child of node \(u\) is exactly as indicated in the witness tree, given that \(A_{k-1}\) is true, and everything is revealed except those nodes that precede \(u\) in the bfs order. This depends on the type of the child. If the child is white or black, the conditional probability is not more than \(2\beta_{3}/n\). This is because each key refers to the unique block that contains it, and moreover, the initial hashing cells of all keys are independent. Multiplying just these conditional probabilities yields \((2\beta_{3}/n)^{w+b-1}\), as there are \(w+b-1\) edges in the witness tree that have a white or black nodes as their lower endpoint. On the other hand, if the child is a block node, the conditional probability is at most \(2/(a\xi)\). This is because a block node corresponds to a block with load of at least \(\xi\), and there are at most \(n/(a\beta_{3}\xi)\) such blocks each of which is chosen with probability of at most \(2\beta_{3}/n\). Since there are \(w-b+1\) block nodes, the result follows plainly by multiplying all the conditional probabilities. To prove Lemma 2, we need to recall the following binomial tail inequality [96]: for \(p\in(0,1)\), and any positive integers \(r\), and \(t\geq\eta rp\), for some \(\eta>1\), we have  
\[\mathbb{P}\{\text{binomial}(r,p)\geq t\}\leq\left(\varphi\Big{(}\frac{t}{rp} \Big{)}\right)^{t}\leq(\varphi(\eta))^{t},\]  
where \(\varphi(x)=x^{-1}e^{1-1/x}\), which is decreasing on \((1,\infty)\). Notice that \(\varphi(x)<1\), for any \(x>1\), because \(1/x=(1-z)<e^{-z}=e^{1/x-1}\), for some \(z\in(0,1)\). Lemma 2: _Let \(\alpha\), \(\delta\), and \(\beta_{3}\) be as defined in Theorem 10. Let \(N\) be the number of blocks with load of at least \(\xi\) upon termination of algorithm WalkFirst\((n,m)\). If \(\xi\geq\delta\beta_{3}\), then \(\mathbb{P}\{N\geq n/(a\beta_{3}\xi)\}=o(1)\), for any constant \(a>0\)._  
Proof. : Fix \(\xi\geq\delta\beta_{3}\). Let \(B\) denote the last block in the hash table, i.e., \(B\) consists of the cells \(n-\beta_{3},\ldots,n-1\). Let \(L\) be the load of \(B\) after termination. Since the loads of the blocks are identically distributed, we have  
\[\mathbb{E}[\,N\,]=\frac{n}{\beta_{3}}\mathbb{P}\{L\geq\xi\}.\]  
Let \(S\) be the set of the consecutively occupied cells, after termination, that occur between the first empty cell to the left of the block \(B\) and the cell \(n-\beta_{3}\); see Figure 1.  
We say that a key is born in a set of cells \(A\) if at least one of its two initial hashing cells belong to \(A\). For convenience, we write \(\
u(A)\) to denote the number of keys that are born in \(A\). Obviously, \(\
u(A)\) is \(\text{binomial}(m,2|A|/n)\). Since the cell adjacent to the left boundary of \(S\) is empty, all the keys that are inserted in \(S\) are actually born in \(S\).