4
$\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$
2
  • $\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, 2012 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, 2012 at 23:35

2 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .