This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 63

Video about shuffling

Due: March 22
Points: 2

Watch this video of Stanford prof. Persi Diaconis on the mathematics of randomizing card orders through shuffling, like we talked about in class: https://youtu.be/AxJubaijQbI

After you watch the video, I have two tasks for you to complete this problem:

  1. In the video he quickly goes through a proof on the expected number of times you have to do the one card at a time "poke" shuffle before the deck is in completely random order. For a standard card deck of size \(n=52\), he says this is roughly 200 pokes.

    Generalize this proof to any deck size \(n\). You probably want to refer to the formula for the sum of a harmonic series: https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Partial_sums I'd like a big-Oh bound of the expected number of "pokes" to reorder a size-\(n\) deck of cards.

  2. The reason Dr. Diaconis was (presumably) asked to do this video is because of a famous paper he co-authored in the 1980s about card shuffling.

    Use your Googling powers to find the name of this paper, and look up the pdf of this original research paper. After reading the paper abstract (the summary at the beginning), tell me something interesting (to you) that the paper goes into but that he doesn't mention in the short video.