上一节笔记:随机过程(4)——返回时间,访问频率定理应用,离出分布,离出时间
————————————————————————————————————
大家好!
这一节我们开始对无限状态马尔可夫链做进一步的介绍。无限状态马尔可夫链的性质和有限状态略有不同,因此在一些问题的分析上,需要更加小心和注意。如果还有空的话,会给大家介绍泊松分布的基本概念。
那么我们开始吧。
目录
- 无限状态马尔可夫链的进一步探讨
- 泊松过程
- 复合泊松过程
无限状态马尔可夫链的进一步探讨
对于无限状态马尔可夫链,主要的问题在于对常返性和平稳分布的探讨。简单来说,在无限状态的情况下,因为状态空间
是一个无限集(别忘了,我们要求可数),所以不可约 闭集不能够再得到马尔可夫链常返的结论。同样,平稳分布也并不是在不可约,常返,闭集等性质存在的时候,就能够存在的。因此在这一节,我们会用一个例子贯穿始终,观察状态无限的时候,性质究竟会如何变化,又应该如何刻画。
Problem 1 考察一个随机游走问题。一个分子在数轴
上向左或者向右移动。并且满足
,
。推导这个马尔可夫链在
的取值变化的时候,对应平稳分布性质的改变。
这里
就可以理解为,分子向右移动一步的概率为
。
研究平稳分布的性质,是因为无限状态马尔可夫链与有限状态,一个最大的区别就体现在了平稳分布的存在性上。现在我们不能够说平稳分布存在,所以我们只能先计算平稳测度。但无所谓,因为计算平稳测度,其实归根到底还是可以使用之前提到的细致平衡条件(见第3节(链接))。通过相邻两步之间的表达式,可以计算出
这里我们设
是我们要的平稳测度的第
个元素。这个推导不难,我们留给读者。
有了这个之后,在运算合法的情况下,我们可以算出
为什么叫运算合法?是因为我们之前提过,如果是一个平稳分布,那么起码要保证
。但是很明显,如果
,这个条件是不满足的,潜在意思就是,这个计算是不合法的,中间一定有出问题的步骤。但至少我们有了一个思考的方向,可以通过这个阈值
,来讨论我们
的取值。
如果
,那么我们有
,潜在意思是
可以认为是一个等比数列,所以通过等比数列求和公式,可以得到我们
的表达式,这里我们就不细推导了,非常简单。
但如果
,这里就有问题了。首先因为
,所以从
出发,计算
的时候,数值就会呈“指数爆炸”的形态。那么很明显,因为我们要计算
以对平稳测度标准化为平稳分布,但是这样的话,
就不是一个有限值,所以就没有办法标准化。总结一下,就是在
的时候,平稳分布是不存在的。同样的,
的时候,虽然不会指数爆炸,但是我们会得到每一个
都是相等的值。这样也是不行的,因为求一个无限和得到的值依然是无限的。所以平稳分布依然是不存在的。
如果我们到此为止了,那么相当于在说
是一个意思。但事实上完全不是。要说清这一点,我们要从常返这个概念出发,重新看这个问题。
如果
,那么每一个
都是有值的。并且根据
,我们就可以得到
。从
出发,有限次之后会回到
,这就是常返的定义。如果
,要想研究常返性,我们可以研究“先到达远点
的概率“,潜在意思就是把它变成一个离出分布问题。
在这个题中,我们可以得出这么一个结论。
Lemma 1:
,其中
。
这里我们设
,那么我们有
,
。这样的话,会有
我们不难得到这个表达式的一个简便写法
(这里通过观察不难发现,但如果是学过数学竞赛或做过江苏高考,应该知道这种递推数列的通项求解其实是有通法的,后面我们会在另外一个例子简单介绍)因此可以得到的是
这是一个很经典的等比数列,并且在
的时候,公比是小于1的。因此我们可以根据式子
也就是说,
,
可以参考上面的定义。
这也就是我们的答案。
这里我们可以令
就得到了无限状态的情况,也就是说
。在这个情况下,我们有
,这就说明状态并不是常返的。
但是在
的时候稍有不同。通过同样的计算方法,我们可以得到
潜在意思就是
,也就是说我们仍然可以得到每一个状态都是常返的。这就得到了两个几乎完全对立的结果:常返和无平稳分布并存。
事实上,如果你计算离出时间(也就是说考虑计算
),按照之前对离出时间的计算方法,我们可以得到。
并且有
。那么这样的话,其实可以得到
其中
。这里我们来介绍一下求解这种递推数组的通法。简单来说,两边都减一个未知数,凑出一个等比数列。也就是说我们有
为了保证是一个等比数列,我们解方程
这就可以得到
。所以我们可以得到的是
这就是最重要的式子,剩下的对结果的推导都交给读者,因为都是等比数列求和的事情(当然这个推导也能够告诉你,
是需要单独计算的)。通过这个,可以得到
,
这里不难看出的结论是,在
的时候,有
,所以常返性是没有疑问的(别忘记
的定义了),
的时候,有
,所以瞬时性也没有疑问。但是如果是
,情况就有意思了。因为这个时候,有
(这是类似的方法推的),而我们又可以通过一步转移,得到
本质上还是一个离出时间公式。但是因为我们有
(多说几句,这是因为
,在
的时候,我们是没办法走到
的,因此就相当于只用考虑“回到0”的情况就可以了)。所以实质上有
。好家伙,一方面我们根据常返的定义,知道
是一个常返状态,但是另一方面又得到了
,说明
不是一个常返状态。那我到底应该听谁的?
为了弥补这个逻辑漏洞,统计学家下了另外一个新的定义。
Definition 1: Positive Recurrent, Null Recurrent 如果
满足
,那么称它是一个正常返状态。如果
但是
,那么称它是一个零常返状态。
所以这样,就解决了我们之前遇到的麻烦。
事实上,关于常返性,还有一个下面的定理。
Theorem 1: 对于一个不可约的马尔可夫链,下面性质等价
- 存在正常返的状态。
- 存在平稳分布
。
- 所有状态都是正常返的。
要想证明一系列的定理等价,重要的是证明出一个逻辑环。而很明显,
是很显然的,所以其实只需要说明
就可以。
我们先说明
。不妨假设我们的
是一个正常返的状态,那么有
。那么这个时候,如果你记着我们当时构造平稳测度的方法的时候,你应该有印象
同时我们还有
忘了的话,就看一下第3节(随机过程(3)——无限状态的平稳测度,返回时间,访问频率:几个定理的证明)。
那么这样的话,
就是我们的平稳分布,所以这一步就说明好了。
至于
,要说明所有状态都常返,其实就说明所有状态的
(假如说这个状态是
)都是正数就可以(因为
)。
这里我们注意到平稳分布是存在的,所以一定有某一个元素是正的。我们不妨假设是
。那么注意到不可约性,说明从任何一个状态出发,都能够到达另外一个状态。
那么对于某一个状态
,我们不妨假设
可以经过
步到达
。用数学的话说,就是
由
的任意性就足够说明结论了。
事实上无限状态马尔可夫链还有更多有趣的例子。不过我们这里已经点明了它最重要的一个与有限状态的区别,碍于篇幅我们就不多说了。也就是说到此为止,我们就算介绍完了离散马尔可夫链的所有内容。
泊松过程
泊松过程(Poisson Process)是一类极为重要的随机过程。与马尔可夫链的场景不同,它主要关注的是状态与状态之间的转移时间的随机性。同时因为一方面,整个过程与泊松分布有关,所以起名叫泊松过程。另一方面,为了保持无记忆性,它与指数分布又密不可分。
首先,我们自然要先好好的定义一下,什么是泊松过程。
Definition 2-1: Poisson Process with rate
设
都是独立同分布的,且服从
,设
,并且
,
表示在时间
之前的访问数,那么称
是一个速率为
的泊松过程。
你看到2-1这个标记就明白了,泊松过程不止一种定义。
这个定义看上去乱七八糟的,但下面一张图可以很好的帮助理解。
所以在泊松过程中,我们不关心状态空间,只关心每一次访问的时间,速率
越大,可以看出两个相邻状态之间的间隔时间
就会越短。可以看出,这里标记的
之前有三次访问,所以
。
接下来几个小的结论,可以刻画出泊松过程的一些有趣的特性。
Proposition 1:
这里
就是伽马分布,具体伽马分布的有关定义和它与指数分布的加和关系,可以参考《数理统计》第1节,这里就不赘述了。
https://zhuanlan.zhihu.com/p/70018601
Proposition 2:
这个性质就解释了为什么称它为泊松过程。
我们证明一下,注意到
后面的概率公式中,
都是随机变量,为了方便计算我们先考虑
的情况。注意到
这是因为
根据定义是相互独立的,所以可以拆开来写。接下来只需要根据
服从伽马分布,
服从指数分布,就可以得到
接下来就是一个纯的微积分计算题了,令
,就可以得到
这就证明结论了,因为这个就是
的概率公式。
下面这个结论其实更加体现出了泊松过程的“无记忆性”。
Proposition 3: 设
,那么
是相互独立的。
要说明这个,有一个证明方法,就是证明下面这一个结论。
Proposition 3-2: 设
,那么
和
是相互独立的。并且
也是一个速率为
的泊松过程。
这个结论其实看上去还是挺好理解的,因为一个相当于“之后的一段过程”,一个则相当于“之前的一段过程”。
用一张图描述,就是下面这个情况。
简单来说,这就是一个非常典型的考察
的定理,注意到而这个东西是服从
的,也就是说具备无记忆性。这和马尔可夫链的结果是一模一样的,更加具体的来说,从任何一个时间点
开始,都是一条全新的泊松过程,所以它是一个速率为
的泊松过程也就很好理解了。
有了这个之后,说明Proposition 3也就不难了。首先
不用说,是起点。然后注意到
与
独立,所以很自然的,可以得到
与
独立(因为
不能包含
之前的信息),后面的都一样推导就可以了。
下面,我们顺便说一下泊松过程的第二种定义。这个定义和Proposition 3也是息息相关。
Definition 2-2: Poisson Process with rate
如果
的增量独立(也就是Proposition 3的题干)
则称
是一个速率为
的泊松过程
既然它能够成为第二个泊松过程的定义,就说明两个定义之间,一定存在等价性。从Definition 2-1推导出Definition 2-2就是Proposition 3,那么反过来又如何推出呢?
要想从Definition 2-2推导出Definition 2-1,我们就需要看怎么推出到达间隔时间(也就是
)相互之间具备独立性,并且都服从指数分布。要想说明这个,我们从
一步步往后看。
首先我们来看,
说明什么。注意到
这是因为
根据条件,是服从泊松分布的,且
。这个式子就说明了
但是下一件事(也就是发现
满足的分布)可能稍微有点复杂,简单来说,需要同时发现独立性和指数分布这两件事。那么最好的一个方案就是计算
这样的话只要说明它也是
,就可以同时说明上面两个结论了。
注意到
中间的两步分别用到了
的定义和“增量独立”的条件。所以这样的话,对于
及以后,我们也有相似的推导方法,因此这就足够说明了Definition 2-1与这个定义的等价性了。
好的,来看一个例子吧。
Problem 2: 设
是一个速率为3的泊松过程,设
表示第
次的到达时间,计算
这个计算是对于泊松过程性质的一个很好的练习。
第一个题非常容易,注意到对一个服从
的随机变量来说,它的期望为
,所以我们有
第二个问题一看就知道要利用一些独立性。注意到
第一行到第二行怎么得到
其实不是很好理解,我们用一张图解释这个推导过程。
简单来说,利用的就是“时间之前和时间之后”的相互独立性,从一个新的起点出发的泊松过程,和之前无关,且性质完全一样。这一点非常像马尔科夫链。
相比较而言,第三个题做起来就更容易一些。一样,先加再减,所以我们有
这是因为
,所以有
。
Problem 3: 考虑一个速率为
的泊松过程,设
是
的时间内的最后一次的到达时间,也就是说如果
,就说明状态在
中没有一次访问。
- 计算
- 计算
很明显,这一个题就是希望了解
所服从的分布。
首先,当
的时候,对应的是
,这个是一个比较好算的情况,因为
但是如果武断地去说,这样可以直接得到分布的话,就太天真了,因为在
的时候,其实计算是比较复杂的。不妨假设我们的密度函数为
,那么有
简单来说,这一步分解就是讨论这个“最后一次到达”究竟是第几次到达。那么这样的话,我们就有
这是因为
和
相互独立。结合
,
,我们有
最后一个等号来源于Taylor展开的级数求和。
这样的话,计算就变得容易了,因为这个时候,分开积分,可以得到
这也就是我们的答案。
有了这个答案之后,第二问就简单了,令
可以得到
。事实上,可以进一步说明,当我们的
的时候,也就是考虑全部时间的时候,
会趋近于指数分布
,换句话说,最后一次访问到最终时间
的差距,在极限状态下就是服从一个正常区间
所服从的分布
。
复合泊松过程
复合泊松过程(Compound Poisson Process)的场景比正常的泊松过程复杂一点(不然也不叫复合了)。在之前的泊松过程中,我们只关心两次相邻访问之间的时间差距
,但是这一次我们把这个时间做进一步的抽象,考虑量
也就是说,这里我们考虑的并不仅仅是
的求和(也就是
),而是相当于,每一个时间都得到了一个“奖赏”
。我们可以用图表示这个。
复合泊松过程的场景一般都是用在计算中,因为它带来的一个最重要的性质就是下面这个公式。
Proposition 4: 设
,且
独立同分布,且
且具备相互之间的独立性(Proposition 3),证明
其实这个定理的难点,也是最重要的点,就是
中同时包含两类随机变量
和
。因此要证明这些公式,拆分出这两个随机变量是必要的。
拆分最好的方案就是重期望公式,简单来说就是
那么注意到这个时候,因为有了一个条件
,所以可以根据这个条件的情况,拆分出不同的结果。具体来说就是
这就证明了结论。
对于方差,我们事实上也是要利用重期望公式,但是是针对方差的。也就是
另外,利用和上面一模一样的推导思路,我们还有
代入,就可以得到结论,这个过程我们留给读者,就不自己写了。
再强调一遍,对于复合泊松过程,主要考查的是对随机变量(也就是对实际问题)的理解。如果能够读懂题目,那么剩下的就只是代入公式的问题了。
多提一句,虽然我们在《数理统计》第1节(链接之前已经提过了)就提到过均值和方差的重期望公式,但是我们并没有给出证明。这里我们补一下相关的证明。
Lemma 1: 证明重期望公式,也即
对于第一个,其实证明思路就是上面用到的推导思路,也即
所以关键还是中间的交换顺序。
对于第二个,证明稍微复杂一些。注意到
注意交叉项为0,是把
取到了后面的乘数上,利用第一个公式得到的。后面就是对于两个平方项的分别处理,也都是利用了第一个公式。
这个证明总体上没有太多的绕弯弯的地方,但是在期望的计算上有很多繁琐的细节,要仔细盘盘才能明白。
还是一样,我们来举一个例子
Problem 4: 考虑一个小店买物的问题。已知前往小店的客户数服从速率为81的泊松分布(按天计),每一个客户的花费服从一个均值为8,标准差为6的分布。问小店一天收益的均值与方差。
很明显,这里我们可以设
是客户数,而
就是每一个客户的花费。这样的话,
的均值和方差,就是这个题的答案。
不难看出,
,同时我们有
。所以直接把公式代入,可以算出
。具体的计算交给读者。
好的,关于泊松过程,我们先说到这里。
小结
本节主要讨论了无限状态马尔可夫链的零常返,正常返问题。并且同时我们也介绍了简单的泊松过程,复合泊松过程的性质和应用。在下一节,我们会介绍泊松过程的一些常见变换。这些变换可以让我们更容易发现一些让人拍案叫绝的性质,也会引出更多与泊松过程有关的具体应用。