期望真是个很神奇的东西啊, 虽然利用方程移项可以证明, 但总感觉很妙
定义
设数 \(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\)个面的骰子, 问期望多少次能掷出所有面( https://cn.vjudge.net/problem/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\leq c_i\), 则会用 \(t_i\)天的时间离开, 否则 \(v\)增加 \(c_i\), 求离开天数的期望(ZOJ-3640 https://cn.vjudge.net/problem/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 游走 https://www.luogu.org/problemnew/show/P3232 )
很明显的贪心思路: 求每条边的访问次数期望, 按照期望大小次序给定边权, 再给边权赋值
但是求边的期望又可以由边两边的点的期望得到, 所以这题的主要难度在于求每个点的访问次数期望
用之前的方法进行设置. 设 \(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 和路径 https://www.luogu.org/problemnew/show/P3211
循环转移的非高斯消元解法
下面介绍两种循环转移的非高斯消元解法(复杂度 \(O(n)\))
线性情况
有三个骰子, 分别有 \(k_1,k_2,k_3\)面, 每次同时投掷得 \(x_1,x_2,x_3\), 分数增加 \(x_1+x_2+x_3\), 若三者的值分别为 \(a,b,c\), 则分数清零, 若分数大于 \(n\), 则结束操作. 求期望多少次投掷后结束操作( https://cn.vjudge.net/problem/zoj-3329 )
尝试用上一题的做法来解, 设 \(f_i\)表示当前分数为 \(i\)时的期望还要进行多少次, 令 \(p_k\)表示三个骰子分数和为 \(k\)的概率
则可以列出方程:\(f_i=\sum_kp_k(f_{i+k}+1)\)
将 \(1\)提出来, 把 \(p_0\)单独提出来, 得到 \(f_i=1+f_0p_0+\sum_{k\not =0}p_kf_{i+k}\)
舍弃之前说的高斯消元做法, 介绍一种更优秀的做法
由于所有式子都要用到 \(p_0\), 所以不妨假设 \(f_i=a_ip_0+b_i\)
然后将 \(f_{i+k}=a_{i+k}p_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_ip_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 随机游走 https://loj.ac/problem/2542 )
这题之前就写过题解, 在这, 可以看看中间如何将树上情况的循环转移优化成递推
基本思路也是设每个节点从父亲转移, 递推求得系数 \(a_i,b_i\), 这样是 \(O(n)\)的
分层图情况 & 一般图情况
这个待填坑吧, 分层图好像可以玩, 听说去年 pkuwc 上有人想出了一个在一般图上高斯消元的高效算法
来源: https://www.cnblogs.com/penth/p/10218441.html