Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Erick Wong Jun 29 '12 at 23:28
    
@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$. –  W.W. Jun 29 '12 at 23:35

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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