数概率

【Puzzle】系列赛中不出现平局

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

摘要: 《概率50题》系列赛中不出现平局

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

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

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

本题是关于概率DP的，与上一期 【Puzzle】选票盒 几乎一样，本题就当是复习了。我们来看一下这个题。

问题

Ties-in-Matching-Tennis

Players A and B match pennies N times
They keep a tally of their gains and losses
After the first toss, what is the chance that at no time during the game will they be even?

A 和 B 进行一场 N 轮的系列赛，并记录每一轮胜负，双方在一轮中的获胜概率均为 0.5
问：第1场比赛之后，直到第 n 场比赛比完之后，双方始终没有出现平局的概率

思路参考

假设系列赛已经进行了 i 轮，也就是还剩 N - i 轮，已经进行的 i 轮中有 j 轮(0 <= j <= i)是 A 赢了，i - j 轮是 B 赢了。

在这种假设下，我们定义后续的 N - i 轮中始终没有出现平局的概率为 dp[i][j]。在这种定义下，我们所求的就是 dp[0][0]

dp[i][j] 的边界值

dp[i][j] 的边界值有两部分，一个就是 i = N，即系列赛已经进行 N 轮的时候，后面已经一轮都没有了，自然也就不会在后续轮次中不出现平局，dp[N][j] = 1

另一个就是前面 i 轮比赛中，A 赢的次数 j 比 B 赢的次数 (i - j) 多的次数 k = 2j - i，其绝对值 abs(k) 比剩余的轮数 N - i 还要多了，那后续轮次中肯定也不会出现平局了，此时 dp[i][j] = 1

dp[i][j] 的转移方程

基于全概率公式，我们可以写出 dp[i][j] 的转移方程

1
dp[i][j] = 0.5 * dp[i + 1][j + 1] + 0.5 * dp[i + 1][j]

本轮比赛有两种可能结果，第一种是 A 赢了，概率 pa = 0.5，第二种是 B 赢了，概率 pb = 0.5。分别对应上面的方程的两部分，下面我们分别考虑

  • (1) 本轮比赛 A 赢了

如果此时 k = -1，也就是前 i 轮中 A 比 B 刚好少赢 1 轮，本轮比赛 A 赢了之后就平局了，dp[i + 1][j + 1] = 0

否则需要继续算 dp[i + 1][j + 1]

  • (2) 本轮比赛 B 赢了

如果此时 k = 1，也就是前 i 轮中 A 比 B 刚好多赢 1 轮，本轮比赛 B 赢了之后就平局了，dp[i + 1][j] = 0

否则需要继续算 dp[i + 1][j]

概率 DP

有了以上推导之后，我们就可以用概率 DP 算法计算答案了，算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
状态定义
dp[i][j] := 已经进行了 i 轮，其中有 j 轮是 A 赢了，后续轮次比赛中始终没有取得平局的概率

答案
dp[0][0]

初始化
dp[N][j] = 1
dp[i][j] = 1    if abs(2j - i) > N - i

状态转移
ans1 = 0                        if 2j - i == -1
       pa * dp[i + 1][j + 1]    other
ans2 = 0                        if 2j - i == 1
       pb * dp[i + 1][j]        other
dp[i][j] = ans1 + ans2

编程计算答案

Python 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@lru_cache(maxsize=int(1e6))
def solve(i, j):
    if N - i == 0:
        return 1.0
    k = j * 2 - i
    if abs(k) > N - i:
        return 1.0
    pa = pb = 0.5
    if k == -1:
        ans1 = 0.0
    else:
        ans1 = pa * solve(i + 1, j + 1)
    if k == 1:
        ans2 = 0.0
    else:
        ans2 = pb * solve(i + 1, j)
    return ans1 + ans2

以 N = 20 为例，计算结果为 0.176197

蒙特卡洛模拟

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
73
74
75
76
77
78
79
import numpy as np
from functools import lru_cache
from multiprocessing import Pool
import sys
sys.setrecursionlimit(int(1e5))

class Series:
    def __init__(self, N):
        self.N = N
        self.ma = self.mb = 0

    def solve(self):
        self.reset()
        return self._solve(0, 0)

    @lru_cache(maxsize=int(1e6))
    def _solve(self, i, j):
        if self.N - i == 0:
            return 1.0
        k = j * 2 - i
        if abs(k) > self.N - i:
            return 1.0
        pa = pb = 0.5
        if k == -1:
            ans1 = 0.0
        else:
            ans1 = pa * self._solve(i + 1, j + 1)
        if k == 1:
            ans2 = 0.0
        else:
            ans2 = pb * self._solve(i + 1, j)
        return ans1 + ans2

    def reset(self):
        self.N += self.ma + self.mb
        self.ma = self.mb = 0

    def match(self):
        if np.random.rand() < 0.5:
            self.ma += 1
        else:
            self.mb += 1
        self.N -= 1
        return self.ma == self.mb

    def finish(self):
        return self.N == 0

    def calc(self):
        from scipy.special import comb
        if self.N % 2 == 0:
            return comb(self.N, self.N / 2) / (2 ** self.N)
        else:
            return comb(self.N - 1, (self.N - 1) / 2) / (2 ** (self.N - 1))

def test(N):
    series = Series(N)
    ans = series.solve()
    res = series.calc()
    np.random.seed()
    T = int(1e6)
    n_tie = 0
    for _ in range(T):
        while not series.finish():
            if series.match():
                n_tie += 1
                break
        series.reset()
    return N, ans, res, (T - n_tie) / T

args = [5, 6, 7, 8, 9, 12, 15, 20]
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    N, ans, res, sim = t
    print("N={}".format(N))
    print("    递推结果:{:.6f}".format(ans))
    print("    计算结果:{:.6f}".format(res))
    print("    模拟结果:{:.6f}".format(sim))

模拟结果

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
N=5
    递推结果:0.375000
    计算结果:0.375000
    模拟结果:0.375120
N=6
    递推结果:0.312500
    计算结果:0.312500
    模拟结果:0.312650
N=7
    递推结果:0.312500
    计算结果:0.312500
    模拟结果:0.311668
N=8
    递推结果:0.273438
    计算结果:0.273438
    模拟结果:0.273671
N=9
    递推结果:0.273438
    计算结果:0.273438
    模拟结果:0.273643
N=12
    递推结果:0.225586
    计算结果:0.225586
    模拟结果:0.225045
N=15
    递推结果:0.209473
    计算结果:0.209473
    模拟结果:0.209532
N=20
    递推结果:0.176197
    计算结果:0.176197
    模拟结果:0.176389
Share