-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.idyll
143 lines (105 loc) · 7.46 KB
/
index.idyll
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
[meta
title:"The Math of Card Shuffling"
description:"Riffling from factory order to complete randomness."
shareImageUrl:"https://fredhohman.com/card-shuffling/static/images/share.png"
shareImageWidth:"1600"
shareImageHeight:"800" /]
[Header
title:"The Math of Card Shuffling"
subtitle:"Riffling from factory order to complete randomness."
author:"Fred Hohman"
authorLink:"http://fredhohman.com" /]
[Analytics google:"UA-42146340-1" /]
You've probably seen a few ways to shuffle a deck of cards.
Sometimes the deck is split in half and the halves are switched.
Sometimes the deck is *[smooshed](https://big.assets.huffingtonpost.com/smooshing.gif)* until it's all mixed up.
But most of the time, a deck of cards is shuffled using a *riffle*.
// [aside]
// Smooshing a deck is arguably more fun.
// [image style:`{width: '100%'}` src:"static/images/smoosh.gif" /]
// [/aside]
[image style:`{width: '100%'}` src:"static/images/riffle.gif" /]
Here's a question: *how many times do you have to riffle a deck of cards before it is completely shuffled?*
// [br/]
It's a tricky one, but math has us covered: [you need seven riffles](https://en.wikipedia.org/wiki/Shuffling#Riffle).
[aside]
We can calculate the number of orderings of a deck of cards using the notion of a [permutation](https://en.wikipedia.org/wiki/Permutation).
To find all arrangements of 52 cards in a deck, we compute **52!**, which happens to be a [really big number](http://www.wolframalpha.com/input/?i=52!).
[/aside]
Riffle seven times and you'll have a sufficiently random ordering of cards, an ordering that has likely [never existed before](http://www.murderousmaths.co.uk/cardperms.htm).
In other words, it's unlikely you'll ever shuffle two decks the same.
The card shuffling result appears in a [Numberphile video from 2015](https://www.youtube.com/watch?v=AxJubaijQbI), along with a number of other card shuffling facts.
Here's another problem posed in that video: what if instead of a standard riffle using a deck roughly split in half, you were to only riffle *1 card at a time*?
[aside]
[This paper](https://projecteuclid.org/download/pdf_1/euclid.aoap/1177005705) shows a number of other interesting card shuffling results in all their gory details.
[/aside]
That is, using a standard deck of 52 cards, in one hand hold 51 cards and in the other hold the remaining single card.
Now riffle these together.
This is equivalent to taking one card and placing it at random inside of the deck.
**So here's the question:**
[br/]
*How many single riffles do you have to do in order to have a completely shuffled deck?*
## Theorem
You could simulate this in a short program, which we will do towards the end, but first we can solve for the number of riffles explicitly.
Consider an ordered deck of cards.
[Without loss of generality](https://en.wikipedia.org/wiki/Without_loss_of_generality), let's say the suits are in the following order: [card suit:"S"/], [card suit:"C"/], [card suit:"H"/], [card suit:"D"/].
So our ordered deck looks like this.
[cardVis static:"True"/]
The bottom suit is [card suit:"D"/], which means the bottom card of our deck is the King of Diamonds ([card number:"K" suit:"D"/]).
Now perform the following iteration:
>Place the top card of the deck randomly inside the deck
This means taking the [card number:"A" suit:"S"/] and placing it randomly somewhere in the deck.
The top card then becomes [card number:"2" suit:"S"/].
If this procedure is repeated, eventually the top card will be placed at the very bottom of the deck, shifting the [card number:"K" suit:"D"/] to the penultimate position.
Since every riffled card has a [Equation]\frac{1}{52}[/Equation] chance of moving to any new position in the deck, that means, on average, after about 52 top card riffles, the top card will become the new bottom card.
[aside]
**Note:** notice the [card number:"K" suit:"D"/] can only rise in the deck.
There are two cases:
1. The top card is placed above the [card number:"K" suit:"D"/], therefore its position does not change.
2. The top card is placed underneath the [card number:"K" suit:"D"/], therefore it rises one position closer to the top.
[/aside]
Once the [card number:"K" suit:"D"/] moves up one position, upon subsequent riffles there are now two spots for the new top card to be placed underneath it.
That means there is now a [Equation]\frac{1}{52}+\frac{1}{52}=\frac{2}{52}[/Equation] chance of a riffled card going underneath the [card number:"K" suit:"D"/].
Continuing this procedure, the original bottom card, the [card number:"K" suit:"D"/], will eventually rise to the top of the deck and be riffled.
Once this happens, the deck is randomly shuffled: the order we're left with is equally as likely as any other order.
So, how many single card riffles does this take?
Recall each time a card is placed underneath the [card number:"K" suit:"D"/], our chances of placing another card increases by [Equation]\frac{1}{52}[/Equation].
We can calculate the number of riffles this would take.
[Equation display:true]
\sum_{i=1}^{52} \frac{52}{i} = \frac{52}{1} + \frac{52}{2} + \frac{52}{3} + ... + \frac{52}{52} \approx 236
[/Equation]
On average, 236 single card riffles will randomly shuffle a deck of cards.
## Let's Riffle
Equations are great, but let's visualize this!
Below is the same ordered deck of cards from before, except the [card number:"K" suit:"D"/] has been highlighted red so we can follow its journey to the top of the deck.
Click the **Riffle** button to move the top card somewhere else in the deck randomly.
Did you see where it went? Click again.
Click a bunch more really fast.
Now I could tell you to keep clicking until the highlighted [card number:"K" suit:"D"/] rises to the top, but as we have already shown, that would take about 236 clicks.
Instead, click the **Riffle (x10)** button to riffle 10 times.
Keep riffling until the [card number:"K" suit:"D"/] moves to the top.
[var name:"iter" value:0 /]
[var name:"points" value:`[{x:0, y:52}]` /]
[var name:"endPoints" value:`[]` /]
[aside]
You have riffled **[Display value:iter format:"d" /]** times.
[br/]
[button onClick:`if(points[points.length-1].y !== 1){iter++}`]Riffle[/button]
[multiRiffle iter:iter points:points ]Riffle (x10)[/multiRiffle]
[/aside]
[cardVis iterVar:iter points:points /]
Here is a chart of the [card number:"K" suit:"D"/]'s position in the deck for each riffle.
Notice how it takes many riffles to move the [card number:"K" suit:"D"/] up just a few positions, but once the [card number:"K" suit:"D"/] starts rising towards the top of the deck, it accelerates.
[aside]
Once the [card number:"K" suit:"D"/] is the top card, click the **Clear** button to try again.
[button className:"clear" onClick:`endPoints.push([{iter:iter, position:-1}, {iter:iter, position:3}]); iter=-1; points=[{x:0, y:52}]; iter++;`]Clear[/button]
[/aside]
[positionChart iterVal:iter points:points endPoints:endPoints /]
On average, the [card number:"K" suit:"D"/] will reach the top position somewhere around 236 riffles.
Since this is the *average* result, there is a chance your first shuffled deck of cards took less riffles (or many more!).
To try again, click the **Clear** button and get riffling.
// We can simulate this multiple times and verify that on average it takes 236 times.
### Acknowledgements
* This article was created using [a href:"https://idyll-lang.org/"]Idyll[/a].
* Shoutout to [a href:"https://twitter.com/mathisonian"]@mathisonian[/a] for help and feedback.
* The source code is available on [a href:"https://github.com/fredhohman/card-shuffling/"]Github[/a].