Published
In this lesson
Wide tables, equations, and code scroll sideways. Swipe, or Tab to focus them and use the left and right arrow keys.
Kruskal count
You will learn: Trace shared counting paths and calculate agreement under explicit starting-choice rules.
Start with: Conditioning and independence
Choose a secret starting number from one to ten. Count that many cards into a shuffled deck. The card you reach tells you how far to count next: an ace means one, a number card means its number, and a jack, queen, or king means five. Continue until the next jump would pass the end of the deck. Remember the last card reached.
A magician can run the same procedure from another starting number and often reach your final card. The reason is not that the two paths remain independent and somehow agree by coincidence. Once they land on the same position, that shared card gives them identical future instructions.
Trace both routes
Path A: 1 → 2 → 11 → 19 → 26 → 31 → 35 → 37 → 40 → 48. Path B: 7 → 16 → 24 → 30 → 32 → 42 → 47 → 52.
These paths never meet and end at different cards. Final positions: A 48, B 52.
Path A cards have a filled background; path B cards have a double border. Letters label both memberships, including shared cards. An ace counts as one, number cards use their number, and face cards use the chosen jump value.
| Final position | Starting choices reaching it (out of 10) |
|---|---|
| 48: 5♥ | 8 |
| 52: J♦ | 2 |
For this fixed deck and magician start 1, success against a uniform subject start is 0.800000. Two independent uniform starts agree with probability 0.680000; two uniform distinct starts agree with probability 0.644444. Those are different sampling rules.
Sampled-deck count: 200. Mean conditional success for magician start 1 is 0.860000. Each deck averages over all ten subject starts. This estimates the random-deck probability; it is not an exact value or a guarantee for this deck.
Inspect all ten paths
| Start | Visited positions | Final position |
|---|---|---|
| 1 | 1, 2, 11, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 2 | 2, 11, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 3 | 3, 6, 11, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 4 | 4, 5, 15, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 5 | 5, 15, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 6 | 6, 11, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 7 | 7, 16, 24, 30, 32, 42, 47, 52 | 52 |
| 8 | 8, 13, 16, 24, 30, 32, 42, 47, 52 | 52 |
| 9 | 9, 10, 15, 19, 26, 31, 35, 37, 40, 48 | 48 |
| 10 | 10, 15, 19, 26, 31, 35, 37, 40, 48 | 48 |
Positions are numbered from one at the top to fifty-two at the bottom. If a key card at position j has value v, the next key card is at j + v. Counting starts with the following card, so there is no extra plus one. A jump beyond position fifty-two ends the procedure at the current key card; it does not select a nonexistent card beyond the deck.
The grid names each card and its jump value. Path membership has both letters and visual distinctions. The first common position is reported when it exists, and all ten possible start paths are available for inspection. Changing the face-card rule preserves the shuffled card order so that its effect can be isolated.
A concrete success and failure
With seed 139 and the classic face value five, start one visits positions 1, 2, 11, 19, 26, 31, 35, 37, 40, and 48. Start two joins it immediately at position two and follows exactly the same remaining suffix. Both finish at position forty-eight.
Start seven, however, ends at position fifty-two. Those two paths never meet. The default pair deliberately shows a failure so that the demonstration cannot be mistaken for a deterministic guarantee. Change subject start B from seven to two to see a successful merge on the same deck.
Eight of this deck’s ten starting choices finish at position forty-eight and two finish at fifty-two. A magician fixed at start one therefore succeeds against a uniformly selected subject start with probability 8/10. That is an exact statement conditional on this displayed deck and this rule for selecting the subject’s start.
Three questions, three denominators
If both starts are independent and uniform, including the possibility of equality, there are one hundred ordered pairs. The two endpoint groups contribute 8² + 2² = 68 agreeing pairs, so agreement probability is 0.68. If the starts must differ, there are ninety ordered pairs; the numerator becomes 8·7 + 2·1 = 58, giving 58/90, about 0.644444.
Neither of those is the fixed-magician-start probability 0.8. The experiment reports all three separately. This distinction matters when comparing a paper, a simulation, and a performance of the trick: a change in the strategy or sampling denominator changes the probability being estimated.
The sampled-deck comparison keeps the magician’s start fixed. For each shuffled deck it checks all ten subject starts, calculates that deck’s exact conditional success probability, and averages those probabilities. The result is a Monte Carlo estimate across decks; increasing the number of decks extends the existing sample. It is not an exact unconditional probability.
Coupling is the mechanism
Every jump is positive, so each route moves strictly forward and must terminate. If two routes meet at position j, they read the same jump value, reach the same next position, and repeat this reasoning until they finish. Contact guarantees a shared suffix. It does not guarantee that contact occurs before the deck ends.
Face-card values influence the chances of meeting. On the displayed seed, changing their value from five to ten changes endpoint groups from eight and two to six and four. The probability for fixed start one falls from 0.8 to 0.6. That example is specific to this deck; it is not a claim that every increase in jump size lowers success on every deck.
Make a prediction
Can two paths land on the same key card and later separate if they use the same jump-value rule?
Explore the answer
No. Their next positions are then determined by the same card value. Separation would require different rules or different underlying decks.
Lagarias, Rains, and Vanderbei analyze simplified coupling models and compare strategies for the actual trick. Their work also explains why a finite shuffled deck cannot simply be replaced by independent jump values without changing the model. Continue to riffle shuffling to examine the randomness assumption behind a shuffled deck itself.