公平遊戲與資訊
定義 2.3.1
(濾過、鞅與停時)
令 為遞增的資訊序列,形式上稱為一個由 -代數組成的濾過。離散時間鞅 適應此濾過,滿足 ,並且 。
停時 的取值在 中,並對每個 滿足 。
其下一個增量的條件平均為零;這是對公平性的精確表述,並不保證每個隨機停下的規則都能保持初始期望。到了時間 ,只用當時已有的資訊便可判斷是否已停下。適應過程首次擊中指定集合的時間是停時;查看未來再選取最後一次贏錢的時間,則未必是停時。
有界可選停時
定理 2.3.2
(有界時刻的可選停時)
設 是鞅, 是停時。對每個確定的整數 ,。特別地,若 幾乎必然成立,則 。
證明
(把停時視為可預測地選取增量)
對任何確定的 及任何停時 ,截停時間 有界。其增量分解為
指示函數 是 可測的,因為其補集是 。增量可積、指示函數有界,故由條件期望可知每一項的平均為零。因此
對無界的 ,要把極限移入期望須另行證明;單靠幾乎必然收斂並不足夠。
有限公平賭徒破產問題
固定整數 及 。令 、,其中各個 相互獨立,並且以各 的概率取 或 。使用由增量生成的自然濾過。設 ,並約定空集的下確界為無窮。未截停的遊走對所有 都有定義;截停後的遊走保持在 中。
命題 2.3.3
(公平賭徒破產)
在此模型中, 幾乎必然成立,,且 。
證明
(在有界時刻截停兩個鞅)
及 都是鞅。後者可展開 ,再利用獨立增量的平均為 、平方為 得出。由有界停時,對每個 有
因為 ,第二個等式給出 。由單調收斂定理,,因此 幾乎必然成立。截停位置有界,故可對位置及其平方使用支配收斂定理。令 ,便得到
證明透視
有限性是推導出來而非假設的
論證從未在無界時刻 本身使用可選停時。它先在 使用有界定理,此時定理自動成立,然後才令 。兩個鞅各有不同任務。二次鞅 把有界範圍 轉為對 一致的界 ;單調收斂把它變成 , 的有限性正由此而來。線性鞅 再確定 。在兩條恆等式中取極限時,位置及其平方用支配收斂, 則用單調收斂。真正起作用的假設是截停位置有界;下一節顯示,沒有它,同一個取極限步驟便會失敗。
此證明沒有先假設期望停時有限再得出它有限。公式只適用於這裏公平且增量獨立的模型;有偏遊走需要不同的鞅,擊中概率也不同。
常見錯誤
(把公平公式用於有偏遊走)
公式 依賴 是鞅。若每步以概率 上升、以概率 下降,取 、,則 ,而 ,不是 。有偏遊走的 不是鞅,須改用另一個鞅。
例題 2.3.4
(上界五、起點二)
取 、。先到達 的概率為 ,先到達 的概率為 ,到達任一邊界的平均步數為 。可用二次鞅核對:,而 。
例題 2.3.5
(緊鄰兩個邊界的起點)
取 、。第一步必定到達 或 ,故 是確定的,與 一致;而 正是第一步向上的概率。這個邊緣情況中 有界,可直接應用有界定理,無須取極限。
例題 2.3.6
(偷看未來的有界時刻)
在同一遊走中,若 令 ,否則令 。則 有界,但 。這並不與定理矛盾: 不屬於 ,所以 不是停時。在時間零決定是否停下時,用上了尚未發生的第一步。
為何無界停時不同
上面的有限性證明依賴截停遊走的有界範圍。去掉下方邊界,結論便會失效。
反例模式
幾乎必然有限的停時仍可破壞可選停時
公平遊走由 開始,令 。對每個正整數 ,改為在擊中 或 時停下。把前述有限區間結果平移後,可知先到達 的概率是 ,且有限區間擊中時間幾乎必然有限。當 ,這些事件遞增至 :一條在有限時間內到達 的路徑必有有限最小值。因此 幾乎必然成立,且 幾乎必然成立,但 。
故若直接把 代入有界定理,便會錯誤得到 。事實上 :若它有限,由 及支配收斂定理,便有 ,矛盾。取極限需要控制:例如截停過程被常數界住,或在增量以一為界且 時,經 被可積變量界住。
常見錯誤
(由幾乎必然有限推出期望有限)
此例也顯示幾乎必然有限的停時不等於有界停時,也不等於具有有限期望持續時間。在賭徒破產中, 來自有界範圍,而不是來自 。
習題
快速檢查
(在有限公平遊戲中,若 、初始位置 ,求先擊中 的概率及擊中任一邊界的平均時間。)
套用 及 。
解答 · 答案
概率是 ,平均持續時間是 。
快速檢查
(對同一遊戲,解釋為何在尚未證明 有限之前,已可對 使用有界可選停時。)
檢查有界定理的兩個條件。
解答 · 答案
不超過確定的整數 ,而且是停時;各鞅在每個確定時間均可積。因此無須假設 便可應用定理。
快速檢查
(在無界例子中,為何 等於對所有 的「先擊中 而非 」事件取聯集?)
證明兩個方向的包含關係。
解答 · 答案
若先擊中 而非 ,則 有限。反過來,到首次擊中 為止的有限路徑有有限最小值;取 大於該最小值的絕對值,便保證沒有先擊中 。