現在僅剩的問題,就是證明阿聰策略的期望停止時間有限了。
遞推法似乎行不通。事實上,用賭本和賭注
作為狀態時,在狀態圖上下一步能走的方向向量
和
還跟當前狀態有關。能不能先把這種複雜性消滅——找一種狀態表示法,使得每一步能走的方向向量跟當前狀態無關呢?
答案是能。還是注意到“一輸一贏”會使得賭本加1,賭注不變;同樣,“一贏一輸”也使得賭本加1,賭注不變。這表明,只要中途遊戲沒有結束,輸和贏的順序是可以交換的;最終的賭本和賭注僅取決於輸和贏的次數,而不取決於輸和贏的順序。假設到某個時刻為止,阿聰輸了
次,贏了
次,那麼總可以交換輸贏的順序,把
次輸放在前面,
次贏放在後面(就算中間輸光了,也讓他繼續賭下去)。
次輸的賭注分別是
;
次贏的賭注分別是
。此時阿聰的賭本
和賭注
就可以用
和
表示出來:
★
★
這就表明,
也可以用來表示狀態。每賭一局,要麼
加1,要麼
加1,但總之
和
的變化量與當前狀態無關了。遊戲結束的條件是
或
,這兩個條件也都可以用
和
表示出來,前者是一條直線,後者是一條拋物線。畫出圖來,就一目瞭然了:
圖中,兩條黃線代表了遊戲結束的條件;紅色格子表示賭注減小到0,藍色格子表示輸光。阿聰從左下角的格子出發,每次只能向右或向上走一格,碰到黃線遊戲就結束了。遊戲能夠進行的區域(綠色格子)是越來越寬的。
現在,狀態表示足夠簡單了,但停止條件還比較複雜。能不能繼續化簡呢?能。上面的圖中,黃色的直線
恰好是拋物線的對稱軸,如果我們把座標系旋轉45度,拋物線的方程就能化簡。把
再反過來代換成
,同時令
,用
表示狀態,則狀態的轉移方式變成了每賭一局,
每加1,
可加1或減1;終止條件則化成
或
,簡單多了。事實上,把
看作時間,把賭注
用
來表示,則
就化成了如下的、帶移動吸收壁的一維隨機遊走過程:
帶移動吸收壁的一維隨機遊走:
設粒子初始位置為
,每步的位移
等可能地取
。在
處有固定吸收壁,
處有移動吸收壁,粒子碰到吸收壁則死亡。問粒子存活時間的期望是否有限?
阿聰的策略轉化到這裡,就有了一種柳暗花明又一村的感覺——問題成功脫離了賭博的背景,變成了一道比較一般的一維隨機遊走問題。事實上,有許多文獻研究過類似的問題,比如:
[1] [2] 研究了有兩個移動吸收壁
的情況,吸收壁的移動速度是減慢的;
[3] 研究了有兩個移動吸收壁
的情況,吸收壁的移動速度是常數;
以上文獻研究的都是離散的一維隨機遊走,而 [4] 研究了連續的一維擴散在單側有吸收壁
(另一側自由)和雙側有吸收壁
時的情形。這兩種情形分別被形象地稱為“後退的懸崖”和“會長大的籠子”。
阿聰策略轉化成的問題,就是一個“會長大的籠子”。但很不幸的是,上述文獻研究都並不是我們感興趣的情景,因為我們的籠子左側是不會長大的。要解決我們的問題,還得自力更生。
參考文獻
[1] David Blackwell and David Freedman, “A remark on the coin tossing game”,
The Annals of Mathematical Statistics
, Vol。 35, No。 3 (Sep。, 1964), pp。 1345-1347。
[2] L。 A。 Shepp, “A first passage problem for the Wiener process”,
The Annals of Mathematical Statistics
, Vol。 38, No。 6 (Dec。, 1967), pp。 1912-1914。
[3] Alan J Bray and Richard Smith, “The survival probability of a diffusing particle constrained by two moving, absorbing boundaries”,
Journal of Physics A: Mathematical and Theoretical
40。10 (2007): F235。
[4] P。 L。 Krapivsky and S。 Redner, “Life and death in an expanding cage and at the edge of a receding cliff”,
American Journal of Physics
64。5 (1996): 546-551。