数概率

【Puzzle】To Begin or Not to begin

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

摘要: 《概率统计40Puzzles》To Begin or Not to begin

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

参考: 《40 Puzzles and Problems in Probability and Mathematical Statistics》

问题描述

An urn contains k black balls and a single red ball. Peter and Paula draw
without replacement balls from this urn, alternating after each draw until the
red ball is drawn. The game is won by the player who happens to draw the
single red ball. Peter is a gentleman and offers Paula the choice of whether
she wants to start or not. Paula has a hunch that she might be better off if
she starts; after all, she might succeed in the first draw. On the other hand,
if her first draw yields a black ball, then Peter’s chances to draw the red ball
in his first draw are increased, because then one black ball is already removed
from the urn. How should Paula decide in order to maximize her probability
of winning?

一个瓮里有 k 个黑球，1 个红球，Peter 和 Paula 两人进行轮流的无放回抽取，直到红球被抽出来。抽出红球的这个人获胜。

Paula 可以决定是否要先抽取。

Paula 觉得她先抽取会更好，毕竟有可能第一抽就中红球。但是她又担心如果第一抽拿到黑球，Peter 抽到红球的概率就提高了。

Paula 为了获胜概率最大，应该先抽还是后抽。

思路参考

记翁中有 k 个黑球时，先抽的人最后获胜的概率为 $p(k)$

分别考虑第一抽抽中红球和第一抽抽中黑球两种情况。若第一抽抽中红球，概率为 $\frac{1}{k+1}$，则直接结束；若第一抽抽中黑球，概率 $\frac{k}{k+1}$，则需要换 Peter 抽。现在相当于是初始翁中有 k - 1 个黑球和 1 个红球，由先 Peter 抽取，这种情况下 Peter 赢的概率为 $p(k - 1)$，Paula 想赢需要先抽的 Peter 输，概率为 $1 - p(k - 1)$。由此可以写出 $p(k)$ 的递推式

k 等于 0, 1, 2, 3 的情况具体分析如下:

  • k = 0，则 $p(0) = 1$
  • k = 1，则 $p(1) = \frac{1}{2}$
  • k = 2，则 $p(2) = \frac{1}{3} + \frac{2}{3}(1 - p(1)) = \frac{2}{3}$
  • k = 3，则 $p(3) = \frac{1}{4} + \frac{3}{4}(1 - p(2)) = \frac{1}{2}$

递归实现 p(k)

1
2
3
4
5
6
7
def prob(k):
    if k == 0:
        return 1.0
    elif k == 1:
        return 0.5
    else:
        return 1 - k / (k + 1) * prob(k - 1)

并画出 p 关于 k 的图像

1
2
3
4
5
k_list = range(1000)
p = [prob(k) for k in k_list]
plt.figure()
plt.plot(k_list, p)
plt.show()

画出图像后可以得出结论，k 为奇数，则 p(k) 等于 0.5，k 为偶数，则 p(k) 大于 0.5 且 p(k) 随着 k 增大不断变小并趋近于 0.5

Paula 应该先抽取

Share