Geometry description of the GSR riffle shuffle model

Question

In 1992 Diaconis and Bayer announced their famous result which is now a well-known folklore: Seven shuffles is enough to randomize a deck of cards.

One of the key ingredients in their proof is that an $a$-shuffle, followed by a $b$-shuffle, is equivalent to a single $ab$-shuffle.

Here an $a$-shuffle is an operation consists of two steps: the first step is called a cut: cut the deck of cards into $a$ packets of size $p_1,p_2,\cdots,p_a$ according to the multinomial distribution $\begin{pmatrix}n\\p_1,p_2,\ldots,p_a\end{pmatrix}/a^n$, here $p_i\geq0$ and $p_1+\cdots+p_a=n$. The second step is called interleave: drop the cards one by one from these packets with probability proportional to their current size. (for more precise explanations, see the paper by Diaconis above or the paper by Mann ) when all cards are dropped, we get a permutation $\pi\in S_n$.

Note that there may be many different pairs (cut,interleave) that result in the same permutation of the deck of the cards. In fact the number of the different pairs (cut, interleave) that result in a given permutation $\pi$ only depends on the number of raising subsequences of $\pi$: Diaconis and Bayer proved that this number is $\begin{pmatrix}n+a-r\\n\end{pmatrix}$, assuming that $\pi$ has $r$ raising subsequnces.

Now we come to the key point: Diaconis found a nice geometry description of the a-shuffle, which enables him to prove his assertion economically. This description goes as follows:

Drop $n$ points into the interval $[0,1]$ independently with the uniform density. Label them from left to right as $x_1<\cdots<x_n$. Now consider the transformation $T(x)=\{ax\}$, the fraction part of $ax$. Set $T(x_i)=y_i$, then the $y_i$'s may not be in order, let's rearrange them as $$y_{\pi(1)}<\cdots<y_{\pi(n)},$$ thus we have got a permutation $\pi$. The permutation $\pi$ must contains no more than $a$ raising subsequences, and every permutation $\pi\in S_n$ with no more than $a$ raising subsequnces can be gotten in this way, with the probability given by $$\frac{\begin{pmatrix}n+a-r\\n\end{pmatrix}}{a^n}.$$

Here Diaconis said this procedure is equivalent to an a-shuffle, but he did not spent much words why they are indeed the same thing. I found it very boring to do the computations in detail to verify these assertions. I thought there maybe some "inner connections" which I have missed.

So can anyone explain me why the geometry description is correct? Thanks.

Answer 1

Consider the following construction: choose $n$ points from $[0,1]$ uniformly and independently, then for each point, choose at random one of its $a$ preimages under $T$ (which amounts to a choice one of the intervals $[0,\frac{1}{a})$, $[\frac{1}{a},\frac{2}{a})$, etc). This gives a permutation distributed as the inverse $a$-shuffling (since for each card we have chosen a pack independently and within each pack the order is preserved).

On the other hand, after this transformation, the points are distributed uniformly and independently in $[0,1]$, and applying $T$ brings us to the initial configuration. Hence, $T$ is distributed as $a$-shuffling.