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

02-03

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

　　遞推法似乎行不通。事實上，用賭本和賭注 $(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$ 表示出來，前者是一條直線，後者是一條拋物線。畫出圖來，就一目了然了：

圖中，兩條黃線代表了遊戲結束的條件；紅色格子表示賭注減小到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}$ 時的情形。這兩種情形分別被形象地稱為「後退的懸崖」和「會長大的籠子」。

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

參考文獻

[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.