I've been reading this article 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$.

  • $\begingroup$ Immediately prior to the passage you state the author notes that the given probability is not exactly correct "because of the remote possibility that, at a given shuffle, there are no cutpoints at all or exactly one cutpoint", but that this becomes vanishingly unlikely as $n$ increases. $\endgroup$ – Kevin P. Costello May 12 '16 at 20:39
  • $\begingroup$ @KevinP.Costello I don't quite see how that leads to the stated formula, though. In the $n = 3, k= 1$ case that I mentioned, if we ignore the possibility of a single cutpoint, we still get $p^2(1-p)=\frac 1 8$, and not $\frac 1 6$. $\endgroup$ – Jack M May 12 '16 at 22:10
  • $\begingroup$ @JackM --- the stated formula is an asymptotic large-$n$ result, I don't think you can hope for an exact agreement at finite $n$, see the derivation below. $\endgroup$ – Carlo Beenakker May 13 '16 at 8:09

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


and hence



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.