本节先研究有限或可数状态空间上的齐次马尔可夫链，再研究以独立周期为单位的更新过程。首步分析给出方程；停时处的强马尔可夫性说明何时可以重新开始。计算中必须分别检查“到达的概率为一”和“平均等待时间有限”，这两个结论并不等价。
12.3.1 首步分解与最小非负解
设链的转移矩阵为 \(P=(p_{ij})\)，自然滤过为 \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\)。对状态集 \(A\)，定义首达时间（hitting time） \(\tau_A=\inf\{n\ge0:X_n\in A\}\)，空集下确界取 \(\infty\)。若初态就在 \(A\)，则首达时间为零；返回时间另用 \(\tau_A^+=\inf\{n\ge1:X_n\in A\}\)。
取不交的目标集 \(A,B\)，记 \(C=(A\cup B)^c\)、\(\tau=\tau_{A\cup B}\)。令 \(h_i=P_i(\tau_A<\tau_B)\)、\(e_i=E_i\tau\)，其中期望允许为 \(\infty\)。则
它们分别是相应边界条件下的最小非负解。取 \(B=\varnothing\)，第一组方程便计算最终命中 \(A\) 的概率。
证明。从 \(i\in C\) 出发，先走一步到 \(j\)，剩余问题具有从 \(j\) 出发的分布；时间方程中的一正是已经走过的一步。非负和及期望按扩展值理解。为证明最小性，从 \(h^{(0)}=1_A\)、\(e^{(0)}=0\) 开始迭代：
归纳可知 \(h_i^{(n)}=P_i(\tau_A\le n,\tau_A<\tau_B)\)，\(e_i^{(n)}=E_i(\tau\wedge n)\)，所以由单调收敛分别趋于 \(h_i,e_i\)。任何非负解都不小于初始向量，代入保持序关系，故归纳不小于每一次迭代，最终不小于上述极限。非负解并不总是唯一，直接解线性方程时不能略去这一步。
12.3.2 强马尔可夫性与返回周期
若 \(T\) 是自然滤过的停时，则在 \(\{T<\infty\}\) 上，给定 \(X_T\) 后，未来的分布是从 \(X_T\) 开始的同一条链。准确地，对任意有界函数 \(g:S^{r+1}\to\mathbb R\)，令 \(G(i)=E_i g(X_0,\ldots,X_r)\)，则
\(\mathcal F_T\) 表示停时处的信息，定义见11.4 节；式中随机变量在 \(\{T=\infty\}\) 上可统一置零。
证明。对 \(D\in\mathcal F_T\)，有 \(D\cap\{T=n\}\in\mathcal F_n\)。在每个这样的事件上使用确定时刻的马尔可夫性，再按 \(n\) 求和：
\(g\) 有界保证求和合法。这正是条件期望的积分刻画。对有限段路径已经证明的结论，再经单调类方法延伸到整个未来路径。
若 \(X_0=a\)，且 \(a\) 常返，令 \(T_0=0,\ T_{k+1}=\inf\{n>T_k:X_n=a\}\)。强马尔可夫性使相邻返回间隔 \(T_{k+1}-T_k\) 独立同分布，而且每次有限。它们的均值仍可能无穷：正常返对应有限平均返回时间，零常返对应无限平均返回时间。若从别的状态出发，首次到达 \(a\) 的时间一般具有不同分布；若 \(a\) 暂留，还可能永不返回，不能直接当作下面的普通更新过程。
12.3.3 有限吸收链与赌徒破产
研究到达集合 \(D\) 时，可令链到达 \(D\) 后留在原地。按非吸收状态 \(C\) 与吸收状态 \(D\) 排序，转移矩阵具有分块形式
最后一个等式需要条件：状态有限，且每个 \(C\) 中的状态都能以正概率沿有限路径到达 \(D\)。为每个状态选一条这样的路径，有限性给出共同的步数上界 \(L\) 和成功概率下界 \(\varepsilon>0\)。于是
因此 \(Q^n\to0\)，几何级数收敛；将有限级数乘以 \(I-Q\) 再取极限，就得到逆矩阵公式。\(\mathsf G\) 称为基本矩阵（fundamental matrix），且
\(\mathsf B_{ia}\) 是从 \(i\) 最终吸收在 \(a\in D\) 的概率。访问次数包含初始时刻。若 \(C\) 内存在无法离开的闭类，上述可达条件失败，有限状态空间本身并不保证吸收，\(I-Q\) 也可能不可逆。
在 \(\{0,1,\ldots,K\}\) 上，\(K\ge2\)，从内部状态以概率 \(p\in(0,1)\) 向右一步，以 \(1-p\) 向左一步，边界吸收。记 \(h_i=P_i(\tau_K<\tau_0)\)。首步方程给出 \(p(h_{i+1}-h_i)=(1-p)(h_i-h_{i-1})\)。因此相邻差组成几何数列，再用 \(h_0=0,h_K=1\)，得到
时间公式的两种表达式分别满足 \(e_0=e_K=0\) 和 \(e_i=1+pe_{i+1}+(1-p)e_{i-1}\)，故由基本矩阵的唯一性就是所求期望。这里各内部状态都可到达边界，前述几何尾界已保证 \(\tau=\tau_{\{0,K\}}\) 的期望有限。
独立验证。把边界前的运动看作整数线上随机游走。若 \(p\ne1/2\)，\(\rho^{X_n}\) 是鞅；先停在 \(\tau\wedge n\)，再利用 \(0\le X_{\tau\wedge n}\le K\) 和控制收敛，得 \(1-h_i+h_i\rho^K=\rho^i\)。鞅 \(X_n-(2p-1)n\) 则给出 \(Kh_i-i=(2p-1)E_i\tau\)，此处由 \(E_i\tau<\infty\) 保证时间项可取极限。公平时使用 \(X_n\) 与 \(X_n^2-n\)，同理得到 \(Kh_i=i\)、\(K^2h_i-E_i\tau=i^2\)。例如 \(K=3,i=1,p=1/2\) 时，命中右边界的概率为 \(1/3\)，平均吸收时间为二。
12.3.4 普通更新过程与更新方程
设间隔 \(Y_1,Y_2,\ldots>0\) 独立同分布，分布函数为 \(F\)，且 \(0<\mu=EY_1<\infty\)。令
\(N(t)\) 是普通更新过程（ordinary renewal process）：时间零为一个新周期的起点，但 \(N(t)\) 只统计其后的更新。强律保证 \(S_n\to\infty\)，所以有限时间内计数有限。间隔无需服从指数分布，泊松过程只是一种特殊情形。
定义更新函数 \(m(t)=EN(t)\)，先允许非负扩展值；下一节验证其有限性。由 \(N(t)=\sum_{n\ge1}1_{\{S_n\le t\}}\) 和 Tonelli 定理，
\(F^{*n}\) 是 \(n\) 个间隔之和的分布函数。积分表示：首次更新在 \(s\le t\) 发生后，剩余 \(t-s\) 时间里的计数具有独立的新副本；\(F(t)\) 则计入这一次更新。从零函数反复代入右边，得到前 \(k\) 项卷积之和，因此 \(m\) 也是该更新方程的最小非负解。若把时间零的起点算进去，更新函数变为 \(U(t)=1+m(t)\)，常数项随之改变。
12.3.5 更新强律与初等更新定理
在上述严格正间隔、独立同分布和有限正均值条件下，
第二个结论称为初等更新定理（elementary renewal theorem）。这两个结论均不需要非格点条件。
强律。由大数强律 \(S_n/n\to\mu\)，且 \(N(t)\to\infty\)。对充分大的 \(t\)，用 \(S_{N(t)}\le t<S_{N(t)+1}\) 夹逼，得 \(t/N(t)\to\mu\)，从而得到第一个结论。
期望极限。先证明一个可积上界。固定 \(b>0\)，令 \(Y_j^{(b)}=Y_j\wedge b\)、\(\mu_b=EY_j^{(b)}>0\)，并用这些较短间隔构造 \(S_n^{(b)}\)。其首次越过 \(t\) 的指标为 \(K_b=\inf\{n\ge1:S_n^{(b)}>t\}\)，几乎必然有限。由于 \(\{K_b\ge j\}=\{S_{j-1}^{(b)}\le t\}\) 只依赖前 \(j-1\) 个间隔，Tonelli 与独立性给出非负 Wald 恒等式：
这一步先允许两端为无穷，不需要预先假设 \(EK_b<\infty\)。越过前的总和不超过 \(t\)，最后间隔不超过 \(b\)，故 \(S_{K_b}^{(b)}\le t+b\)。又因截短间隔使更新次数增加，有 \(N(t)+1\le K_b\)，于是
令 \(b\uparrow\infty\)，单调收敛给出 \(\mu_b\uparrow\mu\)，得到上极限不超过 \(1/\mu\)。另一方面，对非负的 \(N(t)/t\) 使用 Fatou 引理和已经证明的强律，下极限不小于 \(1/\mu\)。两者合起来才得到期望极限；单凭几乎必然收敛不能交换期望。
若 \(F\) 还非格点（nonarithmetic），即不存在 \(d>0\) 使 \(P(Y_1\in d\mathbb Z)=1\)，则 Blackwell 更新定理给出：对每个固定 \(a>0\)，
这描述固定长度时间窗中的平均更新数，不能仅由 \(m(t)/t\to1/\mu\) 相减得到。其耦合证明及下一节所用的关键更新定理，见 Durrett §2.6，定理 2.6.4、2.6.12。格点分布需要保留时间相位，习题 12.3-3 给出反例。
12.3.6 剩余寿命、长度偏倚与平稳更新
普通更新过程在时间零刚开始一个周期，其剩余寿命（residual life）为 \(R(t)=S_{N(t)+1}-t\)，特别地 \(R(0)\) 与 \(Y_1\) 同分布。固定 \(x\ge0\)，对第一周期作分解，\(H_x(t)=P(R(t)>x)\) 满足
若 \(F\) 非格点，则关键更新定理对非负、不增且可积的 \(\overline F(t+x)\) 给出 \(H_x(t)\to\mu^{-1}\int_x^\infty\overline F(u)\,du\)。这里调用的更新定理技术证明不展开，出处见上一节。
这一极限也是平稳更新点过程（stationary renewal point process）在任意观察时刻的剩余寿命分布。平稳版本不把原点固定为一次更新：先让包含原点的周期长度 \(L\) 按长度偏倚（length bias）抽取，再把原点在该周期中均匀放置；两侧的其他周期使用独立的 \(F\) 间隔。于是
较长周期占据更多时间，正是因子 \(y\) 的来源。面向未来观察，这相当于首次等待服从 \(F_{\mathrm e}(x)=\mu^{-1}\int_0^x\overline F(u)\,du\)，以后间隔仍独立服从 \(F\) 的延迟更新过程。这里“平稳”指更新点集合的平移不变性，以及相应计数过程的增量分布具有平移不变性。
该式由给定 \(L=y\) 时剩余长度均值为 \(y/2\) 得到，允许右端为 \(\infty\)；剩余寿命均值有限还需二阶矩有限。这是平稳版本的精确均值，普通过程的分布收敛本身并不能推出期望收敛。
设 \(P(Y_1=1)=P(Y_1=3)=1/2\)，则 \(\mu=2,\ EY_1^2=5\)。按周期编号抽样，两种长度各占一半；平稳观察时，\(P(L=1)=1/4,\ P(L=3)=3/4\)。给定周期长度一或三，剩余寿命分别均匀分布于相应区间，所以
普通版本起点处的平均等待却是 \(EY_1=2\)。这个例子是格点分布，平稳版本的计算不能当成普通版本沿任意实数时间趋于无穷的分布极限；但更新强律与初等更新定理仍给出长期更新率 \(1/2\)。
12.3.7 习题与完整解答
习题 12.3-1 · 用基本矩阵核对四状态吸收链
题目。对图 12.3-1，按 \(C=(1,2)\)、\(D=(0,3)\) 排序，求 \(Q,R,\mathsf G,\mathsf B\) 及吸收时间均值，解释 \(G_{11}\) 的含义。
解答。由转移图直接读出
两行之和都是二，故 \(\boldsymbol e=(2,2)^{\mathsf T}\)。再乘以 \(R\)，得到
第一行表示从状态一出发，最终在零、三吸收的概率分别为 \(2/3,1/3\)，总和为一。\(G_{11}=4/3\) 是从一出发、吸收前访问一的期望次数，包含初始的一次，不能解释成命中概率。
习题 12.3-2 · 几乎必然到达，平均时间仍可无穷
题目。整数线上的简单对称随机游走从整数 \(i\ge1\) 出发，证明 \(P_i(\tau_0<\infty)=1\)，但 \(E_i\tau_0=\infty\)。
解答。取任意整数 \(b>i\)。有限区间赌徒破产公式给出 \(P_i(\tau_0<\tau_b)=1-i/b\)，所以 \(P_i(\tau_0<\infty)\ge1-i/b\)。令 \(b\to\infty\)，便得命中概率为一。另一方面，\(\tau_0\ge\tau_{\{0,b\}}\)，故
因此期望发散。两个推导都只使用有限区间中已证明可积的吸收时间，没有对未知可积性的 \(\tau_0\) 直接套用可选停止。对称游走从原点走一步后再返回的平均时间也因此无穷，对应零常返。
习题 12.3-3 · 确定间隔为何需要保留时间相位？
题目。设每个更新间隔恒为 \(a>0\)。验证更新强律与初等更新定理，说明 Blackwell 结论在长度 \(a/2\) 的时间窗上失败，并比较普通和平稳版本的剩余寿命。
解答。\(S_n=na\)，所以 \(N(t)=m(t)=\lfloor t/a\rfloor\)，两种长期比值都趋于 \(1/a\)。但当 \(t=na\) 时，\(N(t+a/2)-N(t)=0\)；当 \(t=na+3a/4\) 时，该差为一。因此固定窗增量没有极限，缺少的正是非格点条件。
普通版本有 \(R(t)=a(\lfloor t/a\rfloor+1)-t\)，随时间相位周期变化，分布不收敛。平稳版本把更新点设在 \(U+ka\)，\(k\in\mathbb Z\)，其中 \(U\) 在 \((0,a)\) 均匀分布。任意时刻的剩余寿命都服从 \(\operatorname{Unif}(0,a)\)，均值 \(a/2\)，与 \(EY_1^2/(2EY_1)\) 一致。
习题 12.3-4 · 一与二两种间隔的精确更新函数
题目。设 \(P(Y_1=1)=P(Y_1=2)=1/2\)，记 \(m_n=EN(n)\)。求整数时刻的显式公式，并验证长期更新率。
解答。有 \(m_0=0,m_1=1/2\)。当 \(n\ge2\) 时，首次更新一定发生于时间 \(n\) 之前或恰在 \(n\)，故更新方程化为 \(m_n=1+(m_{n-1}+m_{n-2})/2\)。一个特解是 \(2n/3\)，齐次方程的特征根是一和 \(-1/2\)。因此令 \(m_n=2n/3+c+d(-1/2)^n\)，由初值得 \(c=-1/9,d=1/9\)，即
例如 \(m_2=5/4\)，也可直接由 \(P(S_1\le2)+P(S_2\le2)=1+1/4\) 核对。长期比值为 \(2/3=1/EY_1\)。这不是泊松过程：这里 \(N(1)\le1\)，而任意正速率泊松过程在单位时间内至少发生两次的概率为正。
关键术语
- 首达时间：首次进入目标集的时刻，允许为 \(\infty\)。
- 最小非负解：由有限时域递推的单调极限选出的概率或期望解。
- 强马尔可夫性：停时有限时，给定当前状态可重新使用链的转移规律。
- 基本矩阵：有限吸收链中记录吸收前期望访问次数的 \((I-Q)^{-1}\)。
- 普通更新过程：从时间零的新周期开始，累加独立同分布的正间隔。
- 更新函数：某段时间内更新次数的期望。
- 初等更新定理：有限正平均间隔下，平均更新数的长期增长率为 \(1/\mu\)。
- 剩余寿命：从观察时刻到下次更新的时间。
- 长度偏倚：按时间观察时，周期被选中的概率与长度成比例。
- 平稳更新：以平移不变的更新点集合为模型，原点通常位于周期内部。
参考文献与进一步阅读
- Durrett, R. (2019). Probability: Theory and Examples, 5th ed. 作者公开版本，§2.6（更新、平稳延迟与剩余寿命），§5.2，定理 5.2.5（强马尔可夫性质）。Blackwell 与关键更新定理的技术证明分别见定理 2.6.4、2.6.12，剩余寿命应用见例 2.6.15。
- Bertsekas, D. P. and Tsitsiklis, J. N. Introduction to Probability: Selected Textbook Summary Material，MIT RES.6-012 课程材料，§7.4（吸收概率与平均吸收时间方程）。
- Gallager, R. (2011). MIT 6.262, Lecture 15: The Last Renewal（更新强律、Wald 恒等式、初等更新定理和延迟更新）。