為何研究邊界問題?
設狀態代表儲備的單位數。每一步以概率 增加一個單位,或以概率 減少一個單位。儲備到達零或目標 時便停止。我們想知道:先到目標的機會有多大?平均要等多久?兩者是不同問題:概率滿足齊次首步方程,歷時則在每個內部狀態額外累加一個時間單位。
假設各步獨立、, 是整數,初始狀態 。到達邊界即停止。
定義 2.9.1
(離開時間、首達概率與平均歷時)
對在邊界停止、取值於 的遊走 ,定義
概率和期望的下標表示起始狀態。特別地 、 及 :從邊界出發,停止時刻就是零。
首步方程及其解
定理 2.9.2
(兩個吸收邊界)
令 。對 ,先到 的概率及平均歷時為
到達其中一個邊界的時間幾乎必然有限,而且 。
證明
(有限性、首步方程與最大值原理)
有限性。 從任何內部狀態出發,最多連續 次下降便到達零;這些下降的概率至少為 ,且與之前的歷史獨立。條件於時刻 尚未停止,在下一個長度為 的區段仍未停止的概率至多為 。因此 ,它趨向零;由尾和公式, 亦有有限的幾何級數上界。這便確保以下首步方程可用。
方程。 按第一步的結果分情況,對 ,
第一式可重排為 。若 ,相鄰差值成為公比 的等比序列,故 ;代入兩個邊界值得到上述公式。若 ,相鄰差值為常數,因而 。
對歷時方程,若 ,一個特解是 :代入 得 。加上齊次方程的通解,再令兩端為零,便得 。若 , 的二階差分為 ,故可取二次特解 ;邊界條件給出 。
唯一性。 為何代數解就是所求量,而且唯一?若兩個解的邊界值相同,其差 滿足 。若它在內部取得正的最大值,由 可知兩個相鄰值也必須等於這個最大值。依此推至邊界,便與邊界值為零矛盾。對 同樣論證,得 。
證明透視
一個證明裏的三件工作
證明做了三件不同的事,各自用到不同的假設。
- 有限性只用到 :連續 次下降有固定的正概率。若沒有 ,期望方程 可能只以 這種無用的形式成立。
- 求解純粹是二階線性遞推的代數。唯一不顯然的一步是歷時方程中多出的 :第一步還消耗一個時間單位。若漏掉它,所得齊次方程配上零邊界,其解為零,並不是平均歷時。
- 唯一性同時用到 與 :最大值原理需要兩個相鄰狀態都有正權重,內部最大值才會擴散到邊界。
論證得以收結,是因為遞推的解恰有兩個自由常數,而邊界值也恰有兩個;最大值原理則排除了同一邊界數據下的任何第二個解。
詳解例子
例題 2.9.3
(向上有偏的遊走)
取 、、、。此時 ,所以
直接驗算:由 及 得 ,故 。向上的平均趨勢不保證每個起點都是先到目標較可能:此處距離零只需一步,距離目標卻要兩步。平均歷時的單位是步數,而非儲備單位。
例題 2.9.4
(公平遊走)
若 、、,先到上界的概率為 ,平均歷時為 。將起點移到 ,結果分別變為 和 。歷時的對稱性是交換兩個邊界時的對稱性,並非說每個起點的歷時均相同。公平情形是公式中的退化情形 :此時 與 都為零,而另列的公式 正是 時 的極限。
第三個計算把趨勢反轉,再把上界移遠,為下一節作準備。
例題 2.9.5
(向下有偏的遊走與遠方目標)
取 、、、。此時 ,所以
直接驗算:由 及 得 ,故 。固定 而令 ,則 ,所以 且 ;因此 。移除目標使平均歷時由 增至 ,因為原本停在 的路徑現在要繼續走到零。
移除上界
現在令獨立步驟的遊走由整數 出發,並令 ,不設上吸收邊界。
命題 2.9.6
(由上方到達零)
對由 出發的遊走,
其中在永不到達零的路徑上取 。
證明
(把上界逐步提高)
先在到達 或 時停止。隨 ,先到零而非 的事件遞增至 :因為任何有限的到零路徑都有有限最大值。由概率的下方連續性及有限邊界公式,;當 時它等於 ,當 時等於 。
至於均值,設 為首次到達 的時間。隨 增大, 遞增至 ,故由單調收斂定理 。當 , 且 ,所以 ,。當 ,。當 ,事件 有正概率,所以廣義期望為無窮大。
公平情形值得單獨拿出來看,因為它推翻了一個誘人的推論。
反例模式
幾乎必然有限不等於均值有限
聲稱:若首達時間幾乎必然有限,則其期望有限。取公平遊走 ,由 出發。上述命題給出 。但 ,而且
所以聲稱不成立。僅有概率的極限並不足以推得均值的極限,後者需要單調收斂等另外的論證。修正後的命題要求嚴格朝向零的趨勢:當 ,。
常見錯誤
常見錯誤
(只憑趨勢判斷哪個邊界先到)
正趨勢 不表示從每個起點出發先到上界的概率都超過 。在向上有偏的例子中,,因為零只差一步,目標卻差兩步。概率同時取決於 和到兩個邊界的距離。
常見錯誤
(把 直接代入有偏公式)
當 ,式子 成為 ,而 的分母為零。公平情形需要另外求解遞推,得 及 ;它們也正是 時有偏公式的極限。
練習與解答
快速檢查
(公平遊走在 內由 出發,求先到 的概率及平均停止時間。)
用 的公平情形公式。
解答 · 答案
公式給出 ,以及 步。
快速檢查
(取 、、、。用公式求 與 ,然後直接驗算。)
此時 。
解答 · 答案
此時 ,因此 ,。直接觀察,第一步必到其中一個邊界,所以 ;到上界的概率正是 。
快速檢查
(半直線上的遊走由 出發,、。求最終到達零的概率;其廣義平均首達時間有限嗎?)
先比較 與 。
解答 · 答案
由於 ,概率為 。有 的概率首達時間為無窮大,因此廣義期望為無窮大。
快速檢查
(有學生將 代入公平遊走的平均歷時方程。錯在哪裏?)
檢查邊界值與內部方程。
解答 · 答案
函數 是調和函數,邊界值為 ,解的是首達概率問題。平均時間的邊界值是 ,內部方程還有額外的 ;正確結果為 。