数概率

【Puzzle】第二强的选手是否拿亚军

字数统计: 652字   |   阅读时长: 3分
,

摘要: 《概率50题》第二强选手是否拿亚军

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

这是概率面试题连载第 14 期，我们继续看 《Fifty challenging problems in probability with solutions》 中的一道题。

往期的内容整理在这篇文章里；或者看这个 github 仓库。

问题描述

Will-Second-Best-Be-Runner-Up

A tennis tournament has 8 players
The number a player draws from a hat decides his first-round rung in the tournament ladder
Suppose that the best player always defeats the second best player, and that the second best player always beats everyone else
The loser of the finals wins the runner up cup
What is the chance that the second-best player wins the runner-up cup?

一场由 8 个人组成的淘汰赛，对阵图如上图。8 个人随机被分到图中的 1~8 号位置。
第二强的人总是会输给最强的人，同时也总是会赢剩下的人。决赛输的人拿到比赛的亚军。
问: 第二强的人拿到亚军的概率是多少。

思路参考

第二强的人拿到亚军，等价于最强的人和第二强的人在决赛遇到，等价于这两个人一个被分到 1~4，另一个被分到 5~8。

x1: 最强的人被分到 1~4
x2: 最强的人被分到 5~8
y1: 第二强的人被分到 1~4
y2: 第二强的人被分到 5~8

第二强的人获得亚军的概率为 2/7+2/7=0.571428

蒙特卡洛模拟

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
import numpy as np
import operator
from multiprocessing import Pool
from functools import reduce

ladder = range(8)

def run():
    l = np.random.permutation(ladder)
    x = int(np.where(l == 0)[0][0])
    y = int(np.where(l == 1)[0][0])
    return (x <= 3 and y >= 4) or (x >= 4 and y <= 3)

def test(T):
    np.random.seed()
    y = (run() for _ in range(T))
    n = reduce(operator.add, y)
    return n / T

T = int(1e7)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("P(the second-best player wins the runner-up cup): {:.6f}".format(t))

模拟结果

1
2
3
4
5
6
7
8
P(the second-best player wins the runner-up cup): 0.571250
P(the second-best player wins the runner-up cup): 0.571030
P(the second-best player wins the runner-up cup): 0.571432
P(the second-best player wins the runner-up cup): 0.571021
P(the second-best player wins the runner-up cup): 0.571379
P(the second-best player wins the runner-up cup): 0.571495
P(the second-best player wins the runner-up cup): 0.571507
P(the second-best player wins the runner-up cup): 0.571226
Share