Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Imagine I have a set of $N$ binary strings of length $L$, where I generate each string randomly (say, by flipping a coin for each bit). What is the probability that all $N$ strings are at least a Hamming distance $k$ apart?
I would be happy with a good lower bound estimate on the probability that all strings are unique. We can estimate the relative sizes of $N$, $L$, and $k$ as: $N >> L$ (by at least an order of magnitude), $5 \leq L \leq 100$, and $k < L$.
There are $2^L$ binary strings of length $L$. The number of ordered $N$-tuples of distinct strings is $(2^L)!/(2^L-N)!$, so the probability that all are unique is $\dfrac{(2^L)!}{(2^L-N)! 2^{NL}}$. As $M = 2^L \to \infty$ with $N$ fixed, that is asymptotically $$1 - \dfrac{N(N-1)}{2M} + \dfrac{N(N-1)(N-2)(3N-1)}{24M^2} + \ldots$$
The Hamming distance between a pair of random binary strings of length $L$ is a binomial random variable with parameters $L$ and $1/2$. For $k << L$ the probability that this distance is $k$ is ${L \choose k} 2^{-L}$. In $N$ random strings the expected number of unordered pairs with distance $< k$ is $\mu = \dfrac{N(N-1)}{2} \sum_{j=0}^{k-1} {L \choose j} 2^{-L}$. When $\mu$ is small, we should be able to approximate the distribution of the number of such pairs with a Poisson distribution of parameter $\mu$, so the probability that there are no such pairs is approximately $e^{-\mu}$.
If you are only interested in uniqueness, then a precise formula can be given: the probability that $N$ elements randomly chosen from a set of size $K$ are all distinct is $$ \frac{K!}{(K-N)!K^N} = \prod_{n=0}^{N-1}\left(1-\frac{1}{K}n\right), $$ and in your case $K=2^L$. Now suppose that each element has $K'$ neighbors and we want the probability that no two elements are neighbors. When $n$ elements have been selected, at least $K-nK'$ elements are left to select (with the worst case occurring when all the "blocked" neighborhoods are disjoint), so a lower bound on the probability is $$ \frac{K(K-K')(K-2K')\cdots(K-NK'+K')}{K^N} = \prod_{n=0}^{N-1}\left(1-\frac{K'}{K}n\right). $$ In your case $K'$ is the number of strings of length $L$ within a Hamming distance $k$ of a given string, or $\sum_{m=0}^{k}{L\choose{m}}$.
