動機
已知馬爾可夫(Markov)鏈的現在狀態後,過去不再提供預測未來所需的額外資訊。熟悉的公式在固定時刻成立;但實際問題往往從觀察過程時才發現的時刻開始,例如首次到達某狀態之時。到達後能否把過程視作重新開始的鏈?如果該時刻是停時,答案是可以;若選時方法依賴未來觀察,則可能使選中時刻後的分佈產生偏差。
以下 是有限或可數狀態空間 上的時間齊次馬爾可夫鏈,轉移矩陣為 ,自然歷史為 。 表示由 開始。
定義
定義 2.11.1
(根據已觀察歷史作出的決定)
取值於 的隨機時間 稱為停時,若每個有限 都有 。等價地,到時刻 時,已觀察歷史足以判斷是否已經停止。對 ,首次到達時間定義為 ;空集合的下確界取為 。
本章最常用的兩種隨機時間都是停時。
引理 2.11.2
(到達時間與返回時間都是停時)
對每個 ,首次到達時間 是停時。對每個 ,首次返回時間 是停時。
證明
(每個事件只讀取到時刻 n 為止的路徑)
事件 表示 全在 外,而 在 內;它是 中有限個事件之交。同樣,對 , 表示 都不等於 而 ;另外 。
相反,固定期限之前的最後一次到訪一般不是停時:要知道一次到訪是最後一次,便須查看其後的路徑。
隨機時刻所得的資訊用 表示:當每個有限 均有 時,事件 屬於它。下述定理只討論 ;在 上並不定義或聲稱有 及其後路徑。
定理與證明
定理 2.11.3
(在停時重新開始)
設 是停時,,而 、,則
當右邊乘積前的概率為正時,這給出已知上述過去事件及 後,接下來 個狀態的條件分佈。因此未來具有從 重新開始的鏈之分佈;即使 無界或有正概率等於無限大,結論仍成立。
證明
(按停時的取值分拆)
對每個 ,事件 由時刻 的歷史決定。反覆在固定時間 使用普通馬爾可夫性,得到
對互不相交的 求和。各項都是概率,可數可加性適用,不需要假設 。在 上,式中的 分別就是 ,故得結論。有限路徑的概率決定其後離散時間路徑的分佈。
證明透視
停時條件用在哪裏
證明只有一個想法和一個記賬步驟。
- 想法是以固定時刻取代隨機時刻。在 上,命題關乎固定時刻 ,那裏可用普通馬爾可夫性。該性質要求條件事件屬於 ,而這是假設唯一被用到之處: 與 是停時合起來,正好給出 。
- 記賬步驟是對 求和。這是非負項的可數和,所以不需要 的可積性,而 的情形根本不會被計入。
證明沒有說的兩件事:它沒有說 與路徑獨立,通常兩者並不獨立;它也沒有說未來與 獨立,因為未來的分佈明確取決於到達的狀態。下面預看未來的反例顯示,當 時第一步如何失效。
例題
例題 2.11.4
(連續返回的幾何尾概率)
從狀態 出發,令 。定義 及 ;若 ,則令 。這些都是停時。重新開始定理給出遞推關係 ;即使先前返回事件概率為零,此等式仍成立。因此
若 是包括時間零在內的訪問次數,則 。尾和公式給出: 時 ; 時期望無限。後者還可由遞減事件 的概率連續性得到 。這不保證平均返回時間有限:常返與正常返仍是不同性質。
例題 2.11.5
(到達某狀態後重複嘗試)
狀態為 ,其中 吸收;由 必定轉至 ,由 以各 概率轉至 或 。從 出發,每次到達 便開始一次嘗試;下一步到達 的成功概率為 。重新開始定理保證進行中的各次嘗試結果獨立,因此直到首次成功的嘗試次數 滿足
每次嘗試由 經 到達下一個目的地,耗時兩步。失敗後回到 ,故吸收時間為 ,其均值是 。這結論依賴題中指定的轉移,並非所有到達時間的通式。
第三個例子顯示:當到達可以發生在不同狀態,甚至可能根本不發生時,如何使用重新開始定理。
例題 2.11.6
(經兩個不同狀態進入集合)
取狀態 ,其中 吸收。由 以各 的概率轉至 ;由 以各 的概率轉至 或 ;由 必定轉至 。從 出發,令 ,。在 之前鏈停留在 ,所以
同理 。因此 ;在其餘概率為 的事件上,鏈先被 吸收,, 沒有定義。取 ,對每個進入狀態分別使用定理再相加:
給定 ,這是 ;它既不是從 重新開始的值 ,也不是從 重新開始的值 ,而是兩者以進入分佈 加權的平均。注意此處 無界,而定理並不需要任何界。
預看未來的反例
停時假設不能換成較弱的要求,即只要求隨機時刻有限。
反例模式
隨機時刻未必是重新開始的時刻
聲稱:若 是有限隨機時刻且 ,則 之後的路徑是從 重新開始的鏈。令 為獨立的公平二元變量,這是一條每種轉移概率均為 的馬爾可夫鏈。若 則取 ,若 則取 。此時 有限且 有定義,但 不能由 決定,所以 不是停時。計算:,而 ,所以給定 及 後,下一個值以概率 為 ;從 重新開始的鏈,其下一值為 的概率卻是 。此例不違反普通馬爾可夫性:條件 本身已提供關於 的資訊。修正後的敘述就是上述定理:停止時必須能從當時歷史判定選時規則。
常見錯誤
常見錯誤
(除以可能不發生的到達事件的概率)
首次到達時間可能等於無限大。應在確實到達的事件上使用重新開始結論,而且只有該事件概率為正時才可除以它。像 這樣的量,在對 訂下約定之前並無意義。
常見錯誤
(以為停時必須忽略過去)
停時可以高度依賴過去:首次到達正是標準例子,而 本身通常與路徑遠非獨立。不能使用的是作決定當刻尚未取得的資訊。
常見錯誤
(丟棄最後一段行程)
要聲稱完整回返循環彼此獨立,必須說明連續返回時刻及各循環存在的事件。當 時,從 出發的最後一段行程永不返回,不能悄悄丟棄它,也不能把它當作已完成的循環。
練習
快速檢查
(對 和 ,證明 是停時。)
分別處理 與 。
解答 · 答案
若 ,則 。若 ,它是 與所有 的 之交;這些事件都在 中。
快速檢查
(若 ,求時間零後至少返回三次的概率,以及包括時間零在內到訪 的期望總次數。)
利用第一個例題。
解答 · 答案
至少返回三次的概率為 ;期望訪問次數為 ,包括最初一次。
快速檢查
(在重複嘗試例子中,求吸收時間超過四步的概率及恰為六步的概率。)
吸收時間是 。
解答 · 答案
要求頭兩次均失敗,概率是 。恰好六步即 ,兩次失敗後成功的概率是 。
快速檢查
(一條鏈從 出發, 且 。已知 和 ,求 。能否不加說明便寫 ?)
與第三個例題比較。
解答
定理給出 。在 上沒有定義 ;即使給定 ,到達狀態亦未必是 。必須明確說明事件,並計入其他可能到達狀態的貢獻。