Kruskal count

"Kruskal's principle" redirects here. For Kruskal's method, see Kruskal's algorithm.

"Sum Total" redirects here. For the statistical quantity, see Total sum of squares.

"Dynkin's card trick" redirects here. For optimal stopping problems, see Dynkin games.

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

File:Kruskal count principle.svg

Explanation of Kruskal count

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. 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

Further reading

• (1+9+80+9+1 pages) [7] (NB. This is a translation of the first Russian edition published as "Математические беседы: Задачи о многоцветной раскраске / Задачи из теории чисел / Случайные блуждания"[8] 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.)
• [9] (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)
• [10] (2 pages)
• (10 pages)
• (18 pages)
• (23 pages)
• [11][12]
• (1+xvii+1+152 pages)
• (13 pages)
• (17 pages) (NB. This source does not mention Dynkin or Kruskal specifically.)

External links

• [23:40]