2
$\begingroup$

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]$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The usual way to approach your problem is as follows. When you select the $i$th string, there are $i-1$ previous strings that you have to avoid, so the probability that you generate a new string successfully is $\frac{2^D-(i-1)}{2^D}$. The expected number of strings generated before you generate a new string is thus $\frac{2^D}{2^D-(i-1)}$ – this is just the expectation of a geometrically distributed random variable. Considering all $N$ steps, the overall expectation is $$ \sum_{i=1}^N \frac{2^D}{2^D-(i-1)} = 2^D \sum_{j=0}^{N-1} \frac{1}{2^D-j} \approx 2^D \log \frac{2^D}{2^D-N} \approx \frac{2^D}{2^D-N} N. $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ wow thats slow, is there no algorithm to evaluate a binary function randomly in its domain more efficiently in high dimensions? $\endgroup$
    – Charlie Parker
    Mar 2, 2017 at 4:03
  • $\begingroup$ It's only slow if $N$ is large, and in that case you just run the first $N$ steps of the algorithm for generating a random permutation of length $2^D$. $\endgroup$
    – Yuval Filmus
    Mar 2, 2017 at 4:22
  • $\begingroup$ I think there's something wrong in your last two steps. As $N$ approaches $2^D$, your last expression approaches $2^D\cdot2^D$. I think that's way off. Should be something like $2^D\cdot\log(2^D)$, no? $\endgroup$
    – Stefan Pochmann
    Mar 3, 2017 at 17:24
  • $\begingroup$ This is just an approximation. It's true for small $N$. For $N\approx 2^D$ you recover the correct asymptotics from the first approximation, though the second one is very good in that regime. $\endgroup$
    – Yuval Filmus
    Mar 3, 2017 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.