Report

* A Reiteration of “Shuffling Cards and Stopping Times” * “Repeated shuffling is best treated as random walk on the permutation group Sn. For later applications, we treat an arbitrary finite group G. Give some scheme for randomly picking elements of G, let Q(g) be the probability that g is picked… the random variables X0, X1… are the random walk on G with step distribution Q.” * Random Walk: A path that consists of random steps- where those steps follow some probability distribution. * Shuffling Cards and Stopping Times, pg 334 What is Random? • Definition: • The probability of all permutations is equal (in other words, the likelihood of the permutations follows the uniform distribution.) • Mathematical way of expressing: • dQ(k) = lQk- UI→0 as k →∞ • Variation distance • This is where the variation distance is zero Top in at random Take the top card and put it back into a different place in the deck at random. For an example lets look at a deck of 3 cards and the probabilities of the resulting shuffle. π Q(π) 123 0.333 132 0.000 213 0.333 231 0.333 312 0.000 321 0.000 Example Extended Q1(π) Q2(π) Q3(π) Q4(π) Q5(π) Q6(π) Q7(π) Q8(π) Q9(π) Q10(π ) 123 0.333 0.222 0.185 0.173 0.169 0.167 0.167 0.167 0.167 0.167 132 0.000 0.111 0.148 0.160 0.165 0.166 0.166 0.167 0.167 0.167 213 0.333 0.222 0.185 0.173 0.169 0.167 0.167 0.167 0.167 0.167 231 0.333 0.222 0.185 0.173 0.169 0.167 0.167 0.167 0.167 0.167 312 0.000 0.111 0.148 0.160 0.165 0.166 0.166 0.167 0.167 0.167 321 0.000 0.111 0.148 0.160 0.165 0.166 0.166 0.167 0.167 0.167 Tables courtesy of David Austin http://www.ams.org/samplings/feature-column/fcarc-shuffle Bridges = Segues? When to stop? • Stopping time • A rule for when to stop shuffling • Define as P(T>k) • Which says: The probability that the number of shuffles to randomize the deck is greater than the number of shuffles that have been performed. • We want P(T>k) to be close to zero Stopping Time k • ∥R −U∥≤P(T>k) Stopping Time • “The main purpose of this paper is to show how upper bounds on d(k)… can be obtained using the notion of strong uniform times.” • Where d(k) is the difference between the probability of a given permutation and the uniform distribution. • Approximately 11-12 riffle shuffles to randomize • They note that post hoc adjustments led to another model that found that 7 is a sufficient number to for a deck of 52 cards to be randomized. Last Comments • Inverse sorting • They consider it to be a “lovely new idea” which is important to how they developed the model. • It allows them to use models similar to ones of coin flips • Inverse sorting is meant to simulate cutting the deck • Steps • Values of 0 and 1 are assigned to the cards in the deck according to a binomial distribution. • Cards of the same value are grouped together, maintaining their order within the group • The group of zeroes are placed on top of the group of 1’s Questions • How is random defined by Aldous and Diaconis? • How is this related to variation distance? • How many riffle shuffles are necessary for a deck to be randomized- according to Aldous and Diaconis? • What is a stopping time? • What is a random walk?