Christopher D'Urso chris@durso.org
9/25/2002 updated 8/21/04
Perfect Shuffling
Figure 1.
Scatter plot of perfect shuffling of decks of size 4 to
1,570,814. When two or more data points settle on the same pixel
the hue value is bumped up from red(1) to violet(100 or more).
This plot was generated with a simple Java Program takes only a few
moments to draw reading the points from a precalculated file.
My interest with perfect shuffling started with a simple observation
that the standard poker deck containing 52 cards will come back to its
or
original order if riffle shuffled precisely interleaving the two 26
haves 8 times. The same deck with 54 cards, 2 additional cards
thrown
into it (e.g. jokers) and precisely shuffled will now require 52 times
to obtain its starting order. I have heard that mathematician
Perci
Diaconis (Cornell/Stanford) could perform the riffle shuffle perfectly
the
necessary 8 times as a parlor trick. Just as a side note, I
understand that allowing for the
natural error to occur, the determined proper minimum number of times
that
a deck should best shuffled to effectively randomize a standard deck of
52 cards 7-8 times.
Perfect shuffling is the simple interleaving of a evenly split deck
where the top and bottom cards stay in their respective first and last
places.
Preserving the position first and last cards positions
[0,1,2, ... , n/2, n/2+1, ... ,n-2, n-1] -> [0, n/2, 1, n/2 + 1, 2 ..., n-2, n/2-1, n-1], for any n even number of cards in a deck
one may write one shuffle, for k
{k in top half, k = 0.. n/2}to position 2*k,
otherwise one may write one shuffle of position k {in bottom half, k = n/2 + 1 .. n-1} to position 2*k - (n - 1),
this may be rewritten for any k
{0, 1, 2, ... n - 2 }, NOTE:
we already know that n - 1
is not moving.
k shuffles to (2*k) % (n-1), where the operator '%' means
the
remainder of a division by (e.g. 8%3 = 2).
So shuffling any one card k
though any sized deck n
any number of times s can be
achieved by simply
iterating k <- 2*k % ( n-1 ), s times. Call this the S() function.
for any given valid k, its
neighbor if also valid k + 1
may be likewise mapped through one shuffle k+1 <- 2*(k+1)%(n-1), and so k+2, k+3, k+i,
if all valid can be mapped by one shuffle k+i
<- 2*(k + i)%(n-1),
Now consider the physical reality of shuffling. The result of
the aforementioned shuffle for k
and k+i, where both valid positions and
i NOT equal to 0, can
never be the same for constant n
and s.
In other other words it would be impossible to have a n card deck shuffled
s times and have the card that
was initially 2nd and the card that was
initially 5th both simultaneously residing in the 27th
place!, or
Sx(k) != Sx(k+i),
for any x, and any valid k and k+i
As k and i can both be picked arbitrarily,
it can be said that any k
determines all other positions as determined by i for any given number of
shuffles. Therefore when any given k gets back to its original
position
then all other cards are back to their respective original
positions. This means
you need only keep track of 1 card in the deck when you are
perfect
shuffling. When that card gets back to its initial position all
other
cards would of as well, and
there can be no more than n-2
shuffles for a deck with n
cards, for there are no more than n-2
unique postions, the first and the last being stationary. This
special number n-2 means that
every card has visited every position before they get back to their
initial position, aka maximal coverage, finally
decks with n =
2,4,8,16..2x are
always back to there original always in x shuffles where x = {2, 3, 4, ...
}, just choose an initial k =
1, and see that Sx(k=1)
-> 1. In other words in a power 2 deck card 1 goes from 1 to 2
to 4 to 8 ... until it wraps directly back to position 1.
On a graphics calculator, plotting n
v. Sx(n) for n e { 4, 6, 8, ... } starts to
produce a graph with lines radiating at ~1/1 and several others.
One would expect this (1/1) line for maximally covered decks
sizes, and the power 2 decks a floor at log2(x),
but there are numerous other lines and stray points I beleive have to
do with primality or factorization.
With a C program determined for Sx() decks of
size 4 to
1,570,814 creating the above graph. Scatter plotting these
points would result in several points settling on the
same pixel. To better plot on a small graph all these data points
another Java plotting program was
created whereby the coalesing data
points were colored to indicate their density (red means one point on a
pixel to violet 100+ points, figure
1).
In contrast Figure 2, was created was created
with the same data file and a simple scatter plot plotting
program. The number of data points was restricted to the number
of pixels available in order to prevent two points falling onto the
same pixel. The truncated
data set used is in Table 1.
Figure 2. Scatter plot of perfect shuffling of
decks of size 4 to 1022. This time the range has been limited so
that only one point may settle on the same pixel. This plot was
generated using the same Java program above with slight modifications.
This graph
could just as well be drawn by Excel or other standard graphing
program.
The full data is in Table 1 .
