数学期望 学习笔记

前言

期望的广义定义：一次随机抽样中所期望的某随机变量的取值。

一个例子：

一次考试满分 $100pts$，有 $0.5$ 的概率考 $90pts$，$0.3$ 的概率考 $80pts$，$0.2$ 的概率考 $50pts$，则这次考试成绩的期望即为 $0.5\times 90+0.3\times 80+0.2\times 50=79pts$。

与 加权平均值 类似。

P8774 爬树的甲壳虫

Problem Link

Statement

有一只甲壳虫想要爬上一颗高度为 $n$ 的树，它一开始位于树根，高度为 $0$，当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_{i}$ 的概率会掉回树根，求它从树根爬到树顶时，每次尝试花费 $1$ 个单位时间，求经过的时间的期望值是多少。

Solution

正推方法。

设 $f_i$ 表示从根爬到 $i$ 花费时间的期望。

考虑转移，如果尝试成功，可以直接花费 $1$ 单位时间从 $i - 1$ 跳到 $i$，期望为 $(1 - p_{i})\times 1$；如果尝试失败，需要花费 $1$ 单位时间回到根，然后再花 $f_i$ 的时间回到 $i$，期望为 $p_i\times (f_i + 1)$。

容易得到 $f_i = f_{i - 1} + (1 - p_i) + (f_i + 1)\times p_i$。化简后，可以得到下面的方程：

$$f_i = \frac{f_{i-1} + 1}{1 - p_i} = (f_{i - 1} + 1)\times\frac{y_i}{y_i - x_i}$$

比倒推简单许多。

▶

倒推（需消元）

设 $f_i$ 表示从 $i$ 到树顶 $n$ 所花费时间的期望值。

接下来考虑转移，如果这次尝试成功，其期望为 $(1-p_{i+1})f_{i+1}$。如果这次尝试失败，回到树根，则其期望为 $p_{i+1}f_0$。

转移方程为：

$$f_i=1+(i-p_{i+1}f_{i+1})+p_{i+1}f_0$$

观察转移方程，发现其中 $f_0$ 和 $f_{i+1}$ 项是未知的。考虑倒推，可以求出 $f_{i+1}$，但无论如何都无法求 $f_0$，故多写几项寻找规律：

$$f_0=1+(i-p_1f_1)+p_1f_0\\f_1=1+(i-p_2f_2)+p_2f_0\\f_2=1+(i-p_3f_3)+p_3f_0$$

此时即可直接解方程，进行带入，展开后为：

$$f_0=1+(1-p_1)+(1-p_1)(1-p_2)f_2+[p_1+(1-p_1)p_2]f_0$$

因为题意中 $f_n=0$，所以原式化简为：

$$f_0=1+(1-p_1)+[p_1+(1-p_1)p_2]f_0$$

将其表示为 $f_0=A+B$ 形式，则可以进行对应：

$$A=1+(1-p_1)+(1-p_1)(1-p_2)+\cdots+(1-p_1)(1-p_2)\cdots(1-p_{n-1})\\B=p_1+p_2(1-p_1)+p_3(1-p_1)(1-p_2)+\cdots+p_n(1-p_n)\cdots(1-p_{n-1})$$

$A, B$ 都可以直接计算，则本题解决。

另外注意到数据要求输出 $\frac{a}{b}\bmod P$ 的结果，需要用到乘法逆元，由于 $P$ 为质数，可以直接通过费马小定理求出。

Core Code

这是倒推的代码。

ll ksm(ll x,ll y) {//快速幂
    ll res=1;
    while(y) {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int main() {
    n=read();
    for(int i=1;i<=n;i++) {
        int a=read(),b=read();
        p1[i]=a*ksm(b,mod-2)%mod;//失败概率
        p2[i]=(b-a)*ksm(b,mod-2)%mod;//成功概率
    }
    A=1;
    ll t=1;
    for(int i=1;i<=n;i++) {
        if(i!=n) A=(A+p2[i]*t%mod)%mod;
        B=(B+p1[i]*t%mod)%mod;
        t=(p2[i]*t)%mod;
    }
    write(A*ksm((1-B+mod)%mod,mod-2)%mod);
    return 0;
}

ABC360E Random Swaps of Balls

Luogu Link | AtCoder Link

Statement

有 $n$ 个球，其中 $n-1$ 球为白球，剩下一个球为黑球。初始时黑球为第 $1$ 个球。

你可以进行 $k$ 次操作，每次操作等概率随机选择两个整数 $i, j\in [1,n]$，然后交换第 $i$ 个和第 $j$ 个球。

求最终黑球位置期望，对 $P=998,244,353$ 取模。

Solution

设 $f_i$ 为第 $i$ 次操作后的期望值，显然 $f_0=1$。

则有：

$$f_i= \begin{cases} 1 &,i=0\\ \dfrac{(n-1)^2+1}{n^2}\times f_{i-1}+\dfrac{2}{n^2}\times (\dfrac{n(n+1)}{2}-f_{i-1}) &,\text{otherwise.} \end{cases}$$

可以将式子分为两部分：

• 第一部分加号前，表示在第 $i$ 次操作时球 $x$ 的位置没有被移动。此时选择的两数 $a,b$ 各有 $n-1$ 种选择，注意还有一种 $a=b=x$ 的情况，所以该情况概率为 $\dfrac{(n-1)^2+1}{n^2}$，再乘上该情况下 $x$ 的位置，即 $f_{i-1}$；
• 第二部分为加号后，表示在第 $i$ 次操作时移动了 $x$ 的位置。球落到每个位置上的概率显然是相等的 $\dfrac{2}{n^2}$，期望显然为 $\sum_{i=1}^n(\dfrac{2}{n^2}\times i)$。但需要减去 $x$ 仍在操作前位置上的情况，注意由于不确定当前 $x$ 的位置，不能只使 $i\in[2,n]$ 而是需要减掉 $f_{i-1}$。

Core Code

int ksm(int x,int p) {
    int res=1;
    while(p>0) {
        if(p&1) res=res*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return res;
}
signed main() {
    n=read();k=read();
    f[0]=1;
    int n2=ksm((n*n)%mod,mod-2);
    int a=((n-1)*(n-1))%mod;
    int sum=((1+n)*n/2)%mod;
    for(int i=1;i<=k;i++) {
        f[i]=((a+1)*f[i-1]%mod*n2%mod+((2*n2%mod)*(sum-f[i-1])%mod)%mod+mod)%mod;
    }
    printf("%lld\n",f[k]); 
    return 0;
}

P1654 OSU!

Problem Link

Statement

给定 $n$ 次操作，每次操作有成功率 $p_i$，成功记为 $1$，失败记为 $0$，形成一个长度为 $n$ 的 01 串。极长的连续 $x$ 个 $1$ 贡献贡献 $x^3$ 分数，求期望得分。

Solution

设 $f_i$ 为第 $i$ 次操作后的期望得分，$f_0=0$。

每次操作成功对答案的贡献为 $(k+1)^3-k^3=3k^2+3k+1$。

则通过递推求 $k^2$ 和 $k$ 的期望即可，这里设为 $len2$ 和 $len$，要注意 $E(k^2)\not =E(k)^2$，所以 $len2$ 和 $len$ 需要分别求。

则最终转移方程为：

$$\begin{aligned} len_i&=(len_{i-1}+1)\times p_i\\ len2_i&=(len2_i+2\times len2_{i-1}+1)\times p_i\\ f_i&=f_{i-1}+(3\times len2_{i-1}+3\times len_{i-1}+1)\times p_i \end{aligned}$$

这里还注意到最后一个式子与前两个不同。原因是前两个式子的含义是第 $i$ 位的期望，但最终要求的答案是前 $n$ 位的期望。

Core Code

int main() {
    n=read();
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) {
        len[i]=(len[i-1]+1.0)*p[i];
        len2[i]=(len2[i-1]+2.0*len[i-1]+1.0)*p[i];
        f[i]=f[i-1]+(3.0*len2[i-1]+3.0*len[i-1]+1.0)*1.0*p[i];
    }
    printf("%.1lf\n",f[n]);
    return 0;
}

P1297 [国家集训队] 单选错位

Problem Link

Statement

$n$ 道题，第 $i$ 道有 $a_i$ 个选项，选择每个选项的概率第相等的。但是每个选择都会填到后一道题。求对的期望题数。

Solution

对于每一个题目 $i$，其是否正确仅与 $i$ 和 $i-1$ 道题目选项个数有关。

要使 $i$ 和 $i-1$ 个题目选择的答案一样，仅有 $\min(a_i,a_{i-1})$ 种情况，而总共有 $a_i\times a_{i-1}$ 种情况。易证。

所以 $f_i=f_{i-1}+\dfrac{\min(a_i,a_{i-1})}{a_i\times a_{i-1}}$。

题目对内存要求严格，不能用数组保存答案。

Core Code

ans=1.0*min(a[1],a[n])/(a[1]*a[n]*1.0);
for(int i=2;i<=n;i++) {
    ans=ans+1.0*min(a[i-1],a[i])/(a[i-1]*a[i]*1.0);
}
printf("%.3Lf\n",ans);

P4550 收集邮票

Problem Link

Statement

有 $n$ 种不同的邮票，皮皮想收集所有种类的邮票。每次只能买一张，买到的邮票是等概率的。所以皮皮购买第 $k$ 次邮票需要支付 $k$ 元钱。

求得到所有种类的邮票需要花费的钱数目的期望。

Solution

设买了 $k$ 张邮票才能集齐，那么最终答案为 $\sum_{i=1}^ki=\dfrac{k+k^2}{2}$。

所以我们设 $f_i$ 表示已经集齐了 $i$ 张邮票，还需要买的邮票数的期望。

因为有 $\dfrac{i}{n}$ 的概率买到已有的，那么此时次数应 $+1$；有 $\dfrac{n-i}{n}$ 的概率买到没有的，次数应在 $f_{i+1}$ 的基础上 $+1$。

所以可得：

$$\begin{aligned} f_i&=\dfrac{i}{n}\times(f_i+1)+\dfrac{n-i}{n}\times(f_{i+1}+1)\\ f_i&=\dfrac{i}{n}f_i+\dfrac{n-i}{n}f_{i+1}+1\\ \dfrac{n-i}{n}f_i&=\dfrac{n-i}{n}f_{i+1}+1\\ f_i&=f_{i+1}+\dfrac{n}{n-i} \end{aligned}$$

由于上文提到 $E(k^2)\not =E(k)^2$，所以需要根据 $f_i$ 完全平方展开预处理一个 $g_i$：

$$\begin{aligned} g_i&=\dfrac{i}{n}\times(f_i+1)^2+\dfrac{n-i}{n}\times(f_{i+1}+1)^2\\ \Rightarrow&=g_{i+1}+\dfrac{2i}{n-i}f_i+2f_{i+1}+\dfrac{n}{n-i} \end{aligned}$$

由于 $f_i$ 依赖于 $f_{i+1}$ 且已知 $f_{n}=0$，故使用倒推。最终答案 $\dfrac{f_0+g_{0}}{2}$。

Core Code

n=read();
for(int i=n-1;i>=0;i--) {
    f[i]=f[i+1]+n*1.0/(n-i)*1.0;
    g[i]=g[i+1]+i*2.0/(n-i)*1.0*f[i]+2.0*f[i+1]+n*1.0/(n-i)*1.0;
}
printf("%.2lf\n",(f[0]+g[0])/2.0);

---

注：本文最初发表于 2023-05-27。