I've been reading [this article](http://arxiv.org/pdf/math/0501401.pdf) on the overhand shuffle. In it the author uses a simplied mathematical model of the shuffle:



> 
> Pemantle’s model for the overhand shuffle is
>  parameterized by a probability $p \in (0,1)$. The transition rule is the following:
>  Each of the $n − 1$ slots between adjacent cards is, independently of the
>  other slots, declared a cutpoint with probability $p$. This divides in a natural
>  way the deck into subsequences, or packets, of cards. Reverse each of these
>  packets without changing its position relative to the other packets.
> 
> 
> (...)
> 
> 
> To further simplify our calculations, we will to
>  begin with assuming a circular deck convention, that is, regarding the top
>  card and the bottom card as being next to each other. This means that the
>  top packet and the bottom packet may be treated as a single packet (if the
>  slot between that top and the bottom card happens to be a cutpoint).
> 
> 
> 


The author then states without proof that in the case when $p=\frac 1 2$, the probability that any particular card moves $k$ spaces to the right at a single shuffle is $\frac 1 3 (\frac 1 2)^k$. This seems wrong to me. I must not understand the underlying model correctly, because for instance in the case of $3$ cards and $k=1$, I calculate the probability as $p^2(1-p)+p(1-p)^2=\frac 1 4$, and not $\frac 1 6$.



Difficulty with a formula for a probability related to card shuffling
Perhaps its easiest to first ask for the probability $P\_0$ that the card does not move at all ($k=0$). One way to achieve this is to cut immediately below and above that card, with probability $1/2\times 1/2=1/4$. But any symmetric pair of cuts will do, for example you could cut at two cards below and two cards above, with probability $1/4\times 1/4$, or three cards above and three cards below, with probability $2^{-3}\times 2^{-3}$, and so on. Summing the geometric series gives


$$P\_0 = \sum\_{n=1}^\infty \frac{1}{4^n}=\frac{1/4}{1-1/4}=\frac{1}{3}$$


For the general case you first start with a cut just below the card and a second cut $k+1$ cards above, with probability $1/4\times 2^{-k}$. Then extending this symmetrically at both sides and summing the geometric series gives you the additional factor $1/3$, and you arrive at the general formula $P\_k=\frac{1}{3} \times 2^{-k}$.


We are assuming here an infinite set of cards, to sum the geometric series to infinity. For a small number of cards the formula is not exact, as noted by Kevin in a comment.




---


I could try to generalize this to arbitrary cutpoint probability $p\in(0,1)$. Then 


$$P\_0=p^2+p^2(1-p)^2+p^2(1-p)^4=\frac{p^2}{1-(1-p)^2}=\frac{p}{2-p},$$


and hence


$$P\_k=(1-p)^kP\_0=\frac{p(1-p)^k}{2-p}.$$


