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.

  • 2
    $\begingroup$ 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}$. $\endgroup$ – Anthony Quas Apr 25 '13 at 21:18
  • $\begingroup$ @AnthonyQuas I would be happy with bounds that applied for large $n$ as well. $\endgroup$ – user32786 Apr 26 '13 at 16:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.