The Kruskal count (also known as Kruskal's principle, Dynkin–Kruskal count, Dynkin's counting trick, Dynkin's card trick, coupling card trick or shift coupling) is a probabilistic concept originally demonstrated by the Russian mathematician Evgenii Borisovich Dynkin in the 1950s or 1960s discussing coupling effects and rediscovered as a card trick by the American mathematician Martin David Kruskal in the early 1970s as a side-product while working on another problem. It was published by Kruskal's friend Martin Gardner and magician Karl Fulves in 1975. This is related to a similar trick published by magician Alexander F. Kraus in 1957 as Sum total and later called Kraus principle.
Besides uses as a card trick, the underlying phenomenon has applications in cryptography, code breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length codes and variable-length instruction sets, web navigation, object alignment, and others.
Card trick
The trick is performed with cards, but is more a magical-looking effect than a conventional magic trick. The magician has no access to the cards, which are manipulated by members of the audience. Thus sleight of hand is not possible. Rather the effect is based on the mathematical fact that the output of a Markov chain, under certain conditions, is typically independent of the input. A simplified version using the hands of a clock performed by David Copperfield is as follows.http://popularmechanics.com/science/a31136091/math-magic-trick/ A volunteer picks a number from one to twelve and does not reveal it to the magician. The volunteer is instructed to start from 12 on the clock and move clockwise by a number of spaces equal to the number of letters that the chosen number has when spelled out. This is then repeated, moving by the number of letters in the new number. The output after three or more moves does not depend on the initially chosen number and therefore the magician can predict it. To an observer who has not realized that the card or clock numbers form a predictable Markov chain that collapses to a stable output (in the case of Copperfield illustration, a cycle of "one"-"four"-"eight"), it appears that the magician has identified their starting number by successfully identifying their ending number.
See also Coupling (probability) Discrete logarithm Equifinality Ergodic theory Geometric distribution Overlapping instructions Pollard's kangaroo algorithm Random walk Self-synchronizing code
Notes
References (22 pages) (12 pages)
(5 pages) (1 page) (NB. The second part can be found in .); (319 pages) (NB. Volume 1 of a three-volume hardcover reprint of ibidem magazine numbers 1 (June 1955) – 15 (December 1958).) (4 pages) (NB. The first part can be found in .); (319 pages) (NB. Volume 1 of a three-volume hardcover reprint of ibidem magazine numbers 1 (June 1955) – 15 (December 1958).) (2 pages); (319 pages) (NB. Volume 1 of a three-volume hardcover reprint of ibidem magazine numbers 1 (June 1955) – 15 (December 1958).) (4 pages); (1 page); (381 pages) (NB. Volume 3 of a three-volume hardcover reprint of The Pallbearers Review magazine volumes 9 (November 1973) – 10 (1977).); ; (381 pages) (NB. Volume 3 of a three-volume hardcover reprint of The Pallbearers Review magazine volumes 9 (November 1973) – 10 (1977).)
; (1+ix+319 pages)
(7 pages) (11 pages) (1+3 pages) (vi+301 pages) (1 page) (10 pages) (66 pages); (49 pages) (14 pages) (17 pages) (147 pages)
(x+453 pages) (NB. This can be found quoted in .); (497 pages) (NB. This can be found quoted in .) (45 pages) (NB. This can be found quoted in .) (1+9 pages) (NB. This work quotes .) (xvii+610 pages); (xv+685 pages) (2+xii+2+244+4 pages) (xii+235 pages) (NB. The book contains a significant number of typographical errors: ); (xiv+234 pages)
Further reading (1+9+80+9+1 pages) (NB. This is a translation of the first Russian edition published as "" by GTTI () in March 1952 as Number 6 in Library of the Mathematics Circle (). It is based on seminars held at the School Mathematics Circle in 1945/1946 and 1946/1947 at Moscow State University.) (xii+365+1 pages); (viii+274+2 pages) (NB. This was originally published in Russian as "Markovskie prot︠s︡essy" () by Fizmatgiz () in 1963 and translated to English with the assistance of the author.) (x+237 pages) (NB. This is a corrected translation of the first Russian edition published as "" by Nauka Press () in 1967 as part of a series on Probability Theory and Mathematical Statistics () with the assistance of the authors. It is based on lectures held at the Moscow State University in 1962/1963.)
(4 pages) (4 pages); (4 of xiv+373+17 pages) (xvi+421 pages) (4 pages) (6 pages) (1+10 pages)
(8 pages)
(2 pages) (10 pages) (18 pages) (23 pages)
(1+xvii+1+152 pages) (13 pages) (17 pages) (NB. This source does not mention Dynkin or Kruskal specifically.)
External links [23:40]