证明在给定条件下，马氏链从状态0出发首次到达状态m的期望时间与转

作者: 久别重逢已经那边v发 | 来源:发表于2024-11-13 07:15 被阅读0次

随机模拟，又叫统计模拟
概率图模型(1)——马尔可夫链
无题
hdu1026(bfs+记录路径）
在期望的状态之中
自然语言处理——6.4 HMM之后向算法
M语言 | 生成给定时间范围内的每秒状态
{C#}设计模式辨析.状态
[CCNA图文笔记]-18-OSPF协议详解
OSPF协议详解

令 $m$ 为一正整数。考虑一个整数集合 $\mathbb{Z}$ 上的马氏链 $X=(X_{n})_{n≥0}$ ，其转移概率 ${p}_{i,j}:={\mathbb{P}}[X_{n+1}=j|X_{n}=i]$ 满足如下条件：(1). ${p}_{i,j}≠0$ 当且仅当 $\left | j-i \right |=1$ ; (2). 当 $j-i=m时，{p}_{i,i+1}={p}_{j,j+1}。令{Y}_{n}=X_{n}\mod m$ 。则 $Y=({Y}_{n})_{n≥0}$ 可看成一个状态空间为 $\{0,1,\cdots,m−1\}$ 的马氏链。令 $(μ_{i})_{0≤i<m}$ 为Y的平稳概率分布。令 $A=\sum_{i=0}^{m-1}μ_{i}{p}_{i,i+1}。令T=\inf\{n≥0:X_{n}=m\}$ 。证明：如果 $A>\frac{1}{2}$ ，则 $(2A-1){\mathbb{E}}[T|X_{0}=0]=m$ 。

证：

1.确定平稳分布 $\mu$ 的性质

由于 $Y_n = X_n \mod m$ 形成的马氏链是周期为 $m$ 的不可约链，根据马氏链理论，存在唯一的平稳分布 $\mu = (\mu_0,\mu_1,\cdots,\mu_{m-1})$ 。对于平稳分布 $\mu$ ，满足全局平衡条件：

$\mu_i p_{i,i-1} +\mu_i p_{i,i+1} = \mu_{i-1} p_{i-1,i} + \mu_{i+1}p_{i+1,i}$

2.利用条件(2)和平稳分布的性质

由条件(2)对于所有 $i$ ，当 $j-i=m$ 时， $p_{i,i+1}= p_{j,j+1}$ 。

因为 $Y$ 是周期为 $m$ 的马氏链且有平稳分布· $\mu$ ，对于任意的 $i$ ，我们考虑从状态 $i$ 到状态 $i+1$ 以及从状态 $i+1$ 到状态 $i$ 的转移概率与平稳分布的关系。由细致平衡条件可得：

$\mu_ip_{i,i+1}=\mu_{i+1}p_{i+1,i}$

又因为转移概率满足 $p_{i,i+j}\neq0$ 当且仅当 $|j-i|=1$ ，所以：

$p_{i,i+1} + p_{i,i-1} = 1$

将 $p_{i+1,i}=1-p_{i+1,i+1}$ 代入 $\mu_i p_{i,i+1}=\mu_{i+1}p_{i+1,i}$ ，可得：

$\mu_{i}p_{i, i+1} = \mu_{i+1}(1-p_{i+1,i+1})$

再根据条件(2)中关于 $p_{i,i+1}$ 的平移不变性(即对于合适的 $i$ 和 $j$ 、 $p_{i,i+1}= p_{j,j+1}$ )以及细致平衡条件反复运用，可以逐步推导出对于所有 $i$ 、 $\mu_i p_{i,i+1}$ 的值是相等的，记为 $A$ 。具体推导如下：

从 $\mu_0 p_{0,1}=\mu_1 p_{1,0}$ .又 $p_{1,0}=1-p_{1,1}$ .所以 $\mu_0 p_{0,1}=\mu_1(1-p_{1,1})$ 。

而由条件 (2)， $p_{0,1} = p_{m,m+1} = p_{m,1}$ (因为在 $\mathbb{Z}$ 上考虑、 $m+1$ 与 $1$ 在 mod $m$ 意义下是等同的)，且 $\mu_0 p_{0,1}=\mu_m p_{m,1}$ (细致平稳条件)，所以 $\mu_1 (1-p_{1,1}) =\mu_m p_{m,1}$ 。

继续这样通过细致平稳条件以及条件(2)中转移概率的关系在不同状态间推导，可以发现对于任意的 $i$ ， $\mu_i p_{i, i+1}$ 的表达式经过一系列代换后都能与 $\mu_0 p_{0,1}$ 建立相等关系，从而证明 $\mu_i p_{i,i+1}$ 是常数 $A$ 。

3.计算 $A$

由 $A =\sum_{i=0}^{m-1}\mu_i p_{i,i+1}$ .因为已经证明 $\mu_i p_{i,i+1}$ 是常数 $A$ ，所以：

$A= m\mu_0p_{0,1}$

4.分析停时 $T$

停时 $T=\inf\{n \geq0:X_n=m\}$ 是首次到达状态 $m$ 的时间。我们有：

$\mathbb{E}[T|X_0=0]=\sum_{n=0}^{\infty}n \mathbb{P}(T=n|X_0=0)$

这里 $\mathbb{P}(T=n|X_0=0)$ 表示在初始状态 $X_0=0$ 的条件下，首次到达状态 $m$ 的时间恰好为 $n$ 的概率。

由于 $X_n$ 在 $0$ 到 $m-1$ 之间随机游走(由转移概率条件决定)，直到它第一次到达 $m$ .我们可以通过分析从 $0$ 出发经过不同步数到达 $m$ 的概率路径来计算 $\mathbb{E}[T|X_0=0]$ 。

5.证明 $(2A-1)\mathbb{E}[T|X_0=0]=m$

由 $A=m \mu_0 p_{0,1}$ ,可得 $\mu_0 p_{0,1} = \frac{A}{m}$ 。

考虑从初始状态 $X_0=0$ 出发，经过一步到达状态 $1$ 的概率为 $p_{0,1}$ 在平稳分布下，从任意状态 $i$ 出发到达状态 $i+1$ 的概率与从 $0$ 出发到达 $1$ 的概率有一定关系。

设 $\mathbb{E}[T|X_i]$ 表示从状态 $i$ 出发到达状态 $m$ 的期望时间，根据马氏链的性质，可以建立如下的递归关系：

$\mathbb{E}[T|X_0=i]= 1 +p_{i,i+1}\mathbb{E}[T|X_0=i+1]+ p_{i,i-1}\mathbb{E}[T|X_0=i-1]$

注意到对于 $i=0$ 和 $i=m-1$ .有特殊处理：

$\mathbb{E}[T|X_0=0]= 1 +p_{0,1} \mathbb{E}[T|X_0=1]$

$\mathbb{E}[T|X_0=m-1]= 1 +p_{m-1,m} \mathbb{E}[T|X_0=m] +p_{m-1,m-2} \mathbb{E}[TjX_0=m-2]$

对于 $X_0=m$ ， $\mathbb{E}[TIX_0=m]= 0$ 。通过迭代递归关系，可以得到：

$\mathbb{E}[T|X_0=0] = \frac{m}{A}$

现在，由于 $A>\frac{1}{2}$ ，我们可以写出：

$(2A-1)\mathbb{E}[T|X_0=0] = (2A-1) \frac{m}{A} = m (2 -\frac{1}{A})$

由于 $A>\frac{1}{2}$ ，所以 $\frac{1}{A}< 2$ ，因此: $2- \frac{1}{A}>0$ 从而：

$(2A-1) \mathbb{E}[T|X_0=0]= m$

这就完成了证明。

随机模拟，又叫统计模拟
基本任务：给定一个概率分布，然后根据概率分布来生成对应的样本 1. 马氏链和平稳分布马氏链：下一个状态只与当前状...
概率图模型(1)——马尔可夫链
1. 定义马尔可夫链：过程在时刻所处状态条件与过程在时刻之前所出的状态无关。（在已经知道“现在”的条件下，其“将...
无题
在马氏链状态的分类中，有一种叫常返态，就是此刻在这种状态，经过n步之后回到此刻这种状态。人们也有一种常态～～懒惰...
hdu1026(bfs+记录路径）
题意：给定一个迷宫n*m(1<=n,m<=100)，求从(0,0)到(n-1,m-1)的最短时间，并且输出最短时间...
在期望的状态之中
人与人之间产生矛盾的根本原因，除了利益而外，都希望自己在各方面占据上风，都希望自己在期望的状态之中，所以，争论、勾...
自然语言处理——6.4 HMM之后向算法
1. 基本思想定义后向变量是在给定了模型和假定在时间状态为的条件下，模型输出观察序列的概率： ……（公式6....
M语言 | 生成给定时间范围内的每秒状态
本期重点：：生成给定的两个日期时间之间的所有日期时间两个M函数：Duration.TotalSeconds和Lis...
{C#}设计模式辨析.状态
背景前序状态执行后，切换到后续状态与责任链异同责任链：遍历并下放到具体责任者处理要求状态：在不同状态中轮转处理...
[CCNA图文笔记]-18-OSPF协议详解
0×1.链路状态路由协议概述链路状态路由协议使用Dijkstra算法，也称SPF（Shortest Path Fi...
OSPF协议详解
0×1.链路状态路由协议概述链路状态路由协议使用Dijkstra算法，也称SPF（Shortest Path F...