问题背景 #

假设有一场包含$N$名选手的锦标赛，共进行$M$场比赛。每场比赛所有$N$名选手都会参与，比赛结果是选手的排名列表，根据单场排名发放锦标赛积分。$M$场比赛结束后，选手们根据总积分进行排名。我想知道如何计算某一特定选手最终获得指定排名的概率？

显然，当所有选手总积分相等时（比如锦标赛刚开始时），这个概率是$1/N$。我特别感兴趣的场景是：给定锦标赛的中间积分状态，如何计算这个概率？

示例场景 #

$N=3$，$M=3$，单场比赛排名对应的积分是：第1名10分，第2名5分，第3名0分。

当前中间积分状态：

• 队伍A：10分
• 队伍B：5分
• 队伍C：0分

请问队伍A最终获得第2名的概率是多少？

我的尝试与困境 #

注：我意识到下面的方法没有正确处理平局情况，在此致歉。

手动枚举法 #

我最初的朴素思路是手动枚举所有可能的结果。总可能的比赛结果数是$N!^{M_{\text{剩余}}$，在这个示例中还剩2场比赛，所以是$3!}2=36$种可能。我统计了其中队伍A排名第2的情况，得到8种，因此概率是$8/36$。

但这种方法随着$N$或$M$的增大很快就会变得不可行，这正是我的问题所在——我需要一种不需要枚举所有排列就能计算概率的方法。

条件概率法 #

之后我尝试用条件概率计算单轮的情况：
设$S_x$为队伍$x$的总积分，那么：
$$P(\text{A排名第2}) = P(S_b > S_a + 5) + P(S_c > S_a + 10) - P(S_b > S_a + 5 \bigcap S_c > S_a + 10)$$

计算各部分：

• $P(S_c > S_a + 10) = 0$（剩余2场比赛C最多拿20分，A当前10分，总积分最多30分，C不可能超过这个数值）
• $P(S_b > S_a + 5) = P(S_b=10) \times P(S_a=0 | S_b=10) = \frac{1}{3} \times \frac{1}{2} = \frac{1}{6}$

但这种方法很难扩展到多轮比赛，而且对于更大的$N$和$M$来说计算复杂度依然很高。我的直觉告诉我这里有更深层次的组合数学原理，但我没能找到突破口。

我还尝试过拆解子问题，比如计算队伍B在任何排列中超过队伍C的概率，但感觉这没什么用，因为这是一个依赖事件。

备注：内容来源于stack exchange，提问作者squinlan