上一节笔记:随机过程(6)——泊松过程三大变换,更新过程引入
————————————————————————————————————
大家好!
本节我们开始介绍更新过程中的更新奖赏过程,这是一个很有趣的更新过程的应用,也会占据很大的篇幅。
那么我们开始吧。
更新奖赏过程(Renewal Reward Process)是复合泊松过程的一个推广。简单来说,我们希望研究的是
并且这里的
相互独立(但是要注意,没有要求
和
之间的独立性),且
都服从某一个分布
。那么很明显,这就相当于每一次到达,都会得到一个“奖赏”
,然后我们希望观察,这个与奖赏有关的随机变量到底会有什么样的统计性质。
Proposition 1:
以概率1成立。
这个证明不是特别的麻烦,我们简单写一下。就是
这里的极限,一个就是我们上一节推导过的,利用夹逼定理得到的性质。另一个就是简单的同分布情况下的强大数定律。
那么我们看一个具体的例子吧。
Problem 1: 考虑一个修车的问题。假如说车的寿命服从一个密度函数
,且如果老车损坏了,就需要修,修车需要
的费用。寿命到达了
年,就需要更换,换车需要
的费用。问长期来看,单位时间的花费期望为?
这一个题要解决的第一个难关就是建模(这也是更新过程的常态),因为如果不能理清里面的各种要素,其实还是一个挺容易让人慌了手脚的问题。
首先第一件事,既然是一个过程,那么自然需要找到“到达的奖赏”。这里可以抽象出两个事件,一个是“修车”,一个是“换车”。所以如果我们假设每一次出现这样的事情经过的时间是
,那么有
这里的
就是车的自然寿命,服从密度函数
的那个值。因为当
的时候,车就需要被更换了。
根据Proposition 1,其实我们只需要算出
。因为
在
的时候,就是单位时间的平均花费,这里的
就是花费的总和。
我们先考虑
,那么注意到
并且有
所以最终的答案拼在一起就可以了。这里因为没有其他额外的信息(比方说
是什么),所以我们也只能写到这里。
下面这个性质很类似上一节的Theorem 5。不过还是一样,我们也不作证明。
Proposition 2: Reward Function
也是长得很像大数定律的一个定理。
交替更新过程(Alternating Renewal Process)也是一种具体的更新过程。简单来说,在这个模型中,两个相邻点之间经过的时间服从一个“交替的”分布。可以用图简单表示如下。
也就是说,交替的时间由一串独立同分布的随机变量
和
来决定。那么通过更新奖赏过程的性质,我们可以得到下面这样的结论(为了更好描述这个结论,我们设
决定的时间区间表示“处于状态1”,而
决定的时间区间表示“处于状态2”)。
Proposition 3: 设
服从一个分布为
,并且均值为
。
服从一个分布为
,并且均值为
,那么证明,长期来看,处于状态1的时间占比为
这个问题其实如果可以建模成更新奖赏过程的形式,就可以方便代入公式了,因为“时间占比”本质上也就是
。但这个做法也不难想,可以考虑如下的策略
将相邻的两个时间段做两两分组,并且如果处于状态1,就在状态1到达的时候记录一个奖赏
,表示处于状态1的时间
。否则就认为奖赏为0。
大致可以画出如下的图。
这样的话,
,
,这就足够得到结论了。
我们再举两个例子。
Problem 2: 考虑一个换灯泡的问题。假如说灯泡寿命服从分布
,均值为
。一个修理工会不定期来检查灯泡,检查灯泡的时间服从一个速率为
的泊松过程。如果发现灯泡坏了,就会立即更换。问 (1)灯泡更换的速率。 (2)长期来看,灯泡正常工作的时间占比。 (3)长期来看,修理工检查灯泡的时候不用更换灯泡的次数占比。
这个问题初看其实是一个很复杂的问题,因为修理工和灯泡寿命这两个过程是同时在发生的,似乎很难把它统一成一个过程下。但我们其实可以利用“无记忆性”做一个好的刻画。具体可以见下图。
这个图中,红色的点表示灯泡损坏,黑色+蓝色的点都是修理工到达的时刻,但区别在于蓝色的点表示修理工到达之后修好了灯泡。那么我们假设灯泡“正常运行”的时间是状态1,然后注意,在灯泡损坏之后,修理工到达的时间间隔依然服从一个指数分布
(无记忆性用到了这里),这个损坏的时间相当于状态2。而修好灯泡之后,灯泡又回回到“正常运行”的时间,所以 “交替”就体现出来了。
现在再来看题目。第一题事实上就是把这两个状态“并在一起”看成一条随机过程(这个想法我们上一节的“叠加”中有用过),也就是说
第二个题就是非常简单的交替更新过程,按照我们上面的建模,就很容易得到答案为
。第三个题的话,这里就需要考虑两个因素了,一个是“修理工来访了多少次”,这里我们设为
。另外一个是“修理工换了多少次灯泡”,这里我们设为
,也就是上面我们设的那个
。这样的话,我们计算的就是
那么注意到
(想想为什么?),
,对式子上下都除以一个
,就可以得到答案为
。
这个题的思考还是有挺多关键点的,当然最关键的地方还是如何建模和分析问题,这可比复合泊松过程的题目要难很多了……
Problem 3: 考虑一个机场接站的问题。假设大兴机场的国际航班出站旅客分布服从一个速率为10的泊松过程(每小时),并且有一个面包车。面包车每接满7个人就会立刻出发,送这批旅客前往高级酒店隔离。36min之后,这辆面包车就会回来。如果到达的旅客没有看到面包车,就会自行前往邻近的酒店隔离,问长时间来看,多少比例的游客最终会去高级酒店?
这是一道非常符合时事的问题,但是建模难度比上面要低很多了。
注意在这里,
和
一个可以表示“面包车”接的人,一个可以表示“自己走”的人。而它们的期望都很好计算,
,而
(因为36min内的期望根据泊松过程,很容易计算出来),所以直接根据交替更新过程的公式得到答案为
。
生存与濒死时间(Age and Residual Life)是在更新过程中经常会被拿来研究的概念。大致可以描述为研究两个状态到达之间的一个时间关系。具体的定义是
这个定义抽象的话,看一下图就懂了。
(这里有一个菱形一样的符号,用它表示“未到达,仅仅是一个标记”,下同)
所以说,如果描述的是一个电子元件的寿命,并且认为一次”到达“就是”零件损坏“,那么很明显,在中间的某一个时间点
,
就是它“已经工作(存活)的时间“,
就是“它还能工作(存活)多久”的意思。
说“大致描述”的原因是,在状态到达的时刻,对应的
都是0,也就是说到达和“相邻到达之间”这两段一般是要分开来分析的。
离散情况的意思是,只考虑到达的时间是离散正整数的情况,这是因为后面研究需要依赖到之前提到的马尔科夫链。
具体的一个示例也可以看下图。
在离散情况下,一个比较容易观察到的事实是
这可以通过把泊松过程分段,然后每一段分完之后讨论得到。如果你仔细看上一张图的一个示例的话,这个结论就不难得到。也是因为这么一个联系,所以我们研究的时候,只需要关心这两个量中的一个就可以了。
我们以
为例,因为离散情况,所以其实
的变化可以用马尔科夫链来描述,并且有
这里的
表示距离下一次到达时间为
的概率(强调一遍,因为是离散过程,所以这里的时间就是步数的意思)。
这里相当于把每一个点对应的
统计起来,然后用马尔科夫链去描述它。可以使用马尔科夫链进行描述的原因,自然是离散更新过程所带来的马尔科夫性。
为什么是这个转移概率呢?因为一步一步的转移有两种情况,一个是从“到达时间”走到下一步;一个是正常的,从中间的某一步走到下一步。如果从“到达时间”走到下一步,相当于
会从0走到一个正值,这个值取决于这一次,相邻两步的到达时间是多少。如果是另外一种情况,那么因为
下降1是一个必然事件,所以概率为1。如果觉得这一段抽象,对照上面那张图看,就比较明晰了。
当然,这一条马尔科夫链也是不可约和常返的。不可约的原因是,从0可以到任何一个数,从任何一个数也一定会返回到0。常返的原因也很简单,在不可约的假设下,找到一个点是常返的,所有的点就都常返了。以0为例,从0出发到任何一个点之后,一定还会返回到0。
有了马尔科夫链之后,自然就是各种平稳分布什么的推导了,这个可以汇总为下面这一个性质。
Proposition 4: 对于马尔科夫链
来说,如果
,并且是非周期的,那么有
。
一下看这个结论当然不知道是怎么来的。但是如果联系第3节(随机过程(3)——无限状态的平稳测度,返回时间,访问频率:几个定理的证明)的定理内容,你就明白我们本质上就是要求它的平稳分布,同时要有诸如非周期的条件,才能够满足那个定理的结论。
注意本质上这还是一个无限状态的马尔科夫链,所以平稳分布的存在性是一定要考虑的。在第5节(随机过程(5)——无限状态马尔科夫链的进一步探讨,泊松分布引入,复合泊松分布)我们说,这个取决于我们构造的平稳测度是否可以被标准化。
从头开始吧。我们可以按照第3节构造平稳测度的方案,先计算出一个值为
如果仔细观察
的数值,那么你会发现,
这一个事件,在
这个区间中,要不不发生,要不只发生一次(想想为什么?)。而如果不发生,就是0,发生的话,其实这个式子就等价于
,因为必须第一步到达
及以后的位置,才有可能在每一步,往后退一步的时候,经过
这个值(描述可能比较抽象,一定要对着图去看)。
那么注意到
所以分子我们就算出来了。而分母的话,其实把这个式子求和,就可以得到答案是
(参考第1节(随机过程(1)——引入,有限状态马尔科夫链,状态转移,常返与瞬时状态)的Lemma 1)。
那么
是一个有限的值(条件),那么实际上就可以知道,
是合理的,存在的。因此这个就是平稳分布,也就是说我们完成了证明。
我们来看一个实际的例子,加深一点印象。
Problem 4: 考虑一个大富翁的问题。每一次掷骰子决定走的步数。假设大富翁一共有40个格子,构成一个正方形。问“越过的步数”的期望是多少,这里“越过的步数”定义为每一次越过起点中,越过的步数。比方说从第38步走到43步,算“越过3步”。
这个问题其实就可以建模成生存与濒死时间的结构。如果我们站在
这个位置来看,那么这个点对应的濒死时间(步数)的期望,就是我们这里所需要的答案。而根据Proposition 4,我们可以得到这个答案就是
(想想为什么?),也就是说其实和站在哪里没什么关系,和大富翁一圈有多少个格子也没什么关系,完全取决于“骰子点数”这么一个随机变量。
连续情况下就复杂的多,对于它的研究需要一些分析上的工具。
首先我们可以研究一下,在一般的情况下,
的密度函数是什么样的。
Proposition 5:
这个结果还是很有趣的,虽然并没有直接给出密度函数本身的性质,但是研究它的一个平均,很多时候也算够用了。
注意在这里,我们提到我们用到的是“一个平均”。那么有一个思路就是用上面的更新奖赏过程。因为更新奖赏过程本质上也是在研究
的极限情况,所以我们在这里只要定义好
,就可以利用之前的结论,也就是Proposition 1。
我们先画出下面的图。这个图简单的概括了,我们每一次的“奖赏”究竟是怎么定义的。
总体来说,我们可以忽略
的那一段,因为在
的时候,这一段的收益可以忽略不计(这个技巧我们也是不止一次使用了)。然后每一个到达的点,对应的区间的奖赏,就是
,因为我们会去掉一开始的
(对应条件
)和末尾的一段
(对应条件
)那么长的距离。所以根据Proposition 1,我们可以知道,最终要计算的其实就是
(这里注意一下,因为在更新奖赏过程中,
都是同分布的,所以
和
是相同的)所以只需要计算一下分子就可以了。
注意到
所以这就完成了证明。注意我们用到了一个期望与积分的交换顺序。
有了这个结论之后,我们可以观察的就是生存和濒死时间的一些性质。
Proposition 6: 生存和濒死时间的极限密度为
,与离散情况一致。
我们看看怎么说明这个结论。已有的一个式子是
。所以如果我们令
,所得到的其实就是单纯的,仅仅与生存时间有关的式子。同样的,如果令
,就是一个仅仅与濒死时间有关的式子。我们先讨论生存时间的极限情况,因为濒死时间是完全类似的。
在
的时候,所得到的结果就是
根据这个式子,我们不难得到
但是另一方面,我们又有
左边非常像是对
的时间范围内的
的观察值取平均,并且观察事件
发生了几次。右边就是事件
的发生概率,也就是
的分布函数。直观上来看,这个就是“频率趋向于概率”的意思。有了这个式子,就很好办了,因为极限是唯一的,所以有
那么要求极限情况
,其实就是求生存时间这个随机变量的密度函数,那么求导就可以了。这样的话,就可以直接得到我们这里的结论,这个部分交给读者去完成。
关于濒死时间其实读者可以类似去推导,这里因为
的对称性,所以推导过程不会有任何变化,结论也一致。
Proposition 7:
这也是一个纯的微积分计算题,我们简单看一下。
注意到
这就完成了证明。过程中我们也是通过一个交换顺序,将期望符号“提出来”做的证明。
Proposition 8: 固定
,设
的概率密度函数为
,那么
的联合密度函数为
,其中
。
事实上,有了Proposition 5之后,我们还是有办法计算出这两个随机变量的联合密度函数的。这里简单说一下,一开始仿照Proposition 6,可以对
中的一个求一次偏导。然后再对剩下一个求,就能得到这个结果。细节留给读者。
那么我们举一个例子,来看看我们可以怎么样应用这个结论。
Problem 5: 考虑指数分布的情形,也即
,推导
的联合密度函数,并且证明它们俩相互独立。
事实上我们在这里直接利用公式就可以了。设
,那么注意到
,我们就可以得到
这个结果是因为
,所以我们就证明了结论成立。
这个结论说明了,在之前我们学过的泊松过程中,生存和濒死时间相互是无关的,但是这个结论并不适用于所有情况。比方说如果我们设
那么读者可以自己推导出联合密度函数
这一个区域中
相互之间就是有关的,所以不可能得到独立性。
所以可以看出,不同的相邻两个到达之间的时间的分布,就会导出不同的生存与濒死时间的分布。这也算是一种很好的推广,因为更新过程最重要的一个特性,就是
的分布是任意给定的。
作为一个生存和濒死时间的绝佳应用,我们介绍一下究竟什么是观察悖论(Inspection Paradox)。
观察悖论的一个背景就是
地铁平均5分钟来一班,但是如果给每一个人说自己等地铁的时间做一个调查,会发现汇报的等待时间远不止5分钟。
简单来说,就是,站在某一个时间点
看相邻到达时间的极限,和站在“上帝视角”来看相邻到达时间的极限,是不一致的。比方说在这里,“每一个人的调查结果”就相当于每一个人“在某一个时间点”感受到的等待时间,而本身的地铁等待时间,就是“上帝视角”下,实际的相邻两次地铁到达中间经过的时间。
我们来看看,如何用生存与濒死时间来刻画这个问题。
首先,我们假设有一个人在时间
等待地铁,那么平均它的等待时间,应该是
这里的
其实就是站在某一个时间来看的平均等待时间,
就是某个点的特定的等待时间。
那么我们来看一下,所谓的“上帝视角”是什么结果。如果是上帝视角,其实就是
的平均值,
就是真正的,两班地铁之间的等待时间,那么有
那么注意到
,所以可以发现,不仅仅这两个极限值不一致,而且如果对个人进行等待时间的汇报,几乎一定会导致多报。
我们说这是悖论,是因为在严谨的数学推导下,竟然会导致个人的感受和真实情况不一样。那么有没有比较好的解释呢?这里有一个还算不错的推导。我们注意到
因此可以发现,
的期望值,和真正“上帝视角”相比,受到了每一段等待时间的权重影响(
)。简单来说,
越大,那么这个对应的
的权重越大,也就有更大的概率被人所记住。因此有的时候我们会说“人更容易记住不好的事情,比如说地铁延误了”,这句话算是在观察悖论里,得到了数学界和统计界的一致认同。
好的,那么关于生存与濒死时间的介绍,就先到这里。
本节主要介绍了更新奖赏过程,并且介绍了它的诸多应用,包括交替更新过程,生存与濒死时间等,其中以生存分析中的生存与濒死时间作为主体,并介绍了有趣的观察悖论。下一节我们会开始介绍其他的具体的排队模型,大家可以更加深刻地去看待更新过程在不同领域的应用。