Kruskal count
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 is as follows. 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. See also
 Coupling (probability)
 Discrete logarithm
 Equifinality
 Ergodic theory
 Geometric distribution
 Overlapping instructions
 Pollard's kangaroo algorithm
 Random walk
 Self-synchronizing code
 Wikipedia:Getting to Philosophy

Notes

References

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]
 
 

Recreational mathematics
Cryptography
Number theoretic algorithms
Probability theory
Markov processes
Markov models