M4.2 電話隨時會響：Continuous-Time Markov Chain 與 Rate Matrix

本篇重用2 篇

一條只有一個人的客服專線

一家小公司的客服專線只有一位話務員、一條線。電話平均每小時進來 3 通，每通平均講 10 分鐘。線路忙碌時打進來的電話會聽到忙線音、直接掛掉，不排隊。

這位話務員長期有多少比例的時間在講電話？

直接算 $3\times10=30$ 分鐘，會把忙線時沒接到的電話也算進去。我們得先追蹤「閒、忙」兩種狀態如何切換。但電話沒有回合，「隨時可能發生」要怎麼寫成一步的規則？ 先選一個理想模型：來電是 rate $\lambda=3$ 的 Poisson process，通話長度獨立且是平均 $1/\mu=1/6$ 小時的 exponential。這些是另外的假設，不是由兩個平均值直接推出的。

課堂提問Q1

這裡的狀態是什麼？「每小時 3 通」不是機率（它可以大於 1），那它是什麼？如果硬要用前兩篇「每一步一個 transition matrix」的語言，這一步該多長？

先想一想，再展開看整理後的答案

狀態很清楚：線路「閒」（記 0）或「忙」（記 1）， $X_t\in\{0,1\}$ ，但現在 $t$ 是連續的實數（單位：小時），不是回合數。

在 Poisson 假設下，rate 是單位時間的平均次數，也是短時間事件機率的斜率。長度 $\Delta t$ 內恰好一次的機率為 $\lambda\Delta t+O(\Delta t^2)$ ，兩次以上是 $O(\Delta t^2)$ 。Rate 可以大於 1；它乘上短時間，才近似機率。 $\mu=6$ 則是已在忙碌狀態下的結束 rate，不表示整條專線每小時實際完成六通。

所以「硬要用 transition matrix」的答案是：任何一個很短的 $\Delta t$ 都可以，得到的矩陣是 $P(\Delta t)\approx\begin{pmatrix}1-\lambda\Delta t&\lambda\Delta t\\ \mu\Delta t&1-\mu\Delta t\end{pmatrix}$ ， $\lambda=3$ 是來電 rate、 $\mu$ 是結束 rate（一通平均 10 分鐘，每小時「結束」6 次， $\mu=6$ ）。但 $\Delta t$ 選多短是任意的，而且 $\Delta t$ 太大這個式子就錯了（ $\lambda\Delta t$ 會超過 1）。真正不依賴 $\Delta t$ 的物件，是把 $\Delta t$ 除掉之後剩下的東西——這是下一節要引入的 rate matrix。

先抓住這個畫面

想像一顆棋子在「閒」「忙」兩格之間，但這次沒有人喊「下一回合」。棋子站在「閒」格時，頭上有一個以每小時 3 次的頻率隨機響的鬧鐘；響了就跳到「忙」格。站在「忙」格時換另一個鬧鐘，每小時 6 次；響了就跳回「閒」。兩個鬧鐘都沒有記憶：不管已經等了多久，接下來一分鐘響的機率都一樣。

所以我們不先固定一分鐘或一小時為一步，而是記錄短時間機率增加的斜率。這個斜率會決定停留多久，以及離開時去哪一個狀態。

兩個沒有記憶的鬧鐘

圖：CTMC 用 rate 決定 exponential 停留時間；長期占比由兩種平均停留時間的比例決定。

把畫面寫成矩陣

從短時段的 transition matrix 到 rate matrix

上一節的 $P(\Delta t)$ 可以寫成

P(\Delta t)\approx I+R\,\Delta t,\qquad R=\begin{pmatrix}-\lambda&\lambda\\ \mu&-\mu\end{pmatrix}=\begin{pmatrix}-3&3\\6&-6\end{pmatrix}.

$R$ 叫 rate matrix（也叫 generator）。讀法：非對角線 $R(x,y)\ge0$ 是「從 $x$ 跳到 $y$ 的 rate」；對角線 $R(x,x)=-\sum_{y\ne x}R(x,y)$ 是負的「離開 $x$ 的總 rate」，讓每列的和是 0——這是 $P(\Delta t)$ 每列和為 1 在 $\Delta t\to0$ 後留下的痕跡。 $R$ 不依賴 $\Delta t$ ：它是把所有短時段的 transition matrix 共同的「斜率」抽出來的結果， $R=\lim_{\Delta t\to0}\frac{P(\Delta t)-I}{\Delta t}$ 。

走一段時間：矩陣指數

走 $t$ 小時等於走 $n=t/\Delta t$ 個短步。用前面 chain 的乘法規則 $P(t)=P(\Delta t)^n$ （Markov property 在連續時間的版本： $P(t+s)=P(t)P(s)$ ），

P(t)=\lim_{n\to\infty}\Big(I+\frac{tR}{n}\Big)^{n}=e^{tR}\equiv\sum_{k\ge0}\frac{(tR)^k}{k!}.

這跟 $e^{x}=\lim(1+x/n)^n$ 是同一條極限，只是把數字換成矩陣。另一個得到它的方法是微分：

\frac{d}{dt}P(t)=\lim_{\Delta t\to0}\frac{P(t)P(\Delta t)-P(t)}{\Delta t}=P(t)\,R,\qquad P(0)=I,

一個矩陣版的線性 ODE，解正是 $e^{tR}$ 。

分佈怎麼變：forward equation

把上式左乘初始分佈的列向量 $p_0$ ， $p_t=p_0P(t)$ 滿足

\dot p_t=p_tR\quad\Longleftrightarrow\quad \dot p_t(y)=\sum_{x\ne y}\Big[p_t(x)R(x,y)-p_t(y)R(y,x)\Big].

右邊的寫法是把 $R$ 的對角線攤開後得到的： $y$ 的機率增加率＝流進來（各 $x$ 的機率乘上 $x\to y$ 的 rate）減流出去（ $y$ 的機率乘上離開的總 rate）。這叫 forward equation（或 master equation）。

它就是 M3.2 的離散狀態版：那裡質量在連續的位置之間流動，drift 與 diffusion 決定「流到鄰近位置」的速率，方程式是 $\partial_t p=\mathcal L^{*}p$ ；這裡位置是有限個格子，「流到哪裡、多快」全由 $R$ 決定， $\mathcal L^{*}$ 換成了「右乘 $R$ 」。兩者都是守恆律：總機率 $\sum_y p_t(y)$ 的導數是 $\sum_y(p_tR)(y)=p_t(R\mathbb 1)=0$ ，因為 $R$ 每列和為 0。

2 狀態手算

對我們的專線， $p_t(1)$ （忙的機率）滿足 $\dot p_t(1)=\lambda\,p_t(0)-\mu\,p_t(1)=\lambda-(\lambda+\mu)\,p_t(1)$ 。這是一條一階線性 ODE，解是

p_t(1)=\frac{\lambda}{\lambda+\mu}+\Big(p_0(1)-\frac{\lambda}{\lambda+\mu}\Big)e^{-(\lambda+\mu)t}.

Stationary distribution 是 $\pi R=0$ 的解——流進等於流出， $\pi(0)\lambda=\pi(1)\mu$ ——

\pi(1)=\frac{\lambda}{\lambda+\mu}=\frac{3}{3+6}=\frac13 .

而不是 $\tfrac12$ 。今天早上的狀態被忘掉的時間尺度是 $1/(\lambda+\mu)=1/9$ 小時，約 7 分鐘：這是上一篇 $|\lambda_2|^n$ 的連續時間版本， $e^{-(\lambda+\mu)t}$ 裡的 $-(\lambda+\mu)$ 正是 $R$ 的非零 eigenvalue。

展開細節完整的 e^{tR}、停留時間為什麼是 exponential、以及 Δt 太大會怎樣

$e^{tR}$ 的 closed form。 $R$ 的 eigenvalue 是 $0$ （左 eigenvector $\pi$ ）與 $-(\lambda+\mu)$ 。令 $\Pi$ 是每一列都等於 $\pi$ 的矩陣（ $\Pi=\mathbb 1\pi$ ），則 $R\Pi=\Pi R=0$ 、 $R^2=-(\lambda+\mu)R$ ，代入級數得 $e^{tR}=\Pi+e^{-(\lambda+\mu)t}(I-\Pi)$ 。驗算： $t=0$ 得 $I$ ； $t\to\infty$ 每列都變成 $\pi$ ；對 $t$ 微分在 $0$ 得 $-(\lambda+\mu)(I-\Pi)=R$ 。

停留時間。 在狀態 $x$ 待超過 $t$ 的機率是 $\lim(1-|R(x,x)|\Delta t)^{t/\Delta t}=e^{-|R(x,x)|t}$ ：停留時間是 rate $|R(x,x)|$ 的 exponential distribution，平均 $1/|R(x,x)|$ 。它是 geometric distribution 的連續極限，同樣 memoryless——這就是「鬧鐘沒有記憶」。一通電話平均 10 分鐘對應 $\mu=6$ ，就是這樣來的。

$\Delta t$ 太大。 $I+R\Delta t$ 要是合法的 transition matrix，需要對角線 $1-|R(x,x)|\Delta t\ge0$ ，即 $\Delta t\le1/\max_x|R(x,x)|=1/6$ 小時。取 $\Delta t=0.5$ 小時， $\lambda\Delta t=1.5$ ，「機率」超過 1。 $e^{tR}$ 沒有這個問題——它對任何 $t$ 都是合法的 transition matrix，這正是要引入它的原因。

回頭看「一半」

理論的判斷。 在「來電是 rate $\lambda$ 的無記憶鬧鐘、通話長度是 rate $\mu$ 的無記憶鬧鐘、忙線時的來電被丟掉」這三個假設下，長期忙碌比例是 $\lambda/(\lambda+\mu)=\tfrac13$ ，不是 $\tfrac12$ 。「3 通 × 10 分鐘」的直覺錯在一個隱含假設：它把每小時進來的 3 通都算成有講到。但其中一部分打進來時線路是忙的、直接被掛掉；真正接到的電話每小時只有 $\lambda\,\pi(0)=3\times\tfrac23=2$ 通， $2\times10$ 分鐘 $=20$ 分鐘，正好是 $\tfrac13$ 。流量平衡 $\pi(0)\lambda=\pi(1)\mu$ 自動把這件事算進去了。（若電話可以排隊而不是掛掉， $\tfrac12$ 才是負載——但那是另一條 chain，狀態要包含隊伍長度。）

哪裡可能失準？ 若來電仍是固定 rate 的 Poisson process、通話長度獨立且平均有限，把「閒→忙→閒」當成循環，忙碌比例仍是 $\mathbb E[S]/(1/\lambda+\mathbb E[S])$ ，不必要求通話長度 exponential。但忙碌狀態本身一般不再是上述二狀態 CTMC，中途的 $p_t$ 與剩餘等待時間也可能不同。若 $\lambda$ 隨時間變，則不能直接套固定 generator 的 stationary calculation；是否存在共同 stationary distribution，需另外檢查，不能一概說不存在。

動手跑一次

import numpy as np
rng = np.random.default_rng(0)
lam, mu, T = 3.0, 6.0, 20_000.0                # 每小時；模擬 20000 小時
t, x, busy = 0.0, 0, 0.0
while t < T:                                     # 用 exponential 停留時間直接模擬
    stay = rng.exponential(1/lam) if x == 0 else rng.exponential(1/mu)
    busy += stay * x; t += stay; x = 1 - x
print("忙碌比例", busy / T)                       # ≈ 1/3
# 違反「通話無記憶」：通話固定 10 分鐘 → 比例仍 ≈ 1/3
# 違反 Δt 小：用 P ≈ I + R·0.5 走離散步 → 出現負機率，模擬直接壞掉

檢查理解

想一想

假設機器的正常運轉與維修時間都是獨立 exponential，平均分別為 10 與 2 小時。要算長期可用率與剛修好三小時後的狀態，該用什麼工具？

想一想

把專線的通話長度從「平均 10 分鐘的 exponential」改成「每通固定 10 分鐘」。哪個結論會改變？

參考文獻

Norris, J. R. Markov Chains. Cambridge University Press, 1997.（第 2–3 章：連續時間 chain、generator、forward / backward equations。）
Grimmett, G., Stirzaker, D. Probability and Random Processes, 3rd ed. Oxford University Press, 2001.（6.9 節。）
Anderson, W. J. Continuous-Time Markov Chains: An Applications-Oriented Approach. Springer, 1991.