Probability of a matching rotation Consider a uniformly selected random vector $V= (v_1,v_2,\dots, v_n)$ where $v_i \in \{0,1\}$.  Let us define $V_1 = (v_1,v_2,\dots, v_n)$, $V_2 = (v_n, v_1,v_2,\dots, v_{n-1})$, $V_3 = (v_{n-1}, v_n, v_1,v_2,\dots,v_{n-2})$ and so on.
I am trying to work out the probability that there exists $i \ne j$ such that $V_i = V_j$.
This can happen when for example $V=(0,1,0,1)$, but I am stuck in how to work this probability out.  
I worked it out for some small examples.
n = 1. Prob = 0
n = 2. Prob = 1/2
n = 3. Prob = 1/4
n = 4. Prob = 1/4
n = 5. Prob = 1/16
n = 6. Prob = 5/32
n = 7. Prob = 1/64
n = 8. Prob = 1/16  
n = 9. Prob = 1/64
n = 10.Prob = 17/512
n = 11.Prob = 1/1024

If $n$ is prime then only the all $1$ or all $0$ vector have any matching rotation so at least that case is easy.  
I would be very interested in an upper bound if it's too hard to find an exact answer.
 A: Not sure if this helps, but let's put a group theory spin on your problem.  Let's instead call $V_0 = V = (v_1, \ldots, v_n)$, $V_1 = (v_n, v_1, \ldots, v_{n-1})$, etc.  Then we have an action of $\mathbb{Z}/n\mathbb{Z}$ on this vector: an element $k \in \mathbb{Z}/n\mathbb{Z}$ acts by a cyclic shift of $k$ spots.  Your question then becomes whether there is an element of $\mathbb{Z}/n\mathbb{Z}$ that stabilizes one of the $V_i$.  Actually, I think it reduces to whether or not an there is an element stabilizing $V$.  I'm not sure where to go from there, but maybe the orbit-stabilizer theorem would help...
Another approach:  Let's consider how many vectors there are such that $V_1 = V$.  It's not too hard to see that such a vector has all entries equal, i.e., the first entry determines the rest.  Thus there are only 2.  Similarly, if $V_2 = V$, then the first 2 entries determine the rest.  Let $a_k$ be the number of length $n$ vectors $V$ such that $V_k = V$.  Then by the previous argument, $a_k = k$ for $k \leq n/2$.  I'm not sure what to do about $k > n/2$...  It seems like it should be symmetrical, since we're either shifting left or right...  Anyway, if you can determine the $a_k$, the inclusion-exclusion principle would give you the answer.
A: Finally got it.  Call the desired probability $p_n$ for a vector of length $n$.  For $k < n$ we can only have $V_k = V$ if $k \mid n$.  (Well, that's not quite true since if $V = (0,0,0)$, then $V_2 = V$, but it is if we insist that $k$ be minimum.)
If $V_k = V$, then $V$ is determined by its first $k$ entries, so there are $2^k$ choices.  However this leads to overcounting.  For instance, if $V = (0,1,0,1,0,1,0,1)$, then $V_2 = V$ and $V_4 = V$, so it gets counted twice.  At each stage, we only want to count the vectors that are "primitive," i.e., vectors such that $V_k = V$ and $V_\ell \neq V$ for all $\ell < k$.  To correct the overcounting, we must subtract off the number of primitive vectors corresponding to $d$ for each $d \mid k$ with $d < k$.  Denoting the number primitive vectors corresponding to $k$ by $b_k$, then $\displaystyle b_k = 2^k - \sum_{\substack{d \mid k \\ d < k}} b_d$.  Then $2^k = \sum_{d \mid k} b_d$, so $b_k = \sum_{d \mid k} \mu(d) 2^{k/d}$ by Möbius inversion, where $\mu$ is the Möbius function.  Then the total number of length $n$ vectors with rotational symmetry is
$$
\sum_{\substack{k \mid n \\ k < n}} \sum_{d \mid k} \mu(d) 2^{k/d}
$$
so
$$
p_n = \frac{1}{2^n} \sum_{\substack{k \mid n \\ k < n}} \sum_{d \mid k} \mu(d) 2^{k/d} \, .
$$
I wrote a script in SAGE to compute some examples, and this formula agrees with your results!
