I was trying to rigorously/mathematically analyze the runtime of the following algorithm:
while i < n {
b_D = randomly_generate_bit_array_length(D) # simply selects each bit randomly with 1/2 prob of choosing 0 or 1.
if b_n NOT in HashTable[b_D]:
HashTable[b_D] = b_D
i++
}
First I started by thinking what is the probability of two strings matching and realized that the probability is equal to the probability of all bits matching:
$$ Pr[b^1 = b^2] = Pr[\cap^D_{i=1} \{ b^1_i = b^2_i\} ] = \frac{1}{2^D} = 2^{-D}$$
Then I realized that its crucial to know what the probability of a collision happening with something in the hash table if the hash table has $k$ elements (notice that its an equality because there are no intersections with events since all elements in the hash table are assumed to be unique):
$$ Pr[collision] = Pr[\cup^k_{i=1} \{ b^{current} = b^{HashTable}\} ] = k 2^{-D} $$
now the way I would normally proceed to calculate this is by writing the runtime $T(n)$ in terms of indicator random variable or some type or random variable and them compute an expectation over the distribution of coin flips of the algorithm.
$$ \mathbb{E}[T(n)]$$
however, I am having difficulties writing this step. The main issue is that it seems that in principle this algorithm could run forever (with low probability) so its possible that we loop several time in the same iteration trying to find a non colliding binary string. I think this weird unknown repetition is what I am having a hard time including in the summation. Anyone has any suggestion on how to proceed?
I think I just had a realization of maybe how to do this. Define:
$$ X_i = \text{variable indicating if it took i steps to complete} $$
then we can do:
$$ T(n) = \sum^{\infty}_{i=1} i X_i $$
the difference from usual algorithms like this is that the first $n$ terms have to be zero since we need $n$ strings, so we can never take less than $n$ steps since we need $n$ strings.
Now I just need to compute $Pr[X_i]$.