概率期望学习笔记

众所周知,一个随机变量 $x$ 的数学期望定义为 $E(x)$,即是 $E(x)traodinary$ 的缩写形式,代表 $x$ 是一个非凡的数字……

概念

随机变量 $x$ 的数学期望 $E(x)$ 定义为 $x$ 的每种取值的概率加权和,可以理解为 $x$ 在平均情况下的取值,我们一般称其为「期望取值」。
举个例子,若 $x$ 有 $1/3$ 的概率为 $1$,有 $2/3$ 的概率为 $2$,则 $E(x)=1/3+2\times (2/3)=5/3$。

线性性

根据乘法结合律以及分配律,可以发现期望具有线性性,可以将其理解为「元素和的期望等于元素期望的和」,亦即:
$$ E(\Sigma x_i)=\sum E(x_i) $$ 设 $c$ 为常量,也容易验证:
$$E(x+c)=E(x)+c$$

一道简单题

有一个长度为 $n$ 的数列,一开始所有位置都未被访问。每次随机一个未被访问过的位置,将它和它之前的位置都标记为访问过,问期望操作次数。
$n\le 10^{18}$

考虑期望的线性性,答案就等于每个位置能被访问到的概率。一个位置 $i$ 能被访问到当且仅当它在所有它后面的数之前被访问,这个概率是 $\frac{1}{n-i+1}$,因此容易发现答案是调和级数 $H_n$,使用近似公式计算即可。

又一道简单题

有一个 $n$ 个节点的有根树,一开始所有节点都未被访问。每次随机一个未被访问过的节点,将它到根的路径上所有点都标记为访问过,问期望操作次数,对 $998244353$ 取模。
$n\le 10^7$

仿照上题,容易发现答案是 $\sum\limits_{i=1}^n\frac{1}{sz[i]}$,其中 $sz[i]$ 表示子树 $i$ 的大小,线性求逆即可。

双一道简单题

$n$ 堆石子,每堆有 $a_i$ 个,每次随机选一个石子,并取光它所在的那堆石子。问第一堆石子被取到的时间的期望。
$n\le 10^5$

根据期望的线性性,答案等于每堆石子在 $1$ 之前取到的期望之和,即 $1+\sum\limits_{i=2}^n\frac{a_i}{a_1+a_i}$,线性计算即可。

叒一道简单题

一个 $n$ 面的骰子,问每一面都被掷到的期望投掷次数。
$n\le 10^{18}$

此类问题被称作「赠券收集问题」。
设 $f[n]$ 为 $n$ 面掷出后还需投掷的次数的期望,易得 $f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$,整理得 $f[i]=f[i+1]+\frac{n}{n-i}$,从而有 $f[0]=nH_n$,利用公式计算即可。

叕一道简单题

求所有 $n!$ 个 $n$ 的全排列中,逆序对数的期望,对 $998244353$ 取模。
$n\le 10^{7}$

众所周知,$n$ 的全排列一共有 $\dfrac{n!}{2}\dbinom{n}{2}$ 个逆序对,即对每个二元组 $(i,j)$ 讨论一下它们是否会形成逆序对。
因此答案为 $\dfrac{\dfrac{n!}{2}\dbinom{n}{2}}{n!}=\dfrac{n(n-1)}{4}$。

一道栗题

一个长度为 $n$ 的 01 串按以下方式生成:第 $i$ 个位置有 $a_i$ 的概率为 1,$1-a_i$ 的概率为 0。01 串的价值如下计算:每一个极长全 1 子串的长度的三次方之和。
求该 01 串的价值的期望。
$n\le 10^5$

设 $l_1[i]$ 表示末尾一段极长全 1 子串长度的期望, $l_2[i]$ 表示末尾一段极长全 1 子串长度的平方的期望,设 $f[i]$ 为长度为 $i$ 的 01 串价值的期望,考虑到有 $(x+1)^3-x^3=3x^2+3x+1$,则有:
$$ f[i]=f[i-1]+a_i(3l_2[i-1]+3l_1[i-1]+1) $$ 即对最后加入的位置 $i$ 讨论了一下它对答案的贡献。同理有:
$$ \begin{aligned} l_1[i]&=a_i(l_1[i-1]+1) \newline l_2[i]&=a_i(l_2[i-1]+2l_1[i-1]+1) \end{aligned}$$ 于是可以做到 $O(n)$ 求出答案。
注意区分 $f[]$ 和 $l[]$ 的定义,前者是全局的期望价值,后者是末位极长全 1 串的期望价值,同时还需要区分一下 “长度的三次方的期望” 和 “长度的期望的三次方”。

又一道栗题

给定一颗 $n$ 个节点的有根树,$1$ 号节点为根,树上的每个节点 $u$ 都有一个权值 $c_u$。
你需要随机一个节点的排列 $P\in [n]$, 并且按这个排列的顺序依次访问所有树上的节点。每当访问到树上的一个节点 $u$ 时,你需要将子树 $u$ 内所有节点的权值加上 $c_u$(包括点 $u$)。
问在一切的操作结束之后所有节点权值之和的期望。由于期望可能不是一个整数,请将它乘上 $n!$,并对 $10^9+7$ 取模。
$n\le 10^5$, 且保证树的形态随机

根据期望的线性性,我们只需要求出每个节点最后的期望权值即可。设这个东西是 $a_u$ ,容易发现 $a_u$ 的取值只与从根到 $u$ 的这一条祖孙链上的节点有关。
因为树的形态随机,所以树高是期望 $O(\sqrt{n})$ 的。设祖孙链长为 $d$,那么只需考虑 $O(d)$ 地求出 $a_u$ 即可。
运用贡献法考虑:期望权值 = $Σ$权值$×$期望累加次数,那么考虑预处理一个 $t[]$,使得 $a_u=\sum c_v·t_v$ 即可。

容易发现 $t_v$ 的取值只与 $u,v$ 的相对距离有关,则可以设 $f_i$ 表示考虑随机访问一个有 $n$ 位的序列 $a_1,a_2,…,a_n$,$a_1$ 在 $i$ 上的期望累加次数。
考虑一次累加应当是什么样子: $1\to p_1\to p_2\to …\to i$,且满足 $1<p_1<p_2<…<i$。这显然双射了一个上升子序列(IS)。
则 $f_i$ 即代表考虑所有 $P\in [i]$,$P$ 中以 $1$ 起始的 IS 的期望数量。这样我们可以直接拿组合数选出来,即有:
$$ f_i=\sum\limits_d \dbinom{i-1}{d-1}\dbinom{i}{d}(i-d)! $$ 于是就可以计算了,时间复杂度 $O(n\sqrt{n})$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e5 + 6;
const int P = 1e9 + 7;

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}

int n, a[CN], fac[CN], ifac[CN], f[CN];
int C(int n, int m) {return 1ll * (1ll * fac[n] * ifac[m] % P) * ifac[n - m] % P;}

int stk[CN], ans = 0;
void dfs(int u, int p, int dep){
stk[dep] = a[u];
for(int i = dep, j = 1; i; i--, j++) ans = (1ll * stk[i] * f[j] % P + ans) % P;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(v ^ p) dfs(v, u, dep + 1);
}
}

int main()
{
n = read();
for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v), add(v, u);}
for(int i = 1; i <= n; i++) a[i] = read();

fac[0] = ifac[0] = 1;
for(int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[n] = qp(fac[n], P - 2);
for(int i = n - 1; i; i--) ifac[i] = 1ll * (i + 1) * ifac[i + 1] % P;

for(int i = 1; i <= 5000; i++){
for(int d = 1; d <= i; d++){
int prd = 1ll * C(i - 1, d - 1) * C(i, d) % P;
prd = 1ll * prd * fac[i - d] % P, f[i] = (f[i] + prd) % P;
}
f[i] = 1ll * f[i] * ifac[i] % P;
}

for(int i = 1; i <= n; i++) ans = (ans + a[i]) % P;
dfs(1, 0, 1), ans = 1ll * ans * fac[n] % P;

printf("%d", ans);
}

双一道栗题

有 $n$ 种方法,每种方法需要 $k_i$ 条途径,第 $j$ 条途径有 $p[i,j]$ 的概率无法使用。每次可以查询任意一条途径可否使用,直到查询到一种能使用的方法,求最小的“最少查询次数的期望”。
$n,k_i \le 500$

容易发现对于任意一种方法,如果不将其全部查询完,那么这次查询是无意义的。对于任意一种方法,我们应当按照 $p[i,j]$ 降序排序的顺序去查询。
假定 $\forall i$,$p[i,j]$ 已经降序排序为 $p_1,p_2,…p_{k_i}$,那么考虑对所有方法进行排列,设 $E_i$ 为考虑 $[1:i]$ 中的方法时的答案,则有:
$$\begin{aligned} E_i&=p_1(1+E_{i-1}) + p_2(1-p_1)(2+E_{i-1})+…\newline &=k_iE_{i-1}+b_i \end{aligned} $$ 注意到还有 $\prod\limits_j (1-p_j)$ 的概率本次查询不会停止,把这部分加到常数项即可。
于是变成了一次函数嵌套的最小值问题,按 $(k_i-1)/b_i$ 升序排序即可,时间复杂度 $O(\sum k_i + n\log n)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define DB double
const int CN = 550;
const DB EPS = 1e-9;

int n, m, id[CN]; DB k[CN], b[CN], p[CN];
bool cmp(DB x, DB y) {return x > y;}
bool comp(int i, int j) {return k[i] * b[j] + b[i] < k[j] * b[i] + b[j];}

int main()
{
n = read();
for(int i = 1; i <= n; i++){
m = read(); for(int j = 1; j <= m; j++) scanf("%lf", &p[j]);
sort(p + 1, p + m + 1, cmp); DB prd = 1.0;
if(p[1] > 1.0 - EPS) {i--, n--; continue;} while(m && p[m] <= EPS) m--;
for(int j = 1; j <= m; j++) k[i] += p[j] * prd, b[i] += p[j] * prd * j, prd *= (1.0 - p[j]);
b[i] += m * prd, id[i] = i;
}

sort(id + 1, id + n + 1, comp); DB ans = 0;
for(int i, p = n; p; p--) i = id[p], ans = k[i] * ans + b[i];

printf("%.9lf", ans);
}

叒一道栗题

有 $m$ 张牌,其中一张是王牌。现在你执行 $n$ 次如下操作:洗牌后查看第一张牌是什么。
令 $x$ 为洗牌后第一张牌为王牌的次数,现在假设洗牌时 $m!$ 种牌的排列出现的概率均相等,求 $x^k$ 的期望值,对 $998244353$ 取模。
$n,m\le 998244352, k\le 5000$

题目等价于:有 $n$ 个相互独立的随机变量 $x_1,x_2,…x_n$,每个变量有 $\frac{1}{m}$ 的概率为 $1$,其余情况为 $0$,求:
$$E[\left(\sum\limits_{i=1}^nx_i\right)^k]$$

根据期望的线性性,可以枚举 $d=\sum\limits_{i=1}^nx_i$,则有:
$$\begin{aligned} E[\left(\sum\limits_{i=1}^nx_i\right)^k] &=\sum\limits_{d=0}^n E(d^k)\newline &= \sum\limits_{d=0}^n P(d)·d^k\newline &= \sum\limits_{d=0}^n\dbinom{n}{d}\left(\frac{1}{m}\right)^d\left(1-\frac{1}{m} \right)^{n-d} ·d^k \end{aligned}$$ 把后面的 $d^k$ 拿 Stirling 数展开,大力化一下柿子,得到:
$$ \sum\limits_{d=0}^n\dbinom{n}{d}\left(\frac{1}{m}\right)^d\left(1-\frac{1}{m} \right)^{n-d} ·d^k=\sum\limits_{i=0}^k \begin{Bmatrix}k\newline i\end{Bmatrix} n^{\underline{i}}\left(\frac{1}{m} \right)^i $$ 就可以做了,时间复杂度 $O(k^2)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int P = 998244353;
const int CN = 5005;

int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}

int n, m, k, S[CN][CN], ans = 0;

int main()
{
n = read(), m = read(), k = read(), m = qp(m, P - 2);

S[0][0] = 1;
for(int i = 1; i <= k; i++)
for(int j = 1; j <= i; j++) S[i][j] = (1ll * j * S[i - 1][j] % P + S[i - 1][j - 1]) % P;

int fall = 1, pw = 1;
for(int i = 0; i <= k; i++){
int prd = 1ll * S[k][i] * fall % P;
ans = (1ll * prd * pw % P + ans) % P;
pw = 1ll * pw * m % P, fall = 1ll * fall * (n - i) % P;
}

printf("%d", ans);
}

相关题目

  1. 暂无来源
  2. 暂无来源
  3. 暂无来源
  4. 「SPOJ1026」FAVDICE - Favorite Dice
  5. 暂无来源
  6. 「BZOJ4318」OSU!
  7. 暂无来源
  8. 暂无来源
  9. 「CF1278F」Cards

习题
「LG-P6843」梦原
「LG-P5835」线形生物

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×