5D Library › 塔罗超几何抽样、雷诺曼网格拓扑与卡巴拉生命树图论 · English
第二章 洗牌、混合时间与正逆位的相关结构
交叉洗牌要洗几次
最常被研究的洗牌模型是吉尔伯特-香农-里兹(GSR)交叉洗牌:按二项分布把牌切成两叠,再按两叠剩余张数的比例一张一张落下。贝耶与迪亚科尼斯证明, 次交叉洗牌之后,一个有 个上升序列的排列出现的概率只取决于 ,从而可以精确算出与均匀分布的全变差距离 (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。经验公式 给出 8.55 与 9.43 次,说明全变差的陡降大约出现在这个次数附近。图 2 画出两条曲线。
这一结果只说明牌的顺序混合得多快。交叉洗牌从不把任何一张牌转过来,所以它对正逆位毫无作用:一副全部正位的牌洗一百次仍然全部正位。正逆位只能来自另一类动作,即把牌或一叠牌转一百八十度。
正逆位从哪里来
程序比较三类翻牌习惯,每类都从全部正位的牌开始。「硬币」:每张牌独立地以二分之一的概率翻转。「对切转半」:从中间附近切开,把上半叠转过来,再交叉洗一次,重复 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 张牌相邻两张逆位状态的样本相关系数的期望为 ,即 −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,是独立情形的五倍以上。
证据
结论:逆位的分布取决于翻牌的物理过程。 只有当翻牌动作能把相邻的牌打散时,逆位才接近独立的 二项分布;成叠转牌会产生显著的游程聚集。这是洗牌的力学性质,与牌义无关。
一次牌阵能不能看出聚集
在独立翻牌下,前十张牌相邻状态改变的次数服从二项分布 ,均值 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。若把多个牌阵的改变次数取平均作 检验,三个与两个牌阵就足以以 0.90 的把握度发现这样的聚集。逆位聚集是很容易审计的:第八章把它写成一项低成本的预注册研究。
假说 · 尚未验证
作者的假说(尚未验证): 实际使用中的手工翻牌习惯多数属于成叠转牌一类,因此真实牌阵中逆位成串出现的频率显著高于独立模型。什么会证明它错: 若第八章的洗牌审计在足够样本下得到的平均改变次数与 4.5 无显著差异,这一假说就不成立。
小结
78 张牌需要八次 GSR 交叉洗牌才使全变差降到 0.5 以下,但交叉洗牌不产生逆位。逆位的独立与否取决于翻牌动作:对切转半再细致交叉洗一次接近独立,成团落牌或成叠转牌则使相关系数达到 0.597 到 0.774。
参考文献
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).