5D Library › Tarot Hypergeometric Sampling, Lenormand Grid Topology and Kabbalistic Tree Graphs · 中文

Chapter 2. Shuffles, Mixing Times and the Correlation of Reversals

How many riffles?

The most studied model of shuffling is the Gilbert-Shannon-Reeds (GSR) riffle: cut the deck binomially into two packets, then drop cards one at a time with probability proportional to the sizes that remain. Bayer and Diaconis proved that after kk riffles the probability of a permutation with rr rising sequences depends only on rr, which makes the total variation distance to the uniform law exactly computable (Bayer and Diaconis 1992).

Calculation

# Chapter 2. p03: How many riffles mix a 78-card deck?
# Gilbert-Shannon-Reeds model; Bayer and Diaconis (1992): after k
# riffles a permutation with r rising sequences has probability
#   C(2^k + n - r, n) / 2^(kn),
# and A(n, r) permutations (Eulerian numbers) have r rising sequences.
# Total variation distance to uniform:
#   TV = 1/2 * sum_r A(n, r) * | C(2^k + n - r, n) / 2^(kn) - 1/n! |.
# A riffle moves cards but never turns one round: orientation is untouched.
from fractions import Fraction
from math import comb, factorial, log2

def eulerian(n):
    row = [1]                       # n = 1: one permutation, 1 sequence
    for m in range(2, n + 1):
        new = [0] * m
        for j in range(m):          # j descents -> j + 1 rising sequences
            a = row[j] if j < len(row) else 0
            b = row[j - 1] if j >= 1 else 0
            new[j] = (j + 1) * a + (m - j) * b
        row = new
    return row                      # row[r - 1] = A(n, r)

def tv(n, k, A):
    nf = factorial(n)
    s = Fraction(0)
    for r in range(1, n + 1):
        p = Fraction(comb(2 ** k + n - r, n), 2 ** (k * n))
        s += A[r - 1] * abs(p - Fraction(1, nf))
    return s / 2

if __name__ == "__main__":
    tables = {n: eulerian(n) for n in (52, 78)}
    for n in (52, 78):
        assert sum(tables[n]) == factorial(n)
    print("   riffles   TV, 52 cards   TV, 78 cards")
    first = {}
    for k in range(1, 13):
        row = [float(tv(n, k, tables[n])) for n in (52, 78)]
        for n, v in zip((52, 78), row):
            if v < 0.5 and n not in first:
                first[n] = k
        print("   {:7d}   {:12.4f}   {:12.4f}".format(k, *row))
    print("   first k with TV < 0.5: 52 cards -> {}, 78 cards -> {}".format(
        first[52], first[78]))
    print("   rule of thumb (3/2) log2 n: 52 -> {:.2f}, 78 -> {:.2f}".format(
        1.5 * log2(52), 1.5 * log2(78)))
#    riffles   TV, 52 cards   TV, 78 cards
#          1         1.0000         1.0000
#          2         1.0000         1.0000
#          3         1.0000         1.0000
#          4         1.0000         1.0000
#          5         0.9237         0.9996
#          6         0.6135         0.8926
#          7         0.3341         0.5713
#          8         0.1672         0.3065
#          9         0.0854         0.1532
#         10         0.0429         0.0780
#         11         0.0215         0.0392
#         12         0.0108         0.0196
#    first k with TV < 0.5: 52 cards -> 7, 78 cards -> 8
#    rule of thumb (3/2) log2 n: 52 -> 8.55, 78 -> 9.43

For 52 cards the total variation first drops below 0.5 after seven riffles (0.3341), which is where “shuffle seven times” comes from. The 78 cards of a tarot deck need eight (0.3065); after seven the distance is still 0.5713. The rule of thumb 32log⁡2n\tfrac{3}{2}\log_2 n gives 8.55 and 9.43, showing that the steep fall happens around these numbers. Figure 2 plots both curves.

Number of GSR riffles against total variation distance: 52 and 78 cards (p03).

The result says only how fast the order of the cards mixes. A riffle never turns a single card round, so it does nothing to reversals: an all-upright deck riffled a hundred times is still all upright. Reversals can only come from another kind of action, turning a card or a packet through 180 degrees.

Where reversals come from

The program compares three turning habits, each starting from an all-upright deck. “Coin”: each card is turned independently with probability one half. “Split”: cut near the middle, turn the top half round, riffle once, repeated 1, 3 or 7 times; “clumpy” is the same action but the riffle drops small clumps (2.5 cards on average). “Packet”: move packets of geometric size (5 cards on average) to a new pile, turning each packet round as a whole with probability one half.

Calculation

# Chapter 2. p04: Where reversals come from - three shuffling habits.
# Riffles never turn cards, so reversals come from turning packets round.
#  coin   : each card turned independently with probability 1/2
#  split  : cut near the middle, turn one half round, riffle (GSR), r times
#  clumpy : as split x1, but the riffle drops clumps (mean 2.5 cards)
#  packet : overhand pass; packets of geometric size (mean 5) moved to a
#           new pile, each packet turned round with probability 1/2
# The deck starts all upright. We measure, over 78 positions, the lag-1
# correlation of orientation, the mean run length, and the spread of the
# number reversed among the top 10 cards (binomial variance: 2.5).
import random

N, TRIALS = 78, 20000

def coin(deck, rng):
    return [(c, o ^ (rng.random() < 0.5)) for c, o in deck]

def riffle(a, b, rng):
    out = []
    while a or b:
        if rng.random() * (len(a) + len(b)) < len(a):
            out.append(a.pop(0))
        else:
            out.append(b.pop(0))
    return out

def clumpy(a, b, rng):
    out = []
    while a or b:
        src = a if rng.random() * (len(a) + len(b)) < len(a) else b
        k = 1
        while rng.random() < 0.6:
            k += 1
        out.extend(src[:k])
        del src[:k]
    return out

def split(deck, rng, rounds, mix=riffle):
    for _ in range(rounds):
        cut = sum(rng.random() < 0.5 for _ in range(N))
        top = [(c, 1 - o) for c, o in reversed(deck[:cut])]
        deck = mix(top, deck[cut:], rng)
    return deck

def packet(deck, rng):
    pile = []
    i = 0
    while i < N:
        size = 1
        while rng.random() > 0.2 and i + size < N:
            size += 1
        pk = deck[i:i + size]
        if rng.random() < 0.5:
            pk = [(c, 1 - o) for c, o in reversed(pk)]
        pile = pk + pile
        i += size
    return pile

def stats(method, rng):
    num = den = runs = 0.0
    s1 = s2 = 0.0
    for _ in range(TRIALS):
        d = method([(c, 0) for c in range(N)], rng)
        o = [x for _, x in d]
        m = sum(o) / N
        num += sum((o[i] - m) * (o[i + 1] - m) for i in range(N - 1))
        den += sum((x - m) ** 2 for x in o) * (N - 1) / N
        runs += 1 + sum(o[i] != o[i + 1] for i in range(N - 1))
        t = sum(o[:10])
        s1 += t
        s2 += t * t
    mean10 = s1 / TRIALS
    return num / den, N / (runs / TRIALS), s2 / TRIALS - mean10 ** 2

if __name__ == "__main__":
    rng = random.Random(71004)
    rows = [("coin", lambda d, r: coin(d, r)),
            ("split x1", lambda d, r: split(d, r, 1)),
            ("split x3", lambda d, r: split(d, r, 3)),
            ("split x7", lambda d, r: split(d, r, 7)),
            ("clumpy", lambda d, r: split(d, r, 1, clumpy)),
            ("packet", lambda d, r: packet(d, r))]
    print("   habit      lag-1 corr   mean run   var(reversed in top 10)")
    for name, f in rows:
        c, run, v = stats(f, rng)
        print("   {:9s}  {:10.3f}   {:8.2f}   {:8.2f}".format(
            name, c, run, v))
    print("   independent reference: corr {:.3f}, mean run {:.2f},"
          " var 2.50".format(-1 / (N - 1), N / (1 + (N - 1) / 2)))
#    habit      lag-1 corr   mean run   var(reversed in top 10)
#    coin           -0.012       1.98       2.48
#    split x1       -0.013       1.97       2.52
#    split x3       -0.013       1.97       2.46
#    split x7       -0.014       1.97       2.50
#    clumpy          0.597       4.79       7.62
#    packet          0.774       8.97      13.59
#    independent reference: corr -0.013, mean run 1.97, var 2.50

Under independent turning, the expected sample correlation between the orientations of neighbouring cards in 78 is −1/77-1/77, that is −0.013; the mean run length is 1.97 and the variance of the number reversed among the top ten 2.50. One split followed by a GSR riffle already gives almost the same values (−0.013, 1.97, 2.52), because GSR drops arrange the labels of the two packets as a uniformly random binary sequence. But if the riffle is coarse and drops clumps, the correlation rises to 0.597, the mean run to 4.79 and the variance among the top ten to 7.62; overhand packets give a correlation of 0.774, mean runs of 8.97 and a variance of 13.59, more than five times the independent value.

Evidence

Conclusion: the law of reversals depends on the physical process of turning. Only when the turning action separates neighbouring cards do reversals approach an independent binomial with p=0.5p = 0.5; turning whole packets produces marked clustering in runs. This is a mechanical property of shuffling and has nothing to do with card meanings.

Can one spread show clustering?

Under independent turning the number of changes of orientation between neighbours among the top ten cards is binomial B(9,1/2)B(9, 1/2), with mean 4.5 and standard deviation 1.5, so the runs test can be computed exactly (Wald and Wolfowitz 1940).

Calculation

# Chapter 2. p05: Can a reader see clustering in one spread?
# Top 10 cards, orientation sequence. Under independent fair turning the
# number of changes between neighbours is Binomial(9, 1/2), so the exact
# runs test is easy. "Clumpy" and "packet" are the habits of p04.
# One spread: reject independence if there are at most 2 changes.
# Many spreads: compare the mean number of changes with 4.5 (z test).
import random
from math import comb, sqrt, ceil
from statistics import NormalDist

N, TRIALS = 78, 20000

def clumpy_deck(rng):
    deck = [0] * N
    cut = sum(rng.random() < 0.5 for _ in range(N))
    a, b, out = [1] * cut, deck[cut:], []
    while a or b:
        src = a if rng.random() * (len(a) + len(b)) < len(a) else b
        k = 1
        while rng.random() < 0.6:
            k += 1
        out.extend(src[:k])
        del src[:k]
    return out

def packet_deck(rng):
    deck, pile, i = [0] * N, [], 0
    while i < N:
        size = 1
        while rng.random() > 0.2 and i + size < N:
            size += 1
        pk = deck[i:i + size]
        if rng.random() < 0.5:
            pk = [1 - o for o in reversed(pk)]
        pile = pk + pile
        i += size
    return pile

def changes(o):
    return sum(o[i] != o[i + 1] for i in range(9))

if __name__ == "__main__":
    null = [comb(9, c) / 512 for c in range(10)]
    alpha = sum(null[:3])
    print("   exact null: P(changes <= 2) = {:.4f}".format(alpha))
    rng = random.Random(71005)
    z = NormalDist().inv_cdf
    for name, f in (("clumpy", clumpy_deck), ("packet", packet_deck)):
        xs = [changes(f(rng)[:10]) for _ in range(TRIALS)]
        power = sum(x <= 2 for x in xs) / TRIALS
        m = sum(xs) / TRIALS
        v = sum((x - m) ** 2 for x in xs) / TRIALS
        n = ceil(((z(0.975) * 1.5 + z(0.90) * sqrt(v)) / (4.5 - m)) ** 2)
        print("   {:7s} mean changes {:.2f} (null 4.50); one-spread power"
              " {:.3f}".format(name, m, power))
        print("           spreads needed (two-sided 0.05, power 0.90): {}"
              .format(n))
#    exact null: P(changes <= 2) = 0.0898
#    clumpy  mean changes 1.80 (null 4.50); one-spread power 0.741
#            spreads needed (two-sided 0.05, power 0.90): 3
#    packet  mean changes 0.91 (null 4.50); one-spread power 0.946
#            spreads needed (two-sided 0.05, power 0.90): 2

The exact probability of “at most two changes” is 0.0898. Under clumpy riffles the mean number of changes is only 1.80, so a single spread already has power 0.741; under overhand packets the mean is 0.91 and the power 0.946. Averaging the changes over several spreads in a zz test, three and two spreads are enough to detect such clustering with power 0.90. Clustering of reversals is easy to audit: Chapter 8 turns it into a cheap pre-registered study.

Hypothesis · not established

The author’s hypothesis (not yet tested): most hand-turning habits in actual use belong to the packet-turning kind, so reversals come in runs in real spreads markedly more often than the independent model allows. What would show it wrong: if the shuffle audit of Chapter 8, with an adequate sample, finds a mean number of changes not significantly different from 4.5, the hypothesis fails.

Summary

A 78-card deck needs eight GSR riffles before the total variation falls below 0.5, but riffles produce no reversals. Whether reversals are independent depends on the turning action: one split followed by a fine riffle is close to independent, while clumpy drops or turned packets push the correlation to between 0.597 and 0.774.

References

Bayer, Dave, and Persi Diaconis. 1992. “Trailing the Dovetail Shuffle to Its Lair.” The Annals of Applied Probability 2 (2): 294–313.
Wald, Abraham, and Jacob Wolfowitz. 1940. “On a Test Whether Two Samples Are from the Same Population.” The Annals of Mathematical Statistics 11 (2): 147–62.

Fan, Y. (2026). Tarot Hypergeometric Sampling, Lenormand Grid Topology and Kabbalistic Tree Graphs: Reversal Binomial Mixtures, Grand-Tableau Manhattan Distances and Twenty-Two-Edge Spectral Centrality [塔罗超几何抽样、雷诺曼网格拓扑与卡巴拉生命树图论] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090191 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).