鞅与鞅的停时定理

鞅

鞅最早指一种赌博策略，后被引进到了数学中，用来指一类随机过程。它有许多种不同程度的推广，这里义离散时间鞅为满足以下条件的随机过程（依赖于时间的随机变量序列） \(X_0,X_1,X_2,…\) 。

  1. \(?n∈N,E\ [X_n]<∞\)。
  2. \(?n∈N+,E\ [X_{n+1}∣X_n,X_{n?1},…,X_0]=X_n\)。

第一条比较平凡，第二条用比较通俗的语言讲，就是在已知之前的所有观测值的前提下，下一次观测值的期望等于这一次观测值。

同时有更为一般的定义，若：

  1. \(?n∈N,E\ [Y_n]<∞\)。
  2. \(?n∈N+,E\ [Y_{n+1}∣X_n,X_{n?1},…,X_0]=Y_n\) 。

则称随机过程 \(Y0,Y1,…\) 是关于另一随机过程 \(X0,X1,…\) 的鞅。

容易证明，对于任意 \(n∈N+,E\ [X_n]=X_0\)，也就是认为 \(X_0,X_1,…\) 是赌徒的财产，则无论赌多少次，赌徒最后的期望财产依旧等于他最开始的财产。

下面举几个鞅的例子：

  1. 设 \(X_n\) 表示一个赌徒抛掷了 \(n\) 次公平硬币（正反面概率相等）后的财产。规则是若为正面朝上，则获得 \(1\) 元；反之输掉 \(1\) 元。在已知过去所有时刻的财产下，若赌徒再抛掷一次硬币，显然抛掷完后财产的期望依旧等于现在的财产数量。故 \(X_0,X_1,X_2,…\) 这一随机过程是鞅。

  2. 接着上面的例子，设 \(Y_n=X^2_n?n\)，则 \(Y_0,Y_1,…\) 这一随机过程是关于随机过程 \(X_0,X_1,…\) 的鞅，证明如下：

\[E\ [Y_n+1]=\frac{(X_n?1)^2?(n+1)+(X_n+1)^2(n+1)}{2}\\ =\frac{1}{2}(X^2_n?2X_n+1?n?1+X^2_n+2X_n+1?n?1)\\ =\frac{1}{2}(2X^2_n?2n)\\ =X^2_n?n\\ =Y_n \]

注意到：

\[E\ [Y_n]=E\ [X^2_n]?n=E\ [X^2_0] \]

取 \(X_0=0\) 则 \(E\ [X^2_n]=n\) ，如果 \(X_0≠0\) 只需要 \(Y_n\) 定义为 \((X_n?X_0)^2?n\) 即可。

这一例子可以表明赌徒的全部收益或损失大致在抛掷次数的正负平方根之间变化。

鞅的停时定理

对于一列随机变量 \(X_0,X_1,…\)，停时 \(τ\) 为一个随机变量，满足性质：对于任意时间 \(t\)，事件 \(τ=t\) 是否发生仅取决于 \(X_0,X_1,…\) 的取值。也就是说只根据现在获得的信息就可以知道是否已经停下，而不需要将来的信息。

随机时刻：

设随机变量 \(T\) , 如果 \(T∈N∪{+∞}\) , 且 \(T=n\) 的示性函数 \(I_{T=n}\) 为 \(X_0,X_1...,X_n\) 的函数，则称 \(T\) 为 \(X\) 的随机时刻.

停时 :

若 \(T\) 为 \(X\) 的随机时刻且 \(P(T<+∞)=1\) 则称 \(T\) 为 \(X\) 的停时。

停止过程:

若 \(T\) 为 \(X\) 的随机时刻。定义 \(X\) 的停止过程 \(\overline{X}\) 为

\[\overline{X}_n= \begin{cases} X_n\ (n≤T)\\ \\ X_T\ (n>T) \end{cases} \]

显然若 \(X\) 为鞅则 \(\overline{X}\) 为关于 \(X\) 的鞅。

停时定理：

若鞅 \(X\) 和停时 \(T\) 满足以下条件之一：

  1. \(\overline{X}\) 都有界。
  2. \(T\) 有界。
  3. \(E\ (T)<+∞\) , 且 \(E\ (|X_n+1?X_n||X_0,...,X_n)\) 有界。

那么 \(E\ (X_T)=E\ (X_0)\)

套路：

构造势函数 \(?(X)\) , 使得 \(E(?(X_{n+1})|X_0,...,X_n)=?(X_n)+1\)。

这样的话 \(?(X_n)?n\) 就是一个鞅。

利用停时定理有：

\[E(?(X_T)?T)=E(?(X_0))=E(?(X_T))?E(T) \]

即：

\[E(T)=E(?(X_T))?E(?(X_0)) \]

这样求出 \(E(?(X_0))\) 和 \(E(?(X_T))\) 就可以求出 \(E(T)\) 了。

例题

#88. 战争

我们设 \(?(X)=\sum f(a_{i})\) ，列方程：

\[E(?(X_{n+1}))=?(X_n)+1 \]

\[?(X_{n+1})-?(X_n)=-1 \]

假如发生冲突的是 \(i\) 国家和 \(j\) 国家：

\[p\times (f(a_i+1)+(a_j-1)\times f(1))+p\times (f(a_j+1)+(a_i-1)\times f(1))+(1-2p)\times (a_i+a_j)\times f(1)-f(a_i)-f(a_j)=1 \]

令 \(f(1)=0\) 式子会简洁很多

\[p\times f(a_i+1)+p\times f(a_j+1)-f(a_i)-f(a_j)=1 \]

我们只需让 \(?a\)，有 \(p\times f(a+1)-f(a)=\frac{1}{2}\) 即可。

对于 \(f(n)=k\times f(n-1)+b\) 形式的递归式，可以设 \(f(n)+c=k\times (f(n-1)+c)\) ，解出 \(c\) ，剩余的部分是一个等比数列。

本题中 \(c=\frac{1}{2(p-1)}\) ，进而 \(f(n)=(p^{1-n}+1)\times \frac{1}{2(p-1)}\) 。

因此我们可以方便的计算 \(E(X_T)\) 和 \(E(X_0)\) ，输出 \(E(X_T)-E(X_i)\) 即可。

点击查看代码 
#include
using namespace std;
const int p=1e9+7,inv2=(p+1)/2;
int a[40000005],pw0[65537],pw1[65537];
int pw(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=1ll*res*x%p;
        x=1ll*x*x%p;y>>=1;
    }
    return res;
}
int mod(int x){return x>=p?x-p:x;}
unsigned long long x,y,z,b1,b2;
void prework(){
    int m,q=0,now=1;unsigned long long l,r,tmp;
    scanf("%d%llu%llu%llu%llu%llu",&m,&x,&y,&z,&b1,&b2);
    while(m--){
        scanf("%d%llu%llu",&q,&l,&r);
        r=r-l+1;
        while(now<=q)a[now]=(b1%r+l)%(p-1),tmp=x*b2+y*b1+z,b1=b2,b2=tmp,now++;
    }
}
int pw2(int x){return 1ll*pw0[x&65535]*pw1[x>>16]%p;}
int main(){
    int type,n,s,t,r,x0=0;long long x;
    scanf("%d%d%d%d",&type,&n,&s,&t);
    t=1ll*s*pw(t,p-2)%p;r=pw(mod(2*t-2),p-2);
    if(!type)for(int i=1;i<=n;i++)scanf("%lld",&x),a[i]=x%(p-1);
    else prework();
    s=0;
    int ti=pw(t,p-2);
    pw0[0]=pw1[0]=1;
    for(int i=1;i<=65536;i++)pw0[i]=1ll*pw0[i-1]*ti%p;
    for(int i=1;i<=65535;i++)pw1[i]=1ll*pw1[i-1]*pw0[65536]%p;
    for(int i=1;i<=n;i++){
        s=(s+a[i])%(p-1);
        x0=mod(x0+pw2(a[i]+p-2)-1);
    }
    printf("%lld",1ll*(x0-pw(t,p-s)+1+p)*r%p);
    return 0;
}
组合计数

相关

组合计数（初步）

标签