lalala

· · 题解

注：本文中，未指定鞅 \{(X_n,\mathscr{F}_n)\} 适应的流 \mathscr{F}_n，我们默认是包含其最小的 \sigma- 代数，即 \mathscr{F}_n=\sigma(X_1,X_2,X_3,\dots,X_n)。

声明：本人接触鞅的时间不久，理解不深刻，若本文有谬误，请不吝指出。

题意简述

随机一个数 1\sim n 接在歌唱序列后面，问歌唱序列出现给定序列作为子序列的期望随机次数。

Solution

前置知识

关于鞅、停时的基础知识和此定理的证明等可以参见本人博客和北京大学的讲义。

Doob 停时定理：

如果 \{M_n\} 是关于 \{\mathscr{F}_n=\sigma(X_1,X_2,\dots,X_n)\} 的鞅，T 为其停时 ，若：

E|M_T|<\infty P(T<\infty)=1 \lim_{n\to\infty}E(M_n\mid I_{[T>n]})=0

那么

E(M_T)=E(M_1)

Solution

这是 PGF 的经典题目，但是也可以应用 Doob 停时定理做。

设目标串是 T[1:L]。

考虑这样一个以 k 为参数的随机变量列 \{A_m^{(k)}\}_{m\ge 1},\forall k\ge 1，\Omega=\{s[1:+\infty]\mid s[i]\in[1,n]\cap\mathbb{Z}\}。

A_m^{(k)}= \left\{\begin{matrix} C&(k\le m\land t[1:L]=s[k:k+L-1]\land m-k+1>L)\\ n^{m-k+1}&(k\le m\land t[1:m-k+1]=s[k:m]\land m-k+1\le L)\\ 1&(m<k)\\ 0&(otherwise)\\ \end{matrix}\right. 容易证明这在**停时前**是鞅，即除去第一条，而停时后的部分是不关心的。 我们知道，鞅的线性组合是鞅。 所以 $$ M_n=\sum_{k\ge 1}A_n^{(k)}-1 $$ 是鞅。构造 $T$ 为其一停时，为 $$ T(s[])=\min_{s[i-L+1:i]=t[1:L]}i $$ 容易验证其是停时，且适用 Doob 停时定理，注意 $P(T(s[])<+\infty)=1$。 不难发现，其实际意义正好适配本题。 $$E(M_T)=E(M_0)=0$$ $$M_T=\sum_{k=1}^{T}A_T^{(k)}-1$$ $$=\sum_{t[1:i]=t[L-i+1:L]} n^{i}-T$$ $$E(M_T)=\sum_{t[1:i]=t[L-i+1:L]} n^{i}-E(T)=0$$ $$\therefore E(T)=\sum_{t[1:i]=t[L-i+1:L]} n^{i}$$ 第三个等号成立，因为每个 $A_T^{(k)}$ 产生贡献的条件是（已经略去 $1$ 的情况） $$ s[1:T-k+1]=s[k:T] $$ 注意到 $$ T(s[])=\min_{s[i-L+1:i]=t[1:L]}i $$ 所以每个 $A_T^{(k)}$ 产生贡献当且仅当其为 border（第一部分是不需要考虑的，因为停时是 $\min$） 最后的答案就是 $$E(T)=\sum_{t[1:i]=t[L-i+1:L]} n^{i}$$