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

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 math.stackexchange.com.

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