Card Shuffling as a

Dynamical System
Dr. Russell Herman
Department of Mathematics and Statistics
University of North Carolina at Wilmington

How does a magician know that the eighth card in a deck of 50 cards returns to it
original position after only three perfect shuffles?  How many perfect shuffles will
return a full deck of cards to their original order? What is a "perfect" shuffle?  
Introduction
 History of the Faro Shuffle
 The Perfect Shuffle
 Mathematical Models of Perfect Shuffles
 Dynamical Systems – The Logistic Model
 Features of Dynamical Systems
 Shuffling as a Dynamical System
A Bit of History
History of the Faro Shuffle
 Cards
 Western Culture - 14th Century
 Jokers – 1860’s
 Pips – 1890’s added numbers
 First Card tricks by gamblers
 Origins of Perfect Shuffles not known
 Game of Faro
 18th Century France
 Named after face card
 Popular 1803-1900’s in the West
The Game of Faro
 Decks shuffled and rules are simple
 (fâr´O) [for Pharaoh, from an old French playing card design],
gambling game played with a standard pack of 52 cards. First played in
France and England, faro was especially popular in U.S. gambling
houses in the 19th Century. Players bet against a banker (dealer), who
draws two cards–one that wins and another that loses–from the deck
(or from a dealing box) to complete a turn. Bets–on which card will
win or lose– are placed on each turn, paying 1:1 odds. Columbia
Encyclopedia, Sixth Edition. 2001
 Players bet on 13 cards
 Lose Slowly!
 Copper Tokens – bet card to lose
 “Coppering”, “Copper a Bet”
 Analysis – De Moivre, Euler, …
The Game

Wichita Faro
http://www.gleeson.us/faro/ http://www.bcvc.net/faro/rules.htm
Perfect (Faro or Weave) Shuffle
Problem:
 Divide 52 cards into 2 equal piles
 Shuffle by interlacing cards
 Keep top card fixed (Out Shuffle)
 8 shuffles => original order

What is a typical Riffle shuffle?

What is a typical Faro shuffle?
See!

Period 2 @ 18 and 35!

History of Faro Shuffle
 1726 – Warning in book for first time
 1847 – J H Green – Stripper (tapered) Cards
 1860 – Better description of shuffle
 1894 – How to perform
 Koschitz’s
Manual of Useful Information
 Maskelyne’s Sharps and Flats – 1st Illustration
 1915 – Innis – Order for 52 Cards
 1948 – Levy – O(p) for odd deck, cycles
 1957 – Elmsley – Coined In/Out - shuffles
Mathematical Models
A Model for Card Shuffling
 Label the positions 0-51
 Then
 0->0 and 26 ->1
 1->2 and 27 ->3  2x 0  x  25
f ( x)  
 2->4 and 28 ->5 2 x  51 26  x  51
 … in general?

 Ignoring card 51: f(x) = 2x mod 51

 Recall Congruences:
 2x mod 51 = remainder upon division by 51
The Order of a Shuffle
 Minimum integer k such that 2 k x = x mod 51
for all x in {0,1,…,51}

 True for x = 1 !

 Minimum integer k such that 2 k - 1= 0 mod 51

 Thus, 51 divides 2 k - 1
 k= 6, 2 k - 1 = 63 = 3(21)
 k= 7, 2 k - 1 = 127
 k= 8, 2 k - 1 = 255 = 5(51)
Generalization to n cards
The Out Shuffle
The In Shuffle
Representations for n Cards
0  p  n 1
 In Shuffles
mod n  1, n even
I ( p)  2 p  1 
 mod n, n odd
 Out Shuffles
mod n  1, n even and 0  p  n  1
O( p)  2 p 
 mod n, n odd and 0  p  n  1
Order of Shuffles
 8 Out Shuffles for 52 Cards
 In General?
o (O,2n-1) = o (O,2n)
 o (I,2n-1) = o (O,2n)
 => o (O,2n-1) = o (I,2n-1)
o (I,2n-2) = o (O,2n)
 Therefore, only need o (O,2n)
o (O,2n) = Order for 2n Cards
 One Shuffle: O(p) = 2p mod (2n-1), 0<p<N-1

 2 shuffles:
O2(p) = 2 O(p) mod (2n-1) = 22 p mod (2n-1)

 k shuffles: Ok(p) = 2kp mod (2n-1)

 Order: o (O,2n) = smallest k for 0 < p < 2n such that

Ok(p) = p mod (2n-1)

 Or, 2k = 1 mod (2n-1) => (2n – 1) | (2k – 1)

The Orders of Perfect
n
Shuffles
o(O,n) o(I,n) n o(O,n) o(I,n)
2 1 2 13 12 12
3 2 2 14 12 4
4 2 4 15 4 4
5 4 4 16 4 8
6 4 3 17 8 8
7 3 3 18 8 18
8 3 6 50 21 8
9 6 6 51 8 8
10 6 10 52 8 52
11 10 10 53 52 52
12 10 12 54 52 20

Demonstration
Another Model for 2n Cards
 Label positions with rationals

 Out Shuffle 0 1 2 2n  1
0 , , , ,  1.
2n  1 2 n  1 2n  1 2n  1
 Example: Card 10 of 52: x = 9/51
1 2 2n
 In Shuffle ,
2n  1 2 n  1
, ,
2n  1
.

 Example: Card 10 of 52: x = 9/51

Shuffle Types
Domain Endpoints Shuffle Deck Size
 0 1 N -1
 , ,…,  0,1 out N = 2n
N -1 N -1 N -1
1 2 N
 , ,…,  1 in N = 2n - 1
N N N
0 1 N -1
 , ,…,  0 out N = 2n - 1
 N N N 
 1 2 N 
 , ,…,  none in N = 2n
N +1 N +1 N +1

All denominators are odd numbers.

Doubling Function
 1
 2 x, 0 x
2
S ( x)   .
2 x  1, 1  x  1
 2
Discrete Dynamical Systems
 First Order System: xn+1 = f (xn)
 Orbits: {x0, x1, … }
 Fixed Points
 Periodic Orbits
 Stability and Bifurcation
 Chaos !!!!
The Logistic Map
 Discrete Population Model
 Pn+1 = a Pn
 Pn+1 = a2 Pn-1
 Pn+1 = an P0
 a>1 => exponential growth!
 Competition
 Pn+1= a Pn - b Pn2
 xn = (a/b)Pn, r=a/b =>
 xn+1 = r xn(1 - xn), xn[0,1] and r[0,4]
Example r=2.1

Sample orbit for r=2.1 and x0 = 0.5

Example r=3.5
Example r=3.56
Example r=3.568
Example r=4.0
Iterations

More Iterations
Fixed Points
f(x*) = x*
 x*= r x*(1-x*)
 => 0 = x*(1-r (1-x*) )
 => x* = 0 or x* = 1 – 1/r

 Logistic Map - Cobwebs

Periodic Orbits for f(x)=rx(1-x)
 Period 2
 x1= r x0(1- x0) and x2 = r x1(1- x1) = x0
 Or, f 2 (x0) = x0

 Period k
- smallest k
such that f k (x*) = x*
 Periodic Cobwebs
Stability
 Fixed Points
 |f’(x*)| <1
 Periodic Orbits
 |f’(x0)| |f’(x1)| … |f’(xn)| < 1
 Bifurcations
Bifurcations
r1 = 3.0
r2 = 3.449490 ...
r3 = 3.544090 ...
r4 = 3.564407 ...
r5 = 3.568759 ...
r6 = 3.569692 ...
r7 = 3.569891 ...
r8 = 3.569934 ...
Itineraries: Symbolic Dynamics
For G (x) = 4x ( 1-x )
Assign Left “L” and Right “R”
 Example: x0 = 1/3
 x0 = 1/3 => “L”
 x1 = 8/9 => “LR”
 x2 = 32/81 => “LRL”
 x3 = … => “LRL …”
 Example: x0 = ¼
 { ¼, ¾, ¾, …}=>” LRRRR…”
Periodic Orbits
“LRLRLR …”, “RLRRLRRLRRL …”
Shuffling as a Dynamical System
 1
 2 x, 0x
2
S ( x)   .
2 x  1, 1  x  1
 2

S(x) vs S4(x)
Demonstration
Iterations for 8 Cards
S3(x) vs S2(x)
S3(x) vs S2(x)

How can we study periodic orbits for S(x)?

Binary Representations
 Binary Representation
 0.10112=1(2-1)+0(2-2)+1(2-3)+1(2-4) =
 1/2 + 1/8 + 1/16 = 10/16 = 5/8
 xn+1 = S(xn), given x0
 Represent xn’s in binary: x0 = 0.101101
 Then, x1 = 2 x0 – 1 = 1.01101 – 1 = 0.01101
 Note: S shifts binary representations!
 Repeating Decimals
 S(0.101101101101…) = 0.011011011011…
 S(0.011011011011…) = 0.110110110110…
Periodic Orbits
 Period 2
 S(0.10101010…) = 0.01010101…
 S(0.01010101…) = 0.10101010…
 0.102, 0.012, 0.112 = ?
 Period 3
 0.1002, 0.0102, 0.0012 = ?
 0.1102, 0.0112, 0.1012 = ?
 Maple Computations
Card Shuffling Examples
 8 Cards – All orbits are period 3
{1/7, 2/7, 4/7} and {3/7, 6/7, 5/7} and {0/7, 7/7}
 52 Cards – Period 2
1/3 = ?/51 and 2/3 = ?/51
 50 Cards – Period 3 Orbit (Cycle)
1/7 = ?/49
 Recall:
 Period 2 - {1/3, 2/3}
 Period 3 – {1/7, 2/7, 4/7} and {3/7, 6/7, 5/7}
 Out Shuffles – i/(N-1) for (i+1) st card
Finding Specific t-Cycles
 Period k: 0.000 … 0001
 2-t + (2-t)2 + (2-t) 3 + … = 2-t /(1- 2-t )
 Or, 0.000 … 0001 = 1/(2t -1)
 Examples
 Period 2: 1/3
 Period 3: 1/7
 In general: Select Shuffle Type
 Rationals of form i/r => (2t –1) | r
 Example r = 3(7) = 21
 Out Shuffle for 22 or 21 cards
 In Shuffle for 20 or 21 cards Demonstration
Other Topics
 Cards
 Alternate In/Out Shuffles
 k- handed Perfect Shuffles
 Random Shuffles – Diaconis, et al
 “Imperfect” Perfect Shuffles
 Nonlinear Dynamical Systems
 Discrete (Difference Equations)
 Systems in the Plane and Higher Dimensions
 Continuous Dynamical Systems (ODES)
 Integrability
 Nonlinear Oscillations
 MAT 463/563
 Fractals
 Chaos
Summary

 History of the Faro Shuffle

 The Perfect Shuffle – How to do it!
 Mathematical Models of Perfect Shuffles
 Dynamical Systems – The Logistic Model
 Features of Dynamical Systems
 Symbolic Dynamics
 Shuffling as a Dynamical System
References
 K.T. Alligood, T.D. Sauer, J.A. Yorke, Chaos, An
Introduction to Dynamical Systems, Springer,
1996.
 S.B. Morris, Magic Tricks, Card Shuffling and
Dynamic Computer Memories, MAA, 1998
 D.J. Scully, Perfect Shuffles Through Dynamical
Systems, Mathematics Magazine, 77, 2004
Websites
 http://i-p-c-s.org/history.html
 http://jducoeur.org/game-hist/seaan-cardhist.html
 http://www.usplayingcard.com/gamerules/briefhistory.html
 http://bcvc.net/faro/
 http://www.gleeson.us/faro/

Thank you !