Posts

谁是小丑

存在任意多个风和日丽的下午，同事们会一起拼单喝咖啡，然后从拼单的 nn 个人里随机选出一个幸运儿前往店里自提。热心同事 Q 担任荷官每次拼单后为大家开盘，他在群里提出了这样的问题：

思考了一会儿这个轮盘赌的问题，怎么通过赌博记录来评估一个人运气有多好?

换句话说，怎么用一个百分数来表示 ta 的胜率?

每一局参与人数不一样，显然输掉 55 人的局要比输掉 22 人的局更小丑

L 算法

没有什么能比有趣的问题更让人兴奋的了，我放下手头工作小摸了一会鱼设计了这样一个算法：

Li={pi−1pi第 i 次赢了0第 i 次输了L=∑i=1nLin\begin{align*} L_i &= \begin{cases} \frac{p_i-1}{p_i}\quad\text{第\ i\ 次赢了} \\ 0\hspace{0.78cm}\text{第\ i\ 次输了} \end{cases} \newline L &= \frac{\sum_{i=1}^{n} L_i}{n} \end{align*}

并且在两个例子上稍微验证了一下：

[Example 1]:

总共 33 局，人数分别是 22, 33, 44.

甲、乙三局都参加了，其中甲输了第一局，乙输了第三局

L甲=23+343=8+93⋅12=1736L乙=12+233=6+83⋅12=1436\begin{align*} L_{\text{甲}} &= \frac{\frac{2}{3} + \frac{3}{4}}{3} = \frac{8+9}{3\cdot 12} = \frac{17}{36} \newline L_{\text{乙}} &= \frac{\frac{1}{2} + \frac{2}{3}}{3} =\frac{6+8}{3\cdot 12} = \frac{14}{36} \end{align*}

故甲更幸运，乙更小丑

[Example 2]:

总共 nn 局 (n>=10)(n>=10)，每局人数都为 pp. 其中甲输了 55 局，乙输了 1010 局

L甲=(n−5)p−1pn=(n−5)(p−1)npL乙=(n−10)p−1pn=(n−10)(p−1)np\begin{align*} L_{\text{甲}} &= \frac{(n-5)\frac{p-1}{p}}{n} = \frac{(n-5)(p-1)}{np} \newline L_{\text{乙}} &= \frac{(n-10)\frac{p-1}{p}}{n} = \frac{(n-10)(p-1)}{np} \end{align*}

显然 n−5>n−10n-5>n-10 故甲更幸运，乙更小丑

Q 算法

Q 也提出了一套算法：

我想到了一种角度，1 把 XX 人局可以看作 loser 和其他人的 X−1X-1 把 2 人局对决

  • loser 参与局数 +X−1X-1，输掉的局数 +X−1X-1

  • 其它人参与局数 +11，输掉的局数 +00

Example 1（输的局人越多越小丑）

总共 33 局，人数分别是 22, 33, 44，甲、乙三局都参加了

甲输了第 11 局，输率 (1+0+0)/(1+1+1)=1/3(1+0+0)/(1+1+1)=1/3

乙输了第 33 局，输率 (0+0+3)/(1+1+3)=3/5(0+0+3)/(1+1+3)=3/5

Example 2（人数相同的局）

甲、乙参加 33 人局，玩了 55 局

甲输了第 11 局和第 22 局，输率 (2+2+0+0+0)/(2+2+1+1+1)=4/7(2+2+0+0+0)/(2+2+1+1+1)=4/7

乙输了第 33 局和第 44 局，输率 (0+0+2+2+0)/(1+1+2+2+1)=4/7(0+0+2+2+0)/(1+1+2+2+1)=4/7

丙输了第 55 局，输率 (0+0+0+0+2)/(1+1+1+1+2)=1/3(0+0+0+0+2)/(1+1+1+1+2)=1/3

推论（Example 2 的泛化）

甲参加 pp 人局，玩了 nn 局，输了 xx 局

输率为 x⋅(p−1)(x⋅(p−1)+(n−x)⋅1)=x⋅(p−1)(x⋅(p−2)+n)\frac{x \cdot (p-1)}{(x \cdot (p-1) + (n-x) \cdot 1)} = \frac{x \cdot (p-1)}{(x \cdot (p-2)+n)}

  • p=2p=2 时，结果是 x/nx/n

  • p=3p=3 时，结果是 2x/(x+n)2x/(x+n)

  • p=4p=4 时，结果是 3x/(2x+n)3x/(2x+n)

  • p=5p=5 时，结果是 4x/(3x+n)4x/(3x+n)

  • ...

在只参加了一局并且赢的情况下 Q=1Q=1，更像一个「胜率」。QQ 的性质比 LL 看起来更好，但我总觉得哪里奇怪。夜半到家后继续思考这个问题，果然构造出来一些反例：

[Example 3]:

甲只参加了一次 33 人局并且赢了，乙只参加了一次 22 人局并且赢了。按照前面的两个算法

Q甲=22=1Q乙=11=1L甲=23L乙=12\begin{align*} Q_{\text{甲}} &= \frac{2}{2} = 1 \\ Q_{\text{乙}} &= \frac{1}{1} = 1 \end{align*} \quad \begin{align*} L_{\text{甲}} &= \frac{2}{3} \\ L_{\text{乙}} &= \frac{1}{2} \end{align*}

那么在 QQ 中，甲和乙同等幸运；在 LL 中，甲比乙幸运。但显然，乙应当比甲更幸运。

[Example 4]:

甲只参加了一次 33 人局并且输了，乙只参加了一次 22 人局并且输了。那么我们可以计算出

Q甲=0Q乙=0L甲=0L乙=0\begin{align*} Q_{\text{甲}} &= 0 \\ Q_{\text{乙}} &= 0 \end{align*} \quad \begin{align*} L_{\text{甲}} &= 0 \\ L_{\text{乙}} &= 0 \end{align*}

那么在 QQ 和 LL 中，甲乙同样小丑。但按照最初的定义，甲才是小丑。

问题出在哪里呢?

只要甲、乙参加的赌局不同，对比 QQ 和 LL 的值决定谁更小丑的算法似乎就会失效。仔细一思考，QQ 和 LL 都是某种胜率的「变种」1，我们总有 0≤Q,L≤10 \leq Q,L \leq 1。一旦计算出 QQ 和 LL 的值，我们就损失了其中每一局参与人数的信息，假如甲、乙没有参加相同的赌局，QQ 和 LL 自然也就无法对比。

实际上我们可以通过简单的推理得到，任何用类似「胜率」来对比的算法都要求 ∀p≥2\forall p \geq 2: 甲和乙参与 pp 人局的次数相同。

S 算法

不如放弃对胜率的执念? 一个人参加许多次赌局，所有可能的结果如同二项式一般在眼前展开。对于每一种可能的输赢的序列，达成这条路径的概率是每一局达成特定结果的概率之积。我试图把乘积的运算变成某种可加性，于是有了 S 算法：

Si={−ln⁡pi−1pi>0第 i 次赢了ln⁡1pi<0第 i 次输了\begin{align*} S_i &= \begin{cases} \begin{aligned} -\ln{\frac{p_i-1}{p_i}}&\gt 0 \quad\text{第 i 次赢了} \\ \ln{\frac{1}{p_i}}&\lt 0\quad\text{第 i 次输了} \end{aligned} \end{cases} \end{align*}

可以验证对于 Example 1，有乙更小丑

S甲=ln⁡12−ln⁡23−ln⁡34=0S乙=−ln⁡12−ln⁡23+ln⁡14=−ln⁡43≈−0.288<S甲\begin{align*} S_{\text{甲}} &= \ln{\frac{1}{2}} - \ln{\frac{2}{3}} - \ln{\frac{3}{4}} = 0 \newline S_{\text{乙}} &= -\ln{\frac{1}{2}} - \ln{\frac{2}{3}} + \ln{\frac{1}{4}} = -\ln{\frac{4}{3}}\\ & \approx -0.288 \lt S_{\text{甲}} \end{align*}

对于 Example 2 的推广：某人参加 pp 人局，玩了 nn 局，输了 xx 局，有

S=x⋅ln⁡1p−(n−x)⋅ln⁡p−1p=ln⁡((1p)x/(p−1p)n−x)=ln⁡pn−2x(p−1)n−x\begin{align*} S &= x \cdot \ln{\frac{1}{p}} - (n-x) \cdot \ln{\frac{p-1}{p}}\\ &= \ln{((\frac{1}{p})^x/(\frac{p-1}{p})^{n-x})}\\ &= \ln{\frac{p^{n-2x}}{(p-1)^{n-x}}} \end{align*}

可以证明 nn, xx 相同时，SS 单调递减。这和定义相符：参加人多的局输掉的人更小丑。

同时 Example 3 和 Example 4 中，我们也可以对比出谁更小丑：

S甲@3=ln⁡23≈0.31S乙@3=−ln⁡12≈0.69S甲@4=ln⁡13≈−1.10S乙@4=ln⁡12≈−0.69\begin{align*} S_{\text{甲@3}} &= \ln{\frac{2}{3}} \approx 0.31 \newline S_{\text{乙@3}} &= -\ln{\frac{1}{2}} \approx 0.69 \end{align*} \quad \begin{align*} S_{\text{甲@4}} &= \ln{\frac{1}{3}} \approx -1.10 \newline S_{\text{乙@4}} &= \ln{\frac{1}{2}} \approx -0.69 \end{align*}

这个算法还有一个性质：对于相同概率的事件，获得的奖励/惩罚是相同的。例如甲参加了一次六人局输掉了，那么会被扣掉 ln⁡16≈1.79\ln{\frac{1}{6}} \approx 1.79 的积分，他需要连续赢 1010 次六人局 10⋅ln⁡56≈1.8210 \cdot \ln{\frac{5}{6}} \approx 1.82 才能把积分赢回来，因为 (56)10≈0.162≈16(\frac{5}{6})^{10} \approx 0.162 \approx \frac{1}{6}.

等等，那少的积分到哪里去了? 我稍微计算了一下，假设一局有 pp 个人，那么这局结束后所有人获得/失去的积分之和

S∗=ln⁡1p−(p−1)⋅ln⁡p−1pS^*= \ln{\frac{1}{p}} - (p-1) \cdot \ln{\frac{p-1}{p}}

可以证明 ∀p>2,S∗<0\forall p \gt 2,S^* \lt 0，并且人数越多，消失的积分就会越多。这是一个负和博弈！玩了 100 局的人几乎肯定比只玩了一局的人要小丑，甚至玩得越久人越小丑 🤡。

赌场算法

我希望有这样的一个性质：每一局所有人的分数增减之合为 00，也就是博弈论入门常常提到的零和博弈赌博。每场赌局之后，输掉的人给其他所有人发放等额的筹码。假设每个人都收到 11 的筹码，并且我们允许负债，那么在许多次赌局之后，一个人剩下的筹码数量为：

C=∑i=1n{1第 i 次赢了−pi第 i 次输了C = \sum_{i=1}^n \begin{cases} \begin{aligned} 1 \quad & \text{第\ i\ 次赢了} \\ -p_i \quad & \text{第\ i\ 次输了} \end{aligned} \end{cases}

看起来通过了前面提到的所有 example，但很快又一个例子被构造出来了。

[Example 5]:

甲乙丙三人总是一起拼单，在一起参与的 nn 局中甲全部输掉了。某天甲离职了，与此同时新加入了一位同事丁。此时谁是小丑?

按照赌场算法，离职后乙丙剩余的筹码都为正，那么新加入的丁没有筹码就会变成新的小丑，这看起来不太合理。我们当然可以在人离职后重新分配他的筹码，但这样并不优雅。假使他只是暂时不参与，但哪天他想要重新加入呢?

离差和

按照这样的逻辑继续思考，我们需要要求参与赌局的所有人中任意选择 nn 个人的筹码总和也为 00，进一步可以推理出来任何一个人的筹码总数恒为 00。零和的约束，是否过于严苛，导致不存在这样的算法呢?

于此同时，我也在向另一个方向思考，S 算法是否能按照局数和参加人数进行某种放缩? 不过我卡住了。我把文章发给 Q，收到了一些新的想法：

更像是每个人有个能力值，会影响对局

然后根据对局记录去还原那个能力值

我沿着这个方向思考了一下。如果的确有这样的一个能力值，那么它实际上衡量的是这个人投骰子的均匀性。如果我们进行足够多的赌局，那么大数定律会使所有人都应该计算出相同的值——赌局是公平的，骰子不会偏好任何一个人。

直到第二天睡前突然顿悟，在足够多的局数之后讨论这个问题是没有意义的，所有人都不比另一个人小丑或幸运。我们要试图刻画的是这个随机序列在局部上的不均匀性。我们想要知道的是一个人得到了多少命运女神的垂青，也就是「这个人的骰子」与「标准骰子」的偏差 (Deviation)。

假设某人在一次 pp 人局中获胜，那么这一局的胜率是 11，而标准骰子的胜率为 p−1p\frac{p-1}{p}，那么这个人的骰子与标准骰子偏差为 1−p−1p=1p1-\frac{p-1}{p}=\frac{1}{p}。同理，如果某人在一次 pp 人局中输掉，那么这一局的胜率是 00，而标准骰子的胜率为 p−1p\frac{p-1}{p}，这个人的骰子与标准骰子偏差为 0−p−1p=1−pp0-\frac{p-1}{p}=\frac{1-p}{p}。

di={1pi第 i 次赢了1−pipi第 i 次输了Di=∑n=1idn\begin{gather*} d_i = \begin{cases} \begin{align*} & \quad \frac{1}{p_i} & \text{第\ i\ 次赢了} \\ \phantom{}\\ & \frac{1-p_i}{p_i} & \text{第\ i\ 次输了} \end{align*} \end{cases} \\ \\ D_i = \sum_{n=1}^{i} d_n \end{gather*}

假如这个人在 66 次六人局中胜负 5:15:1，那么 D=5⋅16−1⋅56=0D=5\cdot\frac{1}{6}-1\cdot\frac{5}{6}=0。把 DiD_i 当作随机变量，无论 pp 是多少，都有 E(Di)=0E(D_i)=0. 我们得到了一种更弱的零和2：

Pr(lim⁡n→∞∑i=1nDi=0)=1Pr(\lim_{n \to \infty} \sum_{i=1}^{n} D_i = 0) = 1

这就是我实际上想要找到的性质：不必每一局都达成零和，而是任意多个人的分数之和在足够多的局数后收敛到零。而 S 算法的失败，正是因为 lim⁡n→∞∑i=1nSi=−∞\lim_{n \to \infty} \sum_{i=1}^{n} S_i = -\infty 发散。

因此例五并不足以构成一个反例，因为乙和丙确确实实地得到了命运的青睐。

如果把每局的实际胜率作为随机变量，这个算法中「某人的骰子」与「标准骰子」的偏离 DiD_i，就是统计学里一个少见的概念：离差/Deviation3。而赌场算法也是以筹码得失为随机变量的离差之和，两者本质无差。

离差之和，就是这个问题的答案。




后记

在整理文章查证名词使用是否准确的时候，我在随机序列的维基百科中发现了一个名词「鞅」。可以容易验证，离差和是一个鞅：

∀n∈N:E(∣Dn∣)=0<∞E(Dn+1∣D1,…,Dn)=0=Dn\begin{align*} \forall n \in \mathbb{N}:& E(\lvert D_n \rvert) = 0 \lt \infty\\ & E(D_{n+1}|D_1, \ldots, D_{n}) = 0 = D_n \end{align*}

在那个兴奋到难以入睡的夜晚，
我发现了一个被前人发现过的概念。

  1. 即至少满足全胜时胜率为 11，全败时胜率为 00 的性质之一，且 0≤X≤10 \leq X \leq 1。 我们可以构造一串人: ∀p≥2,∃x:x\forall p \geq 2, \exists x: x 参加了一次 pp 人局并且赢/输了。但按照定义，pp 越大，赢得越不幸运，输得越小丑。 ↩

  2. 由大数定律 ↩

  3. 我怀疑大学概率论是否真的学过这个东西 ↩

Loading New Comments...