平均擊中時間與首通時間(mean hitting and first-passage times)
除了「鏈最終會在哪裡?」之外,你常想問「還要『多久』某事才會發生?」。平均而言要走幾步,賭徒才會破產?隊伍才會清空?你才會第一次抵達目標格?這些是首通時間或擊中時間:鏈首次進入某目標狀態集合的時刻。它們的期望值就是平均擊中時間,是一條鏈所能提供最實用的量之一。
令 h(i) 為從狀態 i 出發、首次抵達目標集合 A 的期望步數。有一個乾淨的方法可以一次算出全部:對第一步取條件。從目標狀態出發,h = 0。從任何其他狀態 i 出發,你先走一步(花費 1),然後面對從落腳處起算的期望時間:h(i) = 1 + 對所有 j 加總 P(i, j) h(j)。這是每個非目標狀態一條線性方程,一個小系統,同時求解即可。同樣的一步/首步分析也能給出吸收機率與期望成本。
一個特例是平均返回時間:從狀態 i 出發、回到 i 的期望步數。對不可約且正常返的鏈,這是有限的,且恰好等於 1 除以 pi(i),即平穩機率的倒數 —— 所以平衡機率高的狀態很快就被重訪,罕見狀態則要很久才回得去。擊中時間分析支撐了賭徒破產問題、桌遊的期望長度、排隊延遲,以及系統首次故障時機的可靠度計算。
賭徒手有 1 元,以公正硬幣每次下注 1 元,目標為 0(破產)或 3(贏)。令 h(i) 為從 i 元到被吸收的期望投擲數:h(0) = h(3) = 0,且對 i = 1, 2 有 h(i) = 1 + (1/2)h(i-1) + (1/2)h(i+1)。解得 h(1) = 2、h(2) = 2 次期望投擲。首步方程把一個遊走的問題化成了簡單的代數。
首步分析:h(i) = 1 + sum of P(i,j) h(j),目標上 h = 0 —— 每個狀態一條方程。
一個狀態可以是常返的(必定返回)卻有「無窮」的平均返回時間 —— 那正是零常返。「以機率 1 返回」與「在有限期望時間內返回」是不同的論斷。