## 4 Theoretical Analysis
### Search Failure Probability
#### 4.2.1 Multi-Hash Table  
In inserting an element to a multi-hash table shown in Figure 1a, if four entries in two buckets were already occupied, the element cannot be stored. When \(i-1\) elements were stored, the number of buckets where both entries are occupied is \(\lfloor\frac{i-1}{2}\rfloor\). The \(i^{th}\) element cannot be inserted when each of the two hash indexes of the \(i^{th}\) element is mapped to one of the \(\lfloor\frac{i-1}{2}\rfloor\) occupied buckets. Let \(P_{o_{i}}\) be the probability that an overflow occurs for the \(i^{th}\) element. Then, \(P_{o_{i}}\) has the upper bound as follows.  
\[P_{o_{i}}\leq\left(\frac{\lfloor\frac{i-1}{2}\rfloor}{B_{m}}\right)^{2} \tag{11}\]  
Let \(P_{m}\) be the probability that an element cannot be stored when \(n\) elements are inserted in a multi-hash table. Then, from Label (11), \(P_{m}\) is derived as follows.  
\[P_{m}=\frac{1}{n}\sum_{i=1}^{n}P_{o_{i}}\leq\frac{1}{n}\sum_{i=1}^{n}\left( \frac{\lfloor\frac{i-1}{2}\rfloor}{B_{m}}\right)^{2} \tag{12}\]  
Assuming that \(n\) is even,\[P_{m} \leq \frac{1}{n}\sum_{i=1}^{n}\Big{(}\frac{\lfloor\frac{i-1}{2}\rfloor}{B _{m}}\Big{)}^{2} \tag{13}\] \[= \frac{1}{n{B_{m}}^{2}}\Big{(}0^{2}+0^{2}+1^{2}+1^{2}+\cdots+(\frac {n-2}{2})^{2}+(\frac{n-2}{2})^{2}\Big{)}\] \[= \frac{2}{n{B_{m}}^{2}}\sum_{j=1}^{\frac{n-2}{2}}j^{2}.\]  
As \(B_{m}=\frac{n}{2\alpha}\) in a multi-hash table, and assuming that \(n\) is very large, Label (13) can be formulated as follows,  
\[P_{m} \leq \frac{2}{n{B_{m}}^{2}}\sum_{j=1}^{\frac{n-2}{2}}j^{2}=\frac{(n-2) (n-1)}{12{B_{m}}^{2}} \tag{14}\] \[= \frac{(n-2)(n-1)}{12(\frac{n}{2\alpha})^{2}}=\frac{\alpha^{2}(n^ {2}-3n+2)}{3n^{2}}\] \[\approx \frac{\alpha^{2}}{3}\]  
where \(\alpha\) is the load factor of a multi-hash table. When \(n\) is odd, the same result is obtained.  
Let \(P(F_{m})\) represent the _false negative_ probability of a multi-hash table. It can be formulated as  
\[P(F_{m})=P(S)P(F_{m}|S)+P(S^{c})P(F_{m}|S^{c}) \tag{15}\]  
where \(P(S)\) and \(P(S^{c})\) represent the probability that input \(y\) is included in \(S\) and \(S^{c}\), respectively, and \(U=S\cup S^{c}\) and \(S\cap S^{c}=\emptyset\). For \(3n\) inputs, \(P(S)=\frac{n}{3n}=\frac{1}{3}\) and \(P(S^{c})=\frac{2n}{3n}=\frac{2}{3}\). Among \(n\) elements in \(S\), _false negatives_ occur for the elements that could not be stored, and \(P(F_{m}|S^{c})=0\) as any element in \(S^{c}\) does not produce false negatives. Therefore, \(P(F_{m})\) has the following upper bound.  
\[P(F_{m})=P(S)P(F_{m}|S)=\frac{1}{3}P_{m}\leq\frac{\alpha^{2}}{9} \tag{16}\]  
Labels (14) and (16) hold true when \(\alpha\leq 1\). In case of \(\alpha>1\), the number of elements is more than the number of entries in a hash table (i.e., \(n>2B_{m}\)). Assuming that no empty entry exists in a hash table when the number of programmed elements is \(2B_{m}\), the \(i^{th}\) element cannot be inserted in the table for \(2B_{m}<i\leq n\). In other words, in calculating \(P_{m}\) for \(\alpha>1\), the probability that the \(i^{th}\) element cannot be inserted is 1, which means that the collision unavoidably occurs. Thus, for \(\alpha>1\), \(P_{m}\) is derived as follows.  
\[P_{m} \leq \frac{1}{n}\Big{(}\frac{1}{{B_{m}}^{2}}\cdot\big{(}0^{2}+0^{2}+1^ {2}+1^{2}+\cdots+(\frac{2B_{m}-2}{2})^{2}+(\frac{2B_{m}-2}{2})^{2}\big{)}+(n-2 B_{m})\Big{)} \tag{17}\] \[= \frac{1}{n}\Big{(}\frac{2}{{B_{m}}^{2}}\sum_{j=1}^{B_{m}-1}j^{2} +(n-2B_{m})\Big{)}\] \[\approx 1-\frac{2}{3\alpha}\]  
Therefore, \(P(F_{m})\) for \(\alpha>1\) has the following upper bound.  
\[P(F_{m})=P(S)P(F_{m}|S)=\frac{1}{3}P_{m}\leq\frac{1}{3}\Big{(}1-\frac{2}{3 \alpha}\Big{)} \tag{18}\]