期望真是个很神奇的东西啊，虽然利用方程移项可以证明，但总感觉很妙

定义

设数\(x\)有\(n\)种取值，每种取值\(a_i\)对应概率为\(p_i\)，则\(x\)的数学期望为\(E(x)=\sum a_ip_i\)

• 比如说抛掷一枚硬币，定义正面为\(1\)，反面为\(0\)，则抛一枚硬币的期望为\(E(x)=0.5\times 1+0.5\times 0=0.5\)
• 掷骰子的期望为\(\frac 16\times 1+\frac 16\times 2+\cdots+\frac 16\times 6=\frac 16\sum_{i=1}^6i=3.5\)
• 彩票一张\(1\)元，中奖概率为\(\frac 1{10^6}\)，奖金\(10^5\)，则买一张彩票的收益期望为\(\frac 1{10^6}\times 10^5=0.1\)元

虽然这些期望都是小数，是取不到的值，但期望表示的并不是一个可能发生的情况，而是情况的一个平均，可以形象地理解为当实验进行越来越多的时候，平均情况会趋于接近期望（比如掷骰子\(100\)次的时候，平均情况会接近\(3.5\)，而当掷\(10^6\)次的时候，会更加接近\(3.5\)）

更一般的，若\(x\)的取值并不是离散的，那么可以用积分表达期望 换汤不换药

基础期望

一枚硬币，抛到正面的概率为\(p\)，问期望抛几次得到一个正面

先设答案为\(x\)次，根据期望的定义可以列出式子\(x=p\cdot 1+(1-p)(x+1)\)，可以移项得出\(x=\frac 1p\)

解释一下那个式子的右边，考虑掷一次有两种情况：

• 有\(p\)的概率为正面，这个时候只需要一次操作（即当前这次），取值\(1\)，概率\(p\)，所以第一项为\(p\cdot 1\)；
• 有\(1-p\)的概率为反面，由于抛到反面即返回最初的情况，所以还需要抛\(x\)次，加上这一次，取值\(x+1\)，概率\(1-p\)，所以第二项为\((1-p)(x+1)\)

列出这个方程可以解出其中某一项，可能这就是期望题目的大致玩法吧

给定一个有\(n\)个面的骰子，问期望多少次能掷出所有面（SPOJ-FAVDICE）

发现这题不能像上一题那样只设一个变量，所以需要利用dp思想，设\(f_i\)表示还剩\(i\)面未被掷到时期望还需多少次完成

利用上一题的思想枚举所有后继情况，假设当前还剩\(i\)面未被掷到

• 这一次掷到了还未被掷到的面，概率为\(\frac in\)，剩余次数为\(f_{i-1}+1\)
• 这一次掷到了已经被掷到的面，概率为\(\frac {n-i}n\)，剩余次数为\(f_i\)

而这两个之和为\(f_i\)，即\(f_i=\frac in(f_{i-1}+1)+\frac {n-i}n(f_i+1)\)，移项可得\(f_i=f_{i-1}+\frac ni\)

而\(f_0=0\)，则递推出\(f_n\)即为答案

从这题可以看出一种解题方法，设置状态，列出方程，解出其中某一项，进行dp转移

你有一个战斗力\(v\)，有\(n\)扇门，每天随机抽取一扇门\(i\)，若\(v>c_i\)，则会用\(t_i\)天的时间离开，否则\(v\)增加\(c_i\)，求离开天数的期望（ZOJ-3640）

这题也差不多，算是一个小练习，设\(f_i\)表示当战斗力为\(i\)时离开的期望天数

若\(i\leq c_i\)，\(f_i+=\frac 1nf_{i+c_i}\)，否则\(f_i+=\frac 1nt_i\)

综合这最后这两题可以看出，如果用Dp解简单的期望题，状态的设置需要满足可重复利用（比如当战斗力为一个确值\(x\)时，期望天数一定是个定值）

double f(int x){
	if(x>max_c)return sum_t/n;
	if(dp[x]>-0.5)return dp[x];
	double res=0;
	for(int i=1;i<=n;++i)
		if(x<=c[i])res+=1+f(x+c[i]);
		else res+=t[i];
	return dp[x]=res/n;
}

循环转移

有些题目是没有像上面题目那样的单项转移的，比如说下面这题

一个\(n\)点\(m\)边无向连通图，在图上进行随机游走，初始时在\(1\)号顶点，每一步以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当到达\(n\)号顶点时游走结束，总分为所有获得的分数之和。 要求对所有边进行编号（\(1\)~\(m\)），使得总分的期望值最小。（HNOI-2013游走）

很明显的贪心思路：求每条边的访问次数期望，按照期望大小次序给定边权，再给边权赋值

但是求边的期望又可以由边两边的点的期望得到，所以这题的主要难度在于求每个点的访问次数期望

用之前的方法进行设置。设\(f_i\)表示走到\(i\)节点的次数期望

由于任意两点间都有可能互相访问，所以对于任意一条边\((u,v)\)，\(f_u+=\frac 1{deg_v}f_v,f_v+=\frac 1{deg_u}f_u\)

发现这里不能像之前几道题来解方程了，因为这里存在循环（\(f_1\)要用\(f_2\)推导，\(f_2\)要用\(f_1\)推导）

可以利用高斯消元求解，时间复杂度\(O(n^3)\)

类似的题还有很多，比如HNOI-2011XOR和路径

循环转移的非高斯消元解法

下面介绍两种循环转移的非高斯消元解法（复杂度\(O(n)\)）

线性情况

有三个骰子，分别有\(k_1,k_2,k_3\)面，每次同时投掷得\(x_1,x_2,x_3\)，分数增加\(x_1+x_2+x_3\)，若三者的值分别为\(a,b,c\)，则分数清零，若分数大于\(n\)，则结束操作。求期望多少次投掷后结束操作（zoj-3329）

尝试用上一题的做法来解，设\(f_i\)表示当前分数为\(i\)时的期望还要进行多少次，令\(p_k\)表示三个骰子分数和为\(k\)的概率

则可以列出方程：\(f_i=\sum_kp_k(f_{i+k}+1)\)

将清零的情况提出来，记做 \(p_0\)，得到\(f_i=1+f_0p_0+\sum_{k\not =0}p_kf_{i+k}\)

舍弃之前说的高斯消元做法，介绍一种更优秀的做法

由于所有式子都要用到 \(f_0\)，而由于整个转移系统是线性的，所以不妨假设 \(f_i=a_if_0+b_i\)

然后将\(f_{i+k}=a_{i+k}f_0+b_{i+k}\)套到之前的式子里去，得到

\(f_i=1+f_0p_0+\sum_{k\not =0}p_k(a_{i+k}f_0+b_{i+k})\\=(p_0+\sum_{k\not =0}p_ka_{i+k})f_0+\sum_{k\not =0}p_kb_{i+k}+1\)

对比式子：\(f_i=a_if_0+b_i\)，发现两个式子结构相同，可得：

\(a_i=p_0+\sum_{k\not =0}p_ka_{i+k}\\b_i=1+\sum_{k\not =0}p_kb_{i+k}\)

由于\(a_i,b_i=0(i>n)\)，而上面的式子中所有量是可以递推而得，没有循环转移关系的，所以可以递推得到\(a_0,b_0\)

将\(i=0\)代入，得到\(f_0=a_0f_0+b_0\)，即\(f_0=\frac {b_0}{1-a_0}\)，得解

树上情况

一棵 \(n\) 个结点的树，从点 \(x\) 出发，每次等概率随机选择一条与所在点相邻的边走过去。\(Q\) 次询问，每次询问给定一个集合 \(S\)，求如果从 \(x\) 出发一直随机游走，直到点集 \(S\) 中所有点都至少经过一次的话，期望游走几步。（pkuwc2018随机游走）

这题之前就写过题解，在这，可以看看中间如何将树上情况的循环转移优化成递推

基本思路也是设每个节点从父亲转移，递推求得系数\(a_i,b_i\)，这样是\(O(n)\)的

分层图情况&一般图情况

这个待填坑吧，分层图好像可以玩，听说去年pkuwc上有人想出了一个在一般图上高斯消元的高效算法