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.