2010年12月14日星期二

序贯蒙特卡洛(三)

命题:M2和M3都是无偏估计,E(w[1]...w[n])=Zn,其中w[k]是第k步产生的调整系数,Zn是满足约束的路径数
证明:Zn=sum{1(x) , x是所有哈密尔顿路径}其中1(x)=1当且仅当x满足约束。
1(x)=w(x)p(x)
p(x)为按算法规则产生这个路径x的概率,链式分解:p(x)=p(x[0],x[1],...,x[n])=p(x[0])p(x[1]|x[0])...p(x[n]|x[n-1])
w(x)=0当x不满足约束,否则w(x)=w[1]...w[n],w[k]=1/p(x[k]|x[k-1])
从而得到右端就是期望E(w[1]...w[n])
点评:神奇之处在于概率的链式分解给出了权重的连乘表达,同时给出了迭代构造试探路径的方法。好的构造,即方差小的构造,会以较大概率得到满足约束的路径(接受的样本),这也是Important sampling的初衷。

没有评论: