在Statlect上搜索概率和统计术语
统计列克特
指数 > 的基本原理 统计

马尔可夫链

通过 马可·塔波加(Marco Taboga)博士

马尔可夫链是具有以下特征的随机变量(或向量)序列: 所谓的马尔可夫性质:给定链中的一项(现在), 后续条款(未来)有条件独立于先前条款 条款(过去)。

本讲座是马尔可夫链的路线图。不像大多数讲座 这本教科书,并没有详尽地讨论该主题 证明,派生,示例和练习(为此需要单独的教科书 将需要)。其目的是提供一些概念的快速介绍。 经常用于应用统计信息(例如,在马尔可夫链蒙特卡洛 方法)。对更详细的处理方法感兴趣的读者可以 请查看本页末尾的参考文献。

目录

定义

让我们从一个正式的定义开始。

定义[eq1] 成为 的顺序 随机向量。序列 [eq2] 据说是 马尔可夫链 当且仅当 序列 X_n 独立 在所有之前的术语中 $ X_ {n-1} $ 有条件的 $ X_ {n-1} $: [eq3]哪里 这封信 F 表示一个 有条件的 分配功能.

状态空间

状态空间 $ S $ 马尔可夫链 [eq2] 是所有可能的集合 实现 的 链条条款。换句话说,对于任何给定的术语 X_n, 的 支持X_n 包含在 $ S $.

在接下来的内容中,我们将通过解决以下问题来介绍有关马尔可夫链的主要事实: 难度增加的顺序为:

马尔可夫链与

让我们从有限状态空间的情况开始。特别地,我们假设 那[eq5]那 是,链条中的一项可以采用 $ J $ 价值观 [eq6].

时间均匀性

我们指定一个 初始分配 对于的第一个值 链,即 $ 1imes J $ 初始概率向量 $ pi _ {1} $ 并强加 [eq7]

然后,我们可以选择一个 $ Jimes J $ 转移概率矩阵 $ P $ (一个矩阵,使得它的每一行都是概率的向量)和 强加[eq8]对于 所有 n$ i,jleq J $. 假设 $ P $ 所有人都平等 n 称为时间均一性(认为是指数 n (以时间为单位)。

这两个选择(初始分布 $ pi _ {1} $ 和过渡分布 $ P $) 完全确定所有链条的分布。作为一个 事实上,对于任何 n, 我们有 [eq9]哪里[eq10]

后者平等 因为[eq11]

固定分配

如果,对于给定的转移概率矩阵 $ P $, 有一个初始分布 $ pi $ 这样链中所有项的分布等于 初始分配,然后 $ pi $ 被称为 平稳分布 (或不变的 分布)。

什么时候 $ pi $ 是固定分布,我们有 那[eq12]

连同事实 那[eq13]它 暗示[eq14]

详细余额

具有有限状态空间的马尔可夫链据说满足 详细 平衡 当且仅当存在分布的情况下 $ pi _ {b} $ 这样 那[eq15]对于 任何 $ i,jleq J $.

通过将等式的两边求和 $ j $, 我们 得到[eq16]要么[eq17]

[eq18]

因此,[eq19]对于 任何 $ ileq J $. 但这可以用矩阵形式写 如 [eq20]

作为结果, $ pi _ {b} $ 是链条的固定分布。

请注意,详细的平衡是比现有的更为严格的要求 固定分布:前者暗含后者,但反之 是不正确的。

不可约链

现在,我们介​​绍马尔可夫链的一些属性,这些属性经常用于 研究他们的渐近行为。第一个这样的属性是所谓的 不可约。

$ x,yin S $. 定义击球时间 [eq21]哪里 下标 x 表示假定该链从 $ X_ {1} = x $.

我们说 x 造成 $ y $ 当且仅当 [eq22]

同样,符号 $ QTR {rm} {P} _ {x} $ 表示根据以下假设计算概率 $ X_ {1} = x $.

据说马尔可夫链是 不可约的 当且仅当每个 状态导致其自身以及其他所有状态,也就是说,当且仅当存在 对于任何起始状态都是一个正概率 x 连锁店将达到任何其他状态 $ y $ (包含 x 本身)在有限的时间内。

循环链

一个状态 $ yin S $ 仅当且仅当称为 [eq23]

否则,称为瞬态。

换句话说,状态 $ y $ 当且仅当链条返回的概率为 $ y $ 在有限的时间内(从 $ y $ 本身)等于 1.

马尔可夫链称为 反复发作 当且仅当所有 其状态空间中的元素是周期性的。

非周期性链

$ yin S $. 的时期 $ y $ 被定义为 [eq24]哪里 $ gcd $ 是最大的共同点。换一种说法, $ d_ {y} $ 是链条返回到的最短时间 x (从开始 x 本身)。

有可能证明,如果链是不可约的,则其所有状态 有相同的时期 $ d $, 这被称为链的周期。

一条链叫做 非周期性的 当且仅当 链是 $d=1$.

固定分布的存在性和唯一性

我们有以下重要结果。

主张 如果具有有限状态空间的马尔可夫链是不可约的,则它具有 独特的固定分布。

收敛到平稳分布

如果我们不仅假设不可约性,还假设非周期性,我们得到 以下结果。

主张 如果具有有限状态空间的马尔可夫链是不可约且非周期性的, 然后,无论初始分布如何 $ pi _ {1} $, [eq25]哪里 $ pi $ 是链条的唯一固定分布。

因此,即使链的初始分布不是固定的 发行条款 X_n 的序列变得越来越不依赖于初始值 X_1n 增加并且它们的分布收敛到平稳分布。

强大的大数定律

不可约性也可以用来证明 强大的大法则 号码.

主张 如果是马尔可夫链 [eq2]$ S $ 对于任何有界函数都是不可约的 [eq27],[eq28]哪里 $ pi $ 是链条的唯一固定分布,并且 [eq29] 表示 几乎可以肯定 收敛n 趋于无穷大。

因此,当状态空间有限时,不可约性保证了样本 整个链条上的平均值收敛到 美国。

这种命题通常称为遍历定理。

状态空间可数的马尔可夫链

现在,我们处理国家空间的情况 $ S $ 是无限但可数的。

特别地,我们假设 那[eq30]那 是,状态空间的元素可以安排成一个序列 [eq31].

时间均匀性

初始分配 的链是一个序列 初始概率 [eq32] 这样 [eq33]

然后,我们可以选择 过渡 机率 $ P_ {ijext {}} $这样 那,对于任何索引 i,[eq34]和 我们 强加[eq35]对于 所有 n, i$ j $.

注意过渡概率 $ P_ {ij} $ 独立于 n. 此属性称为时间均匀性。

这两个选择(初始分布 [eq36] 和过渡概率 $ Pij $) 完全确定所有链条的分布。

的分布 X_2 是一个序列 [eq37] 其元素可以如下得出: [eq38]

链中其他术语的分布 X_n 是序列 [eq39] 可以递归导出为 如下:[eq40]

固定分配

固定分配的概念与引入的几乎相同 如果是 。

如果,对于给定的双重转移概率序列 $ P_ {ij} $, 有一个初始分布 [eq41] 这样链中所有项的分布等于 初始分配,然后 [eq42] 被称为 平稳分布 的。

此外,我们有 那[eq43]

详细余额

具有可数状态空间的马尔可夫链据说满足 详细余额 当且仅当存在一个条件时 分配 [eq44] 这样 那[eq45]对于 任何 $ i,jin U {2115} $.

这意味着 那[eq46]要么[eq47]

[eq48]

因此,[eq49]对于 任何 $ ileq J $. 所以, [eq50] 是链条的固定分布。

不可约链

不可约性的概念与有限状态的情况相同 空间。

正循环链

在处理可数状态空间时,我们通常会强化 对于有限状态空间引入了重现。

记住一个状态 $ yin S $ 当且仅当链条返回的概率称为循环 至 $ y $ (从开始 $ y $ 本身)等于 1. [eq51]

即使状态反复出现,也有可能发生 那[eq52]那 是,返回时间的期望值是无限的。

当且仅当后一种可能性时,状态才被称为积极复发 排除,即,仅当 如果[eq53]

马尔可夫链称为 阳性复发 当且仅当 其状态空间的所有元素都是正递归的。

非周期性链

非周期性的概念与有限度的情况相同 状态空间。

固定分布的存在性和唯一性

以下重要结果成立。

主张 如果具有可数状态空间的马尔可夫链是不可约且正的 反复出现,则它具有独特的平稳分布。

请注意,在有限状态空间的情况下,不可约性足以 获得平稳分布的唯一性。在可数的情况下 我们需要增加阳性复发的要求。

收敛到平稳分布

以下收敛结果适用于状态可数的链 空间。

主张 如果状态空间可数的马尔可夫链是不可约的,则正 然后,无论初始分布如何 [eq54], [eq55]对于 任何 $ j $, 哪里 [eq42] 是链条的唯一固定分布。

将该命题与有限状态空间的命题进行比较:

强大的大数定律

还需要正向递归来证明强大的大数定律。

主张 如果是马尔可夫链 [eq2] 具有可数的状态空间 $ S $ 是不可还原的和积极的复发, 然后[eq58]哪里 [eq59] 是期望值的任何函数 [eq60] 存在并且是有限的 [eq61] 是链条的唯一固定分布,并且 [eq62] 表示几乎确定的收敛为 n 趋于无穷大。

通常,在某些情况下很难证明阳性复发,但是 我们知道该链具有固定分布。在这些情况下,我们可以 使用以下命题。

主张 如果是马尔可夫链 [eq2] 具有可数的状态空间 $ S $ 不可约且具有独特的平稳分布 [eq64], 然后[eq65]对于 任何功能 [eq59] 这样期望值 [eq67] 存在并且是有限的。

状态空间不可数的马尔可夫链

现在我们分析状态空间中更困难的情况 $ S $ 是无限且不可数的。

时间均匀性

初始分配 链的可能性 测量 $ pi _ {1} $ 这样 [eq68]对于 任何事件 $ Asubseteq S $.

然后,我们可以选择一个功能 [eq69]过渡内核 和我们 强加[eq70]对于 所有 $ xin S $ 和所有事件 $ Asubseteq S $.

过渡内核不依赖 n. 它是时间均匀的。

这两个选择(初始分布 $ pi _ {1} $ 和过渡内核 [eq71]) 完全确定所有链条的分布。

的分布 X_2 可以得出如下: [eq72]哪里 $ Asubseteq S $ 是任何事件,积分是 勒贝格 积分 关于概率测度 $ pi _ {1} $.

链中其他术语的分布 X_n 可以递归导出为 如下:[eq73]

当序列的项是连续变量(或向量)时,则 X_1 具有概率密度 [eq74] 这样 那[eq75]和 过渡核可以用条件概率表示 密度 [eq76]:[eq77]

结果,边际密度 [eq78] 可以表达链的条件 如 [eq79]

固定分配

固定分配的概念与上面关于固定分配的概念相似。 有限和可数状态空间的情况。

如果,对于给定的过渡内核 [eq80], 有一个初始分布 [eq81] 这样链中所有项的分布等于 初始分配,然后 [eq82] 被称为 平稳分布 的。

此外,我们有 [eq81] 满足[eq84]对于 任何 A.

在过渡核和平稳分布的情况下 有密度,我们可以 写[eq85]

详细余额

具有不可数状态空间和过渡核的马尔可夫链被称为 满足 详细余额 条件只有当存在 存在概率测度 $ pi _ {b} $ 这样 那[eq86]

如果采取措施 $ pi _ {b} $ 和过渡内核 [eq87] 可以写成概率密度,然后是详细的余额 条件可以写 如 [eq88]

通过积分方程的两边 $ y $, 我们 得到[eq89]要么[eq90]

以来[eq91]我们 得到[eq92]

从而, $ pi _ {b} $ 是固定分布。

不可还原链

不可约性的概念可以推广到不可数的情况 状态空间。

$ xin S $$ Asubseteq S $ 成为一个事件。定义击球时间 [eq93]哪里 下标 x 表示假定该链从 $ X_ {1} = x $.

我们说 x 造成 A 当且仅当 [eq94]

同样,符号 $ QTR {rm} {P} _ {x} $ 表示根据以下假设计算概率 $ X_ {1} = x $.

据说马尔可夫链是 $ arphi $-不可约的 当且仅当有措施时 $ arphi $ 这样每个州 x 造成 A 什么时候 [eq95].

换句话说,链条被认为是 $ arphi $-不可约 当且仅当对于任何起始状态都具有正概率 x 链条将到达任何位置 A 在有限的时间内采取积极措施。

哈里斯递归链

在处理不可数的状态空间时,我们经常使用 复发,称为哈里斯复发,比概念更强大 状态空间不可数时引入的正递归概率。

一个事件 $ Asubseteq S $ 叫做 哈里斯复发 当且仅当概率 该链将返回到 A 无限地(从属于某个点开始 A) 等于 1.

马尔可夫链称为 哈里斯复发 当且仅当它 是 $ arphi $-不可约 和所有事件 $ Asubseteq S $ 这样 [eq96] 哈里斯复发。

非周期性链

在无数情况下,非周期性的定义稍微多一些 复杂。

马尔可夫链据说有周期 $ d $ 如果其状态空间最多可以划分为 $ d $ 相互排斥的事件,使链条始终准确地 $ d $ 这些事件的周期。

在符号中,如果事件是 $ A_ {1} $,...,$ A_ {d} $, 那你有 [eq97]

如果链条的周期为 $d=1$.

固定分布的存在性和唯一性

与有限和可数情况不同, $ arphi $-不可约 和Harris复发不足以保证其存在,并且 固定分布的唯一性。需要进一步的技术条件 满足(例如, 格林2013)。

收敛到平稳分布

因为 $ arphi $-不可约 和Harris复发不足以保证其存在,并且 固定分布的唯一性,后者通常直接添加 在链融合到 平稳分布。

主张 如果状态空间不可数的马尔可夫链是 $ arphi $-不可约 哈里斯复发,不定期且分布平稳 $ pi $, 然后 $ pi _ {n} $ 收敛到 $ pi $.

概率分布序列的收敛 $ pi _ {n} $ 到固定分配 $ pi $ 总变化 规范 (我们可以在此处安全跳过的技术细节)。

强大的大数定律

在不可数情况下,以下遍历定理成立。

主张 如果是马尔可夫链 [eq2] 具有不可数的状态空间 $ S $$ arphi $-不可约 哈里斯复发且分布平稳 $ pi $, 然后[eq99]对于 任何功能 [eq59] 这样期望值 [eq101] 存在并且是有限的。

参考文献

Gilks​​,W.R.,Richardson,S.,Spiegelhalter D.(1995年) 马尔可夫链 蒙特卡洛实践,CRC Press。

Glynn,P.W.(2013) 哈里斯 复发,斯坦福大学随机系统讲义。

Hoel,P.G.,Port,S.C.,Stone,C.J.(1986) 简介 随机过程,Waveland出版社。

诺里斯·J·R(1998) 马可夫 链条,剑桥大学出版社。

皮什罗·尼克(Pishro-Nik,H.)(2014) 简介 概率,统计和随机过程,Kappa Research,LLC。

罗伯茨(Roberts G.O.),罗森塔尔(Rosenthal)J.S.(2006) 哈里斯复发 大都市内吉布斯和跨维马尔可夫链年鉴 应用概率,卷16号,第2123-2139页。

如何引用

请引用为:

Taboga, Marco (2017). "马尔可夫链", 列克特ures on probability 的ory 和 mathematical 统计, Third edition. Kindle Direct Publishing. Online appendix. //www.junruiqiche.com/fundamentals-of-statistics/Markov-chains.

这本书

该网站上提供的大多数学习材料现在都以传统教科书格式提供。