在已知資訊下的公平性
我們可以按照已觀察到的歷史停止隨機遊走,例如到達邊界便停止。停止的時間是隨機的,亦可依賴之前的增量,因此不能不加論證便將它代入只對固定時間證明的公式。鞅描述一種特定的公平性,讓我們能有條件地進行這種論證。
設 是概率空間上一列遞增的 代數,代表各時刻可用的資訊。若 是 可測,則時刻 的資訊足以決定它的值。可積且適應這列資訊的過程 稱為鞅,若對每個 ,
可積是指每個固定時刻均有 ;適應是指 為 可測。公平性須在所有已知資訊下成立,單靠各時刻的無條件均值相同並不足夠。例如,若 相互獨立、均值為零且一階絕對矩有限,則對自然資訊流,()是鞅:下一增量獨立於過去,條件均值為零。對鞅定義取期望,可得每個固定 都有 。
反例模式
均值不變並不足夠
設 以相同概率取 或 ,令 、、,並令 。這三個值的均值都是零,但 。一旦知道 ,下一個值便可預測,因此這過程不是鞅。
只根據過去資訊停止
取值於 的隨機變量 稱為停時,若每個 均有 。這表示到了時刻 ,已有的資訊足以判斷是否已經停止。對適應過程,首次到達時間 是停時,因為 。相反,選取某個未來時限前遊走最後一次到零的時間,通常要看未來,未必是停時。
常見錯誤
(事後挑選最佳時刻停止)
「在 中取最大值的時刻停止」這類規則不是停時,即使它以 為上界。對從 出發的公平遊走,令 為最早達到此最大值的時刻。則 是路徑 的補事件,取決於 ,不屬於 。四條等可能路徑 分別給出 ,所以 。有界停時定理在此失效,因為在時刻一是否停止用到了下一個增量。
關鍵恆等式把停止後的值寫成有限個增量之和:
指示變量是 可測:是否繼續進行第 步,在時刻 已經決定。它有界,而增量可積,因此條件期望的定義給出
定理 19.1.1
(有界停時)
若 是可積離散時間鞅,停時 幾乎必然滿足 ,其中 是確定的整數,則 。
證明
(公平增量的有限和)
在上述恆等式取 ,對有限和逐項取期望。每項期望為零,且 幾乎必然成立。
證明透視
停止和式中各假設的作用
整個證明建基於把 寫成 加上由指示變量 開關的增量。停時性質只在這裏使用: 是 的補事件,所以每個開關都在它所控制的增量之前設定。增量可積而指示變量有界,因此每個乘積可積,可用塔性質把增量換成其條件均值,即零。
確定上界 用了兩次,而且只在最後:它令和式有限,期望可以逐項通過;它亦給出 。若 無界,恆等式 對每個 仍然成立;可能失效的只是 的極限。下面的例題以受控收斂補上這一步,而加倍下注的反例說明,沒有這種控制便補不上。
公平遊走的兩個鞅
設 獨立,且 ,令 。對自然資訊流, 和 都是鞅。要證明後者,只需展開平方,並使用 及 。所有固定時刻的變量均可積。
例題 19.1.2
(吸收概率與平均時間)
取整數 和 ,令 為首次到達 或 的時間。從任何內部位置出發,連續 個 增量會迫使遊走在接下來 步內被吸收。利用相繼區塊的獨立性,
因此 幾乎必然成立,而且 ;此和至多為 。對 使用有界停時定理,得 。由於 且它幾乎必然收斂至 ,受控收斂定理給出 。吸收位置只有 或 ,故
同理,對 使用有界停時定理,得 。平方項用受控收斂, 用單調收斂。因為 ,所以
例如 、 時,到達上邊界的概率為 ,平均吸收時間為 。這些公式依賴公平獨立增量的模型;它們並不表示每條路徑都恰好走八步。
例題 19.1.3
(有偏遊走的破產概率)
設增量獨立,、,其中 且 ;從 出發的遊走在首次到達 或 的時刻 停止。令 ,則 是鞅,因為
連續 步向上仍會迫使吸收,現在每段的概率為 ,所以 幾乎必然。有界停時給出 ,而 介於 與 之間,由受控收斂得 。記 ,這就是 ,因此
取 、、,則 ,概率為 。首步分析亦吻合:由 及 得 。
例題 19.1.4
(把到達時間截於兩步)
對從 出發的公平遊走,令 為首次 的時刻。 無界,但 是以 為上界的停時,故 。逐一檢查四條等可能路徑即可確認。若 ,則 且 ,這包括路徑 和 。水平 不可能在偶數時刻 首次到達,所以在路徑 和 上遊走在截斷時刻停止,值為 和 。平均為 。
對每個截斷時刻 ,同樣的計算都成立:由於 ,得 。 增大時,未停止的路徑愈來愈少,但取值愈來愈負;這就是 並非 的極限的原因。
為甚麼無界停時要格外小心
反例模式
首次勝出便停止的公平遊戲
反覆擲公平硬幣,資本由零開始,第 次投注 在正面,首次出現正面後不再下注。令 為首次正面時間, 為第 次擲後資本。每個固定時刻的資本可積,下一步條件期望收益為零:在 前等概率得失 ,之後得失為零。因此 是鞅, 是停時。又 ,所以 幾乎必然有限,且在此事件上 。然而 。
實際上,有正面出現時 ,否則為 ;每個 的期望都是零。罕見虧損的大小隨 增長,所以幾乎必然收斂至 不足以交換期望與極限。這策略亦需要無限額度的信用。此例推翻了僅憑停時幾乎必然有限便能使用可選停止定理的想法。
練習
快速檢查
(設 獨立且 ,。證明 是鞅。)
解答 · 答案
。給定過去, 與 的條件期望均為零,因為 已知、 且 ;適應性和固定時間可積性直接成立。
快速檢查
(對上述吸收遊走取 、,求兩個吸收概率和平均吸收時間。)
解答 · 答案
上邊界概率為 ,下邊界概率為 ,而 。
快速檢查
(設 為獨立公平擲幣首次出現正面的時間。 是否有確定上界的停時?若 是同一資訊流下任意可積鞅, 是多少?)
解答 · 答案
是。當 , 由前 次結果決定;當 ,它是整個樣本空間。此停時至多為 ,故 。
快速檢查
(在加倍下注例子中計算 ,並解釋結果為何不與幾乎必然收斂矛盾。)
解答 · 答案
除非前 次均為反面,差值均為零;在全反面時,絕對差值為 。故期望對每個 都是 。幾乎必然收斂一般不保證絕對期望收斂:這裏罕見虧損的大小不斷增加。