publication . Preprint . Part of book or chapter of book . 2001

The Kruskal Count

Lagarias, Jeffrey C.; Rains, Eric; Vanderbei, Robert J.;
Open Access English
  • Published: 13 Oct 2001
  • Country: United States
Abstract
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.
Subjects
free text keywords: Mathematics - Probability, Mathematics - Optimization and Control, 60J10, ATM card, Computer science, Markov chain, Algorithm, Geometric distribution, Standard 52-card deck, Kruskal's algorithm, Arithmetic, Deck
Download fromView all 3 versions
Caltech Authors
Part of book or chapter of book . 2009
http://www.springerlink.com/in...
Part of book or chapter of book
Provider: Crossref

[1] D. Aldons and P. Diaconis, Shuffling Cards and Stopping Times, Amer. Math. Monthly 93 (1986), 333-348.

[2] P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes - Monograph Series No. 11, Institute of Math. Statistics, Hayward, Calif. 1988.

[3] W. Doeblin, Expos´e de la theorie des chaines simple constantes de Markov ´a un nombre fini d'etats, Rev. Math Union Interbalkanique 2 (1938), 77-105.

[4] M. D. Donsker and S. R. S. Varadhan, Asymptotic Evaluation of Certain Markov Process Expectations for Large Time I, Comm. Pure. Appl. Math. 28 (1975), 1-47. [OpenAIRE]

[5] C. Fulves and M. Gardner, The Kruskal Principle, The Pallbearers Review, June 1975.

[6] M. Gardner, Mathematical Games, Sci. Amer. 238 (1978) No. 2 (February), 19-32.

[7] M. Gardner, From Penrose Tiles to Trapdoor Ciphers, W. H. Freeman Co., New York, 1988. (Chapter 19)

[8] D. Griffeath, Coupling Methods for Markov Processes, in: Studies in Probability and Ergodic Theory (G. C. Rota, Ed.), Academic Press, New York, 1978, pp. 1-43.

[9] W. Haga and S. Robins, On Kruskal's Principle, in Organic Mathematics, (J. Borwein, P. Borwein, L Jorgenson, and R. Corless, Eds.), Canadian Math. Society Conference Proceedings, vol. 20, AMS: Providence, RI, 1997, pp. 407-412.

[10] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, New York, 1979.

[11] C. L. Mallows, On a probability problem suggested by M. D. Kruskal's card trick, Bell Laboratories memorandum, April 18, 1975, unpublished.

[12] J. Pitman, On coupling of Markov Chains, Z. Wahrscheinlichkeitheorie 35 (1976), 315- 322. email: jcl@research.att.com rains@research.att.com rvdb@princeton.edu

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Part of book or chapter of book . 2001

The Kruskal Count

Lagarias, Jeffrey C.; Rains, Eric; Vanderbei, Robert J.;