　　上一篇文章中，我们把阿聪的策略转化成了一个一维随机游走 Y_t ，初始位置为 Y_0 = 1 ，左侧有固定吸收壁 y=0 ，右侧有移动吸收壁 $y = \sqrt{t+5}$ 。我们的目标是证明粒子的期望存活时间有限。为了寻找思路，我首先模拟了一下粒子位置的分布随时间的变化情况。

　　用 p_t 表示时刻粒子位置的分布列，它是一个长度为 $l_t = \lceil \sqrt{t+5} \rceil - 1$ 的列向量，其中第个元素表示粒子处于位置的概率。初始时 $p_0 = [1 \;\; 0]^T$ 。从 $p_{t-1}$ 出发求 p_t 时，要先把 $p_{t-1}$ 与向量 $[1/2 \;\; 0 \;\; 1/2]^T$ 卷积。卷积得到的向量中，第一个元素要去掉，代表被固定壁吸收；最后一个元素也要去掉，代表被移动壁吸收——但当 $l_t = l_{t-1} + 1$ 时除外，因为这时移动吸收壁让出一个位置。模拟发现， p_t 一直保持着如下图所示的“正弦刺猬”的形状，只是幅度在不断减小。

　　我敏锐地意识到：这可能是某个变换矩阵特征值绝对值最大的特征向量！没错。把 $p_{t-1}$ 与 $[1/2 \;\; 0 \;\; 1/2]^T$ 卷积然后掐头去尾，相当于用一个矩阵去乘以 $p_{t-1}$ ，这个矩阵是 $A_{l_t} = \frac{1}{2} \left[ \begin{array}{ccccc}0 & 1 & & & \\1 & 0 & 1 & & \\& 1 & 0 & \ddots & \\& & \ddots & \ddots & 1 \\& & & 1 & 0\end{array} \right]$ ，阶数与 p_t 的长度 l_t 相同。在移动吸收壁两次让出位置之间的时间内，这个矩阵会反复作用于粒子位置的分布列上。矩阵的特征向量可以看成一组基，把分布列按这组基分解，则在矩阵反复作用的过程中，特征值绝对值最大的分量（称为“主分量”）衰减得是最慢的，足够长时间后，就可以认为只剩下主分量了。

　　因为有“掐头去尾”的操作，矩阵 $A_{l_t}$ 并不是一个循环矩阵，它的特征向量也就不是傅里叶变换的基了。不过， $A_{l_t}$ 的基仍然是一系列正弦函数。具体来说，把 $A_{l_t}$ 分解成 $A_{l_t} = V_{l_t} D_{l_t} V_{l_t}^T$ ，则有

★ $V_{l_t} = \sqrt{\frac{2}{l_t + 1}} \left[ \sin \left( \frac{ij}{l_t+1} \pi \right) \right]_{i,j = 1 \ldots l_t}$
★ $D_{l_t} = \text{diag} \left[ \cos \left(\frac{i}{l_t+1} \pi \right) \right]_{i=1 \ldots l_t}$

画成图片更容易理解：

矩阵 $V_{l_t}$ 的每一列是一个正弦函数，第1列在 l_t+1 个点内完成了半个周期，第2列在 l_t+1 个点内完成了一个周期……依此类推。它们构成一组单位正交基。其中第一个基（振荡最慢的）和最后一个基（振荡最快的）的特征值最大，分别是 $\pm \cos \left( \frac{\pi}{l_t+1} \right)$ 。这两个基以相同的系数相加或相减，就能得到“正弦刺猬”。

　　如果吸收壁永远不动，那么随着时间的流逝，粒子位置的分布列 p_t 中确实会只剩下两个主分量。但是，移动吸收壁不时地让出一个位置，导致 $A_{l_t}$ 阶数增加，对应的特征向量也会发生变化（简称“换基”）。模拟发现，每次换基之后，把分布列按新的基重新分解，各个分量又都会获得不可忽略的系数，所以只考虑主分量是不严谨的。

　　没关系，那我们就把所有分量一起考虑。设 $p_{t-1}$ 与 p_t 长度相同，则在由 $p_{t-1}$ 推出 p_t 的过程中，没有发生“换基”， p_t 就等于 $A_{l_t} p_{t-1}$ 。用 v_j 代表 $V_{l_t}$ 的第列，其特征值为 d_j 。把 $p_{t-1}$ 按各个 v_j 分解，得到 $p_{t-1} = \sum\nolimits_j a_j v_j$ 。由 v_j 的正交性，可得 $p_t = \sum\nolimits_j d_j a_j v_j$ 。考虑 $p_{t-1}$ 与 p_t 的2范数：

★ $||p_t||_2^2 = \sum\nolimits_j (d_j a_j)^2 \le \sum\nolimits_j (d_1 a_j)^2 = d_1^2 ||p_{t-1}||_2^2$

故有

★ $\frac{||p_t||_2}{||p_{t-1}||_2} \le \cos \left( \frac{\pi}{l_t+1} \right)$

若 p_t 比 $p_{t-1}$ 长一个元素，那么 p_t 可以看作先在 $p_{t-1}$ 后面添一个0，再与 $A_{l_t}$ 相乘而得。添0不改变2范数，所以上式在发生“换基”时也成立。这是第一次放缩。

　　对上式取个对数，并利用 $\ln\cos(x)$ 在 $x \rightarrow 0$ 时与 -x^2/2 同阶，得到

★ $\ln||p_t||_2 - \ln||p_{t-1}||_2 \lesssim - \frac{1}{2} \left( \frac{\pi}{l_t+1} \right)^2$

（本文中 $A \lesssim B$ 表示“的阶不超过”）

再把 $l_t = \lceil \sqrt{t+5} \rceil - 1$ 代进去，忽略取整号和常数5，得到

★ $\ln ||p_t||_2 - \ln ||p_{t-1}||_2 \lesssim - \frac{\pi^2}{2t}$

求个和，就能得到 $\ln ||p_t||_2 \lesssim -\frac{\pi^2}{2} \ln t$ ，即 $||p_t||_2 \lesssim t^{-\frac{\pi^2}{2}}$ 。

　　算了半天 p_t 的2范数，有什么用呢？它跟粒子被吸收的时刻有什么关系？答案是这样： p_t 的1范数，也就是它的所有元素之和，等于粒子到了时刻还没有被吸收的概率，即 P(T>t) = ||p_t||_1 。而1范数和2范数之间有如下关系：

★ $1 \le \frac{||p_t||_1}{||p_t||_2} \le \sqrt{l_t}$

其中，左边的等号在 p_t 仅有一个元素非0（分布极端集中）时取得，右边的等号在 p_t 的所有元素都相等（分布极端均匀）时取得。我们在这儿要用右边的不等号来限定 ||p_t||_1 的阶：

★ $P(T>t) = ||p_t||_1 \le \sqrt{l_t} \, ||p_t||_2 \lesssim t^{-\frac{\pi^2}{2} + \frac{1}{4}}$

这是第二次放缩。

　　现在离答案只有一步之遥啦！对上式取个差分，就能得到 $P(T = t) \lesssim t^{-\frac{\pi^2}{2} - \frac{3}{4}}$ ，而我们要求的 $E(T) = \sum_{t=1}^\infty t P(T = t) \lesssim \sum_{t=1}^\infty t^{-\frac{\pi^2}{2} + \frac{1}{4}}$ 。通项的阶数约为-4.6848，小于-1，级数收敛，所以粒子的期望存活时间有限。

　　本文在分析矩阵与向量相乘的时候，采用了把向量按矩阵的特征向量分解的方法。这种方法称为“谱分析法”，“谱”指的就是分解后各特征向量的系数。如果矩阵恰好是循环卷积操作对应的矩阵（称为Circulant matrix），则各个特征向量恰好就是傅里叶变换的基，“谱”也就成了大家熟悉的“频谱”。有些同学可能看过我2年前在人人网上写的《用傅里叶变换玩转椭圆》一文，其中用的就是谱分析法；今天，我们又一次领略到了谱分析法的“靠谱”。

　　我在文中使用了两次放缩，求出 P(T>t) 的阶数的上界为 $-\frac{\pi^2}{2} + \frac{1}{4} \approx -4.6848$ 。我曾经认为两次放缩都恰好没有损失阶数，模拟结果也与这个阶数很接近。不过，@Octolet通过把离散一维游走近似成连续一维扩散，算出 P(T>t) 的阶数其实等于-4.7201。更细致的模拟发现， P(T>t) 的阶数小于-4.715，所以@Octolet的结果很可能是正确的，而在我放缩的过程中，阶数有损失。

ITPub博客

10037 赌徒的长征(5)——靠谱的谱分析

最新文章