# Two-Way Linear Probing Revisited
## 5 Upper Bounds
### Two-Way Post-Linear Probing: WalkFirst Algorithm
Thus, a witness tree of height \(h\) exists if and only if there is a key that is inserted into a block of load of at least \(h+\xi-1\) before the insertion. Before we embark on the proof of Theorem 4.1, we highlight three important facts whose proofs are provided in Appendix A. First, we bound the probability that a valid witness tree occurs. Lemma 1: _Let \(D\) denote the event that the number of blocks in \(\textsc{WalkFirst}(n,m)\) with load of at least \(\xi\), after termination, is at most \(n/(a\beta_{3}\xi)\), 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 }|\ A_{k-1}\cap D\}\leq \frac{4^{w}\beta_{3}^{w+b-1}}{(a\xi)^{w-b+1}n^{w+b-1}}.\]  
The next lemma asserts that the event \(D\) in Lemma 1 is most likely to be true, for sufficiently large \(\xi<\beta_{3}\). Lemma 2: _Let \(\alpha\), \(\delta\), and \(\beta_{3}\) be as defined in Theorem 4.1. 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\)._  
Lemma 3 addresses a simple but crucial fact. If the height of a witness tree \(W_{k}(h)\in\mathcal{W}_{k}(h,w,b)\) is \(h\geq 2\), then the number of white nodes \(w\) is at least two, (namely, the root and its left child); but what can we say about \(b\), the number of black nodes? Lemma 3: _In any witness tree \(W_{k}(h)\in\mathcal{W}_{k}(h,w,b)\), if \(h\geq 2\) and \(w\leq 2^{h-\eta}\), where \(\eta\geq 1\), then the number \(b\) of black nodes is \(\geq\eta\), i.e., \(\mathbb{I}_{\left[\{b\geq\eta\}\cup[a>2^{h-\eta}]\right]}=1\)._  
Proof of Theorem 4.1. Recall that \(A_{k}\), for \(k\in\llbracket m\rrbracket\), is the event that after the insertion of \(k\) keys (i.e., at time \(k\)), none of the blocks is fully loaded. Notice that \(A_{m}\subseteq A_{m-1}\subseteq\cdots\subseteq A_{1}\), and the event \(A_{\beta_{3}-1}\) is deterministically true. We shall show that \(\mathbb{P}\{A_{m}^{c}\}=o(1)\). Let \(D\) denote the event that the number of blocks with load of at least \(\xi\), after termination, is at most \(n/(a\beta_{3}\xi)\), for some constant \(a>1\) to be decided later. Observe that  
\[\mathbb{P}\{A_{m}^{c}\} \leq \mathbb{P}\{D^{c}\}+\mathbb{P}\{A_{m}^{c}\,|\,D\}\] \[\leq \mathbb{P}\{D^{c}\}+\mathbb{P}\{A_{m}^{c}\,|\,A_{m-1}\cap D\}+ \mathbb{P}\{A_{m-1}^{c}\,|\,D\}\] \[\vdots\] \[\leq \mathbb{P}\{D^{c}\}+\sum_{k=\beta_{3}}^{m}\mathbb{P}\{A_{k}^{c} \,|\,A_{k-1}\cap D\}.\]  
Lemma 2 reveals that \(\mathbb{P}\{D^{c}\}=o(1)\), and hence, we only need to demonstrate that \(p_{k}:=\mathbb{P}\{A_{k}^{c}\,|\,A_{k-1}\cap D\}=o(1/n)\), for \(k=\beta_{3},\ldots,m\). We do that by using the witness tree argument. Let \(h,\xi,\eta\in[2,\infty)\) be some integers to be picked later such that \(h+\xi\leq\beta_{3}\). If after the insertion of \(k\) keys, there is a block with load of at least \(h+\xi\), then a witness tree \(W_{k}(h)\) (with block nodes representing blocks with load of at least \(\xi\)) must have occurred. Recall that the number of white nodes \(w\) in any witness tree \(W_{k}(h)\) is at least two. Using Lemmas 1 and 3, we see that  
\[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil.\]0 \[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil.\]1 \[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil.\]2 \[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil.\]3 \[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil.\]4  
Note that we disallow \(b=w+1\), because any witness tree has at least one block node. We split the sum over \(w\leq 2^{h-\eta}\), and \(w>2^{h-\eta}\).