• 概率
  • 基础知识
    • 样本空间、事件和概率
      • 概率公理
    • 随机变量
    • 离散型随机变量及其概率分布
    • 连续型随机变量及其概率分布
    • 连续型随机向量及其概率分布
  • 数学期望
    • 离散型随机变量的数学期望
    • 连续型随机变量的数学期望
  • 例题1 LastMarble (TopCoder SRM 349 div one 1000)
    • 题目描述
    • 分析
  • 例题2 Randomness (UVA 11429)
    • 题目描述
    • 分析

概率

基础知识

样本空间、事件和概率

样本空间S是一个集合，它的元素被称为基本事件。样本空间的一个子集被称为事件，根据定义所有的基本事件都互斥。

概率公理

如果有一种事件到实数的映射 $P\{\}$，满足：

1. 对任何事件 $A$，$P\{A\}\geq0$；
2. $P\{S\}=1$；
3. 对两个互斥事件，$P\{A\cup B\}=P\{A\}+P\{B\}$，

则可称 $P\{A\}$ 为事件 $A$ 的概率。

随机变量

如果对样本空间 $S$ 中的任意事件 $e$，都有唯一的实数 $X(e)$ 与之对应，则称 $X=X(e)$ 为样本空间 $S$ 上的随机变量，其中离散型随机变量与连续型随机变量较常见。

离散型随机变量及其概率分布

取值范围为有限或无限可数个实数的随机变量称为离散型随机变量。设离散型随机变量 $X$ 取值 $x_i$ 时的概率为 $p_k (k=1,2,\ldots)$，则称 $X$ 的所有取值以及对应概率为 $X$ 的概率分布，记做 $P\{X=x_k\} = p_k (k=1,2,\ldots)$。

常见的离散型随机变量的概率分布有两点分布，二项分布，几何分布，超几何分布，泊松分布。

连续型随机变量及其概率分布

如果 $X$ 是在实数域或区间上取连续值的随机变量，设 $X$ 的概率分布函数为 $F(x)=P\{X\leq x\}$，若存在非负可积函数 $f(x)$，使对任意的 $x$，有$F(x)=\int^x_{-\infty}f(t)dt$，则称 $X$ 为连续型随机变量，称 $f(x)$ 为 $X$ 的概率密度函数。要注意，概率密度不是概率。常见的连续型随机变量分布有均匀分布，正态分布，指数分布。

连续型随机向量及其概率分布

如果 $X_1,X_2,\ldots,X_N$ 都是连续型随机变量，则称 $(X_1,X_2,\ldots,X_N)$ 为 $N$ 维随机向量，其概率分布函数为 $F(x_1,x_2,…,x_N)=P\{X_1\leq x_1,X_2\leq x_2,\ldots,X_N\leq x_N\}$。若存在非负可积函数 $f(x_1,x_2,\ldots,x_N)$ 使得 $F(x_1, x_2, \ldots, x_N)=\int_D f(x_1, x_2, \ldots, x_N)dx_1dx_2\ldots dx_N$，其中等式右端表示 $N$ 重积分，就称 $f(x_1,x_2,…,x_N)$是 $N$ 为随机向量 $(X_1,X_2,\ldots,X_N)$ 的联合概率密度函数。

如果 $X_1, X_2, \ldots, X_N$ 相互独立，并且分别有概率密度函数 $f_1(x_1), f_2(x_2), \ldots, f_N(x_N)$，那么 $f(x_1, x_2, \ldots, x_N) = f_1(x_1)f_2(x_2)\ldots f_N(x_N)$。

数学期望

离散型随机变量的数学期望

设离散型随机变量 $X$ 的分布律为 $P\{X=x_k\} = p_k(k=1,2,\ldots)$，若 $\sum^{\infty}_{k=1}|x_kp_k|$ 存在，则称 $\sum^\infty_{k=1}x_kp_k$ 为 $X$ 的数学期望，简称期望，记为 $E(X)$。

连续型随机变量的数学期望

设连续型随机变量 $X$ 的概率密度函数为 $f(x)$，若广义积分 $\int^{+\infty}_{-\infty}|xf(x)|dx$ 收敛，则称 $\int^{+\infty}_{-\infty}xf(x)dx$ 为连续型随机变量 $X$ 的数学期望，记为 $E(X)$。

例题1 LastMarble (TopCoder SRM 349 div one 1000)

题目描述

有red个红球，blue个蓝球在一个袋子中。两个玩家轮流从袋子中取球，每个人每次可以取 1，2 或 3 个球，但在他把球拿出袋子之前，他并不知道所取球的颜色。每次球被取出袋子后，它们的颜色被公布给所有人。取走最后一个红球的人输。现在已知有人在游戏开始前取走了removed个球，并且谁也不知道球的颜色。在两个玩家都采取最优策略时，先手的胜率是多少？

数据范围：$1\leq red,blue\leq 100,0\leq removed\leq red-1$。

分析

当 $removed=0$ 的时候，这个问题是很普通的动态规划问题。我们只需设 $F(r,b)$ 代表现在剩 $r$ 个红球，$b$ 个蓝球，面对当前局面的玩家所能得到的最大胜率。那么： $$F(0, b)=1(b\geq 0)\\ F(r, b)=\max_{1\leq m\leq \min(r+b, 3)}(\sum_{0\leq p\leq r, 0\leq q\leq b, p+q=m}\frac{C^p_rC_b^q}{C_{r+b}^m}(1-F(r-p,b-q)))$$ 其中 $\frac{C^p_rC_b^q}{C_{r+b}^m}$ 是取到 $p$ 个红球，$q$ 个蓝球的概率。$F(red,blue)$ 就是我们要的答案。

对于 $removed>0$ 的情况，我们显然可以知道：

定理 在 $red$ 个红球，$blue$ 个蓝球中先取 $a$ 个球，再取 $b$ 个球，剩余不同颜色的球数的概率分布与先取 $b$ 个球，再取 $a$ 个球所对应的剩余不同颜色的球数的概率分布是相同的。

上面的定理告诉了我们，取球的顺序和最终的结果没有关系。

我们设 $F(r,b)$ 表示当前有 $r$ 个红球，$b$ 个蓝球的，被事先取走了 $removed$ 个球（不知道它们的颜色），面对这个局面的玩家所能得到的最大胜率。当玩家取走 $m$ 个球时，根据上面的定理，新的局面与玩家先取走 $m$ 个球，再让 $removed$ 个球被取走所得到的局面完全一样！但是有一种边界情况要考虑:由于不能保证 $removed\leq r$，可能在一些情况下，取走 $m$ 个球后，玩家已经输了，而不能进行下面的游戏。要解决这种特殊情况，只需对 $F$ 的定义和动态规划方程略加修改：让 $F(r,b)$ 表示当前有 $r$ 个红球，$b$ 个蓝球，被取走了 $removed$ 个球但仍然至少还有 1 个红球的情况下，当前玩家的最大胜率。

我们用 $\text{Pro}(r,b,k)$ 表示有 $r$ 个红球，$b$ 个蓝球，取走 $k$ 个球而红球数仍大于 0 的概率，那么 $\text{Pro}(r,b,k)=\sum_{a<r,0\leq k-a\leq b}\frac{C_r^aC_b^{k-a}}{C_{r+b}^k}$。我们可以用递推式求解： $$\text{Pro}(0,b,0)=0;\\ \text{Pro}(r,b,0)=1;(r>0)\\ \text{Pro}(r,b,k)=\frac{r}{r+b}\text{Pro}(r-1,b,k-1)+\frac{b}{r+b}\text{Pro}(r,b-1,k-1)$$ 再考虑最初的dp式，因为 $r$ 个红球，$b$ 个蓝球取走 $removed$ 个球仍有至少 $1$ 个红球的情况，包含了有 $(r-p)$ 个红球，$(b-q)$ 个蓝球，取走 $removed$ 个球后仍有至少 1 个红球的情况，因此在前者满足的基础上后者满足的概率是 $\frac{\text{Pro}(r-p,b-q,removed)}{\text{Pro}(r,b,removed)}$。由此我们得出最终的方程： $$\begin{array}{ll} F(r,b)=0 & (r+b=removed)\\ F(r,b)=\max_{1\leq m\leq min(r+b,3)}(\sum_{p+q=m}\frac{\text{Pro}(r-p,b-q,removed)}{\text{Pro}(r,b,removed)}\frac{C^p_rC_b^q}{C_{r+b}^m}(1-F(r-p,b-q))) & (r+b>removed) \end{array}$$ 最后的答案是$F(red, blue)$。

例题2 Randomness (UVA 11429)

题目描述

有一个随机数生成器能随机返回 $1$ 到 $R$ 的正整数，现在有 $N$ 个事件，要求第 $i$ 个事件的 发生概率是 $\frac{a_i}{b_i}$，用该随机数生成器设计一种事件触发装置，使随机数生成器的期望使用次数 $\text{Exp}$ 尽量少,求出 $\text{Exp}$（精确到 $10^{-7}$）。

数据范围：$2\leq R\leq 1000,1\leq N\leq 1000, 1\leq a_i\leq b_i \leq 1000(1\leq i\leq N)$，且 $\sum^N_{i=1}\frac{a_i}{b_i}=1$，所有的数都是正整数。

分析

为了观察题目规律，我们先看一个例子：
当 $R=100,N=3,\frac{a_1}{b_1}=\frac{a_2}{b_2}=\frac{a_3}{b_3}=\frac{1}{3}$ 时，最优策略可以是：当生成的数 $x\leq 99$ 时执行事件 $x \text{mod} 3$，否则再使用一次随机数生成器，事件的选择与上一次一样。这样每个事件发生的概率是：$\sum_{i=0}^{\infty}\frac{33}{100^i}=\frac{\frac{33}{100}-0}{1-\frac{1}{100}}=\frac{1}{3}$；$\text{exp}=\sum_{i=0}^{\infty}\frac{1}{100^i}=\frac{1-0}{1-\frac{1}{100}}=\frac{100}{99}。$

我们看到第一次使用生成器(定义为第一层生成器)时，有一些直接映射到事件，其余的每一个返回值分别对应一次新的生成器的使用，定义为第二层生成器。归纳地，定义第 $i+1(2\leq i)$ 层生成器为由第 $i$ 层生成器返回值引起的新的生成器的使用。
很明显，对事件 $i$ 而言，假设第 $k$ 层生成器中有 $D(i,k)$ 个返回值对应着事件 $i$ 的发生，一定有 $$\frac{a_i}{b_i}=\sum^{\infty}_{k=1}\frac{D(i,k)}{R^k}$$

这里 $D(i,k)<R(k=1,2,\ldots)$，因为如果某个 $D(i,k)\geq R$，我们把 $D(i,k)$ 减去 $R$，$D(i,k-1)$ 加 1，则等式仍成立，而 Exp 减小了。同时可以看出，这就是 $\frac{a_i}{b_i}$ 的 $\frac{1}{R}$ 进制表示，所以 $D(i,k)$ 的取值是唯一的。

为了计算 Exp，我们定义 $H(i+1)$ 为第 $i$ 层生成器产生的导致新的生成器使用的返回值个数，定义 $H(1)=1$，那么 $\frac{H(i)}{R^i}$ 就是第 $i$ 层生成器对 Exp 的贡献，我们有 $$\text{Exp}=\sum^{\infty}_{i=1}\frac{H(i)}{R^i}$$

至于求 $H(i)$,因为第 $i$ 层生成器中所有导致新生成器使用的返回值的个数，就是第 $i$ 层生成器被使用的个数，减去其中所有导致事件的返回值个数，也就是 $$H(i+1)=H(i)R-\sum_{k=1}^{N}D(i,k)$$

我们不可能求出所有的 $H(i)$，也没有必要，因为对所有的 $m\geq 2$ ，我们有 $$\sum^{\infty}_{k=m}\frac{H(k)}{R^k}<\sum^{\infty}_{k=m}\frac{NR}{R^k}=\frac{N}{R^{m-2}(R-1)}\leq\frac{N}{R^{m-2}}$$

这个式子告诉我们：只要 $m$ 足够大，我们可以让 Exp 的误差小到任意程度，而且这个误差减小的速度是很快的。根据题中要求的精度，只要算到第 50 层就足够了。