3.4 线性递归系统

在自然界中有非常多的随时间而变化的变量.例如某物种种群数量随时间而变化; 矿石放射性元素含量随时间而衰减等. 我们可以尝试用线性变换的知识去理解这些问题: 将所要研究的变量当做一个向量 $\vec v_0$ , 然后通过已知条件求出一个变换矩阵 $A$ . 这样一来 $\vec v_1 = A \vec v_0$ 就可以表示为该变量经过时间等因素的影响在下一时间节点的性质. 我们便可以利用该模型来预测其未来的变化趋势. 我们一起来看一个例子:

例题 3.7

假设存在某鸟类种群,在该鸟类种群中我们将其分为幼年鸟和成年鸟两种. 经过一段时间的调查我们得出以下关系:

① 每一年新孵化的幼年鸟的数量是前一年存活下来的成年鸟的数量的两倍;

② 每一年中约有 $\displaystyle{\frac{1}{2}}$ 的成年鸟能够存活下来;

③ 每一年中约有 $\displaystyle{\frac{1}{4}}$ 的幼年鸟能够存活下来并且成长为成年鸟.

现在经调查得知该种群有100只成年鸟和40只幼年鸟,那么试问在许多年后该鸟类种群数目会发生何等变化?

解答 3.7

我们可以设幼年鸟在第 $k$ 年的数量为 $j_k$ , 设成年鸟在第 $k$ 年的数量为 $a_k$ , 那么我们可以根据上述关系,得到:

\begin{cases} a_{k+1} = \displaystyle{\frac{1}{2}}a_k + \displaystyle{\frac{1}{4}}j_k \\ \\ j_{k+1} = 2a_{k} \end{cases}.

此时我们设 $\vec v_k = \begin{pmatrix} a_k \\ j_k \end{pmatrix}$ , 设 $A = \begin{pmatrix} \frac{1}{2} & \frac{1}{4} \\ 2 & 0 \end{pmatrix}$ , 那么根据题设关系,我们就有

\vec v_{k+1} = A \vec v_k.

因此,结合初始条件 $\vec v_0 = \begin{pmatrix} 100 \\ 40 \end{pmatrix}$ , 我们还可以得到

\vec v_k = \begin{pmatrix} \frac{1}{2} & \frac{1}{4} \\ 2 & 0 \end{pmatrix}^k \begin{pmatrix} 100 \\ 40 \end{pmatrix}.

接下来,我们便一起研究一下矩阵 $A$ . 其中经过计算我们得出 $A$ 的特征多项式为

C_A(x) = (x-1)\left(x+ \frac{1}{2}\right),

因此 $A$ 有两个不同的特征值 $\lambda_1 = 1, \lambda_2 = -\frac{1}{2}$ .那么根据定理3.7可知, $A$ 可对角化.且我们可以计算出 $\lambda_1 = 1$ 对应的特征向量 $\vec u_1 = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$ ; $\lambda_2 = -\frac{1}{2}$ 对应的特征向量 $\vec u_2 = \begin{pmatrix} -1 \\ 4 \end{pmatrix}$ .

也就是说,存在可逆矩阵 $\mathcal{P} = \begin{pmatrix} 1 & -1 \\ 2 & 4 \end{pmatrix}$ 与对角矩阵 $\mathcal{D} = \begin{pmatrix} 1 & 0 \\ 0 & -\frac{1}{2} \end{pmatrix}$ , 使得 $A = \mathcal{P} \mathcal{D} \mathcal{P}^{-1}$ , 即

\begin{aligned} A^k = \mathcal{P} \mathcal{D}^k \mathcal{P}^{-1} &= \begin{pmatrix} 1 & -1 \\ 2 & 4 \end{pmatrix} \begin{pmatrix} 1^k & 0 \\ 0 & (\frac{1}{2})^k \end{pmatrix} \begin{pmatrix} \frac{2}{3} & \frac{1}{6} \\ -\frac{1}{3} & \frac{2}{3} \end{pmatrix} \\ & \\ & = \frac{1}{6} \begin{pmatrix} 4 + 2(-\frac{1}{2})^k & 1 - (-\frac{1}{2})^k \\ & \\ 8 - 8(-\frac{1}{2})^k & 2 + 4(-\frac{1}{2})^k \end{pmatrix}. \end{aligned}

即

\begin{aligned} \vec v_k = \begin{pmatrix} a_k \\ j_k \end{pmatrix} = A^k \vec v_0 &= \begin{pmatrix} 4 + 2(-\frac{1}{2})^k & 1 - (-\frac{1}{2})^k \\ & \\ 8 - 8(-\frac{1}{2})^k & 2 + 4(-\frac{1}{2})^k \end{pmatrix} \begin{pmatrix} 100 \\ \\40 \end{pmatrix} \\ & \\ & = \frac{1}{6} \begin{pmatrix} 440 + 160(-\frac{1}{2})^k \\ \\ 880 - 640(-\frac{1}{2})^k \end{pmatrix}. \end{aligned}

所以我们得到

a_k = \frac{220}{3} + \frac{80}{3} \left(-\frac{1}{2}\right)^k \hspace{0.5cm} j_k = \frac{440}{3} - \frac{320}{3} \left(-\frac{1}{2}\right)^k.

由此可知, 当 $k$ 很大时, $\displaystyle{\left(-\frac{1}{2}\right)^k} \rightarrow 0$ , 因此在很多年之后,种群的数量会趋于稳定, 即

\begin{cases} a_k \approx \frac{220}{3} \\ \\ j_k \approx \frac{440}{3} \end{cases}.

由上面的例子, 我们引出一条概念:

定义 3.6

在 $n \times n$ 矩阵 $A$ 中,如果存在满足一定条件的向量 $\vec v_0,\vec v_1,\cdots$ 和非负整数 $k$ , 使得

\vec v_{k+1} = A \vec v_k,

我们便称该系统为一个线性递归系统 (Linear Dynamical System).

我们设在线性递归系统 $\vec v_{k+1} = A \vec v_k$ 中,矩阵 $A$ 可对角化,设 $A$ 的特征值为 $\lambda_1, \lambda_2, \cdots, \lambda_n$ ( $\dim(A) = n$ ); 与之对应的特征向量为 $\vec u_1, \vec u_2, \cdots, \vec u_n$ .设矩阵 $\mathcal{P} = \begin{pmatrix} \vec u_1 & \vec u_2 & \cdots & \vec u_n \end{pmatrix}$ , $\mathcal{D} = \diag(\lambda_1, \lambda_2, \cdots, \lambda_n)$ , 那么

A^k \vec v_0 = (\mathcal{P} \mathcal{D}^k \mathcal{P}^{-1})\vec v_0 = \mathcal{P} \mathcal{D}^k (\mathcal{P}^{-1}\vec v_0).

我们令 $\vec b = \mathcal{P}^{-1}\vec v_0 = \begin{pmatrix} b_1 & b_2 &\cdots & b_n \end{pmatrix}^\top$ , 那么

\begin{aligned} \vec v_k &= \mathcal{P} \mathcal{D}^k (\mathcal{P}^{-1}\vec v_0) \\ &= \begin{pmatrix} \vec u_1 & \vec u_2 & \cdots & \vec u_n \end{pmatrix} \diag(\lambda_1^k, \lambda_2^k, \cdots, \lambda_n^k) \begin{pmatrix} b_1 & b_2 & \cdots & b_n \end{pmatrix}^\top \\ & = \begin{pmatrix} \vec u_1 & \vec u_2 & \cdots & \vec u_n \end{pmatrix} \begin{pmatrix} b_1 \lambda_1^k & b_2 \lambda_2^k & \cdots & b_n \lambda_n^k \end{pmatrix}^\top. \end{aligned}

因此,我们也得出了一个公式:

\vec v_k = b_1 \lambda_1^k \vec u_1 + b_2 \lambda_2^k \vec u_2 + \cdots + b_n \lambda_n^k \vec u_n.

定理 3.10

在线性递归系统 $\vec v_{k+1} = A \vec v_k \hspace{0.2cm} (k > 0)$ 中, 假设 $\vec v_0, A$ 均给定, 且 $A$ 可对角化.设 $\lambda_1, \lambda_2, \cdots, \lambda_n$ 为 $A$ 的特征值; $\vec u_1, \vec u_2, \cdots, \vec u_n$ 为相对应的特征向量,令 $\mathcal{P} = \begin{pmatrix} \vec u_1 & \vec u_2 & \cdots & \vec u_n \end{pmatrix}$ , 那么我们有

\vec v_k = b_1 \lambda_1^k \vec u_1 + b_2 \lambda_2^k \vec u_2 + \cdots + b_n \lambda_n^k \vec u_n

其中

\vec b = \mathcal{P}^{-1} \vec v_0 = \begin{pmatrix} b_1 & b_2 & \cdots & b_n \end{pmatrix}^\top.

在一些情况下,我们往往不必按照定理3-10所给出的公式进行求解:

定义 3.7

在 $n \times n$ 矩阵 $A$ 中, 如果特征值 $\lambda$ 的代数重数为 $1$ , 且 $\lambda$ 的绝对值是所有特征值的绝对值中的最大值, 我们称 $\lambda$ 为矩阵 $A$ 的主导特征值.

不失一般性地讲, 我们不妨设 $\lambda_1$ 为 $A$ 的主导特征值, 那么我们便有

\vec v_k = \lambda_1^k \left[ b_1 \vec u_1 + b_2\left( \frac{\lambda_2}{\lambda_1} \right)^k\vec u_2 + \cdots + b_n \left( \frac{\lambda_n}{\lambda_1} \right)^k \vec u_n \right].

因此当 $k$ 很大时,我们便会发现 $\displaystyle{\left( \frac{\lambda_j}{\lambda_1} \right)^k \rightarrow 0 \hspace{0.2cm} (j > 1)}$ , 所以决定 $\vec v_k$ 的其实只与主导特征值有关,即 $\vec v_k \approx \lambda_1^k b_1 \vec u_1$ .

例题 3.8

在某线性递归系统中, 给定 $x_0 = 1, x_1 = -1$ , 且

x_{k+2} = -x_{k+1} + 2x_k \quad(k > 0).

据此求 $x_k$ 的通项.

解答 3.8

我们由题意可设 $\vec v_k = \begin{pmatrix} x_k \\ x_{k+1} \end{pmatrix}$ , 由 $\vec v_{k+1} = \begin{pmatrix} x_{k+1} \\ x_{k+2} \end{pmatrix} = \begin{pmatrix} x_{k+1} \\ 2x_k - x_{k+1} \end{pmatrix} = A \vec v_k$ 可以求出其变换矩阵为

A = \begin{pmatrix} 0 & 1 \\ 2 & -1 \end{pmatrix}.

经计算, $A$ 的特征值为 $\lambda_1 = -2; \lambda_2 = 1$ , 其对应的特征向量为 $\vec u_1 = \begin{pmatrix} 1 \\ -2 \end{pmatrix}; \vec u_2 = \begin{pmatrix} 1 \\1 \end{pmatrix}$ , 则 $\mathcal{P} = \begin{pmatrix} 1 & 1 \\ -2 & 1 \end{pmatrix}, \vec b = \mathcal{P}^{-1} \vec v_0 = \begin{pmatrix} \frac{2}{3} \\ \frac{1}{3} \end{pmatrix}$ , 由此可得

\begin{pmatrix} x_{k} \\ x_{k+1}\end{pmatrix} = b_1 \lambda_1^k \vec u_1 + b_2 \lambda_2^k \vec u_2 = (-2)^k \begin{pmatrix} \frac{1}{3} \\ -\frac{2}{3} \end{pmatrix} + 1^k \begin{pmatrix} 1 \\1 \end{pmatrix},

即

x_k = \frac{1}{3} \left[ 2(-2)^k + 1 \right].

形如 $\vec v_{k+1} = A \vec v_k$ 的线性递归系统还有一种特殊情况:如果矩阵 $A \vec v_k$ 代表的是下一阶段( $\vec v_{k+1}$ )所发生的事件的概率,我们把这种结构也可以称作马尔可夫链 (Markov Chain).

定义 3.8

在一个变化的系统中,如果该系统下一时刻的变化仅取决于该系统当前的状态,而不取决于该系统之前的状态,我们就将该系统称作为一个马尔可夫链. 我们一般用 $\{ X_t : t=0,1,\cdots \}$ 来表示一个马尔可夫链: 其中 $t$ 代表所处的单位时刻, $X$ 为一个随机变量, 代表这个系统可能处于的状态.

在一个马尔可夫链中,我们可以假设这个系统存在 $n$ 种不同的状态. 在某时刻 $t$ 该系统处于状态 $X_t=j$ . 那么在下一时刻 $t+1$ 该系统便可以处于 $n$ 种状态中的任意一种. 我们用 $p_{kj}$ 来表示系统在某时刻 $t$ 处于状态 $j$ , 且在下一时刻 $t+1$ 处于状态 $k$ 的概率 (注意顺序!). 不难发现

p_{1j} + p_{2j} + \cdots + p_{nj} = 1, p_{kj} \geq 0.

如果我们取遍 $j=1,2,\cdots,n$ , 便会得到一个 $n \times n$ 矩阵: 矩阵中的元素便是 $p_{kj}$ . 所得到的 $n \times n$ 矩阵 $P = (p_{kj})$ 便被称作是过渡矩阵 (Transition Matrix).

根据定义,矩阵 $P$ 的第 $j$ 列即为 $\begin{pmatrix} p_{1j} & p_{2j} & \cdots & p_{nj} \end{pmatrix}^\top$ , 且 $p_{1j} + p_{2j} + \cdots + p_{nj} = 1$ . 由于 $p_{kj}$ 表示在当前状态为 $j$ 时,经过一次变化到状态 $k$ 的概率, 故 $P$ 也被称作随机矩阵 (Stochastic Matrix). 我们设 $s_i^{(m)}$ 代表系统经过 $m$ 次变化之后最终处于状态 $i$ 的概率, 定义

\vec s_m = \begin{pmatrix} s_1^{(m)} & s_2^{(m)} & \cdots & s_n^{(m)} \end{pmatrix}^\top,\quad (m = 0,1,2 \cdots )

为状态向量 (State Vector), $\vec s_0$ 称作初始状态 (Initial State). 在一个马尔可夫链中, $P, \vec s_0$ 均为已知量.

定理 3.11

设 $P$ 为一个有 $n$ 个状态的马尔可夫链的随机矩阵(过渡矩阵), 若 $\vec s_m$ 代表该马尔可夫链在第 $m$ 阶段时的状态向量,则

\vec s_{m+1} = P \vec s_m = P^{m+1} \vec s_0.

证明

读者不妨尝试自证.

∎

例题 3.9

在一处草原中,某狼群会对 $R_1,R_2,R_3$ 三个不同位置的羊群进行攻击,已知该狼群的攻击有以下规律:

① 若该狼群在某一天攻击了一处羊群,那么下一天该狼群仍攻击该羊群的概率和不攻击该羊群的概率相等;

② 若该狼群在某一天攻击了 $R_1$ 处的羊群,那么下一天该狼群不会攻击 $R_2$ 处的羊群;

③ 若该狼群在某一天攻击了 $R_2$ 或 $R_3$ 位置的羊群, 那么在“不攻击原羊群”的情况下, 下一天攻击另外两个位置羊群的概率相等.

现在已知该狼群在周一攻击了 $R_1$ 处的羊群,那么在周四该狼群仍攻击 $R_1$ 处的羊群的概率是多少?

解答 3.9

根据题意,我们可以得出以下的关系表(该表格即为过渡矩阵):

	$R_1$	$R_2$	$R_3$
$R_1$	0.5	0.25	0.25
$R_2$	0	0.5	0.25
$R_3$	0.5	0.25	0.5

$P = \begin{pmatrix} 0.5 & 0.25 & 0.25 \\ 0 & 0.5 & 0.25 \\ 0.5 & 0.25 & 0.5 \\ \end{pmatrix}$

我们根据第一条规律便可以得知, $p_{11} = p_{22} = p_{33} = 0.5$ . $P$ 的第一列表示当前状态为 $R_1$ 时,下一状态的概率,因此由第二条规律可知 $p_{21} = 0$ , 再由其列中元素之和为 $1$ 可知 $p_{31} = 0.5$ . 随后再利用规律3,便可以求出 $P$ 中的全部元素.我们设周一时对应的状态为 $\vec s_0$ , 根据定义, $\vec s_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}^\top$ , 那么我们就可以知道 $\vec s_3$ 即可表示周四时的状态向量.我们有

\vec s_3 = P^3 (\vec s_0) = \begin{pmatrix} 0.5 & 0.25 & 0.25 \\ 0 & 0.5 & 0.25 \\ 0.5 & 0.25 & 0.5 \\ \end{pmatrix}^3 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} \frac{11}{32} \\ \frac{6}{32} \\ \frac{15}{32}. \end{pmatrix}

由此得知在周四该狼群仍然攻击 $R_1$ 处的羊群的概率为 $\displaystyle{\frac{11}{32}}$ .

在本章的第一个例题中, 我们发现当经过很长一段时间之后, 鸟类种群中成年鸟和幼年鸟的数目趋于稳定. 对于一些马尔可夫链而言, 我们也存在一个使得状态向量 $\vec s$ 收敛于某一位置的向量 $\vec x$ .此时马尔可夫链趋于稳定,我们有

\vec x = P \vec x.

我们称满足条件的 $\vec x$ 为稳定态向量 (Steady-State Vector). 那么什么样的马尔可夫链满足这样的收敛性质呢?

定理 3.12

设 $P$ 为一个有 $n$ 个状态的马尔可夫链的随机矩阵(过渡矩阵), 且假设存在正整数 $m$ , 使得 $P^m$ 中的所有元素均严格大于零 (我们也称 $P$ 为正则矩阵). 则存在唯一的向量 $\vec s$ , 使得

\vec s = P\vec s.

其中, $\vec s = \begin{pmatrix} s_1 & s_2 & \cdots & s_n \end{pmatrix}^\top$ 满足 $\sum_{i=1}^n s_i = 1, s_i >0$ . 同时由任意状态向量构成的数列 $\vec x_0 , \vec x_1, \vec x_2 , \cdots$ 收敛于 $\vec s$ .

该定理的证明已远远超纲. 感兴趣的读者不妨自行阅读相关材料.

{3.4 练习}

1. 在线性递归系统 $\vec v_{k+1} = A \vec v_k$ 中,我们给出

A_1 = \begin{pmatrix} \frac{1}{2} & 0 \\ 0 & \frac{1}{3 } \end{pmatrix} \hspace{0.5cm} A_2 = \begin{pmatrix} \frac{3}{2} & 0 \\ 0 & \frac{4}{3} \end{pmatrix} \hspace{0.5cm} A_3 = \begin{pmatrix} 1 & -\frac{1}{2} \\ -\frac{1}{2} & 1 \end{pmatrix}

如果我们将 $\vec v_0, \vec v_1, \vec v_2, \cdots$ 看作数列,依次标在坐标系中,用箭头来表示其变化趋势.那么下面的三个选项中哪一幅图可以准确地对应上面的矩阵? 对这部分知识感兴趣的读者欢迎阅读第六章第 $4$ 节!

2. 甲要爬一段有 $k$ 级台阶的楼梯,已知甲每一步可以爬一级或两级台阶,要求最后甲可以刚好达到最顶端.记 $s_k$ 为甲刚好爬上台阶所用的不同种类数,当 $k=1$ 时,我们有 $s_1 = 1$ , $k=2$ 时有 $s_2 = 2$ .据此求出 $s_k$ 的通项公式.(HINT : 我们有 $s_{k+2} = s_{k+1} + s_k$ , 据此建立线性递归模型进行求解.)

3. 假设有足够多的红色,蓝色,白色木板,将这些木板从下往上堆成一叠.设 $x_k$ 表示当木板为 $k$ 个时,所有的使白色木板彼此不相邻的堆叠方式.据此求出 $x_k$ 的通项公式.(HINT : 我们有 $x_{k+2} = 2x_{k+1} + 2x_k$ , 据此建立线性递归模型进行求解.并且可以参考第二题!)

4. 在一个核反应堆中含有 $\alpha$ 粒子和 $\beta$ 粒子.每经过一秒就会有一个 $\alpha$ 粒子分解为三个 $\beta$ 粒子;同时也会有一个 $\beta$ 粒子分解为一个 $\alpha$ 粒子和两个 $\beta$ 粒子.在某一时刻该封闭系统内有一个 $\alpha$ 粒子,那么在经过 $t=20$ 秒之后该系统里面有多少个 $\alpha$ 粒子和 $\beta$ 粒子?

5. 在某机器学习模型中,我们给出如下图(见下页)所示的网格迷宫.某 $AI$ 需要从一个位置出发,然后通过图中标出的路径进行节点之间的移动从而到达下一相邻位置.已知 $AI$ 在每一处特定节点位置时所选择的路径概率相等.

① 假设在某一时刻 $AI$ 位于节点 $1$ , 据此求出经过三次移动之后,该 $AI$ 又回到节点 $1$ 处的概率;

② 假设在某一时刻 $AI$ 位于节点 $2$ ,那么在经过次数足够多的移动之后该 $AI$ 最有可能处于哪一处节点?

6. 设 $0<p<1; 0<q<1$ 及随机矩阵 $P = \begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix}$ .

① 证明 : $\displaystyle{\frac{1}{p+q} \begin{pmatrix} q \\ p \end{pmatrix}}$ 为 $P$ 的稳定态向量;

② 证明: $P^m$ 收敛于 $\displaystyle{\frac{1}{p+q} \begin{pmatrix} q & q \\ p & p \end{pmatrix}}$ .

<i>HINT: 先尝试用数学归纳法证明$P^m = \displaystyle{\frac{1}{p+q} \begin{pmatrix} q & q \\ p & p \end{pmatrix} + \frac{(1-p-q)^m}{p+q} \begin{pmatrix}p & -q \\ -p & q \end{pmatrix}}$</i>