一維隨機遊走，帶移動吸收壁，吸收的期望時間是否有限？

01-25

依然聲明不是作業題。雖然看起來越來越像作業題了，但可能仍有相當的難度。
我費了一天的勁，終於把賭徒問題進階版化歸成了如下一個形式很簡單的問題。化歸過程等我下周有時間寫個專欄。化歸後的問題如下：
粒子在數軸上隨機遊走，初始位置為 $X_0 = 1$ ，每次等概率地向左或向右走1步，即 $X_{n+1} = X_n pm 1$ 。
粒子的兩側均有吸收壁。左側的吸收壁固定在 $x=0$ 處；右側的吸收壁會移動，位置為 $W_n = sqrt{n+5}$ 。
如果 $X_n = 0$ 或 $X_n ge W_n$ ，則粒子在 $n$ 時刻被吸收。

問：粒子被吸收的時刻的期望是否有限？
========================
補充一下化歸過程：
我注意到，原問題的狀態的兩個要素（賭本和賭注）僅由輸贏的次數決定，而與輸贏的順序無關。
連續的一輸一贏或一贏一輸，對賭注沒有影響，對賭本的影響是加1。
設一共輸了 $l$ 次，贏了 $w$ 次，則 $l-w ge -1$ 。
當 $l-w ge 0$ 時，輸贏可以抵消 $w$ 次（影響是賭本加 $w$ ，賭注不變），剩下的 $l-w$ 次輸的錢數正是 $1,ldots,l-w$ ，影響是賭本減 $frac{(l-w)(l-w+1)}{2}$ ，賭注加 $l-w$ 。故最終的賭本是 $m = 2 + w - frac{(l-w)(l-w+1)}{2}$ ，賭注是 $x=l-w+1$ （以前賭注用 $n$ 表示，現在改用 $x$ 避免混亂）。
當 $l-w = -1$ （最終贏了）時，輸贏可以抵消 $l$ 次，還剩下一次贏1塊錢，可以發現上面賭本和賭注的表達式也成立。
而賭博進行的時間為 $n=l+w$ 。把賭本 $m$ 用時間 $n$ 和賭注 $x$ 表示出來，結果是 $m = frac{n+5-x^2}{2}$ 。
遊戲結束的條件是 $x = 0$ 或 $m le 0$ ，後者即 $x ge sqrt{n+5}$ 。

我來寫下我的計算過程吧。

之前說的漏洞應該算是修復了，算出來的結果是 $P(N=n) lesssim n^{-frac{pi^2}{2}-frac{3}{4}}$ 。

因為指數小於-2，所以期望吸收時間有限。

雖然上面的式子只是一個上界，但那個指數跟模擬結果居然是吻合的……

下面是計算過程。

定義 $p^{(n)}$ 為 $X_n$ 的分布列，這是一個長度為 $l_n = lceil W_n ceil -1$ 的列向量。

從 $p^{(n-1)}$ 到 $p^{(n)}$ 的遞推關係為 $p^{(n)} = A_{l_n} p^{(n-1)}$ ，

其中 $A_{l_n}$ 是一個形如 $frac{1}{2} left[ egin{array}{ccccc} 0 1 \ 1 0 1 \ 1 0 ddots \ ddots ddots 1 \ 1 0 end{array} ight]$ 的 $l_n$ 階方陣。

如果 $p^{(n-1)}$ 的長度小於 $l_n$ （吸收壁又讓出一個位置），則要先在 $p^{(n-1)}$ 末尾添0湊齊長度。

方陣 $A_{l_n}$ 可以進行特徵值分解，得到 $A_{l_n} = V_{l_n} D_{l_n} V_{l_n}^T$ ，其中

$V_{l_n} = sqrt{frac{2}{l_n + 1}} left[ sin left( frac{ij}{l_n+1} pi ight) ight]_{i,j = 1 ldots l_n}$ ， $D_{l_n} = ext{diag} left[ cos left(frac{i}{l_n+1} pi ight) ight]_{i=1 ldots l_n}$ 。

畫成圖片更容易理解：

最初我還真把 $p^{(n)}$ 按 $V_{l_n}$ 給分解了……

其實並無必要，我們只需關注 $D_{l_n}$ 裡面絕對值最大的特徵值，這個特徵值是 $cos left( frac{pi}{l_n+1} ight)$ 。

一個向量與 $A_{l_n}$ 相乘，它的2範數與原來的2範數的比值，一定不會超過這個特徵值。

也就是說， $||p^{(n)}||_2 le ||p^{(n-1)}||_2 cdot cos left( frac{pi}{l_n+1} ight)$ ，這是第一次放縮。

我們的目的只是證明停時期望有限，並不需要求出具體的值，所以計算過程中我們可以進行各種同階代換。

對上式取個對數，並利用 $lncos(x)$ 在 $x ightarrow 0$ 時與 $-x^2/2$ 同階，得到

$ln ||p^{(n)}||_2 lesssim ln ||p^{(n-1)}||_2 - frac{1}{2} left( frac{pi}{l_n+1} ight)^2$

把 $l_n = lceil W_n ceil -1$ 和 $W_n = sqrt{n+5}$ 代進去，忽略取整號和常數5，得到

$ln ||p^{(n)}||_2 lesssim ln ||p^{(n-1)}||_2 - frac{pi^2}{2n}$

求個和，就能得到 $ln ||p^{(n)}||_2 lesssim -frac{pi^2}{2} ln n$

即 $||p^{(n)}||_2 lesssim n^{-frac{pi^2}{2}}$

$p^{(n)}$ 與吸收時間 $N$ 的分布的關係是這樣的： $P(N > n) = ||p^{(n)}||_1$ ，1範數即所有元素求和。

一個長度為 $L$ 的向量 $v$ ，其1範數和2範數之間有如下關係：

$||v||_2 le ||v||_1 le sqrt{L} ||v||_2$ ，

其中左邊的等號在 $v$ 僅有一個分量非零（分布極端集中）時取得，

右邊的等號在 $v$ 的所有分量絕對值都相等（分布極端均勻）時取得。

我們現在要用的是右一半。 $p^{(n)}$ 的長度為 $l_n = lceil sqrt{n+5} ceil$ ，忽略取整號和常數5，則有

$||p^{(n)}||_1 lesssim n^{frac{1}{4}} ||p^{(n)}||_2 = n^{-frac{pi^2}{2} + frac{1}{4}}$ ，這是第二次放縮。

現在有了 $P(N>n) lesssim n^{-frac{pi^2}{2}+frac{1}{4}}$ ，取個差分就有 $P(N=n) lesssim n^{-frac{pi^2}{2}-frac{3}{4}}$ 。

而吸收時間的期望 $E(N) = sum_{n=1}^infty n P(N=n) lesssim sum_{n=1}^infty n^{-frac{pi^2}{2}+frac{1}{4}}$ ，

通項指數小於-1，故級數收斂，吸收時間的期望有限。

==============================

模擬發現， $P(N=n)$ 的階真的就是 $n^{-frac{pi^2}{2}-frac{3}{4}}$ ，這說明兩次放縮都沒有影響階。

對於第一次放縮，我最初的想法是，方陣作用足夠多次後，只有特徵值最大的分量能夠留下來，所以相鄰兩個 $||p^{(n)}||_2$ 之比就是最大的特徵值。

不過模擬發現，每次吸收壁讓出一個位置時，方陣階數增加會導致特徵向量改變，這一變就使得特徵值並非最大的特徵向量又有了明顯的係數。

好在每次發生這樣的事情的時候，特徵值最大、次大、第三大……特徵向量的係數幾乎總是保持相同的比例，特徵值最大的分量依然佔主導地位，這使得第一次放縮確實不會影響到階。

對於第二次放縮，我觀察到 $p^{(n)}$ 的形狀基本是恆定的，一直是佔滿兩個吸收壁之間空間的、半個周期的正弦。這依然是因為只有特徵值最大的分量佔主導地位。

這使得 $p^{(n)}$ 一直更接近分布均勻的極端而不是分布集中的極端，故第二次放縮也不影響階。

==============================

我還考慮了一下 $W_n = lceil C(n+b)^alpha ceil$ 的一般情況，不過這時，放縮就不一定不影響階了。

特別地，當 $alpha>1/2$ 時，吸收壁移動較快，粒子位置分布的擴散速度趕不上吸收壁的移動速度，這就會導致粒子位置分布遠離「均勻」的極端，第二次放縮就會影響階了。

（但粒子畢竟還在擴散，所以其位置分布也到達不了「集中」的極端。）

更新:

此處更新是因為Mathematica 10.3終於支持解本徵值問題了(贊一個).

用Mathematica處理下面的本徵值問題(詳見原答案):

sol = NDEigensystem[{(-(1/4) + y^2/8) *u[y] - 1/2*(u^[Prime][Prime])[y], DirichletCondition[u[y] == 0, True]}, u[y], {y, 0, 1}, 1];


sol[[1, 1]]

(* 4.72011 *)

跟原來的結果是一樣的. 現在還可以畫出函數 $q(y)$ 的形狀:

q[y_] := -Evaluate@(sol[[2, 1]])*Exp[-(y^2/4)];

Plot[{First@FindMaximum[q[y], {y, 0}]*Sin[[Pi]*y], q[y]}, {y, 0, 1}, PlotLegends -&> {"C[CenterDot]Sin(y)", "q(y)"}, ImageSize -&> 400]

可見 @王贇 Maigo 的答案中說的這個函數接近一個正弦函數

對於第二次放縮，我觀察到 $p^{(n)}$ 的形狀基本是恆定的，一直是佔滿兩個吸收壁之間空間的、半個周期的正弦。這依然是因為只有特徵值最大的分量佔主導地位。
(一維隨機遊走，帶移動吸收壁，吸收的期望時間是否有限？ - 王贇 Maigo 的回答)

是非常正確的.

__________原答案分割線__________

雖然很忙, 但是感覺很有意思, 所以還是答一發.

令這個帶吸收壁的隨機遊走結束之前走完的步數為 $N$ , 則事件 ${N>n}$ 相當於對 $i = 1...n$ , 均滿足 $0 < X_i < sqrt{i+5}$ .

注意到 $ext{Var}(X_n) = n$ . 當 $n$ 很大時, $X_n$ 的分布趨於一個Wiener Process (標準的布朗運動). 所以, 我們可以把這個問題給連續化, 即考慮一個吸收壁為 $0$ 和 $sqrt{t+5}$ 的Wiener Process $W(t)$ 的First Exit Time問題, 只要能求出First Exit Time的PDF就可以了.

因為題主問的只是first exit time的期望值是否有限, 所以常數5並不重要, 我們考慮 $sqrt{t}$ 即可. 注意這裡在 $t = 0$ 是有奇異性, 但是我們可以選擇合適的初始條件, 比如從 $t = 1, W(1) = 1/2$ 出發之類的. 這些並不影響first exit time的PDF的漸進形式.

但是, 變邊界的First Exist Time問題很麻煩, 我們注意到:

$0<W(t)<$ $sqrt{t}$ 等價於 $0< frac{W(t)}{sqrt{t}} < 1$ . 所以, 我們可以考慮另一個Process, 記為 $Y(t) = frac{W(t)}{sqrt{t}}$ .

由Itos Lemma可知 $dY(t) = -frac{W(t)}{2 t^{3/2}} dt + frac{1}{sqrt{t}} dW(t) = -frac{Y(t)}{2t}dt+frac{1}{sqrt{t}} dW(t)$

因此 $Y(t)$ 也是一個Diffusion Process. 我們現在只需要求 $Y(t)$ 以 $0$ 和 $1$ 為邊界的first exit time問題即可.

求解這種問題, 可以用Fokker-Planck Equation. 一般地來說, 對於一個Diffusion Process

$dZ(t) = mu(Z(t), t) dt + sigma(Z(t), t)dW(t)$ , 其PDF滿足一個PDE:

$frac{partial }{partial t}p(z,t)=-frac{partial }{partial z} left[p(z,t) mu (z,t) ight]+frac{1}{2}frac{partial ^2}{partial z^2}left[p(z,t) sigma (z,t)^2 ight]$

對於 $Y(t)$ , 其F-P方程為:

$frac{partial}{partial t}p(y,t) = frac{1}{2t} left(p(y,t) + y frac{partial}{partial y}p(y,t) + frac{partial^2}{partial y^2} p(y,t) ight)$

顯然應該作代換 $xi = log t$ , 則有

$2frac{partial}{partial xi}p(y,xi) = p(y,xi) + y frac{partial}{partial y}p(y,xi) + frac{partial^2}{partial y^2} p(y,xi)$

當然, 由於這是個帶吸收壁的diffusion, 我們還需要邊界條件

$p(0, xi) = 0, p(1, xi) = 0$

上面這個PDE是可以分離變數的, 即有

$p(y, xi) = q(y) u(xi)$ , 則有:

$frac{u^{prime}(xi)}{u(xi)} = k$ ,

$q^{prime prime}(y) + y ,q^{prime}(y) + (1-2k)q(y) = 0, ;q(0) = 0, ;q(1) = 0$

$q(y)$ 的部分是個本徵值問題. 我們做變換 $q(y) = e^{-a y^2}r(y)$ , 則當 $a = 1/4$ 時, 可將一階導數項消去, 得到:

$r^{prime prime}(y) + left(-2 k-frac{y^2}{4}+frac{1}{2} ight)r(y)=0$ .

顯然這個本徵值問題只能有 $k < 0$ 的本徵值. 我們的目的是要看PDF在 $t$ 很大時的漸進行為, 所以我們只需要絕對值最小的那個本徵值即可.

用Mathematica以 $r(0) = 0$ 為條件, 解得:

其中 $D_{-2 k}(y)$ 是所謂的ParabolicCylinderD函數.

現在要選取絕對值最小的 $k$ 使得 $r(1) = 0$ . 經過數值運算, 發現絕對值最小的 $k$ 為

$-4.7201$ .

這意味著 $u(xi) sim e^{-4.7201 xi}$ . 因此, $p(y, t) sim e^{-y^2/4};r(y);t^{-4.7201}$ . 注意到 $int_{0}^{1}p(y,n)dy$ 就是 $P(N > n)$ . 所以, 可以得到結論 $P(N > n) sim n^{-4.7201}$ . 因此, 原來那個隨機遊走的步數期望是有限的.

@王贇 Maigo 的答案說模擬所得的階數就是 $P(N > n) sim n^{-frac{pi ^2}{2} + frac{1}{4}}$ , 即大概 $P(N > n) sim n^{-4.6848}$ , 跟我這個略有不同, 我猜他的放縮中還是改變了階數, $-frac{pi^2}{2}+frac{1}{4}$ 應該是個比較好的近似吧.

以上.

我能證出來如果吸收壁是 $epsilonsqrt{n}$ ，那麼對比較小的 $epsilon$ , 期望是有限的，但目前還沒有把constant改進到1……

大概的思路如下：我們把實數軸分成 $[0,cN],[cN,c^2N],dots,[c^kN,c^{k+1}N],dots$

如果在前k段都沒有碰到吸收壁，那麼 $X_{c^kN}in[0,epsilonsqrt{c^kN}]$ ,

於是第k+1段碰到吸收壁的概率(第二步根據反射原理)

$egin{aligned} p_{k+1} ge P( max_{nle (c-1)c^kN} (X_{c^{k}N+n}-X_{c^kN})ge epsilonsqrt{c^{k+1}N})vee P( min_{nle (c-1)c^kN}(X_{c^{k}N+n}-X_{c^kN})<-epsilonsqrt{c^kN})\ gtrsim 2P( (X_{c^{k+1}N}-X_{c^kN})ge epsilonsqrt{c^{k+1}N})vee 2P( (X_{c^{k+1}N}-X_{c^kN})<-epsilonsqrt{c^kN})\ approx 2P(N(0,1)>epsilonsqrt{frac{c}{c-1}})vee 2P(N(0,1)<-epsilonsqrt{frac{1}{c-1}})=:p_{c,epsilon}. end{aligned}$

而最終的期望則有上界 $mathbb{E}Tlesssim sum_{k=1}^infty (c^{k+1}-c^k)N (1-p_{epsilon,c})^k$ 。

所以如果 $1-p_{epsilon,c}<1/c$ ，那麼這個期望就是有界的，which當 $epsilon$ 足夠小的時候是成立的。

但貌似wolfram alpha認為 $epsilon=1$ 不夠小。

看了王贇的答案感覺還是存在相變的，就是說這個問題對足夠大的 $epsilon$ ，可能這個hitting time的期望就是無窮……那樣的話究竟期望有限和期望無窮的臨界值在哪裡就很好玩了。當然我這個辦法幾乎一定得不到sharp constant，也許加上LDP的計算會好一些。還是等Maigo大神慢慢update吧……

是有限的，證明有時間再補。

我討論一下單側吸收的問題：

即x=0時候結束

假設時間等同於我所說的「步數」，設為n

第一次吸收的幾率，是0.5

第二次吸收的幾率是0.25（要接下來連續兩次向0走）

第三次就是0.125

算下來是1/2*1+1/4*2……

求和怎麼求容我想想，好像是1？大概算的有問題

====

好像有疏漏

無右吸收壁的情況都是有限的，就一類卡特蘭級數，何況這個。