5D Library › 塔罗超几何抽样、雷诺曼网格拓扑与卡巴拉生命树图论 · English

第二章 洗牌、混合时间与正逆位的相关结构

交叉洗牌要洗几次

最常被研究的洗牌模型是吉尔伯特-香农-里兹(GSR)交叉洗牌:按二项分布把牌切成两叠,再按两叠剩余张数的比例一张一张落下。贝耶与迪亚科尼斯证明,kk 次交叉洗牌之后,一个有 rr 个上升序列的排列出现的概率只取决于 rr,从而可以精确算出与均匀分布的全变差距离 (Bayer and Diaconis 1992)。

推导

# 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

对 52 张牌,七次交叉洗牌后全变差第一次降到 0.5 以下(0.3341),这就是「洗七次」的来历。78 张塔罗牌需要八次(0.3065);第七次时仍为 0.5713。经验公式 32log⁡2n\tfrac{3}{2}\log_2 n 给出 8.55 与 9.43 次,说明全变差的陡降大约出现在这个次数附近。图 2 画出两条曲线。

GSR 交叉洗牌次数与全变差距离:52 张与 78 张(p03)。

这一结果只说明牌的顺序混合得多快。交叉洗牌从不把任何一张牌转过来,所以它对正逆位毫无作用:一副全部正位的牌洗一百次仍然全部正位。正逆位只能来自另一类动作,即把牌或一叠牌转一百八十度。

正逆位从哪里来

程序比较三类翻牌习惯,每类都从全部正位的牌开始。「硬币」:每张牌独立地以二分之一的概率翻转。「对切转半」:从中间附近切开,把上半叠转过来,再交叉洗一次,重复 1、3、7 次;「成团落牌」是同样的动作,但交叉洗时一次落下一小团牌(平均 2.5 张)。「分叠手洗」:把牌分成大小服从几何分布(平均 5 张)的小叠移到新的一堆,每一叠以二分之一的概率整体转过来。

推导

# 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

在独立翻牌下,78 张牌相邻两张逆位状态的样本相关系数的期望为 −1/77-1/77,即 −0.013,平均游程长度为 1.97,前十张中逆位张数的方差为 2.50。对切转半再按 GSR 交叉洗一次就已经得到与独立翻牌几乎相同的结果(−0.013、1.97、2.52):原因是 GSR 落牌把两叠的标签排成一个均匀随机的二元序列。但若交叉洗得不细,成团落下,相关系数升到 0.597,平均游程 4.79,前十张逆位数的方差 7.62;分叠手洗的相关系数为 0.774,平均游程 8.97,方差 13.59,是独立情形的五倍以上。

证据

结论:逆位的分布取决于翻牌的物理过程。 只有当翻牌动作能把相邻的牌打散时,逆位才接近独立的 p=0.5p = 0.5 二项分布;成叠转牌会产生显著的游程聚集。这是洗牌的力学性质,与牌义无关。

一次牌阵能不能看出聚集

在独立翻牌下,前十张牌相邻状态改变的次数服从二项分布 B(9,1/2)B(9, 1/2),均值 4.5,标准差 1.5,所以游程检验可以精确计算 (Wald and Wolfowitz 1940)。

推导

# 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

「改变不超过两次」的精确概率是 0.0898。成团落牌下改变次数的均值只有 1.80,单个牌阵就有 0.741 的把握度;分叠手洗下均值为 0.91,把握度 0.946。若把多个牌阵的改变次数取平均作 zz 检验,三个与两个牌阵就足以以 0.90 的把握度发现这样的聚集。逆位聚集是很容易审计的:第八章把它写成一项低成本的预注册研究。

假说 · 尚未验证

作者的假说(尚未验证): 实际使用中的手工翻牌习惯多数属于成叠转牌一类,因此真实牌阵中逆位成串出现的频率显著高于独立模型。什么会证明它错: 若第八章的洗牌审计在足够样本下得到的平均改变次数与 4.5 无显著差异,这一假说就不成立。

小结

78 张牌需要八次 GSR 交叉洗牌才使全变差降到 0.5 以下,但交叉洗牌不产生逆位。逆位的独立与否取决于翻牌动作:对切转半再细致交叉洗一次接近独立,成团落牌或成叠转牌则使相关系数达到 0.597 到 0.774。

参考文献

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).