赞
踩
论文:(看不懂的)彭博《鞅与一类关于停时的概率与期望问题》
鞅是一类特殊的随机过程,起源于对公平赌博游戏的数学描述。假设我们从一开始就在观察一场赌博游戏,现在已经得到了前 t t t 秒的观测值,那么当第 t + 1 t+1 t+1 秒观测值的期望等于第 t t t 秒的观测值时,我们才称这是公平赌博游戏。
随机过程:在随机的背景下,时刻 i i i 会有状态 X i X_i Xi ,把它们依次记录下来就获得了随机过程。
鞅:对于一个随机过程 { X 0 , X 1 , . . . } \{X_0,X_1,...\} {X0,X1,...} ,如果 E ( X n + 1 ∣ X 0 , X 1 , . . . , X n ) = X n E(X_{n+1}|X_0,X_1,...,X_n)=X_n E(Xn+1∣X0,X1,...,Xn)=Xn ,我们就称这个随机过程为鞅。
注: E ( X n + 1 ∣ X 0 , X 1 , . . . , X n ) E(X_{n+1}|X_0,X_1,...,X_n) E(Xn+1∣X0,X1,...,Xn) 是条件期望,且得保证期望状态的定义是存在且合理的。
停时定理:对于任意停时 t t t (在这个时间结束观测,在不知晓中间的随机过程时讨论停时状态的期望),有 E ( X t ) = X 0 E(X_t)=X_0 E(Xt)=X0 。
考虑一个随机过程 { A 0 , A 1 , . . . } \{A_0,A_1,...\} {A0,A1,...},当确定终止状态为 A t A_t At 的时候,怎么求出停时 t t t 的期望 E ( t ) E(t) E(t) ,我们可以构造一个函数 Φ ( A ) \Phi(A) Φ(A) ,满足:
通过构造 B i = Φ ( A i ) + i B_i=\Phi(A_i)+i Bi=Φ(Ai)+i ,可知 E ( B n + 1 ∣ B 0 , B 1 , . . . , B n ) = B n E(B_{n+1}|B_0,B_1,...,B_n)=B_n E(Bn+1∣B0,B1,...,Bn)=Bn ,所以 { B i } \{B_i\} {Bi} 也是一个鞅,根据停时定理,有 E ( B t ) = B 0 ⇒ E ( Φ ( A t ) + t ) = Φ ( A 0 ) ⇒ Φ ( A t ) + E ( t ) = Φ ( A 0 ) E(B_t)=B_0~\Rightarrow~E(\Phi(A_t)+t)=\Phi(A_0)~\Rightarrow~\Phi(A_t)+E(t)=\Phi(A_0) E(Bt)=B0 ⇒ E(Φ(At)+t)=Φ(A0) ⇒ Φ(At)+E(t)=Φ(A0)
所以得到停时期望的计算方法 E ( t ) = Φ ( A 0 ) − Φ ( A t ) E(t)=\Phi(A_0)-\Phi(A_t) E(t)=Φ(A0)−Φ(At) 。
(凑齐六字标题
我们定义状态为 n n n 维向量,那么就可以合法地定义状态的期望,并惊喜地发现该随机过程是个鞅!
现在我们得定义一个势能函数 Φ ( A ⃗ ) \Phi(\vec{A}) Φ(A ) ,满足每次期望减少 1 。
不妨试试
Φ
(
A
⃗
)
=
∑
f
(
a
i
)
\Phi(\vec{A})=\sum f(a_i)
Φ(A
)=∑f(ai) ,令
m
=
∑
a
i
m=\sum a_i
m=∑ai(
m
m
m 是不变的),考察每一个
a
i
a_i
ai 和
f
(
a
i
)
f(a_i)
f(ai) 的变化,根据定义可得
∑
i
=
1
n
a
i
(
m
−
a
i
)
m
(
m
−
1
)
(
f
(
a
i
+
1
)
−
f
(
a
i
)
+
f
(
a
i
−
1
)
−
f
(
a
i
)
)
=
−
1
\sum_{i=1}^{n} \frac{a_i(m-a_i)}{m(m-1)}\left( f(a_i+1)-f(a_i)+f(a_i-1)-f(a_i) \right)=-1
i=1∑nm(m−1)ai(m−ai)(f(ai+1)−f(ai)+f(ai−1)−f(ai))=−1
尝试构造一下?如果能变成
∑
i
=
1
n
a
i
(
1
−
m
)
m
(
m
−
1
)
\sum_{i=1}^{n}\frac{a_i(1-m)}{m(m-1)}
∑i=1nm(m−1)ai(1−m) 该多好啊,令
(
f
(
a
i
+
1
)
−
f
(
a
i
)
)
−
(
f
(
a
i
)
−
f
(
a
i
−
1
)
)
=
1
−
m
m
−
a
i
\big(f(a_i+1)-f(a_i)\big)-\big(f(a_i)-f(a_i-1)\big)=\frac{1-m}{m-a_i}
(f(ai+1)−f(ai))−(f(ai)−f(ai−1))=m−ai1−m
看式子左边会发现非常的美观,令
h
(
x
)
h(x)
h(x) 为
f
(
x
)
f(x)
f(x) 差分两次后的函数(
∑
i
=
1
n
h
(
i
)
=
f
(
n
+
1
)
−
f
(
n
)
\sum_{i=1}^{n}h(i)=f(n+1)-f(n)
∑i=1nh(i)=f(n+1)−f(n)),那么
h
(
x
)
=
1
−
m
m
−
x
h(x)=\frac{1-m}{m-x}
h(x)=m−x1−m
我们可以直接前缀和求出所有的
f
(
a
i
)
f(a_i)
f(ai) ,时间复杂度
O
(
a
log
P
)
O(a\log P)
O(alogP) ,但是我们还需要求出
f
(
m
)
f(m)
f(m) ,直接递推的最高效求法时间和空间都是
O
(
m
)
O(m)
O(m) 的,但是我们注意到这个下标它刚好等于
m
m
m ,可以有美妙的性质:
f
(
m
)
=
∑
i
=
0
m
−
1
∑
j
=
0
i
1
−
m
m
−
j
=
∑
j
=
0
m
−
1
1
−
m
m
−
j
⋅
(
m
−
j
)
=
m
(
1
−
m
)
f(m)=\sum_{i=0}^{m-1}\sum_{j=0}^{i}\frac{1-m}{m-j}=\sum_{j=0}^{m-1}\frac{1-m}{m-j}\cdot (m-j) =m(1-m)
f(m)=i=0∑m−1j=0∑im−j1−m=j=0∑m−1m−j1−m⋅(m−j)=m(1−m)
震惊!竟只用一次乘法就能得出答案!
总时间复杂度 O ( a log P ) O(a\log P) O(alogP) 。
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<random> #include<bitset> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #pragma GCC optimize(2) using namespace std; #define MAXN 100005 #define LL long long #define ULL unsigned long long #define ENDL putchar('\n') #define DB double #define lowbit(x) (-(x) & (x)) #define FI first #define SE second #define PR pair<int,int> #define UIN unsigned int int xchar() { static const int maxn = 1000000; static char b[maxn]; static int pos = 0,len = 0; if(pos == len) pos = 0,len = fread(b,1,maxn,stdin); if(pos == len) return -1; return b[pos ++]; } // #define getchar() xchar() inline LL read() { LL f = 1,x = 0;int s = getchar(); while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();} while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();} return f*x; } void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);} inline void putnum(LL x) { if(!x) {putchar('0');return ;} if(x<0) putchar('-'),x = -x; return putpos(x); } inline void AIput(LL x,int c) {putnum(x);putchar(c);} const int MOD = 1000000007; int n,m,s,o,k; inline int qkpow(int a,int b) { int res = 1; while(b > 0) { if(b & 1) res = res *1ll* a % MOD; a = a *1ll* a % MOD; b >>= 1; } return res; } int a[MAXN]; int f[MAXN]; int main() { freopen("ball.in","r",stdin); freopen("ball.out","w",stdout); n = read(); m = 0; for(int i = 1;i <= n;i ++) a[i] = read(),m += a[i]; for(int i = 1;i <= MAXN-5;i ++) { f[i] = (MOD+1-m) *1ll* qkpow(m-i+1,MOD-2) % MOD; } for(int i = 1;i <= MAXN-5;i ++) (f[i] += f[i-1]) %= MOD; for(int i = 1;i <= MAXN-5;i ++) (f[i] += f[i-1]) %= MOD; int ans = m*1ll*(m-1) % MOD; for(int i = 1;i <= n;i ++) { (ans += f[a[i]]) %= MOD; } AIput(ans,'\n'); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。