取球的次数 🥎

取出某个指定球

不透明箱子里有 $n$ 个颜色不同的球,现在进行有放回的取球,求取出某个指定颜色的球的次数期望。

假设期望次数为 $\mathrm{E}$,那么在每次取球的时候,取到指定颜色的球的次数期望为: $$ \mathrm{E} = \begin{cases} 1 &\text{(}P_{\text{(取到指定球)}}=\frac{1 }{n}\text{)} \\ 1 + \mathrm{E} &\text{(}P_{\text{(未取到指定球)}}=\frac{n-1}{n}\text{)} \\ \end{cases} $$ 因此我们有: $$ \mathrm{E} = \frac{1}{n}\cdot1 + \frac{n-1}{n}\cdot(1+\mathrm{E}) $$ 解得: $$ \mathrm{E} = n $$ 因此取出某个指定颜色的球的次数期望为 $n$。

所有球都被取到过

不透明箱子里有 $n$ 个颜色不同的球,现在进行有放回的取球,求所有球都被取到过的次数期望。

假设 $\mathrm{E}[i]$ 为已经取出 $i$ 个不同的球时,还需要继续取直到完成目标的次数期望。那么对于某次取球,我们已经取出了 $i$ 个不同的球,此时还需要取的次数期望为 $\mathrm{E}[i]$,此时取球可能有两种情况: $$ \mathrm{E}[i] = \begin{cases} 1 + \mathrm{E}[i] &\text{(}P_{\text{(取到旧球)}}=\frac{i }{n}\text{)} \\ 1 + \mathrm{E}[i + 1] &\text{(}P_{\text{(取到新球)}}=\frac{n-i}{n}\text{)} \\ \end{cases} $$ 因此我们有: $$ \mathrm{E}[i] = \frac{i}{n} \cdot(1 + \mathrm{E}[i]) + \frac{n-i}{n}\cdot(1 + \mathrm{E}[i + 1]) $$ 解得: $$ \mathrm{E}[i] = \frac{n}{n - i} + \mathrm{E}[i + 1] $$ 又因为 $\mathrm{E}[n] = 0$,因此我们将递推式展开可得: $$ \begin{aligned} \mathrm{E}[0] &= \frac{n}{n-0} + \mathrm{E}[1] \\ &= \frac{n}{n-0} + \frac{n}{n-1} + \mathrm{E}[2] \\ &= \cdots \\ &= \frac{n}{n-0} + \frac{n}{n-1} + \frac{n}{n-2} + \cdots + \frac{n}{n-(n - 1)} \end{aligned} $$ 举个具体例子,假如一共有 6 个球(相当于投骰子投出所有点数),那么我们计算得次数期望 $\mathrm{E}$ 为: $$ \begin{aligned} \mathrm{E} = \frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} = 14.7 \end{aligned} $$

升级大宝剑 🗡

50% 升级

用宝石升级大宝剑,每使用一个宝石,有 50% 概率升一级、50% 概率不变,求从 1 级升到 10 级需要用到的宝石数量期望。

假设 $\mathrm{E}[i]$ 表示大宝剑从 $i - 1$ 级升级到 $i$ 级需要的宝石数量,那么我们有 $$ \mathrm{E}[i] = \begin{cases} 1 &\text{(}P_{\text{(升级)}}=\frac{1}{2}\text{)} \\ 1 + \mathrm{E}[i] &\text{(}P_{\text{(不变)}}=\frac{1}{2}\text{)} \\ \end{cases} $$ 因此我们有: $$ \mathrm{E}[i] = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot (1 + \mathrm{E}[i]) $$ 解得: $$ \mathrm{E}[i] = 2 $$ 因此从 1 级升到 10 级需要的宝石数量为 $$ \begin{aligned} \sum_{i=2}^{10} \mathrm{E}[i] &= 9 \times 2 = 18 \end{aligned} $$

50% 升级,50% 降级

用宝石升级大宝剑,每使用一个宝石,有 50% 概率升一级、50% 概率降一级,求从 1 级升到 10 级需要用到的宝石数量期望。

假设 $\mathrm{E}[i]$ 表示大宝剑从 $i - 1$ 级升级到 $i$ 级需要的宝石数量,那么我们有 $$ \mathrm{E}[i] = \begin{cases} 1 &\text{(}P_{\text{(升级)}}=\frac{1}{2}\text{)} \\ 1 + \mathrm{E}[i-1] + \mathrm{E}[i] &\text{(}P_{\text{(降级)}}=\frac{1}{2}\text{)} \\ \end{cases} $$ 因此我们有: $$ \mathrm{E}[i] = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot (1 + \mathrm{E}[i-1] + \mathrm{E}[i]) $$ 解得: $$ \mathrm{E}[i] = 2 + \mathrm{E}[i - 1] $$ 因此从 1 级升到 10 级需要的宝石数量为 $$ \begin{aligned} \sum_{i=2}^{10} \mathrm{E}[i] &= \mathrm{E}[2] + \mathrm{E}[3] + \cdots + \mathrm{E}[9] + \mathrm{E}[10] \\ &= 2 + 4 + 6 + \cdots + 18 \\ &= 90 \end{aligned} $$

25% 升级,25% 降级

用宝石升级大宝剑,每使用一个宝石,有 25% 概率升一级、25% 概率降一级、50% 概率不变,求从 1 级升到 10 级需要用到的宝石数量期望。

假设 $\mathrm{E}[i]$ 表示大宝剑从 $i - 1$ 级升级到 $i$ 级需要的宝石数量,那么我们有 $$ \mathrm{E}[i] = \begin{cases} 1 &\text{(}P_{\text{(升级)}}=\frac{1}{4}\text{)} \\ 1 + \mathrm{E}[i] &\text{(}P_{\text{(不变)}}=\frac{1}{2}\text{)} \\ 1 + \mathrm{E}[i-1] + \mathrm{E}[i] &\text{(}P_{\text{(降级)}}=\frac{1}{4}\text{)} \\ \end{cases} $$ 因此我们有: $$ \mathrm{E}[i] = \frac{1}{4} \cdot 1 + \frac{1}{2} \cdot (1 + \mathrm{E}[i]) + \frac{1}{4} \cdot (1 + \mathrm{E}[i-1] + \mathrm{E}[i]) $$ 解得: $$ \mathrm{E}[i] = \mathrm{E}[i - 1] + 4 $$ 因此从 1 级升到 10 级需要的宝石数量为 $$ \begin{aligned} \sum_{i=2}^{10} \mathrm{E}[i] &= \mathrm{E}[2] + \mathrm{E}[3] + \cdots + \mathrm{E}[9] + \mathrm{E}[10] \\ &= 4 + 8 + 12 + \cdots + 36 \\ &= 180 \end{aligned} $$

随机数生成

用 rand7 构造 rand10

假设已有 rand7 函数可以等可能地随机获得 $[0,6]$ 区间内的整数。请利用该 rand7 构造一个 rand10 等可能地随机获得 $[0, 9]$ 区间内的整数。

步骤:

  1. 调用 2 次 rand7 得到两个数字 $a$、$b$,计算 $c = 7a + b$。
  2. 若 $c \le 39$,则返回 $c\bmod10$;否则返回第一步。

原理:

$a$、$b$ 都是区间 $[0, 6]$ 内的随机整数,因此 $7a + b$ 是区间 $[0, 48]$ 内的随机整数,抛弃掉 $[40, 48]$ 之后,刚好剩下 40 个整数,再余 10 就可以等可能地随机获得 $[0, 9]$ 区间内的整数。

注意这里 $7a + b$ 中的 7 是不可替换的,如果小于 7,那么每个区间都会被 $b$ 突破,如果大于 7,那么每个区间都有值不可能被取到。

用 randM 构造 randN

假设已有 randM 函数可以等可能地随机获得 $[0,M-1]$ 区间内的整数。请利用该 randM 构造一个 randN 等可能地随机获得 $[0,N-1]$ 区间内的整数。

这里是上题的拓展,这里我们要区分 $M$、$N$ 可能的大小的情况。

1. 如果 $N \le M$,

那么只调用一次 randM 得到值 $x$,如果 $x < N$ 则返回 $x$,否则丢弃 $x$ 后重新调用 randM

2. 如果 $M < N \le M^2$,

那么我们需要调用 2 次 randM 来获得一个均匀区间 $[0, M^2]$,然后用该区间长度 $M^2$ 除以 $N$,抛弃余数部分,最后返回剩余区间内的值余 $N$ 的结果。

3. 如果 $M^2 < N \le M^3$,

那么我我们需要调用 3 次 randM 来获得均匀区间 $[0, M^3]$,然后用该区间长度 $M^3$ 除以 $N$,抛弃余数部分,最后返回剩余区间内的值余 $N$ 的结果。

……依次类推。

概率发生器

p 概率发生器构造 1/2 发生器

假设我们有一个随机发生器,产生 0 的概率是 $p$,产生 1 的概率是 $1 - p$。请基于它构造一个新的发生器,使得它产生 0 和 1 的概率均为 $\frac{1}{2}$。

根据题意,我们连续产生两个数,我们可能获得 00011011 四种组合,其概率如下:

$$ \begin{aligned} P(00) &= p^2 \\ P(01) &= p(1-p) \\ P(10) &= (1-p)p \\ P(11) &= (1-p)^2 \\ \end{aligned} $$

其中 $P(01) = P(10)$,因此我们可以将他们分别映射到 0、1。也就是说,当我们获得 0110 组合的时候,返回 0 或 1;当我们获得 0011 的时候,丢弃结果重新生成。

p 概率发生器构造 1/n 发生器

假设我们有一个随机发生器,产生 0 的概率是 $p$,产生 1 的概率是 $1 - p$。请基于它构造一个新的发生器,使得它产生 $0$、$1$、……、$n - 1$ 的概率均为 $\frac{1}{n}$。

其实根据上题我们就可以发现,为了构造这种 $1/n$ 发生器,我们需要找到 $n$ 个发生概率相同的事件。

找到概率相同的事件

我们尝试用该发生器产生多个数字,假设产生了 $x$ 次 0、$y$ 次 1,那么出现该事件(即排列)的概率为 $p^x(1-p)^y$。如果我们想使得所有事件发生的概率相同,显然可以令 $x=y$,也就是说排列中 0、1 的数量相同。

应该取多少次

我们应该使得可能的事件数大于 $n$,又因为我们限定了 $x=y$,因此我们只需要在 $2x$ 个位置中选取 $x$ 个位置填入 0、其余位置填入 1 即可获得该序列,可能的最大事件数为 $C_x^{2x}$。我们应该找到一个最小的 $x$,使得 $C_x^{2x} \ge n$,此时我们应该取的次数为 $2x$。

完整操作步骤

  1. 计算需要取的次数 $2x$,将 $[0, n-1]$ 区间内的每个整数赋给长度为 $2x$、0 和 1 的数量相同的不同序列(可能赋不满,多余的序列丢弃即可)。
  2. 连续产生 $2x$ 个数,如果 0 的数量不等于 1 的数量,重复该步骤。
  3. 如果产生的序列对应 $[0, n-1]$ 区间内的整数,返回该整数;否则返回第二步。

未知分布发生器构造 1/2 发生器

假设我们有一个随机发生器,产生的数据分布未知。请基于它构造一个新的发生器,使得它产生 0 和 1 的概率均为 $\frac{1}{2}$。

虽然随机发生器产生的数据分布未知,但是如果我们随机产生两个数 $a$、$b$,那么他们的大小关系只可能是 $a > b$、$a = b$、$a < b$,其中 $a > b$、$a < b$ 的概率是相同的。因此我们可以在碰到这两种情况时分别返回 01,相等时则抛弃。

其他

组成三角形的概率

一根铁棍随机截成三截,求组成三角形的概率。

假设铁棍长度为 $1$,三截的长度分别为 $x$、$y$、$1 - x - y$,满足以下约束: $$ \begin{aligned} 0 < x < 1 \\ 0 < y < 1 \\ 0 < x + y < 1 \\ \end{aligned} $$ 那么如果要能够组成三角形,应该满足两边之和大于第三边的约束: $$ \begin{aligned} x + y > 1 - x - y \\ x + 1 - x - y > y \\ y + 1 - x - y > x \\ \end{aligned} $$ 化简得到: $$ \begin{aligned} x < 1/2 \\ y < 1/2 \\ x + y > 1/2 \\ \end{aligned} $$ 简单画一下函数图像,可以得到概率为 $\frac{1}{4}$。