鞅(martingale)

从一个例子开始

一个赌徒，第\(n\)轮可以下注\(b_n\)价值的赌注，他每局的输赢可以用随机变量序列\({Y_n}\)描述，\(Y_n=1\)表示赢，\(Y_n=-1\)表示输。证明：不存在一种策略使得他的期望收益大于初始赌资。

证明：

用\(X_n\)表示他每局的赌资，\(X_0\)为初始赌资。

我们有：\(X_n=X_0+\sum_{i=1}^n b_iY_i\)

那么断言\(E[X_{n+1}|Y_1,\cdots,Y_n]=X_n\)

事实上，由\(X_n=X_0+\sum_{i=1}^n b_iY_i\)两项相减得\(X_{n+1}=X_n+b_nY_n\)

则\(E[X_{n+1}|Y_1,\cdots,Y_n]=E[X_{n}|Y_1,\cdots,Y_n]+E[b_nY_n|Y_1,\cdots,Y_n]=X_n+b_nE[Y_n|Y_1,\cdots,Y_n] (X_n与b_n被Y_1, \cdots ,Y_n确定)=X_n(Y_n期望为0)\)

定义

例: Bertrand Voting

在一次选举中，甲、乙二位候选人分别获得了 \(a, b\) 张选票 \((a>b)\).

现在考虑：在整个唱票过程中，甲的票数一直领先于乙的票数的可能性.

折线法

第一张选乙的概率为 \(\frac{b}{a+b}\)

之后折线与斜线有交点的概率和第一张选乙的概率相等, 因为可以将斜线一侧的折线翻上去

所以一直领先的概率为 \(1-\frac{b}{a+b}-\frac{b}{a+b}=\frac{a-b}{a+b}\)

鞅的停时定理

令 \(n=a+b\), \(S_k\) 表示 \(k\) 轮唱票后甲领先乙的票数

\(S_n=a+b\)

定义 \(X_k=\frac{S_{n-k}}{n-k}\), 则 \(X_0,\cdots,X_{n-1}\) 构成一个鞅

证明略

定义 \(T\) 是满足 \(X_k=0\) 的最小的 \(k\)

如果 \(k\) 不存在则 \(T=n-1\)

则 \(T\) 是有界停时, 且 \(E[X_T]=E[X_0]=\frac{E[S_n]}{n}=\frac{a-b}{a+b}\)

考虑两种情况

情况一为甲始终领先, 那么 \(X_T=X_{n-1}=S_1=1\)

即甲必须获得第一张选票

情况二为乙可能超过甲, 那么 \(k\) 存在, 这样的 \(k\) 使得 \(S_{n-k}=0\), 即 \(X_k=0\)

所以 \(X_T=X_k=0\)

所以期望为 \(E[X_T]=\frac{a-b}{a+b}=1\cdot P(case_1)+0\cdot P(case_2)\)

所以 \(P(case_1)=\frac{a-b}{a+b}\)