4
$\begingroup$

I pick a set of random strings $S$ of length $L$ over an $P$-letter alphabet. These strings are 'random' in the sense that every character is chosen with uniform random probability over the characters in the alphabet (each character would have a probability of $\frac{1}{P}$ of being chosen).

Let $H(k)$ be the union of $S$ and the set of strings within Hamming distance $k$ of any string in $S$. What are the tightest known bounds for the size of $H(k)$?

We could, for example, generate an upper-bound by assuming that the sets of strings within a Hamming distance $k$ of each element in $S$ are disjoint (and there are similarly obvious lower-bounds), but can we do any better? I would also be happy with some good probabilistic bounds, and I'm particularly interested in a small binary or ternary alphabet.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.