2020-09-28 Math 3600 Kruskal

979 days ago by calkin

Examining the math of the Kruskal Count card trick.


How many permutations of a deck of cards are there?

Around $10^{68}$.  Call this number $N$.
len(factorial(52).digits()) 
        
68
68

Suppose that 10 billion people all shuffle decks of cards 100 times a day for 100 years.

That's $10^{10} \times 100 \times 365 \times 100$ shuffles.

What is the probability that there will be two exactly the same shuffles?

List all $s=10^{17}$ish shuffles. What is the probability that the second shuffle 

is different from the second shuffle?   $(1- \frac{1}{N})$.

Given that we've chosen the first two shuffles, what is the probability that the

third shuffle is different from the first two?  $(1- \frac{2}{N})$.

The probability that the first three shuffles are all distinct is $(1- \frac{1}{N})(1- \frac{2}{N})$.

Similarly, the probability that the first $s$ shuffles are distinct is 

\[ \prod_{i=1}^{s-1} \left 1 - \prod{i}{N} \right). \]
10^10*100*365*100 
        
36500000000000000
36500000000000000
len(36500000000000000.digits()) 
        
17
17

This is related to the "Birthday paradox".  If there are $k$ people in a room, the probabilities that their birthdays are all different is equal to $\frac{(365)(364)...(365-k+1)}{365^k}$
(factorial(365)/(factorial(365-23)*365^23)).n() 
        
0.00143645121188342
0.00143645121188342
def f(k): a= factorial(365)/(factorial(365-k)*365^k) return(1-a.n()) 
       
f(23) 
        
0.507297234323985
0.507297234323985
f(22) 
        
0.475695307662550
0.475695307662550
f(17) 
        
0.315007665296561
0.315007665296561
f(27) 
        
0.626859282263242
0.626859282263242

In general, how big is $\frac{N!}{N^k \times (N-k)!}$

Tools we could use: Stirling's approximation to $N!$ might help.

We'll use some facts: $\exp(\log(x))=x$, and $\log(1+\epsilon) \simeq \epsilon -\frac{\epsilon^2}{2} + \dots$
 
       

Friday, September 25, 2020

To estimate $\frac{N!}{N^k (N-k)!}$ for various values of N,k.
def f(N,k): a = factorial(N)/(N^k*factorial(N-k) ) return(a.n()) 
       
f(100,20) 
        
0.130399501820471
0.130399501820471
B=[f(1000,k) for k in srange(201)] 
       
list_plot(B) 
       
plot( exp(-k*(k-1)/2000) ,k,0,200) 
       

So we see that if we have $N$ birthdays in a year, and $k$ people have independently uniformly chosen birthdays, the probability that there is no repeated birthday behaves like $\exp(-\binom{k}{2}/N)$

Back to Kruskal's trick.  We want a function which returns the step count for each card in a deck of 52 cards.  We'll label the cards 0, 1, ... ,51.

One easy way is the following: 
step_count= [1,2,3,4,5,6,7,8,9,10,10,10,10] step_count+=step_count step_count+=step_count print(step_count) 
        
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 10, 10, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 1, 2, 3, 4,
5, 6, 7, 8, 9, 10, 10, 10, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10]

Now we need to construct a random permutation of the list $[0,1,...,51]$.

What we will do is the following: we'll choose the cards in a random order: if we've picked the first $k$ cards already, there are $52-k$ left in the deck.  We'll choose a random number uniformly from $[0, ..., 52-k-1]$, add that card at that position to our list "deal", and remove it from the deck.
N=52 deck = srange(N) deal = [] for k in srange(N): i=ZZ.random_element(0,N-k) deal.append(deck[i]) deck.pop(i) 
        
9
24
0
35
2
19
39
50
18
30
28
20
10
7
38
6
33
51
14
8
25
22
48
32
41
43
44
26
34
21
27
45
36
16
3
11
12
49
42
17
4
29
47
15
40
23
46
37
1
13
5
31
9
24
0
35
2
19
39
50
18
30
28
20
10
7
38
6
33
51
14
8
25
22
48
32
41
43
44
26
34
21
27
45
36
16
3
11
12
49
42
17
4
29
47
15
40
23
46
37
1
13
5
31

Your task: now that you can generate a random deal, play with Kruskal's count.  Pick a random number from 0 to 9, start with the value of the card at that position in the deal, and increment by the number you see.  Repeat until the next card you see would take you past 51.  Output the position you finish at.

We want to ask some questions: for a given random deal, and for each of the first ten cards, how many different finishing positions do we see?

If we choose many random deals, how often is it the case that all finishing positions end up at the same value?

What are we going to have to change about the code if we want different values for N than 52?

We'll need a better form for step_count.  Let's define it as a function of the card position.
def step_count(k): step_list = [1,2,3,4,5,6,7,8,9,10,10,10,10] i=k %13 return(step_list[i]) 
       

What will you need to code?  A function "kruskal(deal, start)", which takes as input a randomly dealt deck, and outputs a final position\.

A function "random_deal(N)" which creates a random deck of $N$ cards.

Code that uses these two functions to explore the questions above.

Create graphs to visualize what you find.

Strong suggestion: do this with a real deck of cards to get a feel for what is going on.
 
       

Questions to explore.  

For 52 cards, how well does Kruskal's trick work?

For higher numbers of cards, how well does Kruskal's trick work?

How big does $N$ have to be so that a deck with $N$ cards almost always works?