数学期望 学习笔记

前言

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

一个例子：

一次考试满分 $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

Explanation

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

Solution

设 $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;
}