随机投票问题

Posted on 2025-03-08 Waline:

现有 $n$ 人参与投票游戏：设每人均匀随机地选择剩余 $n-1$ 人的其中一人，将其序号投入投票箱，最后从投票箱中统计每人获得的票数。设没有获得任何票的人的数目为 $X$，获得了至少两票的人的数目为 $Y$。求：

概率分析的解答

考虑为每个从第 $i$ 人到第 $j$ 人的投票行为构建边 $(i,j)$，则可以得到一个投票图 $G_n$。

若要 $X= 0 $，则 $G_n$ 的所有顶点都必须处于一个环中，该环的长度可能为 $2, 3, \dots, n$。

记 $f_n$ 为合法（$X=0$ 成立）的 $G_n$ 的个数。

考虑从合法的 $G_{n-1}$ 转移到合法的 $G_n$ 来。此时我们需要将一个顶点插入环内，且每个可插入的点都是一个 $G_{n-1}$ 的边。那么

\[ f_n = (n-1) f_{n-1} \]

一种插入方法如下图所示：

还有一种插入方法如下图所示：

等等，似乎还是漏了什么。我们发现，这样只会产生长度大于 $2$ 的环，长度等于 $2$ 的环永远无法从 $G_{n-1}$ 的“插入”中产生。为此，考虑从 $G_{n-2}$ 转移而来，只需构造一个长度为 $2$ 的环。下面是一个从 $G_4$ 转移到 $G_6$ 的例子：

于是，完整的转移方程为

\[ f_n = (n-1) f_{n-1} + (n-2) f_{n-2} \]

初值条件为 $f_1 = 0, f_2 = 1$。由 OEIS，可以证明，$f_n = O(n!)$。

由于所有可能的投票方式有 $(n-1)^n $ 个，故

\[ P(X=0) = \frac{f_n}{(n-1)^n}. \]

为使 $X=1$，我们考虑从 $X=0$ 的图转移而来。

为了方便阐述，我们将入度为 $0$ 的顶点称为“叶”，将叶到第一个入度大于 $1$ 的顶点形成的路径（不含此顶点）称为“枝”。如图所示：

于是，合法的转移操作就是在 $X=0$ 的 $G_{n-i}$ 上添加一个“枝”，设“枝”的长度为 $i$，那么就得到了一个 $X=1$ 的 $G_{n}$。

记 $g_n$ 为合法（$X=1$ 成立）的 $G_n$ 的个数。由于对 $G_{n-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} \]

为使 $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}. \]

记 $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}$。

同理，获得了至少两票的人的期望数目 $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}$。

下面几句话都是胡说八道。

当社会上的所有人自由交往时：