§5 更新過程

C1 更新過程

1）更新過程：時間到達間隔$X(t)$獨立同分佈($F$)的計數過程$N(t)$

• 避免平凡情形，令$P\{X_n=0\}<1$，記$S_n=\sum\limits_{i=1}^nX_i$，則$N(t) = \max\{n|S_n\le t\}$
• 以概率1有$N(t)<\infin$

2）分佈：$P\{N(t) = n\} = P\{N(t)\ge n\}-P\{N(t)\ge n+1\}=P\{S_n\le t\}-P\{S_{n+1}\le t\}$，而$S_n$的分佈即$F$的$n$重折積$F_n$

3）更新函數：$m(t)=EN(t)=\sum\limits_{n=1}^\infin P\{N(t)\ge n\}=\sum\limits_{n=1}^\infin P\{S_n\le t\}=\sum\limits_{n=1}^\infin F_n(t)$

• 以概率1有$m(t)\lt \infin$

• $m(t) = \int^\infin_0 E[N(t)|X_1=x]f(x)\mathrm{d}x=F(t)+\int_0^tm(t-x)f(x)\mathrm{d}x$

  均勻到達：$F = U(0,1):m(t) = e^t -1,t\in[0,1]$

• 近似計算方法：$m_n = \frac{\sum\limits_{k=1}^{n-1}(1+m_{r-k})E[X^ke^{-\lambda X}](\lambda^k/k!)+Ee^{-\lambda X}}{1-Ee^{-\lambda X}},\lambda=\frac{n}{t},\lim\limits_{n\to\infin}m_n=m(t)$

C2 極限定理

1）定理：$P\{\lim\limits_{t\to \infin} \frac{N(t)}{t} =\frac{1}{\mu} \} = 1$。即期望每$\mu$個時間單位發生一次更新

假設n個玩家單局獲勝率爲$P_i$，當某玩家連勝時結束比賽，求期望結束時間和連勝率

• 對於單個玩家，連勝期望次數爲$EN_i = \frac{P_i^k(1-P_i)}{1-P_i^k}$，則其獲勝速率爲$v_i =\frac1{EN_i}$，獲勝率$\frac{v_i}{\sum\limits_j v_j}$
• 期望遊戲時間爲$\frac{1}{\sum\limits_i v_i}$

2）基本更新定理：$P\{\lim\limits_{t\to \infin} \frac{m(t)}{t} =\frac{1}{\mu} \} = 1$

• 隨機變數以概率1收斂到E，其期望也不一定是E

• 證明：

  • 停時：對於隨機變數序列$X_i$，若隨機變數$N$滿足$P\{N=n\}$獨立於$X_i,i\gt n$有關，則$N$稱停時

    如：$N(t)+1 = n$只依賴於$X_1,\dots,X_n$

  • 瓦爾德方程：$X_i$獨立同分佈，$EX$有限，$N$爲停時且$EN$有限，則$E\sum\limits_{i=1}^NX_i=ENEX$

    $ES_{N(t)+1} = \mu(m(t)+1)$

  • 證明過程：

    $ES_{N(t)+1} = t+\Delta t = \mu(m(t)+1)$

    $\frac{m(t)}{t}-\frac{1}{\mu}=\frac{\Delta t}{\mu t}-\frac{1}{t}\ge\frac{1}{t}$

    若$P\{X_i<M\}=1$，得$\frac{m(t)}{t}-\frac{1}{\mu}=\frac{\Delta t}{\mu t}-\frac{1}{t}\le\frac{M}{\mu t}+\frac{1}{t}$，夾逼取極限即可得證

    若$X_i$無界，令新的更新過程$N'(t)$具有更新間隔$\min\{X_i,M\}$，則$\frac{m(t)}{t}\le\frac{m'(t)}{t} \to \frac{1}{\mu}$

    • 其中$\Delta t$稱爲超額時間，若可確定超額時間則可確定更新函數

• 推論：在時刻$t$發生更新的概率趨於$\frac{1}{\mu}$

3）更新過程的中心極限定理：$\lim\limits_{t\to \infin}P\{\frac{N(t)-t/\mu}{\sqrt{t\sigma^2/\mu^3}}<x\}=\frac{1}{\sqrt{2\pi}}\int^x_{-\infin}e^{-x^2/2}\mathrm{d}x$

• $\frac{N(t)}{t}\rightsquigarrow N(\frac{1}{\mu},\frac{\sigma^2}{\mu^3})$

4）檢驗悖論：包含時刻$t$的更新間隔$X_{N(t)+1}=A(t)+Y(t)$的期望長度大於$X$

• $\lim\limits_{s\to\infin}\frac{\int_0^s X_{N(t)+1}\mathrm{d}t}{s}=\frac{EX^2}{EX}$

  註記：需要C3-2）的引理

• 使用交替更新過程確定$X_{N(t)+1}>s$的長程時間比例爲$\frac{\int_c^\infin xf(x)\mathrm{d} x}{EX}$

C3 更新報酬過程

1）更新報酬過程：在第$n$次更新時獲取報酬$R_n$，則$R(t) = \sum\limits_{n=1}^{N(t)}R_n$

2）期望：若$ER,EX$有限則以概率1$\lim\limits_{t\to\infin}\frac{R(t)}{t}=\lim\limits_{t\to\infin}\frac{ER(t)}{t}=\frac{ER}{EX}$

• 若報酬是在更新過程中逐步獲取的，該式仍然成立

  更新的平均年齡：最後一次更新到現在的時間$A(t) = t - S_{N(t)}$

  有$\lim\limits_{s\to\infin}\frac{\int_0^sA(t)\mathrm{d}t}{s}\rightsquigarrow\frac{EX^2}{2EX}$

  更新的超額壽命：下次更新到現在的時間$Y(t) = S_{N(t)+1}-t$

  有$\lim\limits_{s\to\infin}\frac{\int_0^sY(t)\mathrm{d}t}{s}\rightsquigarrow\frac{EX^2}{2EX}$

C4 再生過程

1）再生過程：隨機過程週期性地從一些「再生點」開始執行

e.g. 常返Markov鏈每次回到某狀態可視爲一次再生

2）命題：$P_i=\frac{\int_0^T (X(t)=i?1:0)\mathrm{d}t}{ET}$

3）交替更新過程：在兩個狀態開、閉間轉換，在開態維持$Z_n$，閉態維持$Y_n$

• $P_Y = \frac{EY}{EY+EZ};P_Z = \frac{EZ}{EY+EZ}$

  更新過程年齡比例：早於c的年齡比例爲：$\frac{E\min\{X,c\}}{ET}=\frac{\int_0^\infin1-F(x)\mathrm{d}x}{EX}$

C5 半Markov過程

1）半Markov過程：在狀態$\{1,\dots,N\}$間轉移，並在每個狀態停留$\mu_i$時間

2）長程比例：$P_i = \frac{\pi_i\mu_i}{\sum\limits_j \pi_j\mu_j}$，$\pi$是嵌入鏈極限概率

若到達間隔滿足$P\{X = i\}=p_i$，則包含時刻$t$的區間長度$L(t)$具有極限概率$P_i=\frac{ip_i}{\sum\limits_jjp_j}$

C6 模型應用

1）保險破產模型：理賠過程是更新報酬過程$\sum\limits_{i=1}^{N(t)}Y_i$，公司初始資金爲$x$，並以常數速率$c$收取保費

• 破產率：$R(x) = P\{\exist t\ge 0:\sum\limits_{i=1}^{M(t)}Y_i\gt x+ct\}=E(\frac{\lambda\mu}{c})^{N(x)+1},\frac{\lambda\mu}{c}<1$
• 其中$N(x)$是一個更新間隔滿足$f(x) = \frac{\bar F_Y(x)}{\mu}$的更新過程