Username: Password: [ Lost Password ]  [ Forgot Username ]
 The Magic Cafe Forum Index » » Magical equations » » Kruskal count (0 Likes)

 magiczak Regular user Granada Hills, CA 159 Posts Posted: Jan 22, 2006 12:46 am    0 (Pardon the formatting...it was a PDF originally) a rX iv :m a th .P R /0 11 01 43 v 1 1 3 O c t 2 00 1 TheKruskal Count JeffreyC. Lagarias AT&TLabs- Research FlorhamPark, NJ07932 EricRains AT&TLabs- Research FlorhamPark, NJ07932 Robert J. Vanderbei PrincetonUniversity Princeton, NJ08544 (October12, 2001) Abstract TheKruskalCountisacardtrickinventedbyMartinKruskalinwhichamagician“guesses” acardselectedbyasubjectaccordingtoacertaincountingprocedure. Withhighprobability themagiciancancorrectly“guess”thecard. Thesuccess of thetrickis basedonamathe- matical principlerelatedtocouplingmodelsforMarkovchains. Thispaperanalyzesindetail twosimplifiedvariants of thetrickandestimates theprobabilityof success. Theresultsare comparedwithsimulationdataforseveral variantsof theactual trick. AMSSubject Classification(2000): 60J10(Primary)91A60(Secondary) Keywords: Markovchain, stoppingtime 1. Introduction TheKruskal CountisacardtrickinventedbyMartinD. Kruskal (whoismostwell known for his workonsolitons) whichis describedinFulves andGardner [5] andGardner [6],[7]. Inthis cardtrickamagician“guesses”onecardinadeckof cards whichis determinedby asubjectusingaspecial countingprocedurethat wecall Kruskal’s countingprocedure. The magiciancanwithhighprobabilityidentifythecorrectcard. Thesubject shuffles adeckof cards as manytimes as helikes. He mentallychooses a (secret)numberbetweenoneandten. Kruskal’scountingprocedurethengoesasfollows. The subjectturnsthecardsof thedeckfaceuponeat atime, slowly, andplaces theminapile. Asheturnsupeachcardhedecreaseshissecretnumberbyoneandhecontinuestocountthis 1 way till he reaches zero. The card just turned up at the point when the count reaches zero is called the first key card and its value is called the first key number. Here the value of an Ace is one, face cards are assigned the value five, and all other cards take their numerical value. The sub ject now starts the count over, using the first key number to determine where to stop the count at the second key card. He continues in this fashion, obtaining successive key cards until the deck is exhausted. The last key card encountered, which we call the tapped card, is the card to be “guessed” by the magician. The Kruskal counting procedure for selecting the tapped card depends on the sub ject’s secret number and the ordering of cards in the deck. The ordering is known to the magician because the cards are turned face up, but the sub ject’s secret number is unknown. It appears impossible for the magician to know the sub ject’s secret number. The mathematical basis of the trick is that for most orderings of the deck most secret numbers produce the same tapped card. For any given deck two different secret numbers produce two different sequences of key cards, but if the two sequences ever have a key card in common, then they coincide from that point on, and arrive at the same tapped card. The magician therefore selects his own secret number and carries out the Kruskal counting procedure for it while the sub ject does his own count. The magician’s “guess” is his own tapped card. The Kruskal Count trick succeeds with high probability, but if it fails the magician must fall back on his own wits to entertain the audience. The problem of determining the probability of success of this trick leads to some interesting mathematical questions. We are concerned with the ensemble success probability averaged over all possible orderings of the deck (with the uniform distribution). Our ob jective in this paper is to estimate ensemble success probabilities for mathematical idealizations of such counting procedures. Then we numerically compare the ensemble success probabilities on a 52-card deck with that of the Kruskal Count trick itself. The success probability of the trick depends in part on the magician’s strategy for choosing his own secret number. We show that the magician does best to always choose the first card in the deck as his first key card, i.e. to use secret number 1. The general mathematical problem we consider applies the Kruskal counting procedure to a deck of N labelled cards with each card label a positive integer, in which each card has its label drawn independently from some fixed probability distribution on the positive integers N+. We call such distributions i.i.d. deck distributions; they are specified by the probabilities 2 {πj : j ≥ 1} of a fixed card having value j . We assume that the sub ject chooses an initial secret number from an initial probability distribution on N+ = {1, 2, 3, **Zak** magiczak Regular user Granada Hills, CA 159 Posts Posted: Jan 22, 2006 12:47 am    0 I see that it got cut off. If you are interested, I'll send you the PDF. Zak **Zak** r1238ex Regular user 102 Posts Posted: Jan 22, 2006 08:04 am    0 Ooops!! sleight of eyes... please edit it for eyes friendly text magiczak regards, r1238ex magiczak Regular user Granada Hills, CA 159 Posts Posted: Jan 22, 2006 03:37 pm    0 I'd rather just send the formatted PDF to anyone who is interested. It was my attempt to repost the PDF however, the file upload limit is about 100K too small. I tried to copy and paste the file.....but as you see...it was a failed effort. Zak **Zak** McCritical Regular user 156 Posts Posted: Apr 18, 2006 09:42 pm    0 Quote:The Kruskal Count is a card trick invented by Martin J. Kruskal in which a magician "guesses" a card selected by a subject according to a certain counting procedure. With high probability the magician can correctly "guess" the card. The success of the trick is based on a mathematical principle related to coupling methods for Markov chains. This paper analyzes in detail two simplified variants of the trick and estimates the probability of success. The model predictions are compared with simulation data for several variants of the actual trick. The PDF file comes in at 21 pages, so you might be interested in going to a direct link. For those who are interested, try this.... http://arxiv.org/pdf/math.PR/0110143 or if you want to get it in a format other than a PDF file... http://arxiv.org/format/math.PR/0110143 Paradise Elite user sheffieldEngland 416 Posts Posted: Apr 19, 2006 06:33 am    0 I am familiar with this but are there any effective effects that use this? The Magic Cafe Forum Index » » Magical equations » » Kruskal count (0 Likes)
 [ Top of Page ]
 All content & postings Copyright © 2001-2021 Steve Brooks. All Rights Reserved. This page was created in 0.2 seconds requiring 5 database queries.
 The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement <