第4卷第8章孤零零的随机漫步

从钢琴旋律的受限路径计数出发，用动态规划与反射原理得到165，再把两国流浪写成转移矩阵，通过凯莱-哈密顿定理、特征值、特征向量与对角化求出第n年概率。

学习目标

能把钢琴旋律翻译成受限路径，用动态规划和反射原理分别数出165条合法路径
能解释随机漫步、两国转移矩阵与马尔可夫性，并检查每一步概率是否守恒
能从特征方程求出两个特征值和特征向量，利用矩阵对角化得到第n年的概率
能用交互实验区分“两步路径的枚举”“长期稳态”和“初始偏差衰减”三种证据

从雨滴和琴键开始：每一步都摇摆，整体仍可计算

章首借孤岛上的呼喊问“你一直在哪里”。本章把这个问题变成数学：旋律在琴键上上下移动，爱丽丝在两个国家之间往返，人的心也在等待、决定与不安之间摇摆。单独一步似乎没有方向，许多步却能由路径、矩阵和特征模式准确描述。

先预测：

12个音从do开始、到高3级的fa结束，为什么实际上只有11次移动，而且必为上7步、下4步？
C(11,7)=330为什么不是答案，怎样精确排除曾跌到do以下的路径？
转移矩阵平方为什么表示两年，而不只是四个代数式？
特征值1与1-p-q分别保存和消除什么信息？

8.1 家

8.1.1 雨天的周六

周六下午连续下雨，空气闷热。“我”准备考试，尤里带着学习用品来房间，却几乎没有进展。她几次用“没什么”挡开询问，最后低声抱怨雨天糟透了。

章名中的“孤零零”先以情绪出现。尤里不是没有问题，而是不知道怎样说；她等待上一章那封信的回音，心像尚未决定下一步方向的游走点。

8.1.2 下午茶时间

妈妈端来水羊羹，尤里立刻切换成认真学习的样子，还称赞门口的紫阳花插花。妈妈谈和式点心中的“感怀四季之心”，尤里的情绪也在点心与对话中稍稍回升。

这里没有数学式，却示范了后文的状态变化：同一个人会因输入与环境改变状态。重要的是找出状态、允许的转移以及每次转移的规则。

8.1.3 钢琴问题

尤里从数学智力题书中找到：

以do为开始音，以高3个音阶的fa为结束音；
旋律由12个音组成；
相邻两个音必须对应相邻白键；
不能使用比开始音do更低的音。

例如，do→re→do→re→mi→re→do→re→mi→fa→so→fa满足条件；若一步从mi跳到do，或连续两次停在mi，就违反“只走相邻白键”。

“我”没有马上套排列组合，而是先确认题意。把旋律画成：横轴是第几个音，纵轴是相对do的音高。题目变成“从高度0出发，走11步到高度3，且始终不低于0的有多少条”。

8.1.4 旋律示例

原题旋律画成锯齿线。尤里又画了“先尽量上升再下降”和“在低处来回后突然上升”的例子。不同形状让不变量显现。

设上升步数为u，下降步数为d。12个音之间只有11段移动，因此：

u+d=11.

结束音比开始音高3级，因此：

u-d=3.

联立得到：

u=7, \qquad d=4.

所以每条候选旋律都只是7个上箭头和4个下箭头的一种排列。但不能立刻写C(11,7)：有些排列会先向下，或中途跌到高度负数，使用了比do低的音。

8.1.5 解题方法一：毅力比拼

第一种解法逐格累加，类似泰朵拉靠毅力列完所有情况。令c(t,h)表示走t步后到达高度h且从未低于0的路径数。初值与边界是：

c(0,0)=1, \qquad c(0,h)=0\quad(h\ne0), \qquad c(t,h)=0\quad(h<0).

到达(t+1,h)的最后一步，要么从h-1向上，要么从h+1向下，因此：

c(t+1,h)=c(t,h-1)+c(t,h+1).

这就是。从左到右填表：

time 0:  h0=1
time 1:  h1=1
time 2:  h0=1, h2=1
time 3:  h1=2, h3=1
...
time 11: h1=132, h3=165, h5=110, h7=44, h9=10, h11=1

终点是t=11、h=3，所以：

c(11,3)=165.

Piano Path Grid：终点条件只检查最后一格，全过程条件还要检查边界以下的每一格。

每个格子的数都来自左上与左下之和。边界以下固定为0，正是“不使用低于do的音”的算法化表达。

8.1.6 解题方法二：一招定胜负

第二种解法先暂时允许路径越界。所有7上4下的排列有：

\binom{11}{7}=\binom{11}{4}=330

条。然后精确数出坏路径。

在高度-1处放一面水平镜子。对每条曾低于0的路径，找到它第一次到达-1的位置，把此后所有上、下方向互换。原终点高度3会映到镜像终点高度-5。反向操作也唯一，因此坏路径与从0走到-5的11步路径。

到-5必须上3步、下8步，所以坏路径数为：

\binom{11}{3}=165.

这种通过首次越界点翻转路径的给出：

\binom{11}{7}-\binom{11}{3} =330-165 =165.

两种解法得到同一答案。动态规划逐格构造所有合法路径；反射原理则把非法路径整体搬到另一个容易计数的集合。

Reflection Bijection：坏路径的首次越界点是唯一切口，所以翻转与反向翻转互为逆操作。

8.1.7 一般化

设路径上升u步、下降d步，终点高度为u-d，仍要求不低于0。所有路径数是：

\binom{u+d}{d}.

反射后的坏路径要下降d-1步，因此：

N(u,d) = \binom{u+d}{d} - \binom{u+d}{d-1}.

通分化简：

\begin{aligned} N(u,d) &= \frac{u-d+1}{u+1} \binom{u+d}{d}. \end{aligned}

令：

a=u+1, \qquad b=d,

则旋律有a+b个音，结束音比开始音高a-b-1级，答案写成：

N(a,b) = \frac{a-b}{a+b} \binom{a+b}{b}.

代入a=8、b=4：

N(8,4) = \frac4{12}\binom{12}{4} =\frac13\cdot495 =165.

不只给出答案，还通过变量替换显露受限路径的统一结构。

8.1.8 摇摆不定的心

解题让尤里暂时轻松，但她终于说出真正烦恼：按照泰朵拉建议寄出的信没有回音。寄信以后无法保证今天、明天或任何一天收到回复。她背对书架说自己不在意，反而暴露出有多在意。

“我”只能提出一个可能解释：对方刚搬家，也许很忙。数学路径有明确边界和终点，等待回信却没有已知的转移概率。尤里的心仍在未知未来中摇摆。

8.2 清晨的上学路

随机漫步

雨中的上学路上，泰朵拉提到自己准备拒绝米尔嘉的一项请求，又转而询问最近的问题。听完钢琴旋律，她联想到random walk。

是的总称。若抛公平硬币，正面让钢琴音高升一级，反面降一级，位置序列可写为：

S_n=X_1+\cdots+X_n, \qquad X_k\in\{+1,-1\}.

这叫一维随机漫步。钢琴音高只有高低一个方向；平面上的粒子才有二维方向。

泰朵拉还联想到物理课看到的：花粉中的微粒在水里不断晃动。钢琴路径不是布朗运动本身，却共享“局部随机移动形成整体轨迹”的建模直觉。

8.3 中午的教室

8.3.1 矩阵的练习

午休时米尔嘉请假，泰朵拉带便当来到“我”的教室。她说自己已经不会混淆矩阵的行与列，也开始喜欢从乘积和中找模式。“我”用一个二阶矩阵继续练习：

A= \begin{pmatrix} a&b\\c&d \end{pmatrix}.

直接平方：

A^2 = \begin{pmatrix} a^2+bc&ab+bd\\ ac+cd&bc+d^2 \end{pmatrix}.

再计算：

(a+d)A = \begin{pmatrix} a^2+ad&ab+bd\\ ac+cd&ad+d^2 \end{pmatrix}.

相减后两个非对角元素消失：

A^2-(a+d)A = \begin{pmatrix} bc-ad&0\\ 0&bc-ad \end{pmatrix} =-(ad-bc)I.

把a+d认作，把ad-bc认作行列式，就得到：

A^2-\operatorname{tr}(A)A+\det(A)I=O.

其中O是零矩阵。这是二阶。它把A²压回A与I的线性组合，也预告了特征方程为何由迹和行列式组成。

8.3.2 摇摆不定的心

吃午饭时，“我”追问泰朵拉早上说的“拒绝”。米尔嘉希望她代替自己，在双仓图书馆的计算机科学小型会议上给初中生作报告。泰朵拉害怕面对近20名听众，已先说自己做不到；米尔嘉和村木老师却都建议她讲最近学过的逐行调试、渐近分析、查找和排序。

“我”提醒她：她曾说想成为信息发送者，而报告正是传递信息的机会。泰朵拉没有立刻答应，只说再想一想。她的摇摆不是没有能力，而是尚未把“学习过”转换成“能传达”。

8.4 放学后的图书室

8.4.1 流浪问题

放学后，泰朵拉已经查到a+d叫矩阵的迹。她强调自己不再只等待学长讲解。村木老师的新卡片给出：

第0年抛公平硬币，正面在A国，反面在B国；
在A国时，以1-p留在A，以p移动到B；
在B国时，以q移动到A，以1-q留在B；
0<p<1且0<q<1；
求第n年在A国的概率。

是A或B；由p、q给出。令：

a_n=\Pr(\text{第n年在A国}), \qquad b_n=\Pr(\text{第n年在B国}).

第n+1年在A的全部情况必须“不遗漏、不重复”地分成两类：从A留下，或从B转来。因此：

a_{n+1}=(1-p)a_n+qb_n.

同理：

b_{n+1}=pa_n+(1-q)b_n.

把两个量组成概率向量：

\boldsymbol{v}_n= \begin{pmatrix} a_n\\b_n \end{pmatrix}.

再定义：

T= \begin{pmatrix} 1-p&q\\ p&1-q \end{pmatrix}.

No-Omission State Sum：每个下一状态都把所有互斥来源相加，转移矩阵的列因此保持概率总和。

递推压成：

\boldsymbol{v}_{n+1}=T\boldsymbol{v}_n, \qquad \boldsymbol{v}_0= \begin{pmatrix} 1/2\\1/2 \end{pmatrix}.

矩阵两列分别描述“当前在A”和“当前在B”时下一年的分布，每列元素和为1。

8.4.2 A²的意义

连续两年：

\boldsymbol{v}_{n+2} =T\boldsymbol{v}_{n+1} =T^2\boldsymbol{v}_n.

展开：

T^2= \begin{pmatrix} (1-p)^2+pq&q(2-p-q)\\ p(2-p-q)&pq+(1-q)^2 \end{pmatrix}.

左上元素不是随意相加：

(1-p)^2+pq

分别对应A→A→A与A→B→A两条互斥的两年路径。矩阵乘法中的行列乘积和自动枚举中间状态，并对其概率求和。矩阵平方因此是“两步转移”，而不是单纯把四个数平方。

8.4.3 向着矩阵的n次方前进

反复递推：

\boldsymbol{v}_n=T^n\boldsymbol{v}_0.

目标变成求Tⁿ。逐次相乘再猜公式虽然可行，却很难让两个耦合状态的变化模式显形。村木老师在卡片背面留下两条提示，引向。

“我”一度犹豫应该怎样向泰朵拉传达：是先做许多计算再归纳，还是直接介绍。想到米尔嘉闭眼思索时也许在选择“传递信息的方法”，最终决定沿提示前进。

8.4.4 上半场准备：对角矩阵

对角矩阵的形式是：

D= \begin{pmatrix} \alpha&0\\ 0&\beta \end{pmatrix}

的幂很简单：

D^n= \begin{pmatrix} \alpha^n&0\\ 0&\beta^n \end{pmatrix}.

非对角元素保持为0，两个对角元素各自独立乘方。这是对角化的“上半场准备”。

8.4.5 下半场准备：矩阵与逆矩阵的三明治

若P可逆，把D夹在P与P⁻¹之间：

A=PDP^{-1}.

平方时：

\begin{aligned} A^2 &=(PDP^{-1})(PDP^{-1})\\ &=PD(P^{-1}P)DP^{-1}\\ &=PD^2P^{-1}. \end{aligned}

中间的P⁻¹P=I消去。一般地：

(PDP^{-1})^n=PD^nP^{-1}.

这就是“三明治的n次方等于n次方的三明治”。困难的Aⁿ被转成容易的Dⁿ。

8.4.6 向着特征值前进

现在令：

T=PDP^{-1}.

右乘P得到：

TP=PD.

若P的第一列为非零向量u，D的第一对角元素为λ，比较第一列可得：

T\boldsymbol{u}=\lambda\boldsymbol{u}.

也就是：

(T-\lambda I)\boldsymbol{u}=\boldsymbol{0}.

因为u非零，T-λI不能可逆，否则左乘逆矩阵会推出u=0。所以：

\det(T-\lambda I)=0.

这就是特征方程。对本题：

\begin{aligned} \det(T-xI) &= \begin{vmatrix} 1-p-x&q\\ p&1-q-x \end{vmatrix}\\ &=(1-p-x)(1-q-x)-pq\\ &=x^2-(2-p-q)x+(1-p-q)\\ &=(x-1)(x-(1-p-q)). \end{aligned}

因此两个特征值是：

\lambda_1=1, \qquad \lambda_2=1-p-q.

它与凯莱-哈密顿定理完全同构，因为：

\operatorname{tr}(T)=2-p-q, \qquad \det(T)=1-p-q.

8.4.7 向着特征向量前进

与λ₁=1对应，解：

(T-I)\boldsymbol{u}_1=\boldsymbol{0}

可取：

\boldsymbol{u}_1= \begin{pmatrix} q\\p \end{pmatrix}.

与λ₂=1-p-q对应，可取：

\boldsymbol{u}_2= \begin{pmatrix} -1\\1 \end{pmatrix}.

满足T u=λu的非零向量叫特征向量。把两根对应的向量按列放入P：

P= \begin{pmatrix} q&-1\\ p&1 \end{pmatrix}, \qquad D= \begin{pmatrix} 1&0\\ 0&1-p-q \end{pmatrix}.

因为p+q>0：

P^{-1} = \frac1{p+q} \begin{pmatrix} 1&1\\ -p&q \end{pmatrix}.

于是确有：

T=PDP^{-1}.

特征向量不唯一，乘任意非零常数仍是同一特征方向；这里只需找到一组让P可逆的列向量。

8.4.8 求Tⁿ

记：

r=1-p-q.

对角化给出：

\begin{aligned} T^n &=PD^nP^{-1}\\ &= \frac1{p+q} \begin{pmatrix} q&-r^n\\ p&r^n \end{pmatrix} \begin{pmatrix} 1&1\\ -p&q \end{pmatrix}\\ &= \frac1{p+q} \begin{pmatrix} q+pr^n&q(1-r^n)\\ p(1-r^n)&p+qr^n \end{pmatrix}. \end{aligned}

乘初始公平分布：

\boldsymbol{v}_0= \frac12 \begin{pmatrix} 1\\1 \end{pmatrix},

得到：

\begin{aligned} a_n &= \frac{2q+(p-q)r^n}{2(p+q)}\\ &= \frac{q}{p+q} + \frac{p-q}{2(p+q)}(1-p-q)^n, \\[4pt] b_n &= \frac{p}{p+q} + \frac{q-p}{2(p+q)}(1-p-q)^n. \end{aligned}

这就是流浪问题的第n年答案。第一个特征值1保存总概率与长期比例；第二个特征值r控制初始偏差的衰减。由于0<p,q<1，有：

|1-p-q|<1.

所以：

\lim_{n\to\infty}a_n=\frac{q}{p+q}, \qquad \lim_{n\to\infty}b_n=\frac{p}{p+q}.

这个长期不再变化的概率向量叫，满足 T v=v。含rⁿ的部分叫瞬态。对角化把守恒模式与衰减模式分开，使复杂公式有了可解释结构。

Mode Decomposition：对角化把长期守恒与短期衰减拆成两条可解释的特征方向。

泰朵拉把整个过程画成“旅行地图”：从矩阵出发，经特征方程找到特征值，再找特征向量组成P，最后利用T=PDP⁻¹求幂。字母很多时，地图记录每一步从哪些条件出发，防止在推理中迷路。

她也意识到爱丽丝只根据上一年所在国家决定下一年，不需要更早历史。这种让状态向量足以携带未来所需信息的性质叫；两国模型也是一种有限状态随机漫步。

8.5 家

8.5.1 摇摆不定的心

夜里，“我”回想一整天都在给泰朵拉讲数学，也不断想到缺席的米尔嘉。流浪问题还可以推广到三个乃至更多状态，也可以研究n趋于无穷的极限；如果米尔嘉在场，她也许会把同一问题连接到更远的世界。短暂离开反而凸显她的存在。

电话忽然响起。身在美国西海岸的米尔嘉不解释行程，直接追问：“你害怕约定吗？”她把约定说成对道路与未来的决心：从不约定的人当然从不违约，却也从未表明自己要走哪条路。她逼“我”面对那个无法由矩阵替代的问题。

8.5.2 雨夜

米尔嘉挂断后，“我”才算出时差：她那里并非清晨，而是凌晨两点。那通突兀电话也许不只是质问，还是她自己在深夜的不安。

尤里等待回信，泰朵拉担心会议报告，米尔嘉与“我”面对未来道路。每个人的内心都在摇摆。数学能求出状态转移与长期比例，却不能替人作出约定；解谜重要，守护内心同样重要。

“我”打开窗，湿冷雨气涌入，外面仍一片昏暗。未来还看不见。章末因此回到真正重要的东西：解决一个问题的方法，往往比某个孤立答案更重要；而选择道路的方法，必须由自己承担。

本章回顾：从165条旋律到两国稳态

钢琴问题的12个音对应11次相邻移动，从do到fa的净位移为3。
上升u与下降d满足u+d=11、u-d=3，所以u=7、d=4。
只计算C(11,7)=330会混入曾跌到do以下的坏路径。
动态规划用c(t+1,h)=c(t,h-1)+c(t,h+1)逐格得到c(11,3)=165。
反射原理把首次越界后的路径翻转，使坏路径与3上8下的路径一一对应。
合法路径数为C(11,7)-C(11,3)=165。
一般受限路径数为C(u+d,d)-C(u+d,d-1)。
变量替换a=u+1、b=d后，答案为(a-b)/(a+b)·C(a+b,b)。
公平硬币驱动的相邻音高变化是一维随机漫步，布朗运动提供物理类比。
二阶凯莱-哈密顿定理是A²-tr(A)A+det(A)I=O。
矩阵的迹是主对角线元素之和，行列式与迹共同组成二阶特征多项式。
流浪问题的概率递推是aₙ₊₁=(1-p)aₙ+qbₙ与bₙ₊₁=paₙ+(1-q)bₙ。
转移矩阵T=[[1-p,q],[p,1-q]]的列保存从当前国家出发的下一年分布。
T²汇总所有两年路径，Tⁿ汇总所有n年路径。
对角矩阵的n次方只需分别计算对角元素的n次方。
三明治公式(PDP⁻¹)ⁿ=PDⁿP⁻¹来自中间P⁻¹P=I连续消去。
特征方程来自(T-λI)u=0存在非零解，因此det(T-λI)=0。
流浪矩阵的特征值是1与1-p-q。
对应特征向量可取[q,p]ᵀ与[-1,1]ᵀ，由此组成可逆矩阵P。
对角化给出Tⁿ与第n年A国概率的闭式。
aₙ=q/(p+q)+(p-q)(1-p-q)ⁿ/(2(p+q))。
特征值1保存稳态，绝对值小于1的特征值控制瞬态衰减。
长期分布为A国q/(p+q)、B国p/(p+q)。
马尔可夫性说明给定当前国家后，更早历史不再影响下一年转移。
尤里的回信、泰朵拉的报告与米尔嘉的深夜电话，把随机摇摆连接到选择未来道路。

概念核对：从路径到特征模式

下面的核对表把原书单元中容易被一句话带过的节点重新写成可检查的解释；每一项都对应正文、图示或实验中的一个证据。

“孤零零的随机漫步”不是把情绪贴在数学外面，而是把无方向的等待翻译为每一步有规则、长期可分析的状态变化。
路径模型把第几个音放在横轴、相对高度放在纵轴，用一条由上行和下行边组成的线记录整个旋律。
终点条件只说最后位于高度3；它不能代替全过程条件，后者还要求每个中间高度都不低于0。
动态规划中的重叠子问题是同一个格子可以由多条前缀到达，保存 c(t,h) 后就不必重复计算每条前缀。
Piano Path Grid把时间和高度画成网格，箭头从左侧格子汇入当前格子，读者能直接看到165如何逐格累加。
Reflection Bijection在首次到达高度-1处翻转后续方向，把每条坏路径唯一送到终点高度-5的路径。
组合数 C(11,7)先数出所有上行位置的选择，再由边界条件减掉非法路径，说明组合数需要配合约束使用。
凯莱-哈密顿定理说矩阵会满足自己的特征多项式，因此高次幂可以压回低次矩阵的线性组合。
Four-Entry Cancellation Table逐项比较A²与(a+d)A的四个位置，非对角项相消而对角项都留下bc-ad。
Characteristic Coefficient Check用迹a+d和行列式ad-bc检查二阶特征多项式的两个系数，而不是只凭展开结果记忆。
概率向量的分量和为1来自A、B两个状态互斥且完备；每次转移都必须保持这个归一化条件。
矩阵对角化把耦合状态换到特征方向，先在对角矩阵中分别乘方，再换回国家概率坐标。
公式 A=PDP⁻¹ 不是新定义的乘法，而是一个相似变换；两侧的P与P⁻¹记录同一线性变换的两套坐标。
写出 det(T-xI)=0 是因为非零特征向量使T-xI有非平凡零空间，所以这个矩阵不能可逆。
特征值1对应的非零方向只被缩放为“缩放因子1”，它表现为总概率守恒，而不是每个坐标都冻结。
特征向量的方向不变：乘上对应特征值后，向量可能变长或反向，但仍落在同一条特征直线上。
稳态分布是转移后仍不变的概率向量，它在本题中满足 Tv=v，并由两个状态的流入流出平衡决定。
Two-Year Path Tree把两年内的A→A→A和A→B→A等互斥路线画开，说明矩阵平方在枚举中间状态。
No-Omission State Sum要求从A留下与从B转来两类来源不遗漏、不重复，正是递推式两项相加的理由。
Diagonalization Travel Map记录T→特征方程→特征值→特征向量→PDP⁻¹的路线，避免在求幂时丢掉坐标变换。
Mode Decomposition把概率拆成守恒模式和衰减模式，前者保留长期比例，后者携带初始状态的记忆。
如果特征方程有重根，还要检查是否有足够的独立特征向量；只有可对角化时，当前的三明治公式才直接适用。
两个独立特征向量才能组成可逆的P；本题的[q,p]ᵀ与[-1,1]ᵀ因p+q>0而不共线。
“旅行地图”是推导顺序的记忆工具：先找不变量，再找特征值，最后用特征向量把抽象模式翻译回概率。

互动实验与四步复盘

先猜一猜：如果暂时允许旋律跌到do以下，候选数会增加多少？如果p+q变大，衰减模式会更快消失还是更慢？切换实验模式后，用图上的证据修正直觉。

Random Walk Evidence Lab

切换同一个问题的三种视角