MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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