这个新的体育评分方法使用了马尔可夫的一个老技术, 因此我 们称之为马尔可夫法 。1906 年, 马尔可夫发明了他的那些之后被 命名为马尔可夫链的方法, 它们用于对随机过程进行描述。尽管马 尔可夫最初将他的方法用于对普希金的诗歌《叶甫盖尼 - 奧涅金》 中的原音和辅音序列进行语言分析, 但自那时以来, 这些链得到了太多太多的应用 。

马尔可夫法的主要思想

马尔可夫评分法可以用一个词来总结：投票。两支队伍之间的每次较量, 都是弱队 给强队投票的机会。

可以有许多方法来衡量对队伍所投的票。最简单的投票方法可能得算是使用胜负情况。失利的队伍为每支击败它的队伍投出一票。更高级的模型则考虑了比赛中的得分。在 这种情况下, 负者投出的票数等于它在与更强的对手交手时输掉的分差。一个再高级些的 模型则是让两支队伍分别向对方投出与各自失分相等数量的选票。最终, 获得票数最多的 队伍将䛙得最高排名。这个思想实际上是谷歌用来进行网页排名的 PageRank 算法的一个 修改。正如第 71 页的讨论所说明的那样, 在这一建模过程中可以进行微调的地方简直数不胜数, 不过, 在介绍各种增强功能之前, 先来直接试一试我们的范例。

利用胜负进行投票

仅使用胜负数据的投票矩阵 $\boldsymbol{V}$ 如下所示。 $\left.\begin{array}{cccccc} & \text { Duke } & \text { Miami } & \text { UNC } & \text { UVA } & \text { VT } \\ \text { Duke } & 0 & 1 & 1 & 1 & 1 \\ \text { Miami } & 0 & 0 & 0 & 0 & 0 \\ =\text { UNC } & 0 & 1 & 0 & 0 & 1 \\ \text { UVA } & 0 & 1 & 1 & 0 & 1 \\ \text { VT } & 0 & 1 & 0 & 0 & 0\end{array}\right)$

由于杜克大学输给了所有的对手，因此, 它为其他每支队伍投出了权重相等的票数。为了 从这个投票矩阵中梳理出一个排名向量, 我们要对 $\boldsymbol{V}$ 中各行进行归一化, 以此来产生一个 (接近于) 随机的矩阵 $\boldsymbol{N}$

$\left.\begin{array}{cccccc} & \text { Duke } & \text { Miami } & \text { UNC } & \text { UVA } & \text { VT } \\ \text { Duke } & 0 & 1 / 4 & 1 / 4 & 1 / 4 & 1 / 4 \\ \text { Miami } & 0 & 0 & 0 & 0 & 0 \\ =\text { UNC } & 0 & 1 / 2 & 0 & 0 & 1 / 2 \\ \text { UVA } & 0 & 1 / 3 & 1 / 3 & 0 & 1 / 3 \\ \text { VT } & 0 & 1 & 0 & 0 & 0\end{array}\right)$

$\boldsymbol{N}$ 目前是准随机的, 因为迈阿密大学末尝败绩。这与网页排名领域中众所周知的悬挂结点 问题类似。在网页排名领域中对这个问题的解决方法, 是将所有的全 0 行 $\mathbf{0}^{\mathrm{T}}$ 用 $1 / n \boldsymbol{e}^{\mathrm{T}}$ 来代替。我们在此借用这一思路, 使得 $\boldsymbol{N}$ 变为一个随机矩阵 $S_{\text {。 }}$ $\left.\begin{array}{cccccc} & \text { Duke } & \text { Miami } & \text { UNC } & \text { UVA } & \text { VT } \\ \text { Duke } & 0 & 1 / 4 & 1 / 4 & 1 / 4 & 1 / 4 \\ \text { Miami } & 1 / 5 & 1 / 5 & 1 / 5 & 1 / 5 & 1 / 5 \\ \text { UNC } & 0 & 1 / 2 & 0 & 0 & 1 / 2 \\ \text { UVA } & 0 & 1 / 3 & 1 / 3 & 0 & 1 / 3 \\ \text { VT } & 0 & 1 & 0 & 0 & 0\end{array}\right)$

尽管悬挂结点（没有出链的页面）在万维网环境中十分常见, 但在一个完整的体育 赛季期间, 它们却极为罕见。

再次模仿网页的 PageRank 算法, 我们计算出这个随机矩阵的稳态向量。该稳态向量即为 $S$ 的主特征向量, 可通过求解特征系统 $\boldsymbol{S r}=\boldsymbol{r}$ 来得到 。下面的小故事简要解释了使用稳态向量来作为队伍排名方法的理由。故事的主角是一名墙头草式的球迷，他或她总是支持当前最好的那支队伍。矩阵 $S$ 可用如图所示的图来表示。这名墙头草球迷由这个网络中 的任一结点开始, 并根据离开当前所支持队伍的链接来选择他要支持的下一支队伍。例如， 如果该球迷从 UNC 开始, 并问 UNC：“谁是最好的队伍?” UNC 将会回答：“迈阿密大学或 $\mathrm{VT}$, 因为他们都击败了我们。”于是这个球迷将接着靠扔硬币来决定要支持的队伍, 并假设 他选中了 VT, 之后他又继续询问相同的问题。这一次, VT 将回答说迈阿密大学是最好的队 伍, 因此他又跳上了迈阿密大学的彩车。一到了迈阿密大学的营地后, 他又提出了他的问题。不过由于迈阿密大学末曾被击败, 因此他随机地跳到其他队伍中的任意一支。（这是由于我们增加了 $1 / 5 e^T$ 这一行的缘故, 不过还有其他几种巧妙的策略可以处理从未告负的球队,

同时仍然能够给出具有良好收敛性能的马尔可夫链。请见第 73 页。）如果墙头草球迷一直 如此行事, 而我们则对他在每支队伍上停留的时间比例加以监视, 那么我们就能得到各支 队伍重要程度的一个衡量。墙头草球迷访问得最为频笅的那支队伍就是排名最高的队伍, 因为该球迷总是从其他强队那里被引向这支队伍。从数学上来说, 这名墙头草球迷就是在 由一条马尔可夫链所定义的图上进行了一次随机游走, 而他在相当长的时间内在链的各个 状态上消耗的时间比例, 就正好是该链的稳态向量或主特征向量。对于这个 5 支队伍的例 子而言, $S$ 的稳态评分向量 $r$ 和相应的排名如表所示。

马尔可夫评分方法总结

下面的阴影框归总了我们在描述体育队伍排名的马尔可夫方法中所使用的记法。

队伍评分的马尔可夫法

  1. 利用感兴趣的 $k$ 种比赛统计数据的投票矩阵来生成 $S_{\text {。 }}$ $$ \boldsymbol{S}=\alpha_1 S_{\text {stat1 }}+\alpha_2 S_{\text {sta12 }}+\cdots+\alpha_k S_{\text {statk }} $$ 式中, $\alpha_i \geqslant 0$, 且 $\sum_{i=1}^k \alpha_i=1$;
  2. 计算 $S$ 的稳态向量或主特征向量 $r_{\circ}$ (如果 $S$ 可约, 则利用不可约的 $\bar{S}=\beta S+(1-$ $\beta) / n \boldsymbol{E}$ 来计算, 其中, $0<\beta<1$ )

资料来源