• Source: 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


Dynkin [Ды́нкин], Evgenii Borisovich [Евге́ний Бори́сович]; Uspenskii [Успе́нский], Vladimir Andreyevich [Влади́мир Андре́евич] (1963). Written at University of Moscow, Moscow, Russia. Putnam, Alfred L.; Wirszup, Izaak (eds.). Random Walks (Mathematical Conversations Part 3). Survey of Recent East European Mathematical Literature. Vol. 3. Translated by Whaland, Jr., Norman D.; Titelbaum, Olga A. (1 ed.). Boston, Massachusetts, US: The University of Chicago / D. C. Heath and Company. LCCN 63-19838. Retrieved 2023-09-03. (1+9+80+9+1 pages) [8] (NB. This is a translation of the first Russian edition published as "Математические беседы: Задачи о многоцветной раскраске / Задачи из теории чисел / Случайные блуждания"[9] 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.)
Dynkin [Ды́нкин], Evgenii Borisovich [Евге́ний Бори́сович] (1965) [1963-03-10, 1962-03-31]. Written at University of Moscow, Moscow, Russia. Markov Processes-I. Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete. Vol. I (121). Translated by Fabius, Jaap [at Wikidata]; Greenberg, Vida Lazarus [at Wikidata]; Maitra, Ashok Prasad [at Wikidata]; Majone, Giandomenico (1 ed.). New York, US / Berlin, Germany: Springer-Verlag (Academic Press, Inc.). doi:10.1007/978-3-662-00031-1. ISBN 978-3-662-00033-5. ISSN 0072-7830. LCCN 64-24812. S2CID 251691119. Title-No. 5104. Retrieved 2023-09-02. [10] (xii+365+1 pages); Dynkin, Evgenii Borisovich (1965) [1963-03-10, 1962-03-31]. Written at University of Moscow, Moscow, Russia. Markov Processes-II. Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete. Vol. II (122). Translated by Fabius, Jaap [at Wikidata]; Greenberg, Vida Lazarus [at Wikidata]; Maitra, Ashok Prasad [at Wikidata]; Majone, Giandomenico (1 ed.). New York, US / Berlin, Germany: Springer-Verlag. doi:10.1007/978-3-662-25360-1. ISBN 978-3-662-23320-7. ISSN 0072-7830. LCCN 64-24812. Title-No. 5105. Retrieved 2023-09-02. (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.)
Dynkin [Ды́нкин], Evgenii Borisovich [Евге́ний Бори́сович]; Yushkevish [Юшкевич], Aleksandr Adol'fovich [Александр Адольфович] [in German] (1969) [1966-01-22]. Written at University of Moscow, Moscow, Russia. Markov Processes: Theorems and Problems (PDF). Translated by Wood, James S. (1 ed.). New York, US: Plenum Press / Plenum Publishing Corporation. LCCN 69-12529. Archived (PDF) from the original on 2023-09-06. Retrieved 2023-09-03. (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.)
Marlo, Edward "Ed" (1976-12-01). Written at Chicago, Illinois, US. Hudson, Charles (ed.). "Approach & Uses for the "Kruskal Kount" / First Presentation Angle / Second Presentation Angle - Checking the Deck / Third Presentation Angle - The 100% Method / Fourth Presentation Angle - "Disaster"". Card Corner. The Linking Ring. Vol. 56, no. 12. Bluffton, Ohio, US: International Brotherhood of Magicians. pp. 82, 83, 83, 84, 85–87. ISSN 0024-4023.
Hudson, Charles (1977-10-01). Written at Chicago, Illinois, US. "The Kruskal Principle". Card Corner. The Linking Ring. Vol. 57, no. 10. Bluffton, Ohio, US: International Brotherhood of Magicians. p. 85. ISSN 0024-4023.
Gardner, Martin (September 1998). "Ten Amazing Mathematical Tricks". Gardner's Gatherings. Math Horizons. Vol. 6, no. 1. Mathematical Association of America / Taylor & Francis, Ltd. pp. 13–15, 26. ISSN 1072-4117. JSTOR 25678174. (4 pages)
Haigh, John (1999). "7. Waiting, waiting, waiting: Packs of cards (2)". Taking Chances: Winning with Probability (1 ed.). Oxford, UK: Oxford University Press Inc. pp. 133–136. ISBN 978-0-19-850291-3. Retrieved 2023-09-06. (4 pages); Haigh, John (2009) [2003]. "7. Waiting, waiting, waiting: Packs of cards (2)". Taking Chances: Winning with Probability (Reprint of 2nd ed.). Oxford, UK: Oxford University Press Inc. pp. 139–142. ISBN 978-0-19-852663-6. Retrieved 2023-09-03. (4 of xiv+373+17 pages)
Bean, Gordon (2002). "A Labyrinth in a Labyrinth". In Wolfe, David; Rodgers, Tom (eds.). Puzzlers' Tribute: A Feast for the Mind (1 ed.). CRC Press / Taylor & Francis Group, LLC. pp. 103–106. ISBN 978-1-43986410-4. (xvi+421 pages)
Ching, Wai-Ki [at Wikidata]; Lee, Yiu-Fai (September 2005) [2004-05-05]. "A Random Walk on a Circular Path". Miscellany. International Journal of Mathematical Education in Science and Technology. 36 (6). Taylor & Francis, Ltd.: 680–683. doi:10.1080/00207390500064254. eISSN 1464-5211. ISSN 0020-739X. S2CID 121692834. (4 pages)
Lee, Yiu-Fai; Ching, Wai-Ki [at Wikidata] (2006-03-07) [2005-09-29]. "On Convergent Probability of a Random Walk" (PDF). Classroom notes. International Journal of Mathematical Education in Science and Technology. 37 (7). Advanced Modeling and Applied Computing Laboratory and Department of Mathematics, The University of Hong Kong, Hong Kong: Taylor & Francis, Ltd.: 833–838. doi:10.1080/00207390600712299. eISSN 1464-5211. ISSN 0020-739X. S2CID 121242696. Archived (PDF) from the original on 2023-09-02. Retrieved 2023-09-02. (6 pages)
Humble, Steve "Dr. Maths" (July 2008). "Magic Card Maths". The Montana Mathematics Enthusiast. 5 (2 & 3). Missoula, Montana, US: University of Montana: 327–336. doi:10.54870/1551-3440.1111. ISSN 1551-3440. S2CID 117632058. Article 14. Archived from the original on 2023-09-03. Retrieved 2023-09-02. (1+10 pages)
Montenegro, Ravi [at Wikidata]; Tetali, Prasad V. (2010-11-07) [2009-05-31]. How Long Does it Take to Catch a Wild Kangaroo? (PDF). Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC 2009). pp. 553–560. arXiv:0812.0789. doi:10.1145/1536414.1536490. S2CID 12797847. Archived (PDF) from the original on 2023-08-20. Retrieved 2023-08-20.
Grime, James [at Wikidata] (2011). "Kruskal's Count" (PDF). singingbanana.com. Archived (PDF) from the original on 2023-08-19. Retrieved 2023-08-19. (8 pages)
Bosko, Lindsey R. (2011). Written at Department of Mathematics, North Carolina State University, Raleigh, North Carolina, US. "Cards, Codes, and Kangaroos" (PDF). The UMAP Journal. Modules and Monographs in Undergraduate Mathematics and its Applications (UMAP) Project. 32 (3). Bedford, Massachusetts, US: Consortium For Mathematics & Its Applications, Inc. (COMAP): 199–236. UMAP Unit 808. Archived (PDF) from the original on 2023-08-19. Retrieved 2023-08-19.
West, Bob [at Wikidata] (2011-05-26). "Wikipedia's fixed point". dlab @ EPFL. Lausanne, Switzerland: Data Science Lab, École Polytechnique Fédérale de Lausanne. Archived from the original on 2022-05-23. Retrieved 2023-09-04. [...] it turns out there is a card trick that works exactly the same way. It's called the "Kruskal Count" [...]
Humble, Steve "Dr. Maths" (September 2012) [2012-07-02]. Written at Kraków, Poland. Behrends, Ehrhard [in German] (ed.). "Mathematics in the Streets of Kraków" (PDF). EMS Newsletter. No. 85. Zürich, Switzerland: EMS Publishing House / European Mathematical Society. pp. 20–21 [21]. ISSN 1027-488X. Archived (PDF) from the original on 2023-09-02. Retrieved 2023-09-02. p. 21: [...] The Kruscal count [...] [11] (2 pages)
Andriesse, Dennis; Bos, Herbert [at Wikidata] (2014-07-10). Written at Vrije Universiteit Amsterdam, Amsterdam, Netherlands. Dietrich, Sven (ed.). Instruction-Level Steganography for Covert Trigger-Based Malware (PDF). 11th International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA). Lecture Notes in Computer Science. Egham, UK; Switzerland: Springer International Publishing. pp. 41–50 [45]. doi:10.1007/978-3-319-08509-8_3. eISSN 1611-3349. ISBN 978-3-31908508-1. ISSN 0302-9743. S2CID 4634611. LNCS 8550. Archived (PDF) from the original on 2023-08-26. Retrieved 2023-08-26. (10 pages)
Montenegro, Ravi [at Wikidata]; Tetali, Prasad V. (2014-09-07). Kruskal's Principle and Collision Time for Monotone Transitive Walks on the Integers (PDF). Archived (PDF) from the original on 2023-08-22. Retrieved 2023-08-22. (18 pages)
Kijima, Shuji; Montenegro, Ravi [at Wikidata] (2015-03-15) [2015-03-30/2015-04-01]. Written at Gaithersburg, Maryland, US. Katz, Jonathan (ed.). Collision of Random Walks and a Refined Analysis of Attacks on the Discrete Logarithm Problem (PDF). Proceedings of the 18th IACR International Conference on Practice and Theory in Public-Key Cryptography. Lecture Notes in Computer Science. Berlin & Heidelberg, Germany: International Association for Cryptologic Research / Springer Science+Business Media. pp. 127–149. doi:10.1007/978-3-662-46447-2_6. ISBN 978-3-662-46446-5. LNCS 9020. Archived (PDF) from the original on 2023-09-03. Retrieved 2023-09-03. (23 pages)
Jose, Harish (2016-06-14) [2016-06-02]. "PDCA and the Roads to Rome: Can a lean purist and a Six Sigma purist reach the same answer to a problem?". Lean. Archived from the original on 2023-09-07. Retrieved 2023-09-07. [12][13]
Lamprecht, Daniel; Dimitrov, Dimitar; Helic, Denis; Strohmaier, Markus (2016-08-17). "Evaluating and Improving Navigability of Wikipedia: A Comparative Study of Eight Language Editions". Proceedings of the 12th International Symposium on Open Collaboration (PDF). OpenSym, Berlin, Germany: Association for Computing Machinery. pp. 1–10. doi:10.1145/2957792.2957813. ISBN 978-1-4503-4451-7. S2CID 13244770. Archived (PDF) from the original on 2023-09-04. Retrieved 2021-03-17.
Jämthagen, Christopher (November 2016). On Offensive and Defensive Methods in Software Security (PDF) (Thesis). Lund, Sweden: Department of Electrical and Information Technology, Lund University. p. 96. ISBN 978-91-7623-942-1. ISSN 1654-790X. Archived (PDF) from the original on 2023-08-26. Retrieved 2023-08-26. (1+xvii+1+152 pages)
Mannam, Pragna; Volkov, Jr., Alexander; Paolini, Robert; Chirikjian, Gregory Scott; Mason, Matthew Thomas (2019-02-06) [2018-12-04]. "Sensorless Pose Determination Using Randomized Action Sequences". Entropy. 21 (2). Basel, Switzerland: Multidisciplinary Digital Publishing Institute: 154. arXiv:1812.01195. Bibcode:2019Entrp..21..154M. doi:10.3390/e21020154. ISSN 1099-4300. PMC 7514636. PMID 33266870. S2CID 54444590. Article 154. p. 2: [...] The phenomenon, while also reminiscent of contraction mapping, is similar to an interesting card trick called the Kruskal Count [...] so we have dubbed the phenomenon as "Kruskal effect". [...] (13 pages)
Blackburn, Simon Robert; Esfahani, Navid Nasr; Kreher, Donald Lawson; Stinson, Douglas "Doug" Robert (2023-08-22) [2022-11-18]. "Constructions and bounds for codes with restricted overlaps". IEEE Transactions on Information Theory. arXiv:2211.10309. (17 pages) (NB. This source does not mention Dynkin or Kruskal specifically.)




External links


Humble, Steve "Dr. Maths" (2010). "Dr. Maths Randomness Show". YouTube (Video). Alchemist Cafe, Dublin, Ireland. Retrieved 2023-09-05. [23:40]
"Mathematical Card Trick Source". Close-Up Magic. GeniiForum. 2015–2017. Archived from the original on 2023-09-04. Retrieved 2023-09-05.
Behr, Denis, ed. (2023). "Kruskal Principle". Conjuring Archive. Archived from the original on 2023-09-10. Retrieved 2023-09-10.

Kata Kunci Pencarian:

• Statistika
• Ilmu aktuaria
• Statistika matematika
• Variabel acak
• Model generatif
• Daftar algoritme
• Efek pengacau
• Eksperimen semu
• Kruskal count
• Martin David Kruskal
• Kruskal–Wallis test
• Kruskal's algorithm
• Coupling (probability)
• Machine code
• Variable-length code
• Goodman and Kruskal's gamma
• Pollard's kangaroo algorithm
• Zero-inflated model