【更新过程】

Poisson 过程的到达时间间隔是相互独立同服从指数分布的随机变量序列，那么一种自然的推广是考虑到达时间间隔相互独立同分布，但分布函数任意的计数随机过程，这样的计数过程即更新过程

设 $\{T_n,n=1,2,\cdots\}$ 是一列相互独立同分布的非负随机变量，令

【引入】

泊松（Poisson）过程是一类直观意义很强且极为重要的计数过程，其应用范围遍布各个领域

考虑一个来到某服务点要求服务的顾客流，顾客到达服务点的到达过程，即可认为是一个 Poisson 过程，当抽象的服务点和顾客流有着不同含义时，即可得到不同的 Poisson 过程

【概述】

1905 年，统计学家卡尔·皮尔逊公开求解随机游走问题（Random Walk Problem）：如果一个醉汉走路时每步的方向和大小完全随机，经过一段时间之后，在什么地方找到他的可能性最大？

1921年，匈牙利数学家 Polya 在研究随机游走问题后，证明了一维或二维随机游走具有常返性的随机游走定理，并得出了随机游走的醉汉最终会返回原点的结论。日本数学家角谷静夫将 Polya 随机游走定理表述为：喝醉的酒鬼总能找到回家的路，因此，随机游走定理也被称为酒鬼回家定理

【等价类】

对于马尔可夫链 $\{X_n,n\geq0\}$，根据互通这一等价关系，可以将状态空间 $S$ 划分为有限个或可列无限个互不相交的子集 $S_1,S_2,\cdots$ 的并，即

显然，同一子集 $S_n$ 中的所有状态都互通，不同子集 $S_m$ 和 $S_n$ 中的状态不互通

【Doeblin 公式】

设马尔可夫链 $\{X_n,n\geq0\}$，对任意 $i,j\in S$，有

进一步，可推得

【可逆马尔可夫链】

设马尔可夫链 $\{X_n,n\geq0\}$ 的转移概率矩阵为 $P$，若有状态分布 $\pi=(\pi_1,\pi_1,\cdots)^T$，对任意状态 $i,j\in S$，对任意一个时刻 $t$ 满足：

则称该马尔可夫链为可逆马尔可夫链（Reversible Markov Chain）

【状态的基本属性】

首达概率与迟早概率

设马尔可夫链 $\{X_n,n\geq0\}$，当 $i,j\in S$，称：

【齐次马尔可夫链】

设 $\{X(n),n\geq 0\}$ 为马尔可夫链，若其一步转移概率 $p_{ij}(n)$ 恒与起始时刻 $n$ 无关，则称 $\{X(n),n\geq 0\}$ 为时间齐次的马尔可夫链（Time Homogeneous Markov Chain），简称齐次马尔可夫链

对于齐次马尔可夫链 $\{X(n),n\geq 0\}$，其一步转移概率简记为 $p_{ij}$，其 $k$ 步转移概率 $p_{ij}^{(k)}(n)$ 也恒与起始时刻 $n$ 无关，可记为 $p_{ij}^{(k)}$，因此在进行具体讨论时，总可假设时间起点为零，即

【转移概率与转移概率矩阵】

转移概率

设 $\{X(n),n\geq 0\}$ 为离散时间马尔可夫链 DTMC，当 $X(t)$ 的状态空间 $S$ 为离散状态空间时

【马尔可夫性】

设 $\{X(t),t\in T\}$ 是一随机过程，当 $\{X(t),t\in T\}$ 在 $t_0$ 时刻所处的状态已知时，若其在 $t>t_0$ 时刻所处状态的条件分布与其在 $t_0$ 之前所处的状态无关，则称 $\{X(t),t\in T\}$ 具有马尔可夫性

简单来说，马尔可夫性是指：在已知过程现在条件下，其将来的条件分布只依赖于现在，不依赖于过去