存在任意多个风和日丽的下午,同事们会一起拼单喝咖啡,然后从拼单的 n 个人里随机选出一个幸运儿前往店里自提。热心同事 Q 担任荷官每次拼单后为大家开盘,他在群里提出了这样的问题:
思考了一会儿这个轮盘赌的问题,怎么通过赌博记录来评估一个人运气有多好?
换句话说,怎么用一个百分数来表示 ta 的胜率?
每一局参与人数不一样,显然输掉 5 人的局要比输掉 2 人的局更小丑
L 算法
没有什么能比有趣的问题更让人兴奋的了,我放下手头工作小摸了一会鱼设计了这样一个算法:
LiL={pipi−1第 i 次赢了0第 i 次输了=n∑i=1nLi并且在两个例子上稍微验证了一下:
[Example 1]:
总共 3 局,人数分别是 2, 3, 4.
甲、乙三局都参加了,其中甲输了第一局,乙输了第三局
L甲L乙=332+43=3⋅128+9=3617=321+32=3⋅126+8=3614故甲更幸运,乙更小丑
[Example 2]:
总共 n 局 (n>=10),每局人数都为 p. 其中甲输了 5 局,乙输了 10 局
L甲L乙=n(n−5)pp−1=np(n−5)(p−1)=n(n−10)pp−1=np(n−10)(p−1)显然 n−5>n−10 故甲更幸运,乙更小丑
Q 算法
Q 也提出了一套算法:
我想到了一种角度,1 把 X 人局可以看作 loser 和其他人的 X−1 把 2 人局对决
Example 1(输的局人越多越小丑)总共 3 局,人数分别是 2, 3, 4,甲、乙三局都参加了
甲输了第 1 局,输率 (1+0+0)/(1+1+1)=1/3
乙输了第 3 局,输率 (0+0+3)/(1+1+3)=3/5
Example 2(人数相同的局)甲、乙参加 3 人局,玩了 5 局
甲输了第 1 局和第 2 局,输率 (2+2+0+0+0)/(2+2+1+1+1)=4/7
乙输了第 3 局和第 4 局,输率 (0+0+2+2+0)/(1+1+2+2+1)=4/7
丙输了第 5 局,输率 (0+0+0+0+2)/(1+1+1+1+2)=1/3
推论(Example 2 的泛化)甲参加 p 人局,玩了 n 局,输了 x 局
输率为 (x⋅(p−1)+(n−x)⋅1)x⋅(p−1)=(x⋅(p−2)+n)x⋅(p−1)
p=2 时,结果是 x/n
p=3 时,结果是 2x/(x+n)
p=4 时,结果是 3x/(2x+n)
p=5 时,结果是 4x/(3x+n)
...
在只参加了一局并且赢的情况下 Q=1,更像一个「胜率」。Q 的性质比 L 看起来更好,但我总觉得哪里奇怪。夜半到家后继续思考这个问题,果然构造出来一些反例:
[Example 3]:
甲只参加了一次 3 人局并且赢了,乙只参加了一次 2 人局并且赢了。按照前面的两个算法
Q甲Q乙=22=1=11=1L甲L乙=32=21那么在 Q 中,甲和乙同等幸运;在 L 中,甲比乙幸运。但显然,乙应当比甲更幸运。
[Example 4]:
甲只参加了一次 3 人局并且输了,乙只参加了一次 2 人局并且输了。那么我们可以计算出
Q甲Q乙=0=0L甲L乙=0=0那么在 Q 和 L 中,甲乙同样小丑。但按照最初的定义,甲才是小丑。
问题出在哪里呢?
只要甲、乙参加的赌局不同,对比 Q 和 L 的值决定谁更小丑的算法似乎就会失效。仔细一思考,Q 和 L 都是某种胜率的「变种」1,我们总有 0≤Q,L≤1。一旦计算出 Q 和 L 的值,我们就损失了其中每一局参与人数的信息,假如甲、乙没有参加相同的赌局,Q 和 L 自然也就无法对比。
实际上我们可以通过简单的推理得到,任何用类似「胜率」来对比的算法都要求 ∀p≥2: 甲和乙参与 p 人局的次数相同。
S 算法
不如放弃对胜率的执念? 一个人参加许多次赌局,所有可能的结果如同二项式一般在眼前展开。对于每一种可能的输赢的序列,达成这条路径的概率是每一局达成特定结果的概率之积。我试图把乘积的运算变成某种可加性,于是有了 S 算法:
Si=⎩⎨⎧−lnpipi−1lnpi1>0第 i 次赢了<0第 i 次输了可以验证对于 Example 1,有乙更小丑
S甲S乙=ln21−ln32−ln43=0=−ln21−ln32+ln41=−ln34≈−0.288<S甲对于 Example 2 的推广:某人参加 p 人局,玩了 n 局,输了 x 局,有
S=x⋅lnp1−(n−x)⋅lnpp−1=ln((p1)x/(pp−1)n−x)=ln(p−1)n−xpn−2x可以证明 n, x 相同时,S 单调递减。这和定义相符:参加人多的局输掉的人更小丑。
同时 Example 3 和 Example 4 中,我们也可以对比出谁更小丑:
S甲@3S乙@3=ln32≈0.31=−ln21≈0.69S甲@4S乙@4=ln31≈−1.10=ln21≈−0.69这个算法还有一个性质:对于相同概率的事件,获得的奖励/惩罚是相同的。例如甲参加了一次六人局输掉了,那么会被扣掉 ln61≈1.79 的积分,他需要连续赢 10 次六人局 10⋅ln65≈1.82 才能把积分赢回来,因为 (65)10≈0.162≈61.
等等,那少的积分到哪里去了? 我稍微计算了一下,假设一局有 p 个人,那么这局结束后所有人获得/失去的积分之和
S∗=lnp1−(p−1)⋅lnpp−1可以证明 ∀p>2,S∗<0,并且人数越多,消失的积分就会越多。这是一个负和博弈!玩了 100 局的人几乎肯定比只玩了一局的人要小丑,甚至玩得越久人越小丑 🤡。
赌场算法
我希望有这样的一个性质:每一局所有人的分数增减之合为 0,也就是博弈论入门常常提到的零和博弈赌博。每场赌局之后,输掉的人给其他所有人发放等额的筹码。假设每个人都收到 1 的筹码,并且我们允许负债,那么在许多次赌局之后,一个人剩下的筹码数量为:
C=i=1∑n{1−pi第 i 次赢了第 i 次输了看起来通过了前面提到的所有 example,但很快又一个例子被构造出来了。
[Example 5]:
甲乙丙三人总是一起拼单,在一起参与的 n 局中甲全部输掉了。某天甲离职了,与此同时新加入了一位同事丁。此时谁是小丑?
按照赌场算法,离职后乙丙剩余的筹码都为正,那么新加入的丁没有筹码就会变成新的小丑,这看起来不太合理。我们当然可以在人离职后重新分配他的筹码,但这样并不优雅。假使他只是暂时不参与,但哪天他想要重新加入呢?
离差和
按照这样的逻辑继续思考,我们需要要求参与赌局的所有人中任意选择 n 个人的筹码总和也为 0,进一步可以推理出来任何一个人的筹码总数恒为 0。零和的约束,是否过于严苛,导致不存在这样的算法呢?
于此同时,我也在向另一个方向思考,S 算法是否能按照局数和参加人数进行某种放缩? 不过我卡住了。我把文章发给 Q,收到了一些新的想法:
更像是每个人有个能力值,会影响对局
然后根据对局记录去还原那个能力值
我沿着这个方向思考了一下。如果的确有这样的一个能力值,那么它实际上衡量的是这个人投骰子的均匀性。如果我们进行足够多的赌局,那么大数定律会使所有人都应该计算出相同的值——赌局是公平的,骰子不会偏好任何一个人。
直到第二天睡前突然顿悟,在足够多的局数之后讨论这个问题是没有意义的,所有人都不比另一个人小丑或幸运。我们要试图刻画的是这个随机序列在局部上的不均匀性。我们想要知道的是一个人得到了多少命运女神的垂青,也就是「这个人的骰子」与「标准骰子」的偏差 (Deviation)。
假设某人在一次 p 人局中获胜,那么这一局的胜率是 1,而标准骰子的胜率为 pp−1,那么这个人的骰子与标准骰子偏差为 1−pp−1=p1。同理,如果某人在一次 p 人局中输掉,那么这一局的胜率是 0,而标准骰子的胜率为 pp−1,这个人的骰子与标准骰子偏差为 0−pp−1=p1−p。
di=⎩⎨⎧pi1pi1−pi第 i 次赢了第 i 次输了Di=n=1∑idn假如这个人在 6 次六人局中胜负 5:1,那么 D=5⋅61−1⋅65=0。把 Di 当作随机变量,无论 p 是多少,都有 E(Di)=0. 我们得到了一种更弱的零和2:
Pr(n→∞limi=1∑nDi=0)=1这就是我实际上想要找到的性质:不必每一局都达成零和,而是任意多个人的分数之和在足够多的局数后收敛到零。而 S 算法的失败,正是因为 limn→∞∑i=1nSi=−∞ 发散。
因此例五并不足以构成一个反例,因为乙和丙确确实实地得到了命运的青睐。
如果把每局的实际胜率作为随机变量,这个算法中「某人的骰子」与「标准骰子」的偏离 Di,就是统计学里一个少见的概念:离差/Deviation3。而赌场算法也是以筹码得失为随机变量的离差之和,两者本质无差。
离差之和,就是这个问题的答案。
后记
在整理文章查证名词使用是否准确的时候,我在随机序列的维基百科中发现了一个名词「鞅」。可以容易验证,离差和是一个鞅:
∀n∈N:E(∣Dn∣)=0<∞E(Dn+1∣D1,…,Dn)=0=Dn在那个兴奋到难以入睡的夜晚,
我发现了一个被前人发现过的概念。