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

Let's say we sample two random binary vectors, one called $A$ of length $n$ and the second called $B$ of infinite length. Now we compute $X_k= \min_{i\in[k]} w(A \oplus B[i,i+n-1])$ where $w$ computes the Hamming weight of a vector and $B[i,i+n-1]$ is the subvector of $B$ of length $n$ starting at position $i$. In other words, we find the minimum Hamming distance between $A$ and the first $k$ overlapping subvectors of $B$.

Is it possible to compute $\mathbb{E}(X_k)$ as a function of $k$ and $n$? We know that $\mathbb{E}(X_1) = n/2$ and for fixed $n$, $\mathbb{E}(X_k) \to 0$ as $k \to 0$.

Cross-posted to

share|cite|improve this question
I doubt that you can give an explicit function. However, I think you can get a very good approximation. For each $\ell$, I would compute $p_\ell$, the probability that a random word has distance $\ell$ from $A$ (i.e. $p_\ell=\binom{n}{\ell}2^{-n}$). You would expect $\mathbb E(X_k)\approx \ell$ where $\ell$ satisfies $p_{\ell}\le 1/k<p_{\ell+1}$. – Anthony Quas Apr 25 '13 at 21:18
@AnthonyQuas I would be happy with bounds that applied for large $n$ as well. – user32786 Apr 26 '13 at 16:21

Your Answer


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