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

Your Answer


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

Browse other questions tagged or ask your own question.