反射原理(reflection principle)
直接去數那些觸及某個水準的隨機漫步路徑 —— 比方說曾經到達高度 5 的路徑,或撞上某道障壁的路徑 —— 看起來毫無希望,因為達成的方式實在太多。反射原理是一個優雅的技巧,藉由一次鏡射翻折的動作,把困難的計數化為容易的計數。它是出奇多隨機漫步精確結果背後的主力工具。
想法如下,以對稱漫步為例。假設你想數從 0 到某終點、途中觸及高度為 a 的障壁的路徑。取任何這樣的路徑;找出它首次撞上高度 a 的時刻;然後把其餘的路徑(那次首觸之後的一切)沿高度 a 的水平線反射,就像對著鏡子折疊。這產生一條結束於鏡像終點的路徑,而這個對應恰好是一對一且可逆的。所以到達原終點的觸壁路徑數,等於到達反射終點的(無限制)路徑總數 —— 而後者數起來易如反掌。困難的、受約束的計數,化為了自由的、無約束的計數。
由這一個技巧傾瀉出一連串結果。它給出漫步直到某給定時刻所達到的最大值之分布、曾經穿越某水準的機率、首次通過時間的法則,以及著名的選票問題(某位候選人在整個計票過程中始終領先的機率)。它的連續對應物為布朗運動做同樣的事,以閉式形式給出布朗運動運行最大值與首次通過時間的分布。反射原理是一個美麗的例子,說明一個巧妙的一對一對應如何把困難的機率溶解為純粹的計數。
要求對稱漫步在時刻 n 之前達到高度 a 的機率,反射原理把觸及 a 的路徑與鏡像路徑相連,給出 P(直到時刻 n 的最大值至少為 a) = P(S_n 至少為 a) + P(S_n 大於 a) —— 約為尾端的兩倍(有微小調整),所以達到某個高水準的可能性,粗略地說,大約是停在那裡的兩倍。同樣的折疊給出選票結果:在一場 A 最終以 a 票對 b 票擊敗 B 的選舉中,A 在整個計票過程中始終領先的機率恰為 (a - b)/(a + b)。
在路徑首次觸及障壁之後將其反射:困難的受約束計數化為鏡像路徑的容易自由計數。
反射原理最簡單的形式仰賴漫步的對稱性(每一步向上與向下等機率)—— 乾淨的反射需要一個翻轉後看起來相同的過程。對非對稱漫步或一般過程,這個一對一對應必須調整、否則失效;切勿盲目套用對稱公式。