数概率

【Puzzle】一排座位

字数统计: 1.2k字   |   阅读时长: 5分
,

摘要: 《概率50题》一排座位

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

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

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

问题描述

The Theatre Row

Eight eligible bachelors and seven beautiful models happen randomly to have purchased single seats in the same 15 seat row of a theatre
On average, how many pairs of adjacent seats are ticketed for marriageable couples?

8个男人和7个女人订了电影院的一排座，一排刚好有15个座位。

问：平均有多少个相邻座位是异性。

思路参考

方法1：全期望公式 + 期望DP

定义 f(x, y) 表示 x 个男，y 个女排一排，相邻座位是异性的平均个数。当 x, y 任意一个为 0 的时候，值为零：f(x, 0) = 0, f(0, y) = 0

当 x > 0, y > 0 时，考虑最左边的座位，它有两种可能性，一种是男的，概率 p1 = x/(x+y), 另一种是女的，概率 p2 = y/(x+y)

(1) 如果最左边是男的:

则期望的相邻座位是异性的个数分为两部分，第一部分是 f(x-1 , y)，第二部分是最左边男人的相邻座位，当相邻位置为女人时，可以贡献 1，概率为 y/(x-1+y)。

(2) 如果最左边是女的:

则期望的相邻座位是异性的个数分为两部分，第一部分是 f(x , y-1)，第二部分是最左边女人的相邻座位，当相邻位置为男人时，可以贡献 1，概率为 x/(y-1+x)。

综合以上若干条，再结合全期望公式

可以写出 f(x, y) 的转移方程。

1
2
f(x, y) = p1 * (f(x - 1, y) + y / (x - 1 + y)) 
          + p2 * (f(x, y - 1) + x / (y - 1 + x))

下面通过期望 DP 的方式解决以上问题，算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义
dp[i][j] := i 个男人，j 个女人的情况，相邻座位是异性的个数的期望

初始化
dp[i][0] = 0
dp[0][j] = 0

答案
dp[8][7]

状态转移
dp[i][j] = i / (i + j) * (dp[i - 1][j] + (j / (i - 1 + j)))
           + j / (i + j) * (dp[i][j - 1] + (i / (j - 1 + i)))

下面编程计算 dp[8][7]，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 8, m = 7;
    vector<vector<double>> dp(n + 1, vector<double>(m + 1, 0));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            dp[i][j] = (double)i / (i + j) * (dp[i - 1][j] + ((double)j / (i - 1 + j)))
                        + (double)j / (i + j) * (dp[i][j - 1] + ((double)i / (j - 1 + i)));
        }
    cout << dp[n][m] << endl;
}

计算结果为 dp[8][7] = 7.46667

方法2: 单独考虑每个相邻座位

一共有 14 个相邻座位。对于每个相邻座位，我们要考虑的都是【从 8 个男人和 7 个女人中选两个人放这个相邻座位的左右两边，这两个人是否为异性】这件事。

假设这个概率为 p，则一个相邻座位可以形成的异性的个数的期望就是 E = p，14 个相邻座位中为异性的期望个数就是 p * 14

考虑一个相邻作为的左边这个座位：

  • 左边座位是男人的概率为 8/15，在此情况下右边作为是女人的概率为 7/14。
  • 左边座位是女人的概率为 7/15，在此情况下右边作为是男人的概率为 8/14。

因此一个相邻座位能够形成异性的概率为

14 个相邻座位中，异性的个数的期望为 8/15 * 14 = 7.46667

蒙特卡洛模拟

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

persons = [1] * 8 + [0] * 7

def run():
    l = np.random.permutation(persons)
    ans = 0
    for i in range(len(l) - 1):
        if l[i] != l[i + 1]:
            ans += 1
    return ans

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

T = int(1e6)
args = [T] * 8
pool = Pool(8)
ts = pool.map(test, args)
for t in ts:
    print("{:.6f} pairs of adjacent are the opposite sex".format(t))

模拟结果

1
2
3
4
5
6
7
8
7.467305 pairs of adjacent are the opposite sex
7.466081 pairs of adjacent are the opposite sex
7.470136 pairs of adjacent are the opposite sex
7.465220 pairs of adjacent are the opposite sex
7.465871 pairs of adjacent are the opposite sex
7.467655 pairs of adjacent are the opposite sex
7.464980 pairs of adjacent are the opposite sex
7.467260 pairs of adjacent are the opposite sex
Share