Markov Chain

1) 单步过度概率矩阵$P=(p_{ij})$，其中$p_{ij}$是状态$i$到状态$j$的概率。也就是条件概率 $$P(X_n=j|X_{n-1}=i)$$ 2)state的选择，初始不是Markov过程的过程可以转变成Markov，比如明天下雨的概率依赖于今天和昨天的情况。这时候可以定义状态为连续两天天气状态的所有可能。

3) 直线上的random walk，状态空间为直线上的整数点，假设$X_n=i$，$X_{n+1}$只能是$i-1,i+1$，也就是 $$ \begin{array}{l} &P(X_{n+1}=i+1|X_n=i)=p\\ &P(X_{n+1}=i-1|X_n=i)=1-p \end{array} $$ 4) 如果一个Markov Chain进入某个状态后不会变成其他状态，这些状态称为absorbing states，用转换概率表达式 $$ \begin{array}{r} &P(X_{n+1}=as | X_n=as)=1\\ &P(X_{n+1}=\text{other states} | X_n=as)=0 \end{array} $$ 5) n-step transition概率定义为$P^n_{ij}=P(X_{n+k}=j | X_k=i)$，Chapman-Kolmogorov方程 $$P_{ij}^{n+m}=\sum_{k=0}^\infty P^n_{ik}P^m_{kj}$$ 是简单的不同path的概率的和式。式中的概率都是条件概率。并且上面的式子正好是矩阵相乘。根据归纳法可知$P^n_{ij}$是一阶转移矩阵n次方$(P_{ij})^n$的元素。

5) n-step transition中n可以为0，这时候transition矩阵是单位矩阵。两个状态称为accessible，如果存在n满足$P^n_{ij} > 0$。互相accessible的状态是称为communicate，记为$i\leftrightarrow j$。communicate是等价关系。如果一个Markov Chain的所有状态互相communicate，那么这个chain称为irreducible。

6) 考虑时间趋于无穷的时候情况，状态有这样的分类。$f_i$记为当时间趋于无穷的时候状态$i$至少会被到达一次的概率。如果$f_i=1$状态称为recurrent，如果$f_i < 1$称为transient。

7) 如果一个Markov Chain在某个时间进入了某个状态$i$，Chain等价于从$i$起始，并且如果$i$是recurrent，那么Chain将会infinitely often进入$i$。所以recurrent和transient可用chian进入这个状态次数的期望来刻画。

8) 假设chain的起始状态是i，$I_n$为indicator，第$n$步的时候如果chain在状态i则$I_n=1$否则$I_n=0$，chian进入状态i次数的期望为 $$E(\sum_{n=0}^\infty I_n | X_0=i)=\sum_{n=1}^\infty P^n_{ii} $$ 同样的道理，transient的数学意义，当时间趋于无穷的时候状态只会被访问有限次。显然transient和recurrent是互斥的。

9) communicate把chain的状态分成等价类，每个等价类状态要么全是recurrent要么全是transient。因为recurrent意味着一旦有可能进入这个状态，那么将会无限次的进入这个状态，加上communicate，和他在同一个等价类的状态都是这样的。

10) 再考虑上面的random walk，所有的状态都是communicate的，所以要么全是recurrent，要么全是transient，可以证明，一维的时候如果$p=\frac{1}{2}$那么所有的状态都是recurrent的，否则都是transient的。二维的时候有类似的结论，但是当维度大于2的时候所有的random walk状态不论$p$是多少都是transient的。

11) n-step transition概率矩阵记为$P^{(n)}$当$n$趋于无穷的时候得到的极限情况。对于ergodic Markov Chain 极限$\lim_{n\to \infty}P^n_{ij}$存在，并且极限值不依赖于$i$，也就是说无论起始状态是什么，n趋于无穷的时候最后达到的状态$j$的概率是固定的，所以可以记为$\pi_j$，(可以构造一个代数方程，$\pi_j$可以用解代数方程的方法求出，不用求极限)。