Physically Simulating the Name Game

 

            We end with descriptions of ways to physically simulate the Name Game.  We can modify the biased coin model to use transparent spinners and a variety of bases to get data about cycle lengths in random permutations.  For the first spin, we use a base labeled from 1 to , with equal regions for each label.  Suppose, for example, that  and we spin a 4.  Then, since each length from 1 to 6 is equally probable for the length of the next cycle, we spin next using a base labeled from 1 to 6 to determine its length, and so on. 

            We can also use a deck of cards labeled from 1 to , letting the first cycle end with card , which has equal probability of being anywhere in the deck.  The next cycle then ends with the greatest card still in the deck after card  has been removed, etc.  This is a slight variation of a simulation described in Golomb and Gaal (1992).

            We can also use cards to gather data on fixed points by counting from 1 to , while dealing out the cards and recording the number of times the number spoken matches the number on the card.  This is a simulation of the problemes des rencontres or the “problem of the matches,” which was one of the first historical appearances of fixed points of permutations.  The main problem with using cards to simulate is making sure that they are sufficiently shuffled to be random (see, for example, Morris, 1998).

 

Golomb, S.W. and Gaal, P.  “On the Number of Permutations of  Objects with Greatest Cycle Length .” Probabilistic Methods in Discrete Mathematics : Proceedings of the Fourth International Petrozavodsk Conference, Petrozavodsk, Russia, May 12-15, 1992.  Utrecht, the Netherlands: VSP, 1997.

Morris, S. Brent.  Magic Tricks, Card Shuffling, and Dynamic Computer Memories.  Washington DC: Mathematical Association of America, 1998.

 

Note: This is a supplement to, Borkovitz, Debra, “The Name Game: Exploring Random Permutations.”  Mathematics Teacher 98 (October 2005).

 

PDF Version                            Back to Articles                        Home