AI tools

Kruskal count

From Wikipedia, the free encyclopedia

"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[1][2] (also known as Kruskal's principle,[3][4][5][6][7] Dynkin–Kruskal count,[8] Dynkin's counting trick,[9] Dynkin's card trick,[10][11][12][13] coupling card trick[14][15][16] or shift coupling[10][11][12][13]) is a probabilistic concept originally demonstrated by the Russian mathematician Evgenii Borisovich Dynkin in the 1950s or 1960s[when?] discussing coupling effects[14][15][9][16] and rediscovered as a card trick by the American mathematician Martin David Kruskal in the early 1970s[17][nb 1] as a side-product while working on another problem.[18] It was published by Kruskal's friend[19] Martin Gardner[20][1] and magician Karl Fulves in 1975.[21] This is related to a similar trick published by magician Alexander F. Kraus in 1957 as Sum total[22][23][24][25] and later called Kraus principle.[2][7][25][18]

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

Thumb
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.[26][27][28][29][6] A simplified version using the hands of a clock is as follows.[30] 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

Notes

  1. [N 1]
    According to Diaconis & Graham (2012), Martin Kruskal explained the trick, which later became known as Kruskal's principle, to Martin Gardner in a reply to a letter Gardner had sent him to recommend Persi W. Diaconis for graduate school. Diaconis graduated in 1971, earned a M.S. in mathematical statistics at Harvard University in 1972, and a Ph.D. from Harvard in 1974, so Kruskal's reply must have been between 1971 and 1974 the latest. Gardner published the trick in Gardner (1975).

References

Further reading

External links

Wikiwand - on

Seamless Wikipedia browsing. On steroids.