Basics

Def 1: Stochastic process 随机过程

一个随机过程 X = { X ( t ) : t ∈ T } \bm{X}=\{X(t):t\in \bm{T}\} X={X(t):t∈T} 是一个随机过程的集合。 t t t 可以是连续的也可以是离散的。如果 T \bm{T} T 是 countably infinite, 我们可以把 X \bm{X} X 称为一个离散时间序列，这时候我们可以取 t = 0 , 1 , 2 , 3 , . . . t=0,1,2,3,... t=0,1,2,3,....

Reamrk: 随机过程就是一堆随机变量的集合，或者说在每个时间点上都是一个随机变量。这些随机变量可能是完全独立的，比如 AWGN noise；这些随机变量也有可能相互有关，这就需要转移概率来描述他们之间的关系。其中一类转移概率无记忆的随机过程就是MC。

Def 2: Markov Chain

一个离散的随机过程 X = { X 0 , X 1 , X 2 , . . . } \bm{X}=\{X_0,X_1,X_2,...\} X={X0​,X1​,X2​,...} 被称为Markov Chain 如果它在时间 t t t 时候的状态仅取决于 t − 1 t-1 t−1 时刻的状态，即状态转移概率
Pr ⁡ ( X t = a t ∣ X t − 1 = a t − 1 , . . . , X 0 = a 0 ) = Pr ⁡ ( X t = a t ∣ X t − 1 = a t − 1 ) \Pr(X_t=a_t|X_{t-1}=a_{t-1},...,X_0=a_0)=\Pr(X_t=a_t|X_{t-1}=a_{t-1}) Pr(Xt​=at​∣Xt−1​=at−1​,...,X0​=a0​)=Pr(Xt​=at​∣Xt−1​=at−1​)

换句话说，MC是无记忆的离散随机过程。

Def 3: Homogeneous MC

齐次 MC指的是转移概率跟初始时间无关，即
Pr ⁡ ( X t = j ∣ X t − 1 = i ) = P i j \Pr(X_t=j|X_{t-1}=i)=P_{ij} Pr(Xt​=j∣Xt−1​=i)=Pij​

并不是初始时间 t t t 的函数

Remark: 一般我们只研究齐次MC且state space 是finite的。这样的话，一个 MC 完全由初始状态和单步转移概率矩阵来决定。

Def 4: 图表示法

只要我们能把单步转移矩阵写出，图表示法就显而易见了。下面是一个例子。

Def 5: Irreducible MC

不管现在的状态在哪，经过有限步可以达到任意状态的性质叫不可约性。

也可以说，MC的所有状态都属于同一个communication class，那么MC不可约。

Remark: 如果从状态 i i i 开始经过 n n n 步之后可以到达状态 j j j, 那么我们记作 i → j i\to j i→j; 如果 i i i, j j j 相互可达，那我们称两个状态 communicate，记作 i ↔ j i\leftrightarrow j i↔j.

比如以下的例子是不可约的。

Def 6: Aperiodic MC

如果 MC 的所有状态的周期都是1，那么我们称这个 MC 是非周期的。一个状态 i i i 的周期定义为
d ( i ) = gcd { m ≥ 1 : P i , i m > 0 } d(i)=\text{gcd}\{m\geq 1: P^m_{i,i}>0\} d(i)=gcd{m≥1:Pi,im​>0}

即，从 i i i 开始走 m m m 步能回到 i i i 状态的所有 m m m 的最大公约数。

比如以下这些 MC，第一个每个状态的 period 都是 2；第二个第三个都是 aperiodic 的。

两个结论

Aperiodic MC:

即从任一状态开始，经过有限的 N N N 步之后的每一步 m ≥ N m\geq N m≥N 都有概率回到原状态。

Irreducible and aperiodic MC:

---

Stationary distributions

所有 finite Markov Chain 都有 stationary distributions

可以看出，所谓的stationary distribution就是MC的终极分布，到了这个分布之后各状态的概率分布便不再动了。

例：令转移矩阵 P i j = Pr ⁡ ( X t + 1 = j ∣ X t = i ) P_{ij}=\Pr(X_{t+1}=j|X_{t}=i) Pij​=Pr(Xt+1​=j∣Xt​=i), 那么这个矩阵的每一行必须加起来是 1 (因为都是从一个状态出去的概率)。此时要转移概率，得把概率分布写成行向量。一个简单的例子，
P = [ 1 2 1 2 1 10 9 10 ] P=\begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\[0.15cm] \frac{1}{10} & \frac{9}{10} \end{bmatrix} P=[21​101​​21​109​​]

那么稳态概率
[ v 1 , v 2 ] [ 1 2 1 2 1 10 9 10 ] = [ v 1 , v 2 ] [v_1,v_2]\begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\[0.15cm] \frac{1}{10} & \frac{9}{10} \end{bmatrix}=[v_1,v_2] [v1​,v2​][21​101​​21​109​​]=[v1​,v2​]

可以得出 v = [ 1 6 , 5 6 ] \bm{v}=[\frac{1}{6},\frac{5}{6}] v=[61​,65​] (行向量).

这里，另一种写法是把 P P P 写成 P P P 的转置，这样方便我们用列向量表示概率分布。那么
P = [ 1 2 1 10 1 2 9 10 ] P=\begin{bmatrix} \frac{1}{2} & \frac{1}{10} \\[0.15cm] \frac{1}{2} & \frac{9}{10} \end{bmatrix} P=[21​21​​101​109​​]

稳态概率
[ 1 2 1 10 1 2 9 10 ] [ v 1 v 2 ] = [ v 1 v 2 ] \begin{bmatrix} \frac{1}{2} & \frac{1}{10} \\[0.15cm] \frac{1}{2} & \frac{9}{10} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}= \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} [21​21​​101​109​​][v1​v2​​]=[v1​v2​​]

---

好，最后我们给出一个结论解释为啥我们一般只考虑 finite, aperiodic and irreducible MC

也就是说，我们从任一概率分布出发最后都能得到稳态分布 (这里采用行向量写法)
v 0 → v 1 → v 2 → . . . → v ∞ = v ∗ v_0\to v_1\to v_2\to ...\to v_\infty=v^* v0​→v1​→v2​→...→v∞​=v∗

v ∗ P = v ∗ v^*P=v^* v∗P=v∗

而另一层意思是
v 0 P ∞ = v ∗ ,   ∀   v 0 v_0 P^\infty=v^*,~\forall~v_0 v0​P∞=v∗, ∀ v0​

即从任一初始分布出发我们都是能得到 v ∗ v^* v∗ 的，其实这就是在告诉我们
lim ⁡ n → ∞ P n = [ v ∗ v ∗ . . . v ∗ ] \lim_{n\to\infty}P^n=\begin{bmatrix} v^* \\ v^* \\ ... \\ v^* \end{bmatrix} n→∞lim​Pn=⎣⎢⎢⎡​v∗v∗...v∗​⎦⎥⎥⎤​

也就是说一步转移矩阵 P P P 的无穷次方是收敛到一个每行都是稳态分布的 matrix.

---

Total Variation Distance

可以看到，这个distance是定义在两个distribution之间的，无非就是两个distribution 对应点差值的 1 norm。为啥要除2尼，因为要确保 d T V d_{TV} dTV​ 在 0, 1 之间。简单的例子 d T V ( ( 0 , 1 ) , ( 1 , 0 ) ) = 1 d_{TV}((0,1),(1,0))=1 dTV​((0,1),(1,0))=1 如果不乘以 1 / 2 1/2 1/2 就变成 2 2 2 了。

下面我们定义概率序列的收敛性

这个定义也很简单，无非就是这个概率分布序列与目标分布的距离慢慢趋近于0.

可以看到，随着MC的概率分布趋向于稳态分布，概率分布与稳态分布的距离慢慢趋近于0.