欧冠淘汰赛抽签的分析

上次简单研究了一下欧冠小组赛的抽签。现在小组赛全部踢完了,14号将举行淘汰赛的抽签仪式。淘汰赛只有16支球队,抽签规则也简化很多,因此可以将问题研究得更加深入一些。

抽签规则

同样,首先看一下抽签规则。

经过6轮小组赛,八个小组的前两名进入淘汰赛。以八个小组第一为第一档,小组第二为第二档。抽签时先从第一档里任意抽出一支球队,然后在可能对阵的第二档球队中随机抽出一支与之对战,依次类推。与小组赛类似,淘汰赛的对阵也有回避原则。

  • 小组赛分组相同的球队要避开。
  • 同一足协下属的球队也需要回避。
  • 乌克兰与俄罗斯球队也不能相互对阵。
  • 淘汰赛抽签不需要考虑收视因素,只需在抽签之后人工调整。

进入淘汰赛的球队分别是:

小组 A B C D E F G H
第一档 皇家马德里 沃尔夫斯堡 马德里竞技 曼彻斯特城 巴塞罗那 拜仁慕尼黑 切尔西 泽尼特
国家 西班牙 德国 西班牙 英格兰 西班牙 德国 英格兰 俄罗斯
第二档 巴黎圣日耳曼 埃因霍温 本菲卡 尤文图斯 罗马 阿森纳 基辅迪纳摩 根特
国家 法国 荷兰 葡萄牙 意大利 意大利 英格兰 乌克兰 比利时

千古奇冤莫耶斯!

理论对阵概率

这里的理论对阵概率,指的是不考虑抽签流程,假设所有可能的抽签结果概率均等,计算各支球队与其他球队相遇的概率。用程序很容易遍历出所有合法的抽签结果,统计各组对战的频数即可得到概率。程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
A = ['ESP','GER','ESP','ENG','ESP','GER','ENG','RUS']
B = ['FRA','NED','POR','ITA','ITA','ENG','UKR','BEL']
pool = []
import itertools
for i in itertools.permutations(range(0,8),8):
for j in range(0,8):
if i[j]==j:
break
else:
pool.append(i)
result = []
for item in pool:
for i in range(0,8):
if B[i]==A[item[i]]:
break
elif A[item[i]]=='RUS' and B[i]=='UKR':
break
else:
result.append(item)
total = len(result)
print 'There are %d kinds of possible results.'%total
teamsA=['Real Madrid','Wolfsburg','Atletico Madrid','Manchester City','Barcelona',
'Bayern Munchen','Chelsea','Zenit']
teamsB=['Paris Saint-Germain','PSV Eindhoven','Benfica','Juventus',
'Roma','Arsenal','Dynamo Kyiv','Gent']
prob_theo = [[0 for col in range(8)] for row in range(8)]
for item in result:
for i in range(0,8):
prob_theo[i][item[i]] += 1
print ' |'+'|'.join(teamsA)
for i in range(8):
print teamsB[i],
for j in range(8):
if prob_theo[i][j] == 0:
print '|0',
else:
prob_theo[i][j] = prob_theo[i][j] / float(total)
print '|%.4f'%prob_theo[i][j],
else:
print ''

计算得知共有9147种可能的抽签结果,概率分布如下:

- 皇家马德里 沃尔夫斯堡 马德里竞技 曼彻斯特城 巴塞罗那 拜仁慕尼黑 切尔西 泽尼特
巴黎圣日耳曼 0 0.1285 0.1285 0.1595 0.1285 0.1373 0.1653 0.1525
埃因霍温 0.1285 0 0.1285 0.1595 0.1285 0.1373 0.1653 0.1525
本菲卡 0.1285 0.1285 0 0.1595 0.1285 0.1373 0.1653 0.1525
尤文图斯 0.1327 0.1327 0.1327 0 0.1327 0.1409 0.1699 0.1583
罗马 0.1285 0.1285 0.1285 0.1595 0 0.1373 0.1653 0.1525
阿森纳 0.1921 0.1921 0.1921 0 0.1921 0 0 0.2317
基辅迪纳摩 0.1583 0.1583 0.1583 0.1979 0.1583 0.1689 0 0
根特 0.1315 0.1315 0.1315 0.1641 0.1315 0.1409 0.1689 0

欧足联抽签流程的分析

那么,欧足联的抽签流程对抽签结果的概率分布会有什么影响呢?以下的分析都出自[1]这篇论文。

首先可以证明,欧足联抽签流程下,任一抽签结果出现的概率具有如下形式:

$$ \frac{m}{8!7^2 5^4 3^6 2^{12}} $$

也就是说,这个概率化简成最简分数的话,分母只有2,3,5,7等4个质因数。之前已经得到,本赛季欧冠淘汰赛抽签共有9147种可能的结果。对9147做质因数分解,得$ 9147 = 3\times 3049 $。可知在欧足联的流程下,每个抽签结果的概率并不相等,换句话说,不是平均分布。假如是平均分布的话,那么每个抽签结果的概率等于1/9147,但是它显然不能表示成上面的形式。作者通过编程计算指出,2012~13赛季欧冠淘汰赛的各个抽签结果的概率,与平均分布概率之间最大的相对偏差超过15%。

既然各个抽签结果并不是等概率的,那么抽签流程也会对两支球队对阵的概率产生影响。我用python写了这部分程序,但是因为用到递归,运行时间非常长,所以就只贴出代码,没有运行结果。也许用其他语言改写一下会好点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import copy
class Node(object):
def __init__(self, parent, node_choice):
self.parent = parent
self.value = copy.copy(parent)
if node_choice != None:
self.value.append(node_choice)
def get_children_choices(self, turn):
return [x for x in turn if x not in self.value]
class Tree(object):
A = ['ESP','GER','ESP','ENG','ESP','GER','ENG','RUS']
B = ['FRA','NED','POR','ITA','ITA','ENG','UKR','BEL']
def __init__(self, node, turn):
self.node = node
self.turn = turn
self.children = []
self.avail = 0
def build(self):
choices = self.node.get_children_choices(self.turn)
if choices:
for i in choices:
cur_node = Node(self.node.value, i)
cur_tree = Tree(cur_node, self.turn)
cur_tree.build()
self.children.append(cur_tree)
if cur_tree.avail:
self.avail += 1
else:
for j in self.turn:
if self.node.value[j]==j or self.B[j]==self.A[self.node.value[j]]:
break
else:
self.avail = 1
class UEFA_draw(object):
result = []
prob = []
def __init__(self, turn):
self.turn = turn
initial_node = Node([],None)
self.tree = Tree(initial_node, turn)
self.tree.build()
def test_avail(self, cur_tree, product):
num_avail = cur_tree.avail * product
if cur_tree.children:
for child in cur_tree.children:
self.test_avail(child, num_avail)
else:
if num_avail != 0:
self.result.append(cur_tree.node.value)
self.prob.append(1.0/num_avail)
if __name__ == "__main__":
teamsA=['Real Madrid','Wolfsburg','Atletico Madrid','Manchester City','Barcelona',
'Bayern Munchen','Chelsea','Zenit']
teamsB=['Paris Saint-Germain','PSV Eindhoven','Benfica','Juventus',
'Roma','Arsenal','Dynamo Kyiv','Gent']
import itertools
prob_cal = [[0 for col in range(8)] for row in range(8)]
for item in itertools.permutations(range(0,8),8):
draw = UEFA_draw(item)
draw.test_avail(draw.tree, 1)
numbers = float(len(draw.result))
for i in range(0,len(draw.result)):
for j in item:
prob_cal[j][draw.result[i][j]] += draw.prob[i]
for i in range(8):
for j in range(8):
prob_cal[i][j] = prob_cal[i][j] / 40320
print prob_cal

根据论文作者对多个赛季的计算结果,实际对阵的发生概率与假设所有结果平均分布的理论概率之间存在偏差,但相对偏差较小,最大的相对偏差不过5%,因此欧足联的抽签流程还算是比较公正的。

作者还计算了抽签流程对球队预期收入的影响,这里就暂时不做介绍了,因为这个计算过程需要预测比赛的胜负,而作者使用的胜负概率模型是最简单的一个,计算的结果就不太准确。况且作者计算的结果,球队的预期收入变化不过几万欧元,还不到很多球星一个星期的工资,这个计算的意义也不大。

抽签流程改进

可不可以重新设计一个抽签流程,让所有合法的结果出现的概率成均匀分布呢?

最容易想到的一条路就是,事先生成所有可能的结果(本赛季有9147种),给它们编号,然后从这些号码中随机抽出一个。具体来讲,可以用类似彩票摇奖的装置,产生一个四位数即可。当然,这种抽签最主要的缺点就是,太无聊了。

于是作者设计了一个新的复杂的方法。首先,用上面的方法随机选出一个合法的结果。然后以它为起点,进行下面的步骤。

  1. (不放回地)随机抽出一个球队A,A目前的对手是B;
  2. 从A的可能的对手中,抽出一个球队C,如果
  • C就是B,则重新进行步骤2;
  • C的对手是D,如果交换B与C之后的结果仍然合规,则交换之,否则保留现有的对阵;
  1. 重复上述步骤。

上述的抽签步骤,实际上可以认为是一个以所有合法的结果为状态空间的马尔科夫链,容易证明其转移状态矩阵是对称的。如果初始状态是均匀分布的话,那么之后每一时刻到达的状态都是均匀分布。也就是说,如果抽签方案的起点选择是等可能的,那么上述的抽签流程可以保证最终的结果仍是均匀分布的。



  1. S. Klößner and M. Becker, “Odd odds: The UEFA Champions League Round of 16 draw,” Journal of Quantitative Analysis in Sports, vol. 9, no. 3, pp. 249–270, Sep. 2013.