現在僅剩的問題,就是證明阿聰策略的期望停止時間有限了。

遞推法似乎行不通。事實上,用賭本和賭注

(m,n)

作為狀態時,在狀態圖上下一步能走的方向向量

(+n, -1)

(-n,+1)

還跟當前狀態有關。能不能先把這種複雜性消滅——找一種狀態表示法,使得每一步能走的方向向量跟當前狀態無關呢?

答案是能。還是注意到“一輸一贏”會使得賭本加1,賭注不變;同樣,“一贏一輸”也使得賭本加1,賭注不變。這表明,只要中途遊戲沒有結束,輸和贏的順序是可以交換的;最終的賭本和賭注僅取決於輸和贏的次數,而不取決於輸和贏的順序。假設到某個時刻為止,阿聰輸了

l

次,贏了

w

次,那麼總可以交換輸贏的順序,把

l

次輸放在前面,

w

次贏放在後面(就算中間輸光了,也讓他繼續賭下去)。

l

次輸的賭注分別是

1,2,\ldots,l

w

次贏的賭注分別是

l+1, l, \ldots, l-w+2

。此時阿聰的賭本

m

和賭注

n

就可以用

l

w

表示出來:

n = l-w+1

m = 2 - \sum_{i=1}^l i + \sum_{j=l-w+2}^{l+1} j = \frac{4 + (l+w) - (l-w)(l-w+2)}{2}

這就表明,

(l,w)

也可以用來表示狀態。每賭一局,要麼

l

加1,要麼

w

加1,但總之

l

w

的變化量與當前狀態無關了。遊戲結束的條件是

n = 0

m \le 0

,這兩個條件也都可以用

l

w

表示出來,前者是一條直線,後者是一條拋物線。畫出圖來,就一目瞭然了:

10036 賭徒的長征(4)——會長大的籠子

圖中,兩條黃線代表了遊戲結束的條件;紅色格子表示賭注減小到0,藍色格子表示輸光。阿聰從左下角的格子出發,每次只能向右或向上走一格,碰到黃線遊戲就結束了。遊戲能夠進行的區域(綠色格子)是越來越寬的。

現在,狀態表示足夠簡單了,但停止條件還比較複雜。能不能繼續化簡呢?能。上面的圖中,黃色的直線

l-w+1=0

恰好是拋物線的對稱軸,如果我們把座標系旋轉45度,拋物線的方程就能化簡。把

l-w+1

再反過來代換成

n

,同時令

t=l+w

,用

(n,t)

表示狀態,則狀態的轉移方式變成了每賭一局,

t

每加1,

n

可加1或減1;終止條件則化成

n = 0

n \ge \sqrt{t+5}

,簡單多了。事實上,把

t

看作時間,把賭注

n

Y_t

來表示,則

Y_t

就化成了如下的、帶移動吸收壁的一維隨機遊走過程:

帶移動吸收壁的一維隨機遊走:

設粒子初始位置為

Y_0 = 1

,每步的位移

Y_{t+1} - Y_t

等可能地取

\pm 1

。在

y=0

處有固定吸收壁,

y_t = \sqrt{t+5}

處有移動吸收壁,粒子碰到吸收壁則死亡。問粒子存活時間的期望是否有限?

阿聰的策略轉化到這裡,就有了一種柳暗花明又一村的感覺——問題成功脫離了賭博的背景,變成了一道比較一般的一維隨機遊走問題。事實上,有許多文獻研究過類似的問題,比如:

[1] [2] 研究了有兩個移動吸收壁

y = \pm \,c \sqrt{t+a}

的情況,吸收壁的移動速度是減慢的;

[3] 研究了有兩個移動吸收壁

y = \pm\, (ct+L)

的情況,吸收壁的移動速度是常數;

以上文獻研究的都是離散的一維隨機遊走,而 [4] 研究了連續的一維擴散在單側有吸收壁

y = \sqrt{At}

(另一側自由)和雙側有吸收壁

y = \pm \sqrt{At}

時的情形。這兩種情形分別被形象地稱為“後退的懸崖”和“會長大的籠子”。

阿聰策略轉化成的問題,就是一個“會長大的籠子”。但很不幸的是,上述文獻研究都並不是我們感興趣的情景,因為我們的籠子左側是不會長大的。要解決我們的問題,還得自力更生。

10036 賭徒的長征(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。