随机过程（7）——更新奖赏过程：交替更新过程，生存与濒死时间，观察悖论

学弱猹

发布于 2021-08-10 11:32:36

9910

发布于 2021-08-10 11:32:36

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记：随机过程（6）——泊松过程三大变换，更新过程引入

————————————————————————————————————

大家好！

本节我们开始介绍更新过程中的更新奖赏过程，这是一个很有趣的更新过程的应用，也会占据很大的篇幅。

那么我们开始吧。

更新奖赏过程

更新奖赏过程（Renewal Reward Process）是复合泊松过程的一个推广。简单来说，我们希望研究的是

R(t) = \sum_{i = 1}^{N(t)} r_i

并且这里的

(r_i, t_i)

相互独立（但是要注意，没有要求

r_i

和

t_i

之间的独立性），且

r_i

都服从某一个分布

。那么很明显，这就相当于每一次到达，都会得到一个“奖赏”

r_i

，然后我们希望观察，这个与奖赏有关的随机变量到底会有什么样的统计性质。

Proposition 1:

\frac {R(t)}t \to \frac{E(r_i)}{E(t_i)}

以概率1成立。

这个证明不是特别的麻烦，我们简单写一下。就是

\frac{R(t)}t = \frac 1t\sum_{i = 1}^{N(t)}r_i = \frac {N(t)}t \frac 1 {N(t)}\sum_{i = 1}^{N(t)}r_i \to \frac 1{E(t_1)}E(r_i)

这里的极限，一个就是我们上一节推导过的，利用夹逼定理得到的性质。另一个就是简单的同分布情况下的强大数定律。

那么我们看一个具体的例子吧。

Problem 1: 考虑一个修车的问题。假如说车的寿命服从一个密度函数

，且如果老车损坏了，就需要修，修车需要

的费用。寿命到达了

年，就需要更换，换车需要

的费用。问长期来看，单位时间的花费期望为？

这一个题要解决的第一个难关就是建模（这也是更新过程的常态），因为如果不能理清里面的各种要素，其实还是一个挺容易让人慌了手脚的问题。

首先第一件事，既然是一个过程，那么自然需要找到“到达的奖赏”。这里可以抽象出两个事件，一个是“修车”，一个是“换车”。所以如果我们假设每一次出现这样的事情经过的时间是

，那么有

t = s_i \land T

这里的

s_i

就是车的自然寿命，服从密度函数

的那个值。因为当

s_i > T

的时候，车就需要被更换了。

根据Proposition 1，其实我们只需要算出

\frac{E(r_i)}{E(t_i)}

。因为

\frac{R(t)}t

在

t \to \infty

的时候，就是单位时间的平均花费，这里的

R(t)

就是花费的总和。

我们先考虑

E(t_i)

，那么注意到

E(t_i) = E(s_i \land T) = \int_0^\infty (s_i \land T)f(s) ds = \int_0^T sh(s) ds + T \int_T^\infty h(s)ds

并且有

E(r_i) = A P(s < T) + B P(s \ge T) = A \int_0^T h(s)ds + B \int_T^\infty h(s)ds

所以最终的答案拼在一起就可以了。这里因为没有其他额外的信息（比方说

是什么），所以我们也只能写到这里。

下面这个性质很类似上一节的Theorem 5。不过还是一样，我们也不作证明。

Proposition 2: Reward Function

\lim_{t \to \infty} \frac{E(R(t))}{t} = \frac{E(r_i)}{E(t_i)}

也是长得很像大数定律的一个定理。

更加具体的应用：交替更新过程

交替更新过程（Alternating Renewal Process）也是一种具体的更新过程。简单来说，在这个模型中，两个相邻点之间经过的时间服从一个“交替的”分布。可以用图简单表示如下。

也就是说，交替的时间由一串独立同分布的随机变量

s_1, s_2, \cdots

和

u_1, u_2, \cdots

来决定。那么通过更新奖赏过程的性质，我们可以得到下面这样的结论（为了更好描述这个结论，我们设

s_i

决定的时间区间表示“处于状态1”，而

u_i

决定的时间区间表示“处于状态2”）。

Proposition 3: 设

s_i

服从一个分布为

，并且均值为

\mu_F

。

u_i

服从一个分布为

，并且均值为

\mu_G

，那么证明，长期来看，处于状态1的时间占比为

\frac{\mu_F}{\mu_F + \mu_G}

这个问题其实如果可以建模成更新奖赏过程的形式，就可以方便代入公式了，因为“时间占比”本质上也就是

\frac{E(r_i)}{E_(t_i)}

。但这个做法也不难想，可以考虑如下的策略

将相邻的两个时间段做两两分组，并且如果处于状态1，就在状态1到达的时候记录一个奖赏

r_i

，表示处于状态1的时间

s_i

。否则就认为奖赏为0。

大致可以画出如下的图。

这样的话，

E(r_i) = E(s_i) = \mu_F

，

E(t_i) = E(s_i + u_i) = \mu_F + \mu_G

，这就足够得到结论了。

我们再举两个例子。

Problem 2: 考虑一个换灯泡的问题。假如说灯泡寿命服从分布

，均值为

\mu_F

。一个修理工会不定期来检查灯泡，检查灯泡的时间服从一个速率为

\lambda

的泊松过程。如果发现灯泡坏了，就会立即更换。问（1）灯泡更换的速率。（2）长期来看，灯泡正常工作的时间占比。（3）长期来看，修理工检查灯泡的时候不用更换灯泡的次数占比。

这个问题初看其实是一个很复杂的问题，因为修理工和灯泡寿命这两个过程是同时在发生的，似乎很难把它统一成一个过程下。但我们其实可以利用“无记忆性”做一个好的刻画。具体可以见下图。

这个图中，红色的点表示灯泡损坏，黑色+蓝色的点都是修理工到达的时刻，但区别在于蓝色的点表示修理工到达之后修好了灯泡。那么我们假设灯泡“正常运行”的时间是状态1，然后注意，在灯泡损坏之后，修理工到达的时间间隔依然服从一个指数分布

\exp(\lambda)

（无记忆性用到了这里），这个损坏的时间相当于状态2。而修好灯泡之后，灯泡又回回到“正常运行”的时间，所以 “交替”就体现出来了。

现在再来看题目。第一题事实上就是把这两个状态“并在一起”看成一条随机过程（这个想法我们上一节的“叠加”中有用过），也就是说

\frac{N(t)} t \to \frac 1 {E(t_i)} = \frac {1}{\mu_F + \frac1 \lambda}

第二个题就是非常简单的交替更新过程，按照我们上面的建模，就很容易得到答案为

\frac {\mu_F}{\mu_F + \frac 1 \lambda}

。第三个题的话，这里就需要考虑两个因素了，一个是“修理工来访了多少次”，这里我们设为

V(t)

。另外一个是“修理工换了多少次灯泡”，这里我们设为

N(t)

，也就是上面我们设的那个

N(t)

。这样的话，我们计算的就是

\frac{V(t) - N(t)}{V(t)}

那么注意到

\frac{V(t)} t \to \lambda

（想想为什么？），

\frac{N(t)}t \to \frac 1 {\mu_F + \frac1 \lambda}

，对式子上下都除以一个

，就可以得到答案为

\frac{\mu_F}{\mu_F + \frac1 \lambda}

。

这个题的思考还是有挺多关键点的，当然最关键的地方还是如何建模和分析问题，这可比复合泊松过程的题目要难很多了……

Problem 3: 考虑一个机场接站的问题。假设大兴机场的国际航班出站旅客分布服从一个速率为10的泊松过程（每小时），并且有一个面包车。面包车每接满7个人就会立刻出发，送这批旅客前往高级酒店隔离。36min之后，这辆面包车就会回来。如果到达的旅客没有看到面包车，就会自行前往邻近的酒店隔离，问长时间来看，多少比例的游客最终会去高级酒店？

这是一道非常符合时事的问题，但是建模难度比上面要低很多了。

注意在这里，

s_i

和

u_i

一个可以表示“面包车”接的人，一个可以表示“自己走”的人。而它们的期望都很好计算，

s_i = 7

，而

u_i = 6

（因为36min内的期望根据泊松过程，很容易计算出来），所以直接根据交替更新过程的公式得到答案为

\frac 7 {13}

。

生存分析：生存与濒死时间

生存与濒死时间（Age and Residual Life）是在更新过程中经常会被拿来研究的概念。大致可以描述为研究两个状态到达之间的一个时间关系。具体的定义是

A(t) = A_t = t - T_{N(t)}

Z(t) = Z_t = T_{N(t) + 1} - t

这个定义抽象的话，看一下图就懂了。

（这里有一个菱形一样的符号，用它表示“未到达，仅仅是一个标记”，下同）

所以说，如果描述的是一个电子元件的寿命，并且认为一次”到达“就是”零件损坏“，那么很明显，在中间的某一个时间点

，

A(t)

就是它“已经工作（存活）的时间“，

Z(t)

就是“它还能工作（存活）多久”的意思。

说“大致描述”的原因是，在状态到达的时刻，对应的

A(t), Z(t)

都是0，也就是说到达和“相邻到达之间”这两段一般是要分开来分析的。

离散情况

离散情况的意思是，只考虑到达的时间是离散正整数的情况，这是因为后面研究需要依赖到之前提到的马尔科夫链。

具体的一个示例也可以看下图。

在离散情况下，一个比较容易观察到的事实是

\lim_{n \to \infty}\frac 1n \sum_{m = 1}^n I(A_m = i) = \lim_{n \to \infty}\frac 1n \sum_{m = 1}^n I(Z_m = i)

这可以通过把泊松过程分段，然后每一段分完之后讨论得到。如果你仔细看上一张图的一个示例的话，这个结论就不难得到。也是因为这么一个联系，所以我们研究的时候，只需要关心这两个量中的一个就可以了。

我们以

Z_n

为例，因为离散情况，所以其实

\{Z_n\}

的变化可以用马尔科夫链来描述，并且有

p(0, j) = f_{j + 1}, j \ge 0

p(j, j - 1) = 1, i \ge 1

这里的

f_{j + 1} = P(t_1 = j + 1)

表示距离下一次到达时间为

j + 1

的概率（强调一遍，因为是离散过程，所以这里的时间就是步数的意思）。

这里相当于把每一个点对应的

Z_n

统计起来，然后用马尔科夫链去描述它。可以使用马尔科夫链进行描述的原因，自然是离散更新过程所带来的马尔科夫性。

为什么是这个转移概率呢？因为一步一步的转移有两种情况，一个是从“到达时间”走到下一步；一个是正常的，从中间的某一步走到下一步。如果从“到达时间”走到下一步，相当于

Z_n

会从0走到一个正值，这个值取决于这一次，相邻两步的到达时间是多少。如果是另外一种情况，那么因为

Z_n

下降1是一个必然事件，所以概率为1。如果觉得这一段抽象，对照上面那张图看，就比较明晰了。

当然，这一条马尔科夫链也是不可约和常返的。不可约的原因是，从0可以到任何一个数，从任何一个数也一定会返回到0。常返的原因也很简单，在不可约的假设下，找到一个点是常返的，所有的点就都常返了。以0为例，从0出发到任何一个点之后，一定还会返回到0。

有了马尔科夫链之后，自然就是各种平稳分布什么的推导了，这个可以汇总为下面这一个性质。

Proposition 4: 对于马尔科夫链

\{Z_n\}

来说，如果

E(t_i) < \infty

，并且是非周期的，那么有

\lim_{n \to \infty} P(Z_n = i) = \frac{P(t_1 > i)}{E(t_i)}

。

一下看这个结论当然不知道是怎么来的。但是如果联系第3节（随机过程（3）——无限状态的平稳测度，返回时间，访问频率：几个定理的证明）的定理内容，你就明白我们本质上就是要求它的平稳分布，同时要有诸如非周期的条件，才能够满足那个定理的结论。

注意本质上这还是一个无限状态的马尔科夫链，所以平稳分布的存在性是一定要考虑的。在第5节（随机过程（5）——无限状态马尔科夫链的进一步探讨，泊松分布引入，复合泊松分布）我们说，这个取决于我们构造的平稳测度是否可以被标准化。

从头开始吧。我们可以按照第3节构造平稳测度的方案，先计算出一个值为

\mu(i) = E_0 (\sum_{m = 0}^{T_0 - 1} I(Z_m = i))

如果仔细观察

Z_m

的数值，那么你会发现，

Z_m = i

这一个事件，在

[0, T_0 - 1]

这个区间中，要不不发生，要不只发生一次（想想为什么？）。而如果不发生，就是0，发生的话，其实这个式子就等价于

P_0(Z_1 \ge i)

，因为必须第一步到达

及以后的位置，才有可能在每一步，往后退一步的时候，经过

这个值（描述可能比较抽象，一定要对着图去看）。

那么注意到

P_0(Z_1 \ge i) = \sum_{k = i}^\infty f_{k + 1} = P(t_1 >i)

所以分子我们就算出来了。而分母的话，其实把这个式子求和，就可以得到答案是

E(t_i)

（参考第1节（随机过程（1）——引入，有限状态马尔科夫链，状态转移，常返与瞬时状态）的Lemma 1）。

那么

E(t_i)

是一个有限的值（条件），那么实际上就可以知道，

\pi(i) = \frac{P(t_1 > i)}{E(t_i)}

是合理的，存在的。因此这个就是平稳分布，也就是说我们完成了证明。

我们来看一个实际的例子，加深一点印象。

Problem 4: 考虑一个大富翁的问题。每一次掷骰子决定走的步数。假设大富翁一共有40个格子，构成一个正方形。问“越过的步数”的期望是多少，这里“越过的步数”定义为每一次越过起点中，越过的步数。比方说从第38步走到43步，算“越过3步”。

这个问题其实就可以建模成生存与濒死时间的结构。如果我们站在

40n

这个位置来看，那么这个点对应的濒死时间（步数）的期望，就是我们这里所需要的答案。而根据Proposition 4，我们可以得到这个答案就是

\frac{P(t_1 > i)}{E(t_1)}

（想想为什么？），也就是说其实和站在哪里没什么关系，和大富翁一圈有多少个格子也没什么关系，完全取决于“骰子点数”这么一个随机变量。

连续情况

连续情况下就复杂的多，对于它的研究需要一些分析上的工具。

首先我们可以研究一下，在一般的情况下，

(A_s, Z_s)

的密度函数是什么样的。

Proposition 5:

\frac 1t \int_0^t I(A_s >x, Z_s > y) ds \to \frac 1 {E(t_1)} \int_{x + y}^\infty P(t_1 > z)dz, t \to \infty

这个结果还是很有趣的，虽然并没有直接给出密度函数本身的性质，但是研究它的一个平均，很多时候也算够用了。

注意在这里，我们提到我们用到的是“一个平均”。那么有一个思路就是用上面的更新奖赏过程。因为更新奖赏过程本质上也是在研究

\frac{R(t)}t

的极限情况，所以我们在这里只要定义好

R(t)

，就可以利用之前的结论，也就是Proposition 1。

我们先画出下面的图。这个图简单的概括了，我们每一次的“奖赏”究竟是怎么定义的。

总体来说，我们可以忽略

[N(t), t]

的那一段，因为在

t \to \infty

的时候，这一段的收益可以忽略不计（这个技巧我们也是不止一次使用了）。然后每一个到达的点，对应的区间的奖赏，就是

(t_i - x - y)_+

，因为我们会去掉一开始的

（对应条件

A_s > x

）和末尾的一段

（对应条件

Z_s > y

）那么长的距离。所以根据Proposition 1，我们可以知道，最终要计算的其实就是

\frac{E(r_i)}{E(t_i)} = \frac{E(r_1)}{E(t_1)} = \frac{E(t_1 - x - y)_+}{E(t_i)}

（这里注意一下，因为在更新奖赏过程中，

r_i, t_i

都是同分布的，所以

E(r_i)

和

E(r_1)

是相同的）所以只需要计算一下分子就可以了。

注意到

E(t_1 - x - y)_+ = E(\int_{x + y}^{t_1} I(t_1 >x + y)dz) = E(\int_{x + y}^\infty I(t_1 > z)dz)

=\int_{x + y}^\infty E(I(t_1 >z))dz = \int_{x + y}^\infty P(t_1 > z)dz

所以这就完成了证明。注意我们用到了一个期望与积分的交换顺序。

有了这个结论之后，我们可以观察的就是生存和濒死时间的一些性质。

Proposition 6: 生存和濒死时间的极限密度为

g(z) = \frac{P(t_1 > z)}{E(t_1)}

，与离散情况一致。

我们看看怎么说明这个结论。已有的一个式子是

\frac 1t \int_0^t I(A_s > x, Z_s > y)ds

。所以如果我们令

y = 0

，所得到的其实就是单纯的，仅仅与生存时间有关的式子。同样的，如果令

x = 0

，就是一个仅仅与濒死时间有关的式子。我们先讨论生存时间的极限情况，因为濒死时间是完全类似的。

在

x = 0

的时候，所得到的结果就是

\frac 1 t\int_0^t I(A_s >x)ds = 1 - \frac 1t \int_0^t I(A_s \le x) ds

根据这个式子，我们不难得到

\frac 1t \int_0^t I(A_s \le x)ds \to 1 - \frac 1{E(t_1)}\int_x^\infty P(t_1 >z)dz

但是另一方面，我们又有

\frac 1t \int_0^t I(A_s \le x)ds \to F(x)

左边非常像是对

[0 ,t]

的时间范围内的

A_s

的观察值取平均，并且观察事件

A_s \le x

发生了几次。右边就是事件

A_s \le x

的发生概率，也就是

A_s

的分布函数。直观上来看，这个就是“频率趋向于概率”的意思。有了这个式子，就很好办了，因为极限是唯一的，所以有

F(x) = 1 -\frac 1{E(t_1)}\int_x^\infty P(t_1 >z)dz

那么要求极限情况

g(z)

，其实就是求生存时间这个随机变量的密度函数，那么求导就可以了。这样的话，就可以直接得到我们这里的结论，这个部分交给读者去完成。

关于濒死时间其实读者可以类似去推导，这里因为

x, y

的对称性，所以推导过程不会有任何变化，结论也一致。

Proposition 7:

\int_0^\infty z g(z) dz = \frac{E(t_1^2)}{2E(t_1)}

这也是一个纯的微积分计算题，我们简单看一下。

注意到

\int_0^\infty z g(z) dz = \int_0^\infty z \frac{P(t_1 >z)}{E(t_1)}dz = \frac{1}{E(t_1)}\int_0^\infty zE(I(t_1 > z))dz

=\frac 1{E(t_1)}E(\int_0^\infty zI(t_1 >z)dz) = \frac 1 {E(t_1)}E(\int_0^{t_1} z dz) = \frac {E(t_1^2)}{2E(t_1)}

这就完成了证明。过程中我们也是通过一个交换顺序，将期望符号“提出来”做的证明。

Proposition 8: 固定

，设

t_1

的概率密度函数为

f(t)

，那么

(A_t, Z_t)

的联合密度函数为

\frac{f(x + y)}{E(t_1)}

，其中

A_t = x, Z_t =y

。

事实上，有了Proposition 5之后，我们还是有办法计算出这两个随机变量的联合密度函数的。这里简单说一下，一开始仿照Proposition 6，可以对

x, y

中的一个求一次偏导。然后再对剩下一个求，就能得到这个结果。细节留给读者。

那么我们举一个例子，来看看我们可以怎么样应用这个结论。

Problem 5: 考虑指数分布的情形，也即

t_i \sim \exp(\lambda)

，推导

(A_t, Z_t)

的联合密度函数，并且证明它们俩相互独立。

事实上我们在这里直接利用公式就可以了。设

A_t = x, Z_t = y

，那么注意到

f(t) = \lambda e^{-\lambda t}

，我们就可以得到

p(x, y) = \frac{\lambda e^{-\lambda (x + y)}}{\frac 1\lambda} = \lambda e^{-\lambda x}\cdot \lambda e^{-\lambda y} = p_A(x)p_Z(y)

这个结果是因为

P(t_1 > x) = e^{-\lambda x}

，所以我们就证明了结论成立。

这个结论说明了，在之前我们学过的泊松过程中，生存和濒死时间相互是无关的，但是这个结论并不适用于所有情况。比方说如果我们设

t_i \sim U(0, b)

那么读者可以自己推导出联合密度函数

p(x, y) = \frac 2 {b^2} I(x > 0, y > 0, x + y < b)

这一个区域中

x, y

相互之间就是有关的，所以不可能得到独立性。

所以可以看出，不同的相邻两个到达之间的时间的分布，就会导出不同的生存与濒死时间的分布。这也算是一种很好的推广，因为更新过程最重要的一个特性，就是

t_i

的分布是任意给定的。

观察悖论

作为一个生存和濒死时间的绝佳应用，我们介绍一下究竟什么是观察悖论（Inspection Paradox）。

观察悖论的一个背景就是

地铁平均5分钟来一班，但是如果给每一个人说自己等地铁的时间做一个调查，会发现汇报的等待时间远不止5分钟。

简单来说，就是，站在某一个时间点

看相邻到达时间的极限，和站在“上帝视角”来看相邻到达时间的极限，是不一致的。比方说在这里，“每一个人的调查结果”就相当于每一个人“在某一个时间点”感受到的等待时间，而本身的地铁等待时间，就是“上帝视角”下，实际的相邻两次地铁到达中间经过的时间。

我们来看看，如何用生存与濒死时间来刻画这个问题。

首先，我们假设有一个人在时间

等待地铁，那么平均它的等待时间，应该是

E(L(t)) = E(A(t)) + E(Z(t)) \to \frac{E(t_1^2)}{E(t_1)}

这里的

L(t) = A(t) + Z(t)

其实就是站在某一个时间来看的平均等待时间，

A(t) + Z(t)

就是某个点的特定的等待时间。

那么我们来看一下，所谓的“上帝视角”是什么结果。如果是上帝视角，其实就是

t_i

的平均值，

t_i

就是真正的，两班地铁之间的等待时间，那么有

\frac{t_1 + \cdots + t_n} n \to E(t_1)

那么注意到

\frac{E(t_1^2)}{E(t_1)} \ge E(t_1)

，所以可以发现，不仅仅这两个极限值不一致，而且如果对个人进行等待时间的汇报，几乎一定会导致多报。

我们说这是悖论，是因为在严谨的数学推导下，竟然会导致个人的感受和真实情况不一样。那么有没有比较好的解释呢？这里有一个还算不错的推导。我们注意到

\frac{E(t_i^2)}{E(t_i)} \simeq \frac{\sum_{i = 1}^n t_i^2}{\sum_{i = 1}^n t_i} = \sum_{i = 1}^n t_i \frac{t_i}{\sum_{j = 1}^n t_j}

因此可以发现，

L(t)

的期望值，和真正“上帝视角”相比，受到了每一段等待时间的权重影响(

\frac{t_i}{\sum_{j = 1}^n t_j}

)。简单来说，

t_i

越大，那么这个对应的

t_i

的权重越大，也就有更大的概率被人所记住。因此有的时候我们会说“人更容易记住不好的事情，比如说地铁延误了”，这句话算是在观察悖论里，得到了数学界和统计界的一致认同。

好的，那么关于生存与濒死时间的介绍，就先到这里。

小结

本节主要介绍了更新奖赏过程，并且介绍了它的诸多应用，包括交替更新过程，生存与濒死时间等，其中以生存分析中的生存与濒死时间作为主体，并介绍了有趣的观察悖论。下一节我们会开始介绍其他的具体的排队模型，大家可以更加深刻地去看待更新过程在不同领域的应用。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-01，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度