Riffle Shuffle — credits ======================== This is an INDEPENDENT REIMPLEMENTATION of published mathematics. It is not affiliated with, endorsed by, or derived from the code of any author below. No text, figure or table image from any paper is reproduced in this bundle; only numeric values, which are facts and not expression. The mathematics --------------- * Dave Bayer and Persi Diaconis, "Trailing the Dovetail Shuffle to its Lair", The Annals of Applied Probability, volume 2, number 2 (May 1992), pages 294-313. Published by the Institute of Mathematical Statistics. Theorem 1 (the closed form for the chance of an arrangement after m riffles), the total variation convention, Tables 1, 3, 4 and 5, and the card-guessing game of section 5.1 all come from this paper. * L. N. Trefethen and L. M. Trefethen, "How many shuffles to randomize a deck of cards?", Proceedings of the Royal Society A, volume 456, number 2002 (8 October 2000), pages 2561-2568. The information/entropy measurement, the observation that the cutoff is absent in that measure, and the figures of 3.52% and 0.92%. * Edgar N. Gilbert, "Theory of shuffling", technical memorandum, Bell Laboratories, 1955, and independently Jim Reeds, unpublished manuscript, 1981. The shuffle model itself, universally called the Gilbert-Shannon-Reeds model. Claude Shannon is the Shannon in that name. * David Aldous and Persi Diaconis, "Shuffling cards and stopping times", The American Mathematical Monthly, volume 93, number 5 (1986), pages 333-348. The n log n mixing time for the top-to-random shuffle used here as a control. * C. O. Williams, "A card reading", The Magician Monthly 8 (1912), page 67, and Charles T. Jordan, "Long distance mind reading", The Sphinx 15 (1916), page 57, and "Thirty Card Mysteries" (1919). Rising sequences -- the invariant the whole analysis rests on -- were a magicians' discovery first. * Michael McGrath devised the guessing strategy used in Table 5, according to the 1992 paper. What this bundle adds --------------------- * The exact law of the top-to-random shuffle started from a sorted deck, used for the control comparison. The papers give an asymptotic; the exact finite-n curve here is derived in js/control.js and checked against a brute-force enumeration of the whole symmetric group for decks of 3 to 7 cards. * The observation that the separation distance of that shuffle is the survival function of the SECOND-from-bottom card's departure time, which is one geometric step sharper than the textbook coupon-collector bound. * The "bounded regime" table: the same deck and the same shuffle, scored against twelve different definitions of "randomised", giving answers from 4 to 13. * All of the code, the charts, the artwork and the page. What differs from the papers ---------------------------- * Table 5 is re-run here at 20,000 trials per cell rather than 100,000, and the 95% interval is printed beside each figure. All ten no-cut cells agree with the published row inside that interval. * The with-cut row agrees for six or more shuffles but not for one or two. The cut-adapted strategy is described only in prose and attributed to McGrath; the reconstruction here turns out to be slightly stronger than whatever produced the published row. This is reported, not tuned away. * The 1992 paper's asymptotic Theorem 2 is quoted but not used: for a 52-card deck the exact computation is cheap, and it gives 7 where the asymptotic formula gives 8.55. Code and assets --------------- No third-party code, font, image or stylesheet ships in this bundle. The renderer, the charts, the card faces, the icons and the social card were all written for this app. The pseudo-random generator is mulberry32, a public-domain one-line generator by Tommy Ettinger. Licence ------- The code is MIT licensed; see LICENSE.txt.