Probability a rotation has a small distance to a vector Given two binary vectors $V_1$, $V_2$ of length $\ell$, say that the distance between $V_1$ and $V_2$ is the number of positions in the vectors that don't match. So the distance between $001$ and $101$ is $1$.  We also define rotations of $V$ so that if $V$ is $01011$, for example, the five rotations are $01011$, $10110$, $01101$, $110101$ and $10101$. We can therefore index the rotations from $0$ to $\ell-1$ so that index $i$ refers to rotation $i$ and index $0$ refers to the identity rotation.
If the vector is chosen uniformly at random and we are given an index $i$, how can I compute the probability that $V$ has distance at most $k$ to rotation $i$?  
 A: If you draw a graph with vertex set $\{1,\dots,\ell\}$, joining vertices $j$ and $j'$ if $j'\equiv j+i \pmod \ell$, then it will consist of $\gcd(i,\ell)$ disjoint cycles, each one of length $d:=\ell/\gcd(i,\ell)$.  So, if the random variable $R_i$ is the distance between a random vector and its $i$th rotation,
$$
R_i=J_1+\dots+J_{\gcd(i,\ell)},
$$
where $J_1$, $J_2$, $\dots$ are i.i.d. and each $J_j$ counts the number of transitions, either from $0$ to $1$ or from $1$ to $0$, in a circle of random bits of length $d$.  If you chop the circle at any point, making it a linear string, you will have removed a transition from the circle iff the bits at the start and finish of the string are different, i.e., iff the string had an odd number of transitions.  Therefore, each $J_j$ is distributed in the same way as the number of transitions in a linear string of bits of length $d$, rounded up to an even number:
$$
J_1, \dots, J_{\gcd(i,\ell)} \sim 2\left\lceil\frac{{\rm Bin}(d-1, \frac12)}{2}\right\rceil.
$$
So, there are $K_1$, $K_2$, $\dots$, $K_{\gcd(i,\ell)}$ with
$$
K_j\sim {\rm Bin}(d, \frac12), \qquad |K_j-J_j|\le 1,
$$
and $R_i$ is approximately binomial in the sense that there is a random variable $S=\sum_j K_j$ with
$$
|R_i-S|\le \gcd(i,\ell), \qquad S\sim {\rm Bin}(\ell, \frac12).
$$
This may help to estimate the distribution in the case where $\gcd(i,\ell)$ is small.
