Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.