期望整理&&期望学习笔记&&期望入门

我以后再也不写纸质整理报告了，纸上一直爽，一直纸上一直爽。

前言:

转载自dsr的https://www.cnblogs.com/dsrdsr/protected/p/11373538.html

常用技巧及其套路

$\sum\limits_{i=0}^{n}x^i=\frac{1-x^{n+1}}{1-x}$
当n趋于oo时候
$\sum\limits_{i=0}^{oo}x^i=\frac{1}{1-x}$
期望的线性性。
$E(x+y)=E(x)+E(y)$
前缀和技巧
对于离散变量。
$P(x=k)=P(x<=k)-P(x<=k-1)$

小例题1

有 $n$ 个随机变量 $X[1…n]$，每个随机变量都是从 $1…S$ 中
随机一个整数，求 $Max(X[1…n])$ 的期望
解：$E(max)=\sum\limits_{i=1}^{S}P(max=i)*i$
$=\sum\limits_{i=1}^{S}(P(max<=i)-P(max<=i-1))*i$
$=\sum\limits_{i=1}^{S}(\frac{i^n}{S^n}-\frac{(i-1)^n}{S^n})*i$

小例题2

概率为 $p$ 的事件期望 $\frac{1}{p}$ 次后发生
你：这不显然吗？我：…………
$E(x)=\sum\limits{i} P(x=i)*i$
$=\sum\limits{i} (P(x>=i)-P(x>=i+1))*i$
$=\sum\limits{i} ((1-P)^{i-1}-(1-p)^i)*i$
$=[(1-p)^0-(1-p)]+[(1-p)-(1-p)^2]*2+[(1-p)^2-(1-p)^3]*3…………$
$=\sum\limits_{i=0}^{oo}(1-p)^i$
$=\frac{1}{1-(1-p)}=\frac{1}{p}$

拿球问题

典例1.

箱子里有 $n$ 个球 $1…n$，你要从里面拿 $m$ 次球，拿了后不放
回，求取出的数字之和的期望
解:$\sum\limits_{i=1}^{n}P(i)*i=\sum\limits_{i=1}^{n}\frac{m}{n}*i=\frac{m*(n+1)}{2}$

典例2.

箱子里有 $n$ 个球 $1…n$，你要从里面拿 $m$ 次球，拿了后放
回，求取出的数字之和的期望
小学老师教过我们，放不放回他们的概率是相等的。
$\sum\limits_{i=1}^{n}P(i)*i=\sum\limits_{i=1}^{n}\frac{m}{n}*i=\frac{m*(n+1)}{2}$

典例3.

箱子里有 $n$ 个球 $1…n$，你要从里面拿 $m$ 次球，拿了后以
$p1$ 的概率放回，以 $p2$ 的概率放回两个和这个相同的球，
求取出的数字之和的期望
感性吧，我都忘了。
每个球都是相等的，所以每个球都有概率被选中，
都有同样的概率被放回去，也都有同样的概率放回两个.
所以选$i$的概率都是$\frac{m}{n}$

游走问题

典例1.

在一条 $n$ 个点的链上游走，求从一端走到另一端的概率
$X_i$表示$i$走到$i+1$的步数。
$E(n)=\sum\limits_{i=1}^{n}E(X_i)$
$E(X_i)=\frac{1}{2}+\frac{1}{2}(1+E(X_{i-1})+E(X_i))$
$E(X_i)=\frac{1}{2}+\frac{1}{2}+\frac{1}{2}E(X_{i-1})+\frac{1}{2}E(X_i)$
$E(X_i)=E(X_{i-1})+2$
$E(n)=1+3+5…………+2n-3=(n-1)^2$

典例2.

在一张 $n$ 个点的完全图上游走，求从一个点走到另一个点的概率
每个点都是等价的，$p=\frac{1}{n-1}$，所以期望就是n-1次成功。

典例3.

在一张 $2n$ 个点的完全二分图上游走，求从一个点走到另一个点的概率
还是左边等价，右边等价。
A:同侧 $\frac{1}{n}+\frac{n-1}{n}(2+A)$
B:异侧 $1+A$
4.在一张 $n$ 个点的菊花图上游走，求从一个点走到另一个点的概率
A:根->叶 $\frac{1}{n-1}+\frac{n-2}{n-1}(2+A)$
B:叶->根 $1$
C:叶->叶 $A+1$

典例5.

在一棵 $n$ 个点的树上游走，求从根走到 $x$ 的期望步数
$X_i$从i开始游走，走到$father_i$的步数，$d_i$为$i$的度数
$f(x)=\frac{1}{d[x]}+\frac{1}{d[x]}*\sum\limits_{i=1}^{d[x],i!=fa[x]}(1+f(son[x])+f(x))$

典例6.

构造一张$200$个点的无向图，使得上面从 $S$ 走到 $T$ 的随机游走期望步
数>=1000000
棒棒糖图: 1000个点构造一个完全图，然后里面找一个点连出一条链子。
这个期望步数差不多是$100^3$

经典问题

典例1.

每次随机一个 $[1,n]$ 的整数，问期望几次能凑齐所有数
一直选，直到出现没出现过的数字。
$p=\frac{n-i+1}{n},E=\frac{n}{n-i+1}$
$\sum\limits_{i=1}^{n}\frac{n}{n-i+1}$
$\sum\limits_{i=1}^{n}\frac{n}{i}$

典例2.

随机一个长度为 $n$ 个排列 $p$，求 $p[1…i]$ 中 $p[i]$ 是最大的数的概率
$\frac{1}{i}$,最大值有i个位置可以挑。

典例3.

问满足上面那个题的 $i$ 的个数的平方的期望
$(x_i)^2=x_i=[P(i)==max(1…i)]$
$X=\sum\limits_{i=1}^{n}x_i$
$E(X^2)=E(X^2)$
$=E({(\sum\limits_{i=1}^{n}x_i)}^{2})$
$=E(\sum\limits_{i!=j}x_i*x_j+\sum\limits{i=1}^{n}x_i)$
因为$x_i,x_j$相互独立
$=E(\sum\limits_{i!=j}\frac{1}{i*j}+\sum\limits{i=1}^{n}\frac{1}{i})$

典例4.

随机一个长度为 $n$ 的排列 $p$，求 $i$ 在 $j$ 的后面的概率
$\frac{1}{2}$
合法的位置可以颠倒过来嘛。

典例5.

随机一个长度为 $n$ 的排列 $p$，求它包含 $w[1…m]$ 作为子序列/连续子序列的概率
子序列：$C_{n}^{m}\frac{(n-m)!}{n!}=\frac{1}{m!}$
$n-m$乱排，剩下的m顺序不变，插入n中，从n中选出m个位置。
连续子序列：$(n-m+1)\frac{(n-m)!}{n!}=\frac{(n-m+1)!}{n!}(n-m+1)$
不是一个个插入n中了，是找个缝全钻进去。

典例6.

有 $n$ 堆石头，第 $i$ 堆个数为 $a[i]$，每次随机选一个石头然后把那一整堆都扔了，求第 $1$ 堆石头期望第几次被扔
看不懂

典例7.

随机一个长度为 $n$ 的$01$串，每个位置是 $1$ 的概率是 $p$ ，定义 $X$ 是每段连续的 $1$ 的长度的平方之和，求$E[X]$
$g(x)$连续1的最长长度。$f(x)$价值。
$0:g(x)=0,f(x)=f(x-1);$
$1:g(x)=g(x-1)+1,f(x)=f(x-1)-g(x-1)^2+(g(x-1)+1)^2$
$=f(x-1)+2g(x-1)+1$
$E(f(x))=p*(E(f(x-1))+2*E(g(x-1))+1)+(1-p)*E(f(x-1))$
$E(g(x))=p*(E(g(x-1))+1)$

典例8.

给一个序列，每次随机删除一个元素，问 $i$ 和 $j$ 在过程中相邻的概率
$1-无关区间-i-有关-x-j-无关区间-n$
考虑交换x和i的位置，$len=j-i+1$。
就是求len个数中，i,j(可颠倒)总是在后面的概率,$\frac{2*(j-i-1)!}{(j-i+1)!}$

典例9.

给定一棵树，将他的边随机一个顺序后依次插入，求 $u,v$ 期望什么时候连通
u,v,路径上的边全连上才会联通，其他变雨我无瓜。
枚举第几次恰好联通
$\sum\limits_{i=1}^{n-1}\frac{k!C_{i-1}^{k-1}(n-k-1)!}{(n-1)!}*i$

典例10.

给 $1…n$ 这 $n$ 个数，每次随机选择一个还在的数并且删掉他的所有倍数，求期望几次删完
每次选一个还在的数删掉，然后标记他的倍数。
$E(x)$没标记前被删掉的期望。
$P(x)=\frac{1}{floor(n/x))}$
$E(x)=floor(n/x)$

期望线性性问题

典例1.

给定 $n$ 个硬币，第 $i$ 个硬币的价值为 $w[i]$，每次随机取走一个硬币，获得的
收益是左右两个硬币的价值的乘积，求期望总价值.
$1-无关区间-i-有关-x-j-无关区间-n$
还是差不多的，$len=j-i+1$
$\sum\limits_{i!=j} \frac{2*(len-2)!}{len!}*w[i]*w[j]$

典例2.

有 N 个数 a[1…N]，每次等概率选出两个数，然后合并成?一个新的数放回
来，得到的收益是新的数的值，求总收益的期望
x_i为出现次数。
$E(x)=\sum\limits_{i=1}^{n}E(x_i)*a_i$
$E(x_j)=\sum\limits_{i=1}^{n-1}\frac{2}{n-i+1}$
感觉这个$E(x_j)$可以拿出来

典例3.

给定一个数列 $W[1…N]$，随机一个排列 $H$，如果 $H[i]$ 比 $H[i-1]$ 和 $H[i+1]$ 都
大，就获得 $W[i]$ 的收益，求期望收益
$E(X)=\sum\limits_{i=1}^{n}P(x_i)*w[i]$
$P(x_i)=h[i]>max(h[i-1],h[i+1])=\frac{1}{3}$

典例4.

给出一棵树，一开始每个点都是白的，每次选一个白点将他子树里所有点染
黑，求期望几次染黑整个树
在父亲被染黑之前才有贡献。
$\sum\limits_{i=1}^{n}\frac{1}{dep[i]}$

典例5.

有 $N$ 个黑球，$M$个白球，每次等概率取出一个球（不放回），将取出来的球
的颜色写成一个$01$序列，求 $”01”$ 的期望出现次数
可能是错的过程:
在$2~n+m$中，考虑第$i$个数为$1$,概率为$\frac{n}{n+m-1}$
第$i-1$为0的概率为$\frac{m}{n+m}$
可能是正确的答案：
整得答案就是$\frac{n*m}{n+m}$

一些例题

1.换教室

链接

loj

思路

f[i][j][0/1] 前i个人，用了j次机会，第i节课有没有申请过。

代码

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
const int _ = 2019;
const double INF = 0x3f3f3f3f;
using namespace std;
int read() {
    int x = 0, f = 1;char s = getchar();
    for (; s>'9' || s<'0';s = getchar()) if (s == '-') f = -1;
    for (; s>='0' && s<='9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}
int n, m, v, e, c[_], d[_], dis[_][_];
double f[_][_][2], k[_];
int main() {
    n = read(), m = read(), v = read(), e = read();
    FOR (i, 1, n) c[i] = read();
    FOR (i, 1, n) d[i] = read();
    FOR (i, 1, n) scanf("%lf", &k[i]);
    FOR (i, 1, v) FOR (j, 1, v) dis[i][j] = (i != j) * INF;
    FOR (i, 1, e) {
        int u = read(), v = read();
        dis[v][u] = dis[u][v] = min(dis[u][v], read());
    }
    FOR (k, 1, v) FOR (i, 1, v) FOR (j, 1, v)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    FOR (i, 1, n) FOR (j, 0, m) f[i][j][0] = f[i][j][1] = INF;
    f[1][0][0] = 0, f[1][1][1] = 0;
    FOR (i, 2, n) {
        FOR (j, 0, m) {
            f[i][j][0] = min(f[i - 1][j][0] + 1.0 * dis[c[i - 1]][c[i]],
                             f[i - 1][j][1] + k[i - 1] * dis[d[i - 1]][c[i]] + (1.0 - k[i - 1]) * dis[c[i - 1]][c[i]]);
            if(j) {
                f[i][j][1] = min(f[i - 1][j - 1][0] + k[i] * dis[c[i - 1]][d[i]] + (1 - k[i]) * dis[c[i - 1]][c[i]],
                                 f[i - 1][j - 1][1] + k[i] * k[i - 1] * dis[d[i - 1]][d[i]] + k[i] * (1 - k[i - 1]) * dis[c[i - 1]][d[i]] + 
                                (1 - k[i]) * k[i - 1] * dis[d[i - 1]][c[i]] + (1 - k[i]) * (1 - k[i - 1]) * dis[c[i - 1]][c[i]]);
            }
        }
    }
    double ans = INF;
    FOR (i, 0, m) ans = min(ans, min(f[n][i][0], f[n][i][1]));
    printf("%.2f\n", ans);
    return 0;
}

2.Deep Dark Forest(树的期望直径)

题目大意

给出一棵树，其中每条边的长度有 $0.5$ 的概率是 $1$，$0.5$的
概率是 $0$，求直径的期望
$1<=n<=200$

思路

$E(S)=\sum\limits_{i} p(i=S)*i$
$E(S)=\sum\limits_{i} p(i=S)*\sum\limits_{j=1}^{i}1$
$E(S)=\sum\limits_{j=1}\sum\limits_{i>=j} p(i=S)$
$E(S)=\sum\limits_{j=1} p(S>=j)$
$E(S)=1-\sum\limits_{j=1}p(S<=j-1)$
枚举这个$j$，就叫他$K$。
设$f[i][j]$表示i这颗子树内，从i到下最长的深度为j。
$g[k]=\frac{1}{2}f[v][k],g[k+1]=\frac{1}{2}f[v][k]$
然后枚举$j$和$k,(j+k<=K)$.
$f[i][max(j,k)]=f[i][j]+g[k]$

3.球染色

题目大意

有 $n$ 个球，一开始颜?色是 $c[1…n]$，每次随机一对数 $(i,j)$ 然
后 $c[j]=c[i]$，求让 $c$ 全部相同的期望步数
$1<=n<=1000000$

思路

每种颜色都是等价的
$f_i$为有了i个目标颜色，还要期望走$f_i$步全部变为x
$p1$俩都是x或者都不是x
$p2$x变为不是x
$p3$不是x变为x
$f_n=0$
$f_i=f_i*p1+f_{i-1}*p2+f_{i+1}*p3$

4.拓扑排序

题目大意

给定一张$n$个点的有向图，$f(E)$表示边集$E$的拓扑序个
数，现在随机取一个边的子集$E$，求$f(E)$的期望。
$n<=20$

思路

WTF,他在说啥。

5.单选错位

链接

luogu

思路

权为1，求期望就是求概率。
前面ans和后面ans相等，期望的线性性拆开.
分开算。

代码

#include <bits/stdc++.h>
using namespace std;
int n, a, A, B, C, first, las, now;double ans;
int main() {
    scanf("%d%d%d%d%d",&n,&A,&B,&C,&first);
    las = first;
    for (int i = 2; i <= n; i++) {
        int now = (1LL * las * A + B) % 100000001;
        int x = las % C + 1, y = now % C + 1;
        ans += 1.0 * min(x, y) / x / y;
        las = now;
    }
    las = las % C + 1, first = first % C + 1;
    ans += 1.0 * min(las, first) / las / first;
    printf("%.3f\n", ans);
    return 0;
}

6.区间翻转

题目大意

给定一个长度为 $n$ 的 $01$ 串，每次随机一个区间将里面所有元素翻转
求 $m$ 次操作后 $1$ 的期望个数
$n=100000$
$m=10^9$

思路

被覆盖的概率为$p=\frac{i*(n-i+1)}{n*(n-1)}$
所以每一位上的1都是等价的，0也一样。
考虑每一位的概率(即期望)。
$0->0*(1-p)$
$1->1*(1-p)$
$1->0*p$
$0->1*p$
矩阵快速幂维护一下就做完了。

7.区间交

题意

我们定义一种随机区间的方法：
$L=Random(1,N)$
$R=Random(L,N)$
现在这样随机出两个区间，求他们相交的概率
$N<=1000000$

思路

$g_r$为区间右端点$=r$的概率
$g_r=\sum\limits_{i=1}^{r}\frac{1}{n}\frac{1}{n-l+1}$
f为g的前缀和,枚举靠右区间的端点
$ans=\sum_{i=1}^{n}f_i$

代码

#include <bits/stdc++.h>
using namespace std;
const int _=1e6+7;
int n;
double g[_], f[_], ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        g[i] = g[i - 1] + 1.0 / n / (n - i + 1);
        f[i] = f[i - 1] + g[i];
        ans += f[i];
    }
    printf("%.8f\n", ans);
    return 0;
}

8.凸包的期望

链接

我找到了，不过是个私密网站，真抠。
不过他们的凸包期望面积题解还是能看的

题目大意

给 $n$ 个点，随机选一个点集，求二维凸包的期望点数
$1<=n<=200$
保证没有三点共线

思路

枚举两点。它为凸包上的线段当且仅当所有的点都在同侧.
期望为$2*p(A)*p(b)*\prod_{i \in右边} (1-p(i))$
复杂度$O(n^3)$
三维凸包也差不多，好想要用欧拉定理。

代码

FOR(i,1,n) FOR(j,1,n) {
    if(i==j) continue
    int tmp=2*p[i]*p[j];
    FOR(k,1,n) {
        if(k==i||k==j) continue
        if(onleft(i,j,k)) tmp*=1-p[k];
    }
    ans+=tmp;
}

9.KILL

题目大意

一个游戏有 n 个人，规则是这样的：
1. 随机选择一个还没死的人，让他活着离开
2. 活着离开之前，他会向剩下所有人开一枪，有 $p$ 的概率致死
重复以上步骤直到所有人要么死了要么离开了
求一个?人活着离开且一共被开了 $k$ 枪的概率
$1<=n<=2000$

思路

$f[i][j]$表示剩下i个，已经开了j抢了。
这个男银勒了，$f[i][j]*(1-(1-p)^j) -> f[i-1][j]$
他是欧皇，$f[i][j]*(1-p)^j -> f[i-1][j+1]$
$f[n][0]=1$