3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you looking for a precise formula or asymptotics/bounds? The former will probably look horrendous (judging from the very easy case $N=2$). For the latter, it may be helpful to specify more precisely how large $N$, $k$, $L$ are relative to each other. $\endgroup$ – Erick Wong Jun 29 '12 at 23:28
  • $\begingroup$ @Erick Wong, absent a precise formula, I'm looking for as tight a lower-bound probability as possible that all strings are unique. I'll add relative size estimates for $N$, $k$, and $L$. $\endgroup$ – W.W. Jun 29 '12 at 23:35
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.