# Two-Way Linear Probing Revisited
## 4 Lower Bounds
### Algorithms That Behave Poorly  
We characterize some of the inefficient two-way linear probing algorithms. Notice that the main mistake in algorithms \(\textsc{ShortSeq}(n,m)\) and \(\textsc{SmallCluster}(n,m)\) is that the keys are allowed to be inserted into empty cells even if these cells are very close to some giant clusters. This leads us to the following theorem whose proof utilizes Lemmas 4-6, stated in Appendix A, regarding negative association of random variables. Throughout, we write \(\textsc{binomial}(n,p)\) to denote a binomial random variable with parameters \(n\in\mathbb{N}\) and \(p\in[0,1]\). **Theorem 7**: _Let \(\alpha\in(0,1)\) be constant. Let \(\mathbf{A}\) be a two-way linear probing algorithm that inserts \(m=\lfloor\,\alpha n\,\rfloor\) keys into \(n\) cells such that, whenever a key chooses an empty and an occupied initial cells, the algorithm inserts the key into the empty one. Then algorithm \(\mathbf{A}\) produces a giant cluster of size \(\Omega(\log n)\), w.h.p._  
Let \(\beta=\lfloor\,b\log_{a}n\,\rfloor\) for some positive constants \(a\) and \(b\) to be defined later, and without loss of generality, assume that \(N:=n/\beta\) is an integer. Suppose that the hash table is divided into \(N\) disjoint blocks, each of size \(\beta\). For \(i\in\llbracket N\rrbracket\), let \(\mathfrak{B}_{i}=\{\beta(i-1)+1,\ldots,\beta i\}\) be the set of cells of the \(i\)-th block, where we consider the cell numbers in a circular fashion. We say that a cell \(j\in\llbracket n\rrbracket\) is \"covered\" if there is a key whose first initial hashing cell is the cell \(j\) and its second initial hashing cell is an occupied cell. A block is _covered_ if all of its cells are covered. Observe that, if a block is covered, then it is fully occupied. Thus, it suffices to show that there would be a covered block, w.h.p. For \(i\in\llbracket N\rrbracket\), let \(Y_{i}\) be the indicator that the \(i\)-th block is covered. The random variables \(Y_{1},\ldots,Y_{N}\) are negatively associated which can been seen as follows. For \(j\in\llbracket n\rrbracket\) and \(t\in\llbracket m\rrbracket\), let \(X_{j}(t)\) be the indicator that the \(j\)-th cell is covered by the \(t\)-th key, and set \(X_{0}(t):=1-\sum_{j=1}^{n}X_{j}(t)\). Notice that the random variable \(X_{0}(t)\) is binary. The zero-one Lemmaasserts that the binary random variables \(X_{0}(t),\ldots,X_{n}(t)\) are negatively associated. However, since the keys choose their initial hashing cells independently, the random variables \(X_{0}(t),\ldots,X_{n}(t)\) are mutually independent from the random variables \(X_{0}(t^{\prime}),\ldots,X_{n}(t^{\prime})\), for any distinct \(t,t^{\prime}\in\llbracket m\rrbracket\). Thus, by Lemma 5, the union \(\cup_{t=1}^{m}\{X_{0}(t),\ldots,X_{n}(t)\}\) is a set of negatively associated random variables. The negative association of the \(Y_{i}\) is assured now by Lemma 6 as they can be written as non-decreasing functions of disjoint subsets of the indicators \(X_{j}(t)\). Since the \(Y_{i}\) are negatively associated and identically distributed, then  
\[\mathbb{P}\{Y_{1}=0,\ldots,Y_{N}=0\}\leq\mathbb{P}\{Y_{1}=0\}\times\cdots \times\mathbb{P}\{Y_{N}=0\}\leq\exp(-N\mathbb{P}\{Y_{1}=1\}).\]  
Thus, we only need to show that \(N\mathbb{P}\{Y_{1}=1\}\) tends to infinity as \(n\) goes to infinity. To bound the last probability, we need to focus on the way the first block \(\mathfrak{B}_{1}=\{1,2,\ldots,\beta\}\) is covered. For \(j\in\llbracket n\rrbracket\), let \(t_{j}\) be the smallest \(t\in\llbracket m\rrbracket\) such that \(X_{j}(t)=1\) (if such exists), and \(m+1\) otherwise. We say that the first block is \"covered in order\" if and only if \(1\leq t_{1}<t_{2}<\cdots<t_{\beta}\leq m\).