数学 - 概率与期望

古典概型

Little Pony and Expected Maximum

一个骰子有 $m$ 个面，第 $i$ 个面点数为 $i$，每一面等概率出现，计算投掷 $n$ 次骰子能获得最大值的期望。

设随机变量 $X$ 是投掷出的最大值，下面有两种方法求出 $P(X=i)$。

可以枚举最大值的数量 $c$，并且根据二项式定理合并：

$$\begin{aligned} P(X=i)&=\frac{1}{m^n}\sum_{c=1}^n \binom{n}{c}(i-1)^{n-c}\\ &=\frac{1}{m^n}(i-1)^n\left(\sum_{c=0}^n \binom{n}{c}(i-1)^{-c}-\binom{n}{0}(i-1)^0\right)\\ &=\frac{1}{m^n}(i-1)^n\left(\left((i-1)^{-1}+1\right)^n -1\right)\\ &=\frac{i^n-(i-1)^n}{m^n} \end{aligned}$$

也可以换一种思路，求 $P(X\le i)$ 更简单，因为这只需要在 $1\sim i$ 中任意选择数字即可：

$$P(X\le i)=\frac{i^n}{m^n}$$

因此：

$$\begin{aligned} P(X=i)&=P(X\le i)-P(X\le i-1)\\ &=\frac{i^n-(i-1)^n}{m^n} \end{aligned}$$

然后，考虑期望的求法：

$$\mathbb{E}[X]=\sum_{i=1}^m i\frac{i^n-(i-1)^n}{m^n}$$

所以用快速幂可以做到 $O(m\log n)$。

期望 DP

给定一个 DAG，每条边 $(u,v)$ 有权值 $w_{u,v}$，一个人从节点 $x$ 出发，假设当前处于节点 $u$，则

• 如果没有任何出边，则过程停止；
• 否则，随机走向一个相邻的点 $v$，概率为 $p_{u,v}$，并且 $\sum_v p_{u,v}=1$。

求 $x$ 出发到停止走过的总路程的期望。

根据期望的定义，设随机变量 $D_u$ 表示路程的长度，我们从终点往前递推，可以得到：

$$\begin{aligned} \mathbb{E}[D_u]&=\sum_{d}dP(D_u=d)\\ &=\sum_d\sum_{(u,v)}dP(D_v=d-w_{u,v})p_{u,v}\\ &=\sum_{(u,v)}\sum_ddP(D_v=d-w_{u,v})p_{u,v}\\ \end{aligned}$$

然后，我们把 $d-w_{u,v}$ 换元为 $d'$：

$$\begin{aligned} \mathbb{E}[D_u]&=\sum_{(u,v)}\sum_{d'}(d'+w_{u,v})P(D_v=d')p_{u,v}\\ &=\sum_{(u,v)}p_{u,v}\left(\sum_{d'}d'P(D_v=d')+w_{u,v}\sum_{d'}P(D_v=d')\right)\\ &=\sum_{(u,v)}p_{u,v}\left(\mathbb{E}[D_v]+w_{u,v}\right) \end{aligned}$$

这个式子是符合我们的直觉的，即好像是把期望当成一个所谓的真正的值来用。

New Year and Arbitrary Arrangement

给定三个整数 $k,p_a,p_b$ 以及一个空的序列。

每次随机在这个序列末尾添加字符 a 或者 b，概率分别是 $\frac{p_a}{p_a+p_b}$ 以及 $\frac{p_b}{p_a+p_b}$，直到出现 $\ge k$ 个形如 ab 的子序列。

求操作结束时子序列期望出现次数，答案对 $10^9+7$ 取模。

我们发现这是状态之间的转移，所以考虑以 DP 视角来看。

那怎么设计状态？最无脑的方案当然是 $(s,a,b)$ 表示子序列数量、a 的数量和 b 的数量，接下来我们考虑转移。

$$dp(s,a,b)\gets \begin{cases} dp(s,a+1,b)\quad P_A=\frac{p_a}{p_a+p_b}\\ dp(s+a,a,b+1)\quad P_B=\frac{p_b}{p_a+p_b} \end{cases}$$

我们发现 $b$ 这个状态在转移的时候并没有影响到别的状态，所以不妨把它扔掉。

$$dp_{s,a}=P_Adp_{s,a+1}+P_Bdp_{s+a,a}$$

根据题目要求，当 $s\ge k$ 时，$dp_{s,a}=s$。因此当 $s+a\ge 0$ 时，有：

$$dp_{s,a}=P_A dp_{s,a+1}+P_B(s+a)$$

这个数列是无穷的，我们可以换个思路，枚举一下后续添加了几个 a 后停止，并且让这个数量取到一个 $+\infty$ 的极限即可。

$$\begin{aligned} dp_{s,a}&=\sum_{i=0}^{+\infty} P_A^i P_B(s+a+i)\\ &=P_B\left((s+a)\sum_{i=0}^{+\infty}P_A^i+\sum_{i=1}^{+\infty} iP_A^i\right)\\ &=P_B\left(\frac{s+a}{1-P_A}+\frac{P_A}{(1-P_A)^2}\right)\\ &=s+a+\frac{P_A}{P_B} \end{aligned}$$

特殊地，当 $a=0$ 时，$(s,0)$ 会从 $(s,0+1),(s+0,0)$ 这两个状态转移，其中 $(s+0,0)$ 就是它本身，所以我们需要进行特殊处理，移项解方程即可：

$$dp_{s,0}=\frac{1}{1-P_B}P_Adp_{s,1}$$

Fork in the Road

给定一个有向图，保证每个节点都能走到 $n$。

高桥从 $1$ 开始每次等概率随机选择一条边走。

现在删一条边，使得他到 $n$ 经过边的期望数量最小。

这显然无法通过枚举边后每次重新计算的方式操作。

我们可以看出，如果某个点 $u$ 后面的点已经删过，那么 $(u,v)$ 这些边都不能删；只有当 $u$ 后面的点都没删过它才可以删。

这里用 $dp_{u,0/1}$ 表示 $u$ 后面是否删过对应的最小期望，其中 $0$ 代表没删过，$1$ 代表删过。

对于没删过，它后面也必须没删过。设 $d_u$ 是 $u$ 的出边数量。

$$dp_{u,0}=\frac{1}{d_u}\sum_{v} (dp_{v,0}+1)$$

对于删过的，它可能是后面的已经删过，也可能是某个 $(u,v)$ 被删了。

$$dp_{u,1}=\min \begin{cases} \min_{v_0} \cfrac{1}{d_u-1}\sum_{v\neq v_0} (dp_{v,0}+1)\\ \min_{v_0} \cfrac{1}{d_u}\sum_{v} (dp_{v,[v=v_0]}+1) \end{cases}$$

答案是 $dp_{1,1}$。

Checkpoints

$n$ 个关卡，有一些关卡有存档点，有些没有。

从 $1\sim n$ 过关，对于每一个关卡，都相互独立并且通过和失败的概率均为 $\cfrac{1}{2}$。

如果通过关卡 $i$，则进入关卡 $i+1$，否则返回最近的、有存档点的关卡 $j\le i$。关卡 $1$ 一定有存档点。

给定一个 $k\le 10^{18}$，构造出一个 $n\le 2000$ 且通过关卡 $n$ 的总次数的期望为 $k$ 的方案，或报告方案不存在。

显然，我们需要推一下，如果已经知道所有的存档点，目标期望的表达式。

假设从 $i$ 开始通关 $n$ 的期望为 $E_i$，上一个、下一个存档点分别是 $l,r$ 并且满足 $l\le i\le r-1$。

最后一段

首先来求最后一段，即 $r$ 不存在的情况。设关卡为 $l,\dots,n-1,n$。

对于每一个 $l\le i\le n-1$，都有：

$$E_i=\frac{1}{2}(E_{i+1}+1)+\frac{1}{2}(E_l+1)$$

特别地，对于 $i=n$，有：

$$E_n=\frac{1}{2}+\frac{1}{2}(E_l+1)$$

从 $i=l,l+1,l+2$ 可以得出一个规律：

$$E_{l+j-1}-E_{l+j}=2^{j}$$

可以列出：

$$\begin{cases} E_l-E_{l+1}&=2^1\\ E_{l+1}-E_{l+2}&=2^2\\ \cdots\\ E_{n-1}-E_{n}&=2^{n-l}\\ E_n&=1+\frac{1}{2} E_l \end{cases}$$

因此：

$$E_l=2^1+2^2+\cdots+2^{n-l+1}=2^{n-l+2}-2$$

前面的段

同样地，我们可以找到上面的规律：

$$E_{l+j-1}-E_{l+j}=2^{j}$$

列出：

$$\begin{cases} E_l-E_{l+1}&=2^1\\ E_{l+1}-E_{l+2}&=2^2\\ \cdots\\ E_{r-1}-E_{r}&=2^{r-l}\\ \end{cases}$$

因此：

$$E_l=2^1+2^2+\cdots+2^{r-l}+E_r=2^{r-l+1}-2+E_r$$

合并两种情况

我们发现，无论是在最后一段，还是前面的段，如果我们设一个存档点 $j$ 后没有存档点的数量为 $c_j$，那么 $E_1=\sum_j(2^{c_j+2}-2)$。

当 $c_j=0$ 时，贡献为 $2$；我们可以将其与一个 $c_j=0$ 的段一起来看，它们的贡献是 $2^{c_j+2}$，因此所有的 $2$ 的 $\ge 1$ 次方的幂都可以构造出来。

我们将 $k$ 看作一个二进制数，那么一定可以用至多 $n=O(2\log_2 k)$ 个数字凑出一个方案。这是显然满足 $n\le 2000$ 的。

这里每一段的贡献最小也是 $2$，所以对于 $k$ 为奇数的情况，是没有方案存在的。