首页 Stochastic Processes

Sheldon M. Ross "Stochastic Processes" 2nd Edition
随机过程（第二版）习题

# 3.4

证明更新方程

m(t)=F(t)+∫0tm(t−x)dF(x)m(t)=F(t)+\displaystyle\int_0^tm(t-x)\,{\rm d}F(x)

解：

取条件于首次更新的等待时间 S1S_1（也即 X1X_1），并假定积分与求和可交换。则

m(t)=∑n=1∞Fn(t)=F(t)+∑n=2∞Fn(t)=F(t)+∑n=2∞P(Sn⩽t)=F(t)+∑n=2∞∫0tP(Sn⩽t∣X1=x)dF(x)=F(t)+∑n=2∞∫0tP(X1+X2+⋯+Xn⩽t∣X1=x)dF(x)=F(t)+∑n=2∞∫0tP(X2+⋯+Xn⩽t−x)dF(x)=F(t)+∑n=2∞∫0tFn−1(t−x)dF(x)=F(t)+∫0t∑n=1∞Fn(t−x)dF(x)=F(t)+∫0tm(t−x)dF(x)\begin{aligned} m(t)&=\sum\limits_{n=1}^{\infty}F_n(t)=F(t)+\sum\limits_{n=2}^{\infty}F_n(t)\\ &=F(t)+\sum\limits_{n=2}^{\infty}P(S_n\leqslant t)\\ &=F(t)+\sum\limits_{n=2}^{\infty}\displaystyle\int_0^tP(S_n\leqslant t\mid X_1=x)\,{\rm d}F(x)\\ &=F(t)+\sum\limits_{n=2}^{\infty}\displaystyle\int_0^tP(X_1+X_2+\cdots+X_n\leqslant t\mid X_1=x)\,{\rm d}F(x)\\ &=F(t)+\sum\limits_{n=2}^{\infty}\displaystyle\int_0^tP(X_2+\cdots+X_n\leqslant t-x)\,{\rm d}F(x)\\ &=F(t)+\sum\limits_{n=2}^{\infty}\displaystyle\int_0^tF_{n-1}(t-x)\,{\rm d}F(x)\\ &=F(t)+\displaystyle\int_0^t\sum\limits_{n=1}^{\infty}F_{n}(t-x)\,{\rm d}F(x)\\ &=F(t)+\displaystyle\int_0^tm(t-x)\,{\rm d}F(x) \end{aligned}

# 3.7

若到达间隔分布 FF 为 (0,1)(0,1) 的均匀分布，证明

m(t)=et−1,0⩽t⩽1m(t)={\rm e}^t-1,\ 0\leqslant t\leqslant1

并论证：为了使得到达间隔分布之和大于 11，需要的间隔数的期望为 e{\rm e}{}

解：

将 F(x)=x,0⩽t⩽1F(x)=x,\,0\leqslant t\leqslant1 代入习题 3.4 所证结论有

m(t)=t+∫0tm(t−x)dx=t+∫0tm(x)dx\begin{aligned} m(t)&=t+\displaystyle\int_0^tm(t-x){\rm d}x\\ &=t+\displaystyle\int_0^tm(x){\rm d}x\\ \end{aligned}

两边对 tt 求导得

m′(t)=1+m(t)m'(t)=1+m(t)

解微分方程即可。令 g(t)=1+m(t)g(t)=1+m(t)，则有 g′(t)=g(t)g'(t)=g(t) 即 dgg=dt\dfrac{ {\rm d}g}{g}={\rm d}t. 于是

ln⁡g(t)=t+Cg(t)=Cet\begin{aligned} \ln g(t)&=t+C\\ g(t)&=C {\rm e}^t \end{aligned}

代入 g(0)=1+m(0)=1g(0)=1+m(0)=1 得 C=1C=1，即 g(t)=etg(t)={\rm e}^t. 于是 m(t)=g(t)−1=et−1m(t)=g(t)-1={\rm e}^t-1

在 (0,1](0,1] 上发生的事件数为 N(1)N(1)，那么第 N(1)+1N(1)+1 个事件发生的时刻即 “第一个在 1 之后发生的事件”，或者说即 “使得间隔之和大于 1 所需的更新数目”. 于是题目所求即为

E[N(1)+1]=m(1)+1=eE[N(1)+1]=m(1)+1={\rm e}

# 3.10

设 X1,X2,⋯X_1,X_2,\cdots 独立同分布，E[Xi]<∞E[X_i]<{\infty}. 设 N1N_1 为它的停时，即在满足 “一个仅依赖于 X1∼XN1X_1\sim X_{N_1} 的条件” 之后停止实验。实验停止之后，再次定义一个停时 N2N_2，即在满足 “一个仅依赖于 XN1∼XN1+N2X_{N_1}\sim X_{N_1+N_2} 的条件” 之后停止实验。重复上述操作，得到序列 N1,N2,⋯N_1,N_2,\cdots，称为对 {Xn}\left\{X_n\right\} 的停时序列.

  1. 令 S1=∑i=1N1XiS_1=\sum\limits_{i=1}^{N_1}X_i，S2=∑i=N1+1N1+N2XiS_2=\sum\limits_{i=N_1+1}^{N_1+N_2}X_i，S2=∑i=N1+N2+1N1+N2+N3XiS_2=\sum\limits_{i=N_1+N_2+1}^{N_1+N_2+N_3}X_i，⋯\cdots. 使用强大数定律计算

lim⁡m→∞S1+⋯+SmN1+⋯+Nm\lim\limits_{m\to {\infty} }\dfrac{S_1+\cdots+S_m}{N_1+\cdots+N_m}

  1. 把 S1+⋯+SmN1+⋯+Nm\dfrac{S_1+\cdots+S_m}{N_1+\cdots+N_m} 上式改写为 S1+⋯+SmmmN1+⋯+Nm\dfrac{S_1+\cdots+S_m}{m}\dfrac{m}{N_1+\cdots+N_m}，再次计算其极限.
  2. 由上面两题证明 Wald 方程.

解：

(1) 事实上 ∑i=1mSi=∑n=1∑1mNiXn=S∑1mNi\sum\limits_{i=1}^m S_i=\sum\limits_{n=1}^{\sum_1^m N_i}X_n=S_{\sum_1^m N_i}. 令 k=∑1mNik=\sum_1^m N_i，则当 m→∞m\to\infty 时，k→∞k\to\infty. 于是由强大数定律

lim⁡m→∞∑1mSi∑1mNi=lim⁡k→∞Skk=μX=E[X]\lim\limits_{m\to\infty}\dfrac{\sum_1^m S_i}{\sum_1^m N_i}=\lim\limits_{k\to\infty}\dfrac{S_k}{k}=\mu_X=E[X]

(2) ∑1mSi∑1mNi=∑1mSi/m∑1mNi/m\dfrac{\sum_1^m S_i}{\sum_1^m N_i}=\dfrac{\sum_1^m S_i/m}{\sum_1^m N_i/m}. 由 SiS_i 的定义可知，SiS_i 之间独立同分布。故当 m→∞m\to\infty 时，由强大数定律，分子分母极限都存在

lim⁡m→∞∑1mSim=μS=E[S]lim⁡m→∞∑1mNim=μN=E[N]\begin{aligned} \lim\limits_{m\to\infty}\dfrac{\sum_1^m S_i}{m}&=\mu_S=E[S]\\ \lim\limits_{m\to\infty}\dfrac{\sum_1^m N_i}{m}&=\mu_N=E[N]\\ \end{aligned}

代入即得

lim⁡m→∞∑1mSi∑1mNi=lim⁡m→∞∑1mSi/mlim⁡m→∞∑1mNi/m=E[S]E[N]\lim\limits_{m\to\infty}\dfrac{\sum_1^m S_i}{\sum_1^m N_i}=\dfrac{\lim\limits_{m\to\infty}\sum_1^m S_i/m}{\lim\limits_{m\to\infty}\sum_1^m N_i/m}=\dfrac{E[S]}{E[N]}

(3) 于是 E[X]=E[S]E[N]E[X]=\dfrac{E[S]}{E[N]}，即 E[S]=E[X]E[N]E[S]=E[X]{E[N]}. 此即为 Wald 方程.

# 3.17

形如 g(t)=h(t)+∫0tg(t−x)dF(x)g(t)=h(t)+\displaystyle\int_0^tg(t-x)\,{\rm d}F(x) 的方程称为更新型方程（或使用卷积记号记为 g=h+g∗Fg=h+g*F）. 迭代之 / 使用 Laplace 变换，证明更新型方程具有解

g(t)=h(t)+∫0th(t−x)dm(x)g(t)=h(t)+\displaystyle\int_0^th(t-x)\,{\rm d}m(x)

若 h(x)h(x) 直接 Riemann 可积、且 FF 是均值有限的非格点分布，则可应用关键更新定理得

lim⁡t→∞g(t)=1μX∫0∞h(t)dt=∫0∞h(t)dt∫0∞F‾(t)dt\lim\limits_{t\to {\infty} }g(t)=\dfrac{1}{\mu_X}\int_0^{\infty}h(t){\rm d}t=\dfrac{\int_0^{\infty}h(t){\rm d}t}{\int_0^{\infty}\overline F(t){\rm d}t}

对 g(t)g(t) 的更新型方程得自取条件于过程按概率意义上重新开始的时刻，对下列函数建立更新型方程：

  1. 一个交替更新过程在时刻 tt 处于开状态的概率 P(t)P(t)
  2. 更新过程在时刻 tt 的期望年龄 g(t)=E[A(t)]g(t)=E[A(t)]

使用题示结论给出更新型方程的解，并运用关键更新定理得到上述两题中的极限值.

解：

对更新型方程作 Laplace 变换，由卷积定理得

L[g]=L[h]+L[g]L[F]L[g]=L[h]1−L[F]\begin{aligned} {\mathcal L}[g]&={\mathcal L}[h]+{\mathcal L}[g]{\mathcal L}[F]\\ {\mathcal L}[g]&=\dfrac{ {\mathcal L}[h]}{1-{\mathcal L}[F]} \end{aligned}

考虑更新函数的 Laplace 变换

m(t)=∑n=1∞Fn(t)L[m]=∑n=1∞(L[F])n=L[F]1−L[F]\begin{aligned} m(t)&=\sum\limits_{n=1}^{\infty}F_n(t)\\ {\mathcal L}[m]&=\sum\limits_{n=1}^{\infty}({\mathcal L}[F])^n\\ &=\dfrac{ {\mathcal L}[F]}{1-{\mathcal L}[F]}\\ \end{aligned}

于是 L[F]=L[m]1+L[m]{\mathcal L}[F]=\dfrac{ {\mathcal L}[m]}{1+{\mathcal L}[m]}. 代入 Laplace 变换后的式子得

L[g]=L[h]1−L[F]=L[h]1−L[m]1+L[m]=L[h](1+L[m])=L[h]+L[h]×L[m]\begin{aligned} {\mathcal L}[g]&=\dfrac{ {\mathcal L}[h]}{1-{\mathcal L}[F]}=\dfrac{ {\mathcal L}[h]}{1-\dfrac{ {\mathcal L}[m]}{1+{\mathcal L}[m]} }\\ &={\mathcal L}[h](1+{\mathcal L}[m])\\ &={\mathcal L}[h]+{\mathcal L}[h]\times{\mathcal L}[m] \end{aligned}

最后做 Laplace 逆变换得

g(t)=h(t)+[h∗m](t)=h(t)+∫0th(t−x)dm(x)g(t)=h(t)+[h*m](t)=h(t)+\displaystyle\int_0^th(t-x)\,{\rm d}m(x)

(1) 称 “从关到开” 为一次更新，开状态时间序列 {Zn}\left\{Z_n\right\} 独立同分布 HH、关状态时间序列 {Yn}\left\{Y_n\right\} 独立同分布 GG，Xi=Zi+YiX_i=Z_i+Y_i. 取条件于事件从概率意义上重新开始（即首次更新）的时刻

P(t)=∫0+∞P(t时刻为开∣X1=s)dF(s)\begin{aligned} P(t)&=\displaystyle\int_0^{+\infty}P(\,t时刻为开\mid X_1=s){\rm d}F(s)\\ \end{aligned}

对于 s⩽ts\leqslant t，那么条件概率相当于从 ss 时刻重新开始，∫0tP(t−s)dF(s)\displaystyle\int_0^tP(t-s){\rm d}F(s)；
对于 s>ts>t，“tt 时刻处于开状态” 等价于 “t<Z1t<Z_1”，而 ss 从 tt 积到正无穷也即所有可能的条件的总和.

于是更新型方程为

P(t)=∫0tP(t−s)dF(s)+∫t+∞P(t<Z1∣X1=s)dF(s)=P(Z1>t)+∫0tP(t−s)dF(s)=H‾(t)+∫0tP(t−s)dF(s)\begin{aligned} P(t)&=\displaystyle\int_0^tP(t-s){\rm d}F(s)+\displaystyle\int_t^{+\infty}P(t<Z_1\mid X_1=s){\rm d}F(s)\\ &=P(Z_1>t)+\displaystyle\int_0^tP(t-s){\rm d}F(s)\\ &=\overline H(t)+\displaystyle\int_0^tP(t-s){\rm d}F(s)\\ \end{aligned}

进而

lim⁡t→∞P(t)=∫0∞H‾(t)dtμX=E(Z)E(X)\lim\limits_{t\to {\infty} }P(t)=\dfrac{\int_0^{\infty}\overline H(t){\rm d}t}{\mu_X}=\dfrac{E(Z)}{E(X)}

(2) 取条件于事件从概率意义上重新开始（即首次更新）的时刻，拆积分区间，得更新型方程

g(t)=E[A(t)]=∫0∞E[A(t)∣X1=s]dF(s)=∫t+∞E(t∣X1=s)dF(s)+∫9tE[A(t−s)]dF(s)=∫t+∞tdF(s)+∫0tg(t−s)dF(s)=tF‾(t)+∫0tg(t−s)dF(s)\begin{aligned} g(t)=E[A(t)]&=\displaystyle\int_0^{\infty}E[A(t)\mid X_1=s]{\rm d}F(s)\\ &=\displaystyle\int_t^{+\infty}E(t\mid X_1=s){\rm d}F(s)+\displaystyle\int_9^tE[A(t-s)]{\rm d}F(s)\\ &=\displaystyle\int_t^{+\infty}t{\rm d}F(s)+\displaystyle\int_0^tg(t-s){\rm d}F(s)\\ &=t\overline F(t)+\displaystyle\int_0^tg(t-s){\rm d}F(s) \end{aligned}

进而

lim⁡t→∞g(t)=∫0∞tF‾(t)dtμX=∫0∞F‾(t)d(12t2)E[X]=12t2F‾(t)∣0∞−∫0∞12t2dF‾(t)E[X]=0+12∫0∞t2dF(t)E[X]=E[X2]2E[X]\begin{aligned} \lim\limits_{t\to {\infty} }g(t)&=\dfrac{\int_0^\infty t\overline F(t){\rm d}t}{\mu_X}\\ &=\dfrac{\int_0^\infty\overline F(t){\rm d}(\frac12t^2)}{E[X]}\\ &=\dfrac{\dfrac12t^2\overline F(t)\bigg|_0^\infty-\displaystyle\int_0^\infty\dfrac12t^2{\rm d}\overline F(t)}{E[X]}\\ &=\dfrac{0+\dfrac12\displaystyle\int_0^\infty t^2{\rm d} F(t)}{E[X]}\\ &=\dfrac{E[X^2]}{2E[X]} \end{aligned}

# 3.27

对更新报酬过程证明：

lim⁡t→∞E[RN(t)+1]=E[R1X1]E[X1]\lim\limits_{t\to\infty}E[R_{N(t)+1}]=\dfrac{E[R_1X_1]}{E[X_1]}

假定 XiX_i 的分布不是格点的，而有关的任何函数都是直接 Riemann 可积的，当循环的报酬定义为等于循环的长度时，上式导致

lim⁡t→∞E[XN(t)+1]=E[X2]E[X]\lim\limits_{t\to\infty}E[X_{N(t)+1}]=\dfrac{E[X^2]}{E[X]}

请说明：它总是大于 E[X]E[X]，除非 XX 以概率 1 地是常数.

解：

取条件于 SN(t)S_{N(t)} 的值，将报酬转化到第一个更新区间内。参考交替更新中处于开状态的概率的极限，需要对 SN(t)=0S_{N(t)}=0 单独讨论，注意到此时 N(t)=0N(t)=0.

E[RN(t)+1]=E[RN(t)+1∣SN(t)=0]F‾(t)dm(0)+∫0tE[RN(t)+1∣SN(t)=s]P(SN(t)=s)=E[R1∣X1>t]F‾(t)+∫0tE[R1∣X1>t−s]F‾(t−s)dm(s)\begin{aligned} E[R_{N(t)+1}]&=E[R_{N(t)+1}\mid S_{N(t)}=0]\,\overline F(t){\rm d}m(0)+\displaystyle\int_0^{t} E[R_{N(t)+1}\mid S_{N(t)}=s]P(S_{N(t)}=s)\\ &=E[R_1\mid X_1>t]\,\overline F(t)+\displaystyle\int_0^{t} E[R_1\mid X_1>t-s]\,\overline F(t-s){\rm d}m(s)\\ \end{aligned}

令 t→+∞t\to {+\infty}，前项中 F‾(∞)=0\overline F(\infty)=0，后项使用关键更新定理

lim⁡t→∞E[RN(t)+1]=1μX∫0+∞E[R1∣X1=τ]F‾(τ)dτ(τ换成x)=1E(X1)∫0+∞F‾(x)dx∫0+∞rP(R1=r∣X1=x)=1E(X1)∫0+∞∫0+∞xP(X1=x)rP(R1=r∣X1=x)=1E(X1)∫0+∞∫0+∞rxP(R1=r,X1=x)=E(R1X1)E(X1)\begin{aligned} \lim\limits_{t\to \infty}E[R_{N(t)+1}]&=\dfrac1{\mu_X}\displaystyle\int_0^{+\infty}E[R_1\mid X_1=\tau]\overline F(\tau){\rm d}\tau\quad(\tau 换成 x)\\ &=\dfrac{1}{E(X_1)}\displaystyle\int_0^{+\infty}\overline F(x){\rm d}x\displaystyle\int_0^{+\infty}rP(R_1=r\mid X_1=x)\\ &=\dfrac{1}{E(X_1)}\displaystyle\int_0^{+\infty}\displaystyle\int_0^{+\infty}xP(X_1=x)rP(R_1=r\mid X_1=x)\\ &=\dfrac{1}{E(X_1)}\displaystyle\int_0^{+\infty}\displaystyle\int_0^{+\infty}rxP(R_1=r,\,X_1=x)\\ &=\dfrac{E(R_1X_1)}{E(X_1)} \end{aligned}

而 D(X)=E(X2)−E2(X)⩾0D(X)=E(X^2)-E^2(X)\geqslant0，故E(X2)⩾E2(X)E(X^2)\geqslant E^2(X)，即

lim⁡t→∞E[XN(t)+1]=E[X2]E[X]⩾E2(X)E(X)=E(X)\lim\limits_{t\to\infty}E[X_{N(t)+1}]=\dfrac{E[X^2]}{E[X]}\geqslant\dfrac{E^2(X)}{E(X)}=E(X)

上式取等号当且仅当 D(X)=0D(X)=0，即 XX 为常数.

# 3.32

考虑一个按速率 λ\lambda 的 Poisson 过程到达的单服务线排队系统，其具有均值为 μG\mu_G 的服务时间分布 GG. 假定 λμG<1\lambda\mu_G<1.

  1. 求系统空闲的时间比例 P0P_0
  2. 计算忙期的平均长度
  3. 利用 (2) 和 Wald 方程计算在一个忙期中服务过的顾客数的期望

解：

(1) 在首个顾客到达时开始计时。每当顾客发现系统为空的时候，这个过程相当于在概率意义上重新开始。进一步定义 tt 时刻系统的状态数 jj 等于系统中的顾客数 Y(t)Y(t)，那么 {Y(t),t>0}\{Y(t),t>0\} 是一个再现过程。于是所求比例即为状态 0 的时间的长程比.
假设一个循环中服务的顾客数为 NiN_i，单个顾客的服务时间为 TjT_j，则

lim⁡t→∞处于状态0的总时间t=E[单循环中系统内系统顾客为0的时间]E[循环周期]=E[∑1NiXj−∑1NiTj]E[∑1NiXj]=E[N](E[X]−E[T])E[N]E[X](Wald)=μX−μGμX=1−μGμX\begin{aligned} \lim\limits_{t\to\infty}\dfrac{处于状态0的总时间}{t}&=\dfrac{E[单循环中系统内系统顾客为0的时间]}{E[循环周期]}\\ &=\dfrac{E\left[\sum\limits_1^{N_i}X_j-\sum\limits_1^{N_i}T_j\right]}{E\left[\sum\limits_1^{N_i}X_j\right]}\\ &=\dfrac{E[N](E[X]-E[T])}{E[N]E[X]}\quad(\text{Wald})\\ &=\dfrac{\mu_X-\mu_G}{\mu_X}\\ &=1-\dfrac{\mu_G}{\mu_X} \end{aligned}

也即 P0=1−μG1/λ=1−λμGP_0=1-\dfrac{\mu_G}{1/\lambda}=1-\lambda\mu_G

(2)

lim⁡t→∞P(t时刻在忙期内)=E[忙期时间]E[忙期时间]+E[空闲时间]=1−P0=λμG\lim\limits_{t\to \infty}P(t时刻在忙期内)=\dfrac{E[忙期时间]}{E[忙期时间]+E[空闲时间]}=1-P_0=\lambda\mu_G

空闲时间即为 “单循环中最后一位顾客离开、到下一个顾客到来” 的这段时间，其分布即到达间隔分布，即

E[空闲时间]=E[X]=1λE[空闲时间]=E[X]=\dfrac1\lambda

于是

E[忙期时间]E[忙期时间]+E[空闲时间]=λμGE[忙期]=λμGE[空闲时间]1−λμG=μG1−λμG\begin{aligned} \dfrac{E[忙期时间]}{E[忙期时间]+E[空闲时间]}&=\lambda\mu_G\\ E[忙期]=\dfrac{\lambda\mu_GE[空闲时间]}{1-\lambda\mu_G}&=\frac{\mu_G}{1-\lambda\mu_G} \end{aligned}

(3) 设一个忙期内共 NN 人接受了服务，则由 Wald

E[B]=E[∑1NTi]=E[N]E[Ti]E[N]=E[B]E[Ti]=11−λμG\begin{aligned} E[B]&=E\left[\sum\limits_1^NT_i\right]=E[N]E[T_i]\\ E[N]&=\dfrac{E[B]}{E[T_i]}=\dfrac{1}{1-\lambda\mu_G} \end{aligned}