概率与期望中又好玩又难的好东西

鞅与停时定理

这个东西本来与 OI 的联系并不是很多，但是有一个比较厉害的势能法就是基于这个基础上的，所以还是来学了学。

具体定义是什么由于俺的水平远不及，关于历史什么的俺就跳过了，所以就只简单讲几个最重要的：

离散时间鞅

鞅是一种离散时间的随机过程 \(\{X_0, X_1, ..., X_n\}\) 要求满足：

• \(E(|X_n|) < \infty\) ；

• \(E(X_{n + 1}) = E(X_n|X_0, ..., X_n)\) 。

---

用大白话说一遍，以赌博为例，随机过程就对应的赌博的每一局：

1. 赌完 \(n\) 局之后只有有限种可能的结果，每种结果中赌本的绝对值都是有限的，所以期望就有限。

2. 即便是前面赌了 \(n\) 局，第 \(n + 1\) 局后赌本的期望值和 \(n\) 局后是一样的。也就是说 \(n + 1\) 局的期望收益为零，就是所谓的“公平赌博”。

停时定理

设 \({\tau}\) 为随机过程 \(\{X_0, X_1, ..., X_n\}\) 的停时，当下面三个条件满足一个时，有结论 \(E(X_{\tau}) = X_0\) ：

• \({\tau}\) 几乎一定有界；

• \(|X_{{\tau} + 1} - X_{\tau}|\) 一致有界，且 \(E({\tau})\) 有限；

• \(X_i\) 一致有界，且 \({\tau}\) 几乎一定有限。

---

描述的通俗解释：

几乎一定：直接就理解成一定没有问题；

有界：取值范围在一个与其无关的范围内；

有限：不跟无限扯上关系就行；

一致有界：就是里面所有的东西都有界。

---

用大白话说一遍，还是以赌博为例（停时：赌本攒到 \(5\) 就结束）：

1. 上述方式表示的可能会进行任意局数，不叫做有界；

2. \(X_{\tau}\) ：该符号表示赌本范围，赌本只会从 \(0 - 5\) 不等，所以是有限的。 \({\tau}\) ：假设 \(f(m)\) 表示赌本从 \(m\) 出发，到游戏结束时赌本的期望，于是有： \(f(0) = 0,\ f(5) = 5\) ，然后易知赢和输的概率一样，所以有 \(f(m) = \frac{f(m + 1)}{2} + \frac{f(m - 1)}{2}\) ，可以算出 \(f(m) = m\) ，也正好对应了上文讲的每一局的期望收益为零，所以 \(E({\tau})\) 是有限的。

3. \(X_{\tau}\) ：该符号指随机过程代表的就是每一局下的注，必然是有限的。 \({\tau}\) ：局数一定有限。

大概就这么理解一个例子，其他的就好说了。

势能函数

终于和势能扯上关系了。。

还是一样，设 \({\tau}\) 为随机过程 \(\{X_0, X_1, ..., X_n\}\) 的停时。

考虑构造势能函数 \(\varphi\) ，要求能够做到 \(E(\varphi(X_{\tau + 1})) + 1 = E(\varphi(X_{\tau})|X_0, ..., X_n)\) 。

如果我们改变一下随机过程：令 \(Y_{\tau} = \varphi(X_{\tau}) + {\tau}\) ，能得到式子： \(E(Y_{n + 1}) = E(Y_n|Y_0, ..., Y_n)\) ，即为离散时间鞅。

然后根据停时定理，有结论： \(E(Y_{\tau}) = Y_0\) 。然后带换回一下就是 \(E(\varphi(X_{\tau}) + {\tau}) = \varphi(X_0)\) ，那么 \(E({\tau}) = \varphi(X_0) - \varphi(X_{\tau})\) 。

（注：其实那个要求的式子不一定只能 \(+1\) ，只要是常熟就行，改变一下 \(Y_{\tau}\) 的定义就行了）

---

如果能够有这样的一个势能函数，期望值的计算就变得非常清新，会有非常意想不到的效果！

所以上例题！（默认 \(\tau\) 为停时）

CF1025G Company Acquisitions

Description

给定 \(n\) 个点，有两种状态选中或者未选中，未选中的点必定跟在一个选中的点后面。

每次随机选择两个被选中的点，将其中一个变为未选中，跟在另一个点后面，然后把原来跟在后面的点改为选中。

问只剩一个选中的点的操作期望次数。

\(2\leq n \leq 500,\ a_i = -1\ or\ 1\leq a_i \leq n\)

Solution

乍一看的话，因为 \(n\) 个点的局势情况过多，并不好直接设势能函数，但实际上每次操作只影响两选中的点以及跟随的点。

所以不妨设一个函数 \(f(x)\) 表示一个被选中点跟随的点数量为 \(x\) 的势能，但仍以 \(\varphi(X_{\tau})\) 为整个局势下的势能和。

设操作的两个点跟随的点数为 \(x\) 和 \(y\) ，就能构造式子：

\[E(\varphi(X_{\tau + 1})) + 1 = E(\varphi(X_{\tau})|X_0, ..., X_n) \]

\[\frac{1}{2} \cdot \big(f(x + 1) + y \cdot f(0)\big) + \frac{1}{2} \cdot \big(f(y + 1) + x \cdot f(0)\big) + 1 = f(x) + f(y) \]

能很明显观察到能化成关于 \(x\) 和 \(y\) 的两个同构的式子，因为有任意性，所以推得：

\[2\cdot f(x) = 1 + f(x + 1) + x \cdot f(0) \]

我们可以令 \(f(0) = 0\) ，所以最终能得到式子： \(f(x) = 1 - 2 ^ x\) 。

根据题意，停时的势能和为 \(\varphi(X_{\tau}) = f(n - 1) = 1 - 2 ^ {n - 1}\) ，而最终的答案是 \(E({\tau}) = \varphi(X_0) - \varphi(X_{\tau})\)

/*
 
*/
#include
using namespace std;
typedef long long ll;
const int N = 520, mod = 1e9 + 7;
int n, a[N], it[N], ans;
inline int read() {
	char ch = getchar();
	int s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
int main() {
	n = read(); it[0] = 1;
	for (int i = 1, x; i <= n; ++i) {
		x = read(); if (x != -1) ++a[x];
		it[i] = (it[i - 1] << 1) % mod;
	}
	for (int i = 1; i <= n; ++i) (ans += 1 - it[a[i]] + mod) %= mod;
	(ans += it[n - 1] - 1) %= mod;
	printf("%d\n", ans);
	return 0;
}

CF1349D Slime and Biscuits

Description

有 \(n\) 个人，第 \(i\) 个人有 \(a_i\) 个饼干。

现在每次随机选择一个饼干，等概率分给除持有者以外的人，求一个人拥有所有饼干的期望步数。

\(2\leq n\leq 10 ^ 5,\ 1\leq \sum a_i \leq 3 \cdot 10 ^ 5\)

Solution

实际上和上一道题是有点类似的，同样地，我们设一个函数 \(f(x)\) 表示一个有 \(x\) 个饼干的人的势能，仍以 \(\varphi(X_{\tau})\) 为整个局势下的势能和。

因为一个操作能波及到整个局势，暂且现在设一个函数 \(a_{{\tau}, i}\) 表示在第 \({\tau}\) 局之后第 i 个人的饼干数，并且令饼干总数为 \(m\) 。

继续构造：

\[E(\varphi(X_{\tau + 1})) + 1 = E(\varphi(X_{\tau})|X_0, ..., X_n) \]

\[\sum_i \sum_{j \neq i} \frac{a_{n, i}}{m \cdot (n - 1)} \cdot \Big( f(a_{n, i} - 1) + f(a_{n, j} + 1) + \sum_{k \neq i,\ k \neq j} f(a_{n, k}) \Big) + 1 = \sum_k f(a_{n, k}) \]

将有关 \(j\) 和 \(k\) 的贡献全用 \(i\) 重新带换一下，有：

\[\sum_i \Big( \frac{a_{n, i}}{m} \cdot f(a_{n, i} - 1) + \frac{m - a_{n, i}}{m} \cdot f(a_{n, i} + 1) + \frac{(m - a_{n, i}) \cdot (n - 2)}{m \cdot (n - 1)} f(a_{n, i}) \Big) + 1 = \sum_i f(a_{n, i}) \]

因为对于任意 \(a_{n, i}\) 均成立，所以又有：

\[\frac{x}{m} \cdot f(x - 1) + \frac{m - x}{m} \cdot f(x + 1) + \frac{(m - x) \cdot (n - 2)}{m \cdot (n - 1)} f(x) + 1 = f(x) \]

\[f(x + 1) = \frac{m + (n - 2) \cdot x}{m - x} \cdot f(x) - \frac{(n - 1) \cdot x}{m - x} \cdot f(x - 1) - \frac{(n - 1) \cdot x}{m - x} \]

令 \(f(0) = 0\) 递推式子即可求出 \(f\) 。

根据题意，停时的势能和为 \(\varphi(X_{\tau}) = f(m)\) ，而最终的答案是 \(E({\tau}) = \varphi(X_0) - \varphi(X_{\tau})\)

/*
 
*/
#include
using namespace std;
typedef long long ll;
const int N = 3e5 + 10, mod = 998244353;
int n, a[N], s, inv[N], f[N], ans;
inline int read() {
	char ch = getchar();
	int s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
int main() {
	n = read(); inv[1] = 1;
	for (int i = 1; i <= n; ++i) a[i] = read(), s += a[i];
	for (int i = 2; i <= s; ++i) inv[i] = mul(mod - mod / i, inv[mod % i]);
	for (int i = 2; i <= s; ++i) {
		(f[i] += mul(mul(mul(s, n - 1), inv[s - i + 1]) - n + 2 + mod, f[i - 1])) %= mod;
		(f[i] += mod - mul(mul(mul(i - 1, n - 1), inv[s - i + 1]), f[i - 2] + 1)) %= mod;
	}
	for (int i = 1; i <= n; ++i) (ans += f[a[i]]) %= mod;
	printf("%d\n", (ans - f[s] + mod) % mod);
	return 0;
}

CF850F Rainbow Balls

Description

给定 \(n\) 个颜色，每种颜色有个 \(a_i\) 个球。

每次随机抽取两球，指定一个球的颜色变更为另一个球的颜色。求所有的球变成一个颜色的期望次数。

\(1\leq n\leq 2.5 \cdot 10 ^ 3,\ 1\leq \sum a_i \leq 2.5 \cdot 10 ^ 8\)

Solution

可以说和上一道题非常的相似了！基本上要设的东西都不用变！只需要把什么饼干换成小球之类的就行了。

继续构造：

\[E(\varphi(X_{\tau + 1})) + 1 = E(\varphi(X_{\tau})|X_0, ..., X_n) \]

\[\sum_i \frac{a_{n, i} \cdot (a_{n, i} - 1)}{m \cdot (m - 1)} \sum_k f(a_{n, k}) + \sum_i \sum_{j \neq i} \frac{a_{n, i} \cdot a_{n, j}}{m \cdot (m - 1)} \cdot \Big( f(a_{n, i} - 1) + f(a_{n, j} + 1) + \sum_{k \neq i,\ k \neq j} f(a_{n, k}) \Big) + 1 = \sum_k f(a_{n, k}) \]

按照老套路，将有关 \(j\) 和 \(k\) 的贡献全用 \(i\) 重新带换一下，有：

\[\sum_i \frac{a_{n, i} \cdot (m - a_{n, i})}{m \cdot (m - 1)} \cdot f(a_{n, i} - 1) + \frac{a_{n, i} \cdot (m - a_{n, i})}{m \cdot (m - 1)} \cdot f(a_{n, i} + 1) + \big( 1 - \frac{2a_{n, i} \cdot (m - a_{n, i})}{m \cdot (m - 1)} \big) \cdot f(a_{n, i}) + 1 = \sum_i f(a_{n, i}) \]

省了一两步，不过问题不大，就是把 \(a_{n, i}\) 换成了 \(x\) ，然后处理了下系数，唯一要注意就是常数项要对应成 \(\frac{x}{m}\) 。

\[f(x + 1) = 2 \cdot f(x) - f(x - 1) - \frac{m - 1}{m - x} \]

规定好 \(f(0)\) 后，你甚至可以直接递推。。但是如果这样直接结束的话：

• 根据题意，停时的势能和为 \(\varphi(X_{\tau}) = f(m) - (n - 1) \cdot f(0)\) ，而最终的答案是 \(E({\tau}) = \varphi(X_0) - \varphi(X_{\tau})\)

看到什么没有，如果要求得 \(f(m)\) 的话，时间上是不能接受的，所以要考虑怎么规定 \(f(0)\) 才能避免。

继续观察，发现这三项的系数有点微妙的关系，想到差分代换，设 \(g(x) = f(x) - f(x - 1)\) ：

\[g(x + 1) = g(x) - \frac{m - 1}{m - x} \]

暂且规定 \(f(0)\) 和 \(g(0)\) 均为常数（具体是多少看最后式子情况）

\[g(x + 1) = g(0) - \sum_{i = 0} ^ {x - 1} \frac{m - 1}{m - i} \]

转化到 \(f\) 上，有：

\[f(x) = f(0) + \sum_{i = 1} ^ {x} g(i) \]

\[f(x) = f(0) + x \cdot g(0) - \sum_{i = 0} ^ {x - 1} \frac{(x - i) \cdot (m - 1)}{m - i} \]

\[f(x) = f(0) + x \cdot g(0) + x \cdot (m - 1) + \sum_{i = 0} ^ {x - 1} \frac{\big((m - i) - (x - i)\big) \cdot (m - 1)}{m - i} \]

\[f(x) = f(0) + x \cdot g(0) + x \cdot (m - 1) + (m - x) \cdot (m - 1) \cdot \sum_{i = 0} ^ {x - 1} \frac{1}{m - i} \]

这不直接 \(f(0) = 0,\ g(0) = m - 1\) ，化得：

\[f(x) = (m - x) \cdot (m - 1) \cdot \sum_{i = 0} ^ {x - 1} \frac{1}{m - i} \]

然后就能得到 \(f(m) = 0\) 的好结果，这时候在收尾的话：

根据题意，停时的势能和为 \(\varphi(X_{\tau}) = f(m) - (n - 1) \cdot f(0) = 0\) ，而最终的答案是 \(E({\tau}) = \varphi(X_0) - \varphi(X_{\tau})\)

完美！

/*
 
*/
#include
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, a[N], m, s, f[N], ans;
inline int read() {
	char ch = getchar();
	int s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline int ksm(int a, int b) {
	int tmp = 1;
	while (b) {
		if (b & 1) tmp = mul(tmp, a);
		a = mul(a, a); b >>= 1;
	}
	return tmp;
}
int main() {
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read(), (s += a[i]) %= mod, m = max(m, a[i]);
	for (int i = 1; i <= m; ++i) f[i] = (f[i - 1] + ksm(s - i + 1, mod - 2)) % mod;
	for (int i = 1; i <= m; ++i) f[i] = mul(f[i], mul(s - 1, s - i));
	for (int i = 1; i <= n; ++i) (ans += f[a[i]]) %= mod;
	printf("%d\n", ans);
	return 0;
}

CF1479E School Clubs

Description

有 \(n\) 个学生和 \(m\) 个组，第 \(i\) 组的人数为 \(a_i\) 。

每次随机一位学生，他要么有一半的概率自己单独成立一个组，要么有一半的概率进入一个已知的组，概率为 \(\frac{a_i}{n}\) 。

求所有学生出现在同一组的期望次数。

\(1\leq m \leq 10 ^ 3,\ 1\leq n\leq 4 \cdot 10 ^ 8,\ 1\leq a_i\leq 4 \cdot 10 ^ 8\)

Solution

乍一看是比较迷糊的，因为还存在新建一个组出来的情况，但后来发现不影响，可以继续参照第一题的玩法。

设一个函数 \(f(x)\) 表示一个被选中点跟随的点数量为 \(x\) 的势能，仍以 \(\varphi(X_{\tau})\) 为整个局势下的势能和。

那么仍然是构造式子：

\[E(\varphi(X_{\tau + 1})) + 1 = E(\varphi(X_{\tau})|X_0, ..., X_n) \]

直接写除势能的表达式：

\[\sum_i \frac{a_i}{n} \cdot \frac{1}{2} \cdot \Big(\big(\varphi(X_{\tau}) + f(a_i - 1) + f(1) - f(a_i) - f(0)\big) + \frac{a_i}{n} \cdot \varphi(X_{\tau}) + \sum_{j \neq i} \frac{a_j}{n} \cdot \big(\varphi(X_{\tau}) + f(a_i - 1) + f(a_j + 1) - f(a_i) - f(a_j)\big)\Big) + 1 = \varphi(X_{\tau}) \]

\[\sum_i \frac{a_i}{n} \cdot \Big(\frac{2n - a_i}{n} \cdot \big(f(a_i - 1) - f(a_i)\big)\Big) + f(1) - f(0) + \sum_i \frac{a_i}{n} \sum_{j \neq i} \frac{a_j}{n} \cdot \big(f(a_j + 1) - f(a_j)\big) + 2 = 0 \]

将 \(j\) 直接化掉，转化成 \(i\) 的写法，整理得：

\[f(1) - f(0) + 2 + \sum_i \Big(\frac{n \cdot a_i - a_i ^ 2}{n ^ 2} \cdot f(a_i + 1) + \frac{2n \cdot a_i - a_i ^ 2}{n ^ 2} \cdot f(a_i - 1) - \frac{3n \cdot a_i - 2a_i ^ 2}{n ^ 2} \cdot f(a_i)\Big) = 0 \]

根据定义 \(f(0) = 0\) ，所以为了方便，我们令 \(f(1) = -2\) ，因为 \(a_i\) 就有任意性，就把 \(a_i\) 用 \(x\) 替换。

\[(3n - 2x) \cdot f(x) = (n - x) \cdot f(x + 1) + (2n - x) \cdot f(x - 1) \]

根据题意，停时的势能和为 \(\varphi(X_{\tau}) = f(n)\) ，而最终的答案是 \(E({\tau}) = \varphi(X_0) - \varphi(X_{\tau})\)

然后这个就可以直接线性算，由于 CF 机子过快所以甚至可以过！

其实这个系数能够发现可以转换成差分的形式，也就是设 \(g(x) = f(x) - f(x - 1)\) :

\[g(x + 1) = \frac{2n - x}{n - x} \cdot g(x) \]

\[g(x + 1) = -\prod_{i = 0} ^ {x}\frac{2n - i}{n - i} \]

然后我们利用 \(g\) 的定义暴力算 \(f\) ：

\[f(x + 1) = -\sum_{i = 0} ^ {x} \prod_{j = 0} ^ {i} \frac{2n - j}{n - j} \]

\[f(x) = -\sum_{i = 0} ^ {x} \frac{\Big(\prod_{j = 0} ^ {i}{(2n - j)} \cdot \prod_{j = i + 1}^{x}{(n - j)}\Big)}{\prod_{j = 0} ^ {x} {(n - j)}} \]

这样的话别看式子变麻烦了，实际上想一想运算次数是能减少很多，会跑得更快一些。

/*
*/
#include
using namespace std;
typedef long long ll;
const int N = 1e3 + 10, mod = 998244353;
int n, s, a[N], id = 1;
ll now, f1 = 1, fm = 1, ans;
inline int read() {
	char ch = getchar();
	int s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline int ksm(int a, int b) {
	int tmp = 1;
	while (b) { if (b & 1) tmp = 1ll * tmp * a % mod; a = 1ll * a * a % mod; b >>= 1; } return tmp;
}
int main() {
	n = read();
	for (int i = 1; i <= n; ++i) s += (a[i] = read());
	if (n == 1) return printf("0\n"), 0;
	sort(a + 1, a + 1 + n);
	for (int i = 0; i < s; ++i) {
		ans = ans * (s - i) % mod; fm = fm * (s - i) % mod;
		f1 = f1 * (2 * s - i) % mod; now = (now * (s - i) + f1) % mod;
		while (id <= n && a[id] == i + 1) ++id, ans = (ans + now) % mod;
	}
	printf("%lld\n", (now - ans + mod) * ksm(fm, mod - 2) % mod);
	return 0;
}

Infinity

\[g(x + 1) = -\prod_{i = 0} ^ {x}\frac{2n - i}{n - i} \]

能够发现这乘的东西是连续的，所以可以考虑用拉格朗日插值加速，不过太难了，我不太会，之后有时间再补上吧。

这一部分的内容可以详见 zght 的博客中的算法三。