Martingales
Martingales (鞅方法)
初始赌博1元，每次输，就在上一次基础上翻倍，那么第一次获胜的时候会赚1元
$2^n - \sum_{i=0}^{n-1}2^i = 1$
那么对于任何一个公平的博弈，$X_i$表示第i轮结束时拥有的财富，在游戏是公平的情况下：
$E(X_{i+1} | X_1,X_2,…,X_i) = X_i$
简单理解下上述的式子就是第i+1轮输赢的概率是相同的，所以相对上一轮来说期望的结果是和上一轮是相同的。
Azuma’s Inequality
定理描述：
Let $X_0,X_1,…$ be Martingales such that for all $k \ge 1$ ($X_i$不相互独立)
$|X_k - X_{k-1}| \le c_k$ $c_k$表示第k次的相对期望变化的上限，那么对random walk问题 all $c_k = 1$
Proving Azuma’s Inequality
Let $X_0,X_1,…$ be Martingales such that for all $k \ge 1$,
$$
|X_k - X_{k-1}| \le c_k
$$
Then,
$$
P(X_n - X_0 \ge t) \le exp(- \frac{t^2}{2\sum_{k=1}^nc_k^2}) \\
P(X_n - X_0 \le -t) \le exp(- \frac{t^2}{2\sum_{k=1}^nc_k^2})
$$
证明第一个式子
assume $X_0 = 0$. 令 $X_i^{‘} = X_i-X_0$
Define $Y_i = X_i - X_{i-1}$，it is easy to see $E(Y_i|X_{i-1}) = 0$。
简单证明: $E(Y_i|X_{i-1}) = E(X_i-X_{i-1}|X_{i-1}) = E(X_i|X_{i-1}) - E(X_{i-1}|X_{i-1}) = 0 - 0 = 0$。
Martingales Example: Random walk
问题描述
从一个二维空间点每次上下左右随机走一步，$X_i$表示走完i步之后距离原点的曼哈顿距离，这个满足Martingales的
Doob Sequence
定义
The Doob sequence of a function f with respect to a sequence of random variables $X_1,X_2,…,X_n$ is
$$
Y_i = E(f(X_1,X_2,…,X_n) | X_1,…,X_i)
$$
In particular,$Y_0 = E(f(X_1,…,X_n))$ and $Y_n=f(X_1,…,X_n)$
会随着i的增加，能知道的信息因素越多，从而对结果有着更准确的判断。
