数概率

【Puzzle】孪生骑士

字数统计: 1.3k字   |   阅读时长: 6分
,

摘要: 《概率50题》孪生骑士

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

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

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

问题描述

Twin Knights

(a)

Suppose King Arthur holds a jousting tournament where the jousts are in pairs
The 8 knights in the tournament are evenly matched, and they include the twin knights Balin and Balan
What is the chance that the twins meet in a match during the tournament?

(b)

Replace 8 by 2^n in the above problem
Now, what is the chance that they meet?

(a)

8 个骑士进行淘汰赛，对阵图与上图这样的网球对阵图类似。8 个骑士的水平一样，任意一组比赛双方的获胜概率均为 0.5。8 个骑士中有两个人是孪生兄弟。
问: 这两个孪生兄弟在比赛过程中相遇的概率。

(b)

将 8 个骑士的淘汰赛改为 2^n 个人的淘汰赛，问这两个孪生兄弟相遇的概率。

思路参考

(a)

8 个骑士的比赛共有 3 轮，我们一轮一轮地考虑。

记事件 X1 为孪生骑士在第一轮相遇，若想在第一轮相遇，则它们必须同时被分到 (1, 2), (2, 1), (3, 4), (4, 3), (6, 5), (5, 6), (8, 7), (7, 8) 这八种情况之一。概率为

记事件 X2 为孪生骑士在第二轮相遇，若想在第二轮相遇，则需要它们两个被分到以下十六种情况的一种，同时它们两个还要都赢了

1
2
(1, 3), (1, 4), (2, 3), (2, 4), (5, 7), (5, 8), (6, 7), (6, 8) 
(3, 1), (4, 1), (3, 2), (4, 2), (7, 5), (8, 5), (7, 6), (8, 6)

概率为

记事件 X3 为孪生骑士在第三轮相遇，若想在第三轮相遇，需要它们两个其中一个被分到 [1..4] 中的一个，另一个被分到 [5..8] 中的一个。且他们在前两轮的共四场比赛都要赢，概率为

把 X1, X2, X3 这三种情况的概率加起来，得到孪生骑士相遇的概率

(b)

记事件 Xi 为孪生骑士在第 i 轮相遇，其中 i 取值为 1, 2, …, n，共 T = 2^n 人。

对第 i 轮，将 1 ~ 2^n 连续地分为 B = (2^n)/(2^(i-1)) 个桶，每个桶 C = 2^(i-1) 个元素。孪生骑士需要在编号为 (2k+1, 2k+2) 的相邻桶中(k=0,1,…,(2^n)/(2^i) - 1)，相邻桶的组数为 N = (2^n)/(2^i)，孪生骑士在满足要求的桶中的概率为

孪生骑士在第 1,2,…,i-1 轮中，共有 (i-1) * 2 场比赛。这些比赛还要赢，概率为

将两个概率相乘就是孪生骑士在第 i 轮相遇的概率

孪生骑士相遇的概率为

蒙特卡洛模拟

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

def P(n):
    return 1 / (2 ** (n - 1))

def run(n):
    l = np.random.permutation(ladder)
    for _ in range(1, n + 1):
        for i in range(0, len(l), 2):
            if l[i] + l[i + 1] == 1:
                return 1
            if np.random.rand() < 0.5:
                l[int(i / 2)] = l[i]
            else:
                l[int(i / 2)] = l[i + 1]
        l = l[:int(len(l) / 2)]
    return 0

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

def main(n):
    print("n = {}: P(n) = {}".format(n, P(n)))
    args = [n] * 8
    pool = Pool(8)
    ts = pool.map(test, args)
    for t in ts:
        print("P(twin knight meet): {:.6f}".format(t))
    print()

for n in range(3, 7):
    global ladder
    ladder = range(2 ** n)
    main(n)

模拟结果

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
n = 3: P(n) = 0.25           
P(twin knight meet): 0.249970
P(twin knight meet): 0.249815
P(twin knight meet): 0.250011
P(twin knight meet): 0.249984
P(twin knight meet): 0.249990
P(twin knight meet): 0.250079
P(twin knight meet): 0.249889
P(twin knight meet): 0.250108 

n = 4: P(n) = 0.125
P(twin knight meet): 0.124822
P(twin knight meet): 0.124963
P(twin knight meet): 0.124807
P(twin knight meet): 0.125172
P(twin knight meet): 0.124867
P(twin knight meet): 0.124937
P(twin knight meet): 0.124887
P(twin knight meet): 0.124992

n = 5: P(n) = 0.0625
P(twin knight meet): 0.062401
P(twin knight meet): 0.062294
P(twin knight meet): 0.062492
P(twin knight meet): 0.062508
P(twin knight meet): 0.062588
P(twin knight meet): 0.062417
P(twin knight meet): 0.062393
P(twin knight meet): 0.062459

n = 6: P(n) = 0.03125
P(twin knight meet): 0.031231
P(twin knight meet): 0.031373
P(twin knight meet): 0.031206
P(twin knight meet): 0.031259
P(twin knight meet): 0.031189
P(twin knight meet): 0.031246
P(twin knight meet): 0.031311
P(twin knight meet): 0.031256
Share