Consider a deck of N cards, labeling each card from top to bottom as 0 to N-1, respectively. We consider a shuffle S acting on the deck as a permutation of the N cards. We will consider N even, although shuffles on odd decks are also quite well defined. The Faro Shuffle (or Perfect Shuffle) is a shuffle where the deck of cards is split perfectly in half and then shuffled so that the cards from each half of the deck are exactly alternating. An Out Shuffle (O) is a Faro shuffle where the top card remains on top and the bottom card remain on the bottom. An In Shuffle (I) is a Faro shuffle where the top card (in the zero place) moves to the one place. Thus, for a deck of N=6 cards we have,
It is easy to see that the card in position p is mapped to positionsO[0 1 2 3 4 5] = [0 3 1 4 2 5]
I[0 1 2 3 4 5] = [3 0 4 1 5 2]
by the Out shuffle and In shuffle, respectively.O(p) = 2p mod(N-1) and I(p) = (2p + 1) mod(N+1)
We denote the Identity permutation (Id) as the proper ordering of cards from 0 to N-1, where for N=6
All the permutations generated by just In shuffles and Out shuffles form the <I> and <O> groups, respectively, where the intersection of <I> and <O> is the Id. The order of the Out shuffle, l(O) = k, can be described as the least k such thatId = [0 1 2 3 4 5].
The order of the In shuffle for N cards, l(I), is simply l(O) for N+1 cards.2k = 1 mod(2n - 1).
The group formed by both In and Out shuffles can be denoted by either <I,O> or <O,I>. The group generated by an Out shuffle followed by an In shuffle is denoted <IO> and the group generated by an In shuffle followed by an Out Shuffle is denoted <OI>, where l(IO) = l(OI). It is important to note that any two of the groups intersect only at the Id. To explain this we must introduce the Perfect Cut (P). A Perfect cut is obtained by splitting the deck of N = 2n cards exactly between the n-1st and nth cards, and then interchanging the deck. Thus, in a deck of N = 6 cards we have,
It is easy to see that an Out shuffle is simply a Perfect cut followed by an In shuffle. Similarly, an In shuffle is simply a Perfect cut followed by an Out shuffle. For a deck of N = 6 cards we have,P[0 1 2 3 4 5] = [3 4 5 0 1 2].
Since O = IP we have <O> = <IP> != <I> except at the Id because the permutation generated by P is not defined in either <I> or <O>. From here it is trivial to show that any two of <I>, <O>, <IO>, <OI> intersect only at the Id permutation. We do not have an equation to express l(IO) and l(OI) mathematically; however, we can obtain l(IO) and l(OI) for decks of N = 2k cards by looking at the dyadic expansion of N under these shuffles. First it is important to note that l(IO) = l(OI).O = IP, IP[0 1 2 3 4 5] = I[3 4 5 0 1 2] = [0 3 1 4 2 5] = O and
I = OP, OP[0 1 2 3 4 5] = O[3 4 5 0 1 2] = [3 0 4 1 5 2] = I.
Let m in N be the smallest number such that (IO)m=Id, where m > 0, and let n in N be the smallest number such that (OI)n=Id, where n > 0. Then m = n.
We have (IO)m = Id and (OI)n = Id, and suppose that m > n, then we have
Id = (IO)m = I (OI)m-1 O = I(OI)m-1 (OI)-n (OI)n O =
= I (OI)m-n-1 (OI)n O = I (OI)m-n-1 O = (IO)m-n = Id.
So m-n < m, but then we have a contradiction because m != 0 is the smallest positive integer such that (IO)m = Id. This can be shown for n > m as well, thus yielding m = n.
To obtain l(OI) for a deck of N = 2k cards, write out the dyadic expansion for an arbitrary card, perform an In shuffle followed by an out shuffle as outlined here, and repeat until the card returns to its original dyadic expansion. l(OI) is the number of repetitions necessary to complete this process. It can be shown that for even k, l(OI) = k and for odd k, l(OI) = 2k.
Dealing with a finite number of cards where N = 2k has now become significantly easier, but what happens when we perform In and Out shuffles on an infinite deck?
Given a deck containing an infinite number of cards, only decks with measure equal to one or zero remain unchanged under a permutation F, where F is in <I,O>.
There is a proof. It will be here soon.