随机投票问题
现有 n 人参与投票游戏：设每人均匀随机地选择剩余 n−1 人的其中一人，将其序号投入投票箱，最后从投票箱中统计每人获得的票数。设没有获得任何票的人的数目为 X，获得了至少两票的人的数目为 Y。求：
- P(X=0)
- P(X=1)
- P(X=k)
- E(X)
- E(Y)
概率分析的解答
1
考虑为每个从第 i 人到第 j 人的投票行为构建边 (i,j)，则可以得到一个投票图 Gn。
若要 $X= 0 $，则 Gn 的所有顶点都必须处于一个环中，该环的长度可能为 2,3,…,n。
记 fn 为合法（X=0 成立）的 Gn 的个数。
考虑从合法的 Gn−1 转移到合法的 Gn 来。此时我们需要将一个顶点插入环内，且每个可插入的点都是一个 Gn−1 的边。那么
fn=(n−1)fn−1
一种插入方法如下图所示：
还有一种插入方法如下图所示：
等等，似乎还是漏了什么。我们发现，这样只会产生长度大于 2 的环，长度等于 2 的环永远无法从 Gn−1 的“插入”中产生。为此，考虑从 Gn−2 转移而来，只需构造一个长度为 2 的环。下面是一个从 G4 转移到 G6 的例子：
于是，完整的转移方程为
fn=(n−1)fn−1+(n−2)fn−2
初值条件为 f1=0,f2=1。由 OEIS，可以证明，fn=O(n!)。
由于所有可能的投票方式有 $(n-1)^n $ 个，故
P(X=0)=fn(n−1)n.
2
为使 X=1，我们考虑从 X=0 的图转移而来。
为了方便阐述，我们将入度为 0 的顶点称为“叶”，将叶到第一个入度大于 1 的顶点形成的路径（不含此顶点）称为“枝”。如图所示：
于是，合法的转移操作就是在 X=0 的 Gn−i 上添加一个“枝”，设“枝”的长度为 i，那么就得到了一个 X=1 的 Gn。
记 gn 为合法（X=1 成立）的 Gn 的个数。由于对 Gn−i 而言，这样的“枝”一共有 \binom n i i! 种，可插入的位置有 n-i 个，故
g_n = \sum_{i=1}^n \binom n i i! (n-i) f_{n-i}.
故
P(X=1) = \frac{g_n}{(n-1)^n}
3
为使 X=k，我们考虑从 X=k-1 的图转移而来，为此需要在图中添加一个“枝”。这个“枝”只能加在那些入度不为 0 的顶点上，这样的顶点有 n-(k-1) 个。
并且，应该注意到这样转移会存在重复。考虑 X=k 的一张图，其包含的“枝”的数目为 k，因此我们每次对 X=k-1 的图添加“枝”时，该“枝”必然被重复添加了 k 次（考虑 k=1，k=2 的情况可方便理解）。因此，需要对最终结果除以 k。
记 f_{n,k} 为合法（X=k 成立）的 G_n 的个数，那么
f_{n,k} = \frac{1}{k} \sum_{i=1}^{n-k+1} \binom n i i! (n-i-k+1) f_{n-i, k-1}.
故
P(X=k) = \frac{f_{n,k}}{(n-1)^n}.
期望分析的解答
1
记 X_i\in\{0,1\} 表示“第 i 个人没有得票”，则
P(X_i = 1) = \left(\frac{n - 2}{n-1} \right)^{n-1}
故 E(X_i)=\left(\frac{n - 2}{n-1} \right)^{n-1}，没有得票的人的期望数目 $E(X_i) = E(X_i) =n ( )^{n-1} $。当 n 充分大时，E(\sum X_i) = \frac{n}{\mathrm e}。
2
同理，获得了至少两票的人的期望数目 E(\sum Y_i) = \sum E(Y_i) = n - \left(2n - \frac{n}{n-1} \right) n\left(\frac{n - 2}{n-1} \right)^{n-2}。
当 n 充分大时，E(\sum Y_i) = n - \frac{2n}{\mathrm e}。
社会意义
下面几句话都是胡说八道。
当社会上的所有人自由交往时：
- 大概有 1/\mathrm e 的人不会受到任何人的青睐。
- 大概有 1 - 2/ \mathrm e 的人会受欢迎。
预览: