马尔科夫矩阵;人口;经济

• Markov Matrices, Population, and Economics
• 只完整记录 <#1>
• 马尔科夫矩阵是$\lambda _ { \max } = 1$ 的应用，人口增长 $\lambda _ { \max } = 1$ 的应用，消费矩阵 $\lambda _ { \max } <1$ 的应用。后面2个有需要再看把

这一节都是关于正值矩阵(positive matrices)：每一个 $a_{ij}>0$.对于这样的矩阵，关键事实是：**它最大的特征值是实数并且是正值的，它的特征向量也是如此。**在经济学、生态学、人口动态和随机游走中，这一事实大有帮助：

$$\text{Markov：} \quad \lambda _ { \max } = 1 \quad \\ \text { Population： } \quad \lambda _ { \max } > 1 \quad \\ \text { Consumption： } \quad \lambda _ { \max } < 1$$

马尔科夫矩阵

• Markov martices
• 综合V24前半部分

V24:在微分方程当中：特征值为0,会得到稳态.但是矩阵幂的情况,就不是0特征值,特征值为1才是最重要的.稳态完全和值为1特征值及其特征向量联系在一起,实际上：稳态就是特征值为1的特征向量！马尔科夫矩阵每列相加为1,这保证了一个特征值为1.所以在不用 $A-λI$ 的前提下,都可以算出马尔科夫矩阵的特征值.

关键在于：

1. λ=1是特征值. 而且.特征向量向量 $x_1$ 的所有分量都 $\ge 0$.因此初始值为正,稳态就是正值.
2. 其他所有的特征值 $|\lambda_i|< 1$ (可能会有例外的情况,有一些绝对值还是等于1，但绝不会大于0)

请记住对于 $u_k= A^k u_0$,这里的A的幂的特别之处

$$> u_k=A^k u_0 = c_1 λ_1^k x_1+…+c_n λ_n^k x_n >$$

要求有一套完整的特征向量,否则 $u_0$ 不能扩展为特征向量形式,问题无法开始.观察上式，如果$λ_1=1$ ，它取k次幂不变,其他的λ小于1,会随着时间的递增会趋于0,所以最终，稳态趋向于初始条件 $u_0$ 沿着特征向量的 $x_1$ 部分 $c_1x_1$ !

假设对于如下的A矩阵，不断使用A矩阵乘以正值向量 $u_0 =(a,1-a)$ ：

$$\begin{array} { l } \text { Markov } \\ \text { matrix } \end{array} \quad A = \left[ \begin{array} { l l } .8 & .3 \\ .2 & .7 \end{array} \right] \quad u _ { 1 } = A u _ { 0 } \quad u _ { 2 } = A u _ { 1 } = A ^ { 2 } u _ { 0 } \tag{L1}$$

k步之后得到 $A^k u_0$.向量 $u_1,u_2,u_3...$ 会逐渐接近一个稳态(steady state) $u_{\infty} = (.6,.4)$.而且，这个最终的稳态向量不取决与输入向量：任何 $u_0$ 都会收敛到相同的 $u_{\infty}$！ 为什么呢？

稳态等式 $Au_{\infty} = u_{\infty}$ 使得 $u_{\infty}$ 是特征值为1的特征向量：

$$\text{Steady state}\qquad \left[ \begin{array} { l l } .8 & .3 \\ .2 & .7 \end{array} \right] \left[ \begin{array} { l } .6 \\ .4 \end{array} \right] = \left[ \begin{array} { l } .6 \\ .4 \end{array} \right]$$

再次乘以A，不会改变 $u_{\infty}$.但还没有解释为什么所有的 $u_0$ 最终都是得到 $u_{\infty}$.其他的矩阵也有稳态，但是它们不吸引人：

$$\text{Not Matkov}\qquad \quad B = \left[ \begin{array} { l l } 1 & 0 \\ 0 & 2 \end{array} \right] \quad \text { 也有稳态，但不吸引人： } B \left[ \begin{array} { l } 1 \\ 0 \end{array} \right] = \left[ \begin{array} { l } 1 \\ 0 \end{array} \right] \tag{L2}$$

对与上面的B，如果输入 $u_0 = (0,1)$,会得到 $u_1 = (0,2)$,B再乘一次得到 $u_2=(0,4)$...第2个分量被加倍了。以特征值的语言来描述一线，B有 $\lambda = 1$,但它也有 $\lambda =2$ -- 这就产生了不稳定性.也就是说，$\vec{u}$ 向量当，沿着那个不稳定的特征向量的分量会乘以 $\lambda$,而 $|\lambda|>1$ 意味着增长。

马尔科夫矩阵A的2个关键性质，使得可以确保存在稳态。这些性质定义了马尔科夫矩阵，Eq(L1) 的A就是1个马尔科夫矩阵

马尔科夫矩阵性质

---

1. A的每个元素 $a_{ij} \ge 0$
2. A的每一列的元素和是1

---

注意，马尔科夫矩阵的幂，还是马尔科夫！

Eq(L2) B没有性质2。 对于马尔科夫矩阵A，立刻可以得到2个性质：

1. A乘以 非负的 $u_0$ 可以产生 非负的 $u_1 = Au_0$
2. 如果 $u_0$ 的分量加起来是1，那么 $u_1 = Au_0$ 的分量也是

sp:注意这里的分量和为1 $u_0$ 是一个特殊的概率向量，第2点要说明的是马尔科夫可以保持概率向量一直都是概率向量，而最终的稳态，也就是概率向量的极限，是最终每个部分所站的比例，如例1。不是说所有的初始向量必须都是概率向量。如例V24-2的人口向量就不是，这时得到的直接就是每个部分的具体数字。

第2点原因： 首先，如果乘法 $[1...1]u_0 = 1$ ，就说明 $u_0$ 的分量和是1.而对于马尔科夫矩阵A，根据性质2，每一列的分量和都是1.所以矩阵乘法可得 $[1...1]A = [1...1]$，现在再把 [1...1] 乘以 $Au_0$,可得：

$$\text{Components of }A u _ { 0 } \text { add to } 1: \quad \left[ \begin{array} { l l l } 1 & \cdots & 1 \end{array} \right] A u _ { 0 } = \left[ \begin{array} { l l l } 1 & \cdots & 1 \end{array} \right] u _ { 0 } = 1 .$$

所以 $Au_0$ 的分量和是1.同样的事实对于 $u_2 = Au_1,u_3 = Au_2$ 也是成立的。可得，任何向量 $A^k u_0$ 都是非负的，而且分量和是1. 这些都是概率向量(probablity vectors),它们的极限 $u_{\infty}$ 也是一个概率向量--但我们需要证明存在这样一个极限，我们会证明，对于**正值的(sp:意思是不能有0元素的？）**马尔科夫矩阵，存在 $\lambda_{max} = 1$

例1 丹佛出租的车占比是 1/50 =.02,其他地区占比 .98. 每个月，80%的车留在丹佛，20%的车离开，而其他地区5%的车开进丹佛(95%的车继续留在其他地区).这意味着A乘以 $u_0 = (.02,.98)$

$$\text{First month:}\quad A = \left[ \begin{array} { l l } .80 & .05 \\ .20 & .95 \end{array} \right] \quad \text { leads to } \quad u _ { 1 } = A u _ { 0 } = A \left[ \begin{array} { l } .02 \\ .98 \end{array} \right] = \left[ \begin{array} { l } .065 \\ .935 \end{array} \right]$$

注意，$.065+.935 =1$，所有的车都计算在内了。之后的每个月，都是被A乘：

$$\text{Next month:} \quad u _ { 2 } = A u _ { 1 } = ( .09875 , .90125 ) \text { . 这就是 } A ^ { 2 } u_0$$

所有的 $u$ 向量都是正值的，因为A是正值的。而且每个向量 $u_k$ 的分量和都是1.那么很长时间后，丹佛的车最终能占多少比例？

这里又涉及到矩阵幂(powers of matrices)。在<01-06>，对幂$A^k$ 的分析，是我们第一个也是最佳的对角化的应用。$A^k$ 可能很复杂，但是对角矩阵 $\Lambda^k$ 是简单的，而且它们有特征向量矩阵S所连接：$A^k = S\Lambda^k S^{-1}$.我们会证明，$u_{\infty}$ 是对应 $\lambda=1$ 的特征向量

因为A的每一列加起来是1，没任何损失也没得到任何东西。所以不管是在例1租车模型还是人口模型当中，是假设了没有车(人)突然消失或出现的。部分和加起来必须是1，而且马尔科夫矩阵会一直保持保持部分和为1.问题在于，经过k个时间周期之后，也就是 $A^k$,每部分现在是怎么分布的呢？

解： $A^ku_0$ 给出了k步之后，丹佛的车所占的比例。我们对角化A来理解 $A^k$.A的特征值是$\lambda_1 =1,\lambda_2=0.75$（迹是1.75）

$$A \boldsymbol { x } = \lambda \boldsymbol { x } \quad A \left[ \begin{array} { l } .2 \\ .8 \end{array} \right] = 1 \left[ \begin{array} { l } .2 \\ .8 \end{array} \right] \quad \text { and } \quad A \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right] = .75 \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right] .$$

初始向量 $u_0$ 是 $x_1,x_2$ 的组合，系数是1、0.18

$$\text{Combination of eigenvectors ： }\quad u _ { 0 } = \left[ \begin{array} { c } .02 \\ .98 \end{array} \right] = \left[ \begin{array} { l } .2 \\ .8 \end{array} \right] + .18 \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right]$$

现在 $u_0$ 乘以A得到 $u_1$,特征向量分别被 $\lambda_1 =1,\lambda_2=0.75$ 乘：

$$\text {Each x is multiplied by } \lambda: \quad u _ { 1 } = 1 \left[ \begin{array} { c } .2 \\ .8 \end{array} \right] + ( .75 ) ( .18 ) \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right]$$

每个月，都有1个额外的0.75乘以 $x_2$,而特征向量 $x_1$ 不改变：

$$\text {After k steps :} \quad u_ { k } = A ^ { k } \boldsymbol { u } _ { 0 } = \left[ \begin{array} { l } .2 \\ .8 \end{array} \right] + ( .75 ) ^ { k } ( .18 ) \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right] .$$

上面等式揭示了：特征值 $\lambda=1$ 对应的特征向量 $x_1$ 就是稳态，另外1个特征向量 $x_2$ 因为 $|\lambda|<1$ 而最终消失了。 经过越多的步骤，我们越接近 $u_{\infty} = (.2,.8)$.极限就是 20% 的车丹佛，80%的车在其他地区。这就是马尔科夫链(Markov chain)的模式，就算初始向量是 $u_0 = (0,1)$

sp:对于 $u_0 = (0,1)$ 可以分解为 $u_0 = 1 \left[ \begin{array} { c } .2 \\ .8 \end{array} \right] + .2 \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right]$,可得：

$$> u_ { k } = A ^ { k } \boldsymbol { u } _ { 0 } = \left[ \begin{array} { l } .2 \\ .8 \end{array} \right] + ( .75 ) ^ { k } ( .2 ) \left[ \begin{array} { r } - 1 \\ 1 \end{array} \right] >$$

所以也是趋向于 $u_{\infty} = x_1$.这里好像是 $c_1$ 一定是1，为啥呢？应该不是，不应该是 $x_1$ 的倍数才一定是稳态，而不是就是$c_1$，但在sp-Note-8.3.1,说的就是$c_1 = 1$ 啊

---

例V24-1 假设马尔科夫矩阵是

$$A = \left[ \begin{array} { c c c } .1 & .01 & .3 \\ .2 & .99 & .3 \\ .7 & 0 & .4 \end{array} \right]$$

为什么会有特征值=1?实际上第2个性质就保证了.我们看看

$$| A - 1I | = \left[ \begin{array} { c c c } - .9 & .01 & .3 \\ .2 & - .01 & .3 \\ .7 & 0 & - .6 \end{array} \right]$$

$A-λI$,相当于这个矩阵平移一个单位矩阵,如果此时是奇异的,那么 $λ=1$就是特征值(因为特征值是对角线元素减去之后使得矩阵奇异的数字).那么为什么这里的 $A− I$是奇异的呢?当然可以计算行列式,但是我们想得到每个马尔科夫矩阵都适用的方法，而不是这个特殊的例子

现在看看 $A− I$ 的各列的元素,加起来是0!这就说明 A-I 是奇异的!因为每一列都是线性相关,所以行列式0,所以奇异(实际上从行向量角度出发更简单,行向量也是线性相关,每列和是0,怎么说明行向量是线性相关呢?哪些行向量的什么线性组合可以得到零向量? (1,1,1)！用它乘以行向量,也就是把各行加起来，结果得到0，它是 $A-I$ 的左零空间$N((A−I)^T)$的向量在(对于方阵,行向量线性相关,就一定是奇异的,所以这也可以证明).

再考虑 $A-I$ 的零空间,列向量的什么组合得到零向量?(列向量不独立，一定存在这样的向量！而且我们想要通用的方法，而不是仅对这个特殊的例子计算！).注意，一旦在 $A-I$ 的零空间找到这个向量,它就是特征向量 $x_1$,为什么?

$$(A-I)x = 0→Ax =x→λ=1$$

而且这个 $x_1$ 就是稳态! 我们就是这样求的对应特征值为1的特征向量 $x_1$ 的! (sp:这里教授应该也是说错了,教授把A-I说成是A),

注意,关于特征值有一个要点：任何 $A$ 和 $A^T$ 的特征值是一样的。为什么？回忆一下,我们是通过计算如下行列式为0求特征值的：

$$> \det (A - λI) = 0 \tag{P1} >$$

而矩阵的行列式等于转置的行列式.所以我们转置Eq(P1). $λI$ 转置之后还是 $λI$, 得到

$$> \det (A - λI) = 0 \quad \Rightarrow \quad \det (A^T - λI) = 0 \tag{P2} >$$

从而从 $A,A^T$ 的行列式是一样的，我们得到 $A,A^T$ 的特征值是一样的。

那么 $x_1$ 到底怎么求？1是 $A^T$ 的特征值,其特征向量是(1,1,1)(sp:因为我们前面证明过，(1,1,1) 可以组合 A 行空间得到0，也就是 $A^T(1,1,1) = 0$)。根据前面的论证，我们得到，1也是A的特征值,但是特征向量不同.我们需要找出来，也就是存在某个向量$x_1$

$$\left[ \begin{array} { c c c } - .9 & .01 & .3 \\ .2 & - .01 & .3 \\ .7 & 0 & - .6 \end{array} \right] \left[ x _ { 1 } \right] = \left[ \begin{array} { l } 0 \\ 0 \\ 0 \end{array} \right]$$

计算一下,得到

$$x _ { 1 } = \left[ \begin{array} { c } .6 \\ 33 \\ .7 \end{array} \right]$$

注意到，这里特征向量的分量都是正值。这和我们的理论是一样的。

---

证明马尔科夫矩阵A存在 $\lambda _{max} = 1$ 如果A是正值的马尔科夫矩阵(每个元素 $a_{ij} > 0$ ，每一列分量和是1),那么 $\lambda_1 = 1$ 是最大的特征值，对应的特征向量 $x_1$ 是稳态：

$$> u _ { k } = x _ { 1 } + c _ { 2 } \left( \lambda _ { 2 } \right) ^ { k } x _ { 2 } + \cdots + c _ { n } \left( \lambda _ { n } \right) ^ { k } x _ { n } \quad \text { 总是逼近 } \quad u _ { \infty } = x _ { 1 } \tag{W1} >$$

---

首先要证明：$\lambda = 1$ 是A的一个特征值。原因：$A-I$ 的每一列的和都是 1-1 = 0，也就是 $A-I$ 的全部行加起来是0，这些行线性相关，所以 $A-I$ 是奇异的，$\lambda = 1$ 是一个特征值。

第2点就是：没有特征向量$|\lambda|>1$.因为如果存在的话，幂 $A^k$ 会不断增长。但注意：$A^k$ 也是马尔科夫矩阵:$A^k$ 元素都非负的，并且每列加起来是1--从而不会增长！

---

sp-Note-8.3.1:

1. 注意上面的条件，A必须是严格正值的，而不仅仅是 $a_{ij}\ge 0$，必须是 $a_{ij}>0$，比性质1要求更严格一点。
2. Eq(w1) 的分解里面，$x_1$ 的系数 $c_1$ 就是1！为啥啊，有点不明白。例V24-2里面，可以看到所有 $a_{ij}>0$，满足要求，但$c_1$ 不是1！所以可以确定，是 $c_1x_1$ 是稳态，而不仅仅$x_1$,应该是书本没有描述清楚！

例2 $A = \left[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right]$ 没有稳态，因为 $\lambda_2 = -1$.

以例1的租车例子来看，这个矩阵A，把所有丹佛的车都送到其他地区，也把其他地区的车都送到丹佛。幂$A^k$ 在 $A,I$ 之间不断交替，第2个特征向量 $x_2 = (-1,1)$ 会不断的被 $\lambda_2 = -1$ 在每一个步骤相乘，并且没有变小，所以没有稳态

假设A和A的幂的所有元素都是正值的--不允许出现0，在这种正规情况(regular case)下**,$\lambda=1$ 会严格大于任何其他的特征值**，幂$A^k$ 会逐渐逼近一个各列都是稳态的秩1矩阵(The powers $A^k$ approach the rank one matrix that has the steady state in every column)

例3 假设有3个小组。在每个步骤

1. 组1的一半人移动到组2，另外1半移动到组3
2. 其他2组也是对半分，然后分别移动到另外2组

假设一开始的人数是 $p_1,p_2,p_3$,那么经过1步之后，人数是

$$u _ { 1 } = A u _ { 0 } = \left[ \begin{array} { c c c } 0 & \frac { 1 } { 2 } & \frac { 1 } { 2 } \\ \frac { 1 } { 2 } & 0 & \frac { 1 } { 2 } \\ \frac { 1 } { 2 } & \frac { 1 } { 2 } & 0 \end{array} \right] \left[ \begin{array} { l } p _ { 1 } \\ p _ { 2 } \\ p _ { 3 } \end{array} \right] = \left[ \begin{array} { c } \frac { 1 } { 2 } p _ { 2 } + \frac { 1 } { 2 } p _ { 3 } \\ \frac { 1 } { 2 } p _ { 1 } + \frac { 1 } { 2 } p _ { 3 } \\ \frac { 1 } { 2 } p _ { 1 } + \frac { 1 } { 2 } p _ { 2 } \end{array} \right]$$

A是马尔科夫矩阵，并且包含了在例2产生麻烦的0元素（有0元素！）。但继续看，第2步之后，$A^2$的0元素消失了：

$$u _ { 2 } = A ^ { 2 } u _ { 0 } = \left[ \begin{array} { l l l } \frac { 1 } { 2 } & \frac { 1 } { 4 } & \frac { 1 } { 4 } \\ \frac { 1 } { 4 } & \frac { 1 } { 2 } & \frac { 1 } { 4 } \\ \frac { 1 } { 4 } & \frac { 1 } { 4 } & \frac { 1 } { 2 } \end{array} \right] \left[ \begin{array} { l } p _ { 1 } \\ p _ { 2 } \\ p _ { 3 } \end{array} \right]$$

A的特征值是$\lambda_1 = 1$（因为A是马尔科夫！）和 $\lambda_2 = \lambda_3 =- \frac{1}{2}$.$\lambda=1$ 对应的特征向量 $x_1 = (\frac{1}{3},\frac{1}{3},\frac{1}{3})$ 将会是稳态。也就是，当3个相等的人数的小组，每个小组的人数都平分然后移动到其他小组，最后的人数还是相等的。如从 $u_0 = (8,16,32)$ 开始，马尔科夫链会逐渐接近稳态：

$$\boldsymbol { u } _ { 0 } = \left[ \begin{array} { r } 8 \\ 16 \\ 32 \end{array} \right] \quad \boldsymbol { u } _ { 1 } = \left[ \begin{array} { l } 24 \\ 20 \\ 12 \end{array} \right] \quad \boldsymbol { u } _ { 2 } = \left[ \begin{array} { l } 16 \\ 18 \\ 22 \end{array} \right] \quad \boldsymbol { u } _ { 3 } = \left[ \begin{array} { c } 20 \\ 19 \\ 17 \end{array} \right]$$

注意 $u_4$ 会尝试将 $u_3$ 第2、3元素的奇数人数在分为1半，这在现实是不可能发生的，没办法在模型中改进这一点。每一步的总人数都是8+16+32=56.稳态就是 $56 * (\frac{1}{3},\frac{1}{3},\frac{1}{3})$

挑战问题 6.7.16 以网站之间的链接数目创建了1个马尔科夫矩阵A.稳态的 $\vec{u}$ 就是Google rankings. Google 通过链接之间的随机游走(random walks) 找到了 $u_{\infty}$ .

注意，第2大特征值 $|\lambda_2|$ 控制秩收敛到稳态的速度

---

例V24-2 现在讲应用,马尔科夫矩阵是怎么来的.我要求解和要就的是 $u_{k+1}=Au_k$,A是马尔科夫矩阵.假设是2-2的,有两个州,加州(cal)和麻省(mass),看这两个州的人口问题.矩阵A表示,一年后发生了人口的迁移,一些人留在麻省,一些人搬去了加州.矩阵的元素表示,迁移或留下的人，占总人数的比例,以分数表示,所以是非负的,而且加起来是1(这里矩阵的元素就是表示留下或者迁移的概率，每一列都是正值，并且加起来是1！).所以满足马尔科夫矩阵的限定.那么我们得到

$$\left[\begin{matrix} u_{cal} \\ u_{mass} \end{matrix} \right]_{t = k+1} = \left[\begin{matrix} .9 & .2 \\ .1 & .8 \end{matrix} \right] \left[\begin{matrix} u_{cal} \\ u_{mass} \end{matrix} \right]_{t = k}$$

注意矩阵有严格的限制:在k不断变换的过程，这个矩阵A是保持不变的。也就是马尔科夫矩阵A是不变的。

矩阵A第1列代表的是加州人的迁移,.9的人留在了加州,.1的人搬去了麻省.我们考虑一下稳态是什么,100年后,麻省加州的人数是怎么样的呢?假设初始状态是，加州0人,麻省1000人，那么稳态是什么？

一旦给出了建模,就要开始求特征值和特征向量了.A的一个特征值是1,第二个特征值可以根据迹算出来,就是0.7(小于1，行列式是就是0.7).再看特征向量,直接计算

$$(A- 1I ) x_1 = 0\quad \Rightarrow \left[\begin{matrix} -.1 & .2 \\ .1 & -.2\end{matrix} \right]x_1= 0 \qquad \Rightarrow x_1=(2,1)$$

注意到特征向量的分量是正值的.现在我们可以开始跳到无穷步后的人数了,稳态就是由这个特征向量给出的,是这个向量的倍数,怎么确定倍数关系呢?稳态下

$$\left[\begin{matrix} u_{cal} \\ u_{mass} \end{matrix} \right]_{t = \infty} = c_1 \lambda_1^{\infty} x_1 + c_2\lambda_2^{\infty}x_2$$

注意到以为$\lambda_2<1$,所以 $\lambda_2^{\infty}$ 收敛大0，那么式子只剩下 $c_1\lambda_1^{\infty}x_1 = c_1x_1$,而 $x_1$ 的分量和是3,而总人数数是1000，所以1000的2/3,1/3就是稳态！稳态就是 $x_1$ 的倍数！而优先步骤，如100步以后的人数，怎么得到呢》还是要求一下 $x_2$,也就是 $|A-λ_2 |$ 的零空间,得到 $x_2=(−1,1)$,那么

$$\left[\begin{matrix} u_{cal} \\ u_{mass} \end{matrix} \right]_{t = 100} = c_1 1^{100} \left[\begin{matrix} 2 \\1 \\\end{matrix} \right] + c_2(.7)^{100}\left[\begin{matrix} -1 \\1 \\\end{matrix} \right]$$

在根据$u_0$求出 $c_1,c_2$. 我们的矩阵是作用在 $u_0=\left[\begin{matrix} 0 \\1000 \\\end{matrix} \right]$ 上的,如果我们将 k = 0 带入上面的公式,得到

$$u _ { 0 } = \left[ \begin{array} { c } 0 \\ 1000 \end{array} \right] = c _ { 1 } \left[ \begin{array} { l } 2 \\ 1 \end{array} \right] + c _ { 2 } \left[ \begin{array} { c } - 1 \\ 1 \end{array} \right]$$

两个方程,两个常数,两个特征向量肯定线性无关,有唯一解,得到

$$u _ { 0 } = \left[ \begin{array} { c } 0 \\ 1000 \end{array} \right] = \frac{1000}{3} \left[ \begin{array} { l } 2 \\ 1 \end{array} \right] + \frac{2000}{3}\left[ \begin{array} { c } - 1 \\ 1 \end{array} \right]$$

这就是马尔科夫矩阵！特征值小于1的部分将会在无穷步骤之后消失！

注意，在很多应用当中,人们更喜欢使行向量，此时用行向量来左乘矩阵,我们使用的是矩阵的转置,因此在很多课本当中,你会看到马尔科夫矩阵的行向量的元素和是1,而不是列向量

Perron-Frobenius Theorem

• 以下简称为PF定理

只要矩阵所有的元素 $a_{ij}\ge0$， 就可以应用PF定理，不需要列元素加起来是1。我们证明其最简洁的形式:所有 $a_{ij} > 0$

Perron-Frobenius for A > 0

---

$Ax = \lambda_{max}x$ 当中的x的所有分量都是严格正值的。(注意，需要是$\lambda_{max}$ 对应的特征向量)

证明： 证明思想是：对一些非负向量 x （而不是$\vec{x}=\vec{0}）$.寻找所有满足 $Ax \ge tx$ 的数字 t,这些 t 当中，肯定有1个最大的$t_{max}$ ，对于 $t_{max}$ 我们证明 $Ax = t_{max}x$ 等式成立

如果 $Ax \ge t_{max}x$ 不能取得等号，因为A>0，所以可取得严格不等式 $A^2x > t_{max}Ax$.因此对于正值的 y=Ax,有 $Ay > t_{max}y$.

sp:证明看不懂，记住定理把

人口增长

Population growth

把全国人口划分为3个区间： $年龄<20;20 \le 年龄 \le 39;40\le 59$. 如果在年份T，3个组的人口分别是 $n_1,n_2,n_3$.设3个组的生育率分别为 $F_1,F_2,F_3$（$F_2$ 会最大），那么20年过后，每个组的人口的会因为出生率和存活率有所变动：

• $n_1$组：20年后，这一组的人口全部都是新出生的人口，也就是 $n _ { 1 } ^ { \text {new } } = F _ { 1 } n _ { 1 } + F _ { 2 } n _ { 2 } + F _ { 3 } n _ { 3 }$
• $n_2$组：人口全部来自于$n_1$ 组的存活：$n _ { 2 } ^ { \text {new } } = P _ { 1 } n _ { 1 }$
• $n_2$组：人口全部来自于$n_2$ 组的存活：$n _ { 3 } ^ { \text {new } } = P _ { 2 } n _ { 2 }$

如下是建模，矩阵称为莱斯利矩阵（Leslie matrix A）：

$$\left[ \begin{array} { c } n _ { 1 } \\ n _ { 2 } \\ n _ { 3 } \end{array} \right] ^ { \text {new } } = \left[ \begin{array} { c c c } F _ { 1 } & F _ { 2 } & F _ { 3 } \\ P _ { 1 } & 0 & 0 \\ 0 & P _ { 2 } & 0 \end{array} \right] \left[ \begin{array} { l } n _ { 1 } \\ n _ { 2 } \\ n _ { 3 } \end{array} \right] = \left[ \begin{array} { c c c } .04 & 1.1 & .01 \\ .98 & 0 & 0 \\ 0 & .92 & 0 \end{array} \right] \left[ \begin{array} { l } n _ { 1 } \\ n _ { 2 } \\ n _ { 3 } \end{array} \right]$$

以上是最简单的人口模型，矩阵A 不改变，现实当中上A会随着时间改变(环境、经济因素等).更专业的模型还会包括第4个 年龄>60.

这个矩阵 $A \ge 0$ 但不是 $A>0$.但仍然可以使用PF定理，以为 $A^3 >0$.最大的特征值是 $\lambda_{max} = 1.06$

$$\operatorname { eig } ( A ) = \begin{array} { r } 1 . 0 6 \\ - 1.01 \\ - 0.01 \end{array} \quad A ^ { 2 } = \left[ \begin{array} { c c c } 1.08 & 0.05 & .00 \\ 0.04 & 1.08 & .01 \\ 0.90 & 0 & 0 \end{array} \right] \quad A ^ { 3 } = \left[ \begin{array} { l l l } 0.10 & 1.19 & .01 \\ 0.06 & 0.05 & .00 \\ 0.04 & 0.99 & .01 \end{array} \right]$$

如果从初始向量 $u_0 = (0,1,0)$,也就是只有 $n_2 = 1$开始。第1个20年过后，$n_2$ 产生了1.1个$n_1$,存活了0.92到$n_3$.所以$n_2 = (1.1,0,.92) = A 的列2$ 。 注意： $u_2 = Au_1 = A^2u_0=A^2的列2$(因为$u_0$ 只有第2个元素是1).前面的一些序列严重依赖与初始向量 $u_0$ ,但渐进增长率(the asymptotic growth rate) $\lambda_{max}$ 对所有的起点 $u_0$ 都是一样的。$\lambda_{max}$ 对应的特征向量是 $x= (.63,.58,.51)$

经济学当中的线代：消费矩阵

Linear Algebra in Economics: The Consumption Matrix

消费矩阵可以告诉我们：生产1单位的产出，需要消耗各种输入分别多少单位。设有3个产额：化学物品、食物、石油。而生产1单位的化学物质需要 .2单位的化学物质、.3单位的食物和 .4 单位的石油，这些数字成为消费矩阵A的第1行：

$$\left[ \begin{array} { c } \text { chemical output } \\ \text { food output } \\ \text { oil output } \end{array} \right] = \left[ \begin{array} { c c c } .2 & .3 & .4 \\ .4 & .4 & .1 \\ .5 & .1 & .3 \end{array} \right] \left[ \begin{array} { c } \text { chemical input } \\ \text { food input } \\ \text { oil input } \end{array} \right]$$

现实生活种，USA 1958年的消费矩阵包含83个行业，很复杂，这里我们选择的消费矩阵的特征向量是特殊的。

现在有了问题:经济可以承担对化学物品=y1、食物=y2、石油=y3的要求吗？注意，输入的 $p_1,p_2,p_3$ 会比想象的大一点，因为部分的p需要在生产y的时候被消耗掉：输入p，消耗了Ap,净产出是 p - Ap.

问题： 求一个向量p满足 $p - Ap = y$ 或 $p = (I - A)^{-1} y$

明显这个问题的线代方法就是判断 $I-A$ 是否可逆。但实际上仅考虑这一点不够，以为 y 明显是非负的，而且A也是，而且 $p = (I - A)^{-1} y$ 也必须是非负的。实际问题是：什么时候 $(I - A)^{-1}$ 是1个非负矩阵？

如果A比I小，那么Ap就比p小，会有很多的产出。如果A很大，那么产出所消耗的比产出本身更多，这时需求y就无法被满足

其实A的小、大的概念是根据A的最大特征值$\lambda_1$ (是一个正数)来判断的:

• 如果 $\lambda_1>1$,那么 $(I - A)^{-1}$ 有负元素
• 如果 $\lambda_1=1$,那么 $(I - A)^{-1}$ 不存在
• 如果 $\lambda_1<1$,那么 $(I - A)^{-1}$ 是非负的，并且是我们想要的

我们把注意力几种在最后1种情况。我们为什么选 $(I - A)^{-1}$ 这种形式表达呢？回忆一下几何级数： $1+x+x^2+...$ ，如果$-1<x<1$,那么极限是 $1/(1-x)$.否则级数不收敛。

$(I - A)^{-1}$ 也有一个漂亮的公式：矩阵几何级数(geometric series of matrices):

$$\text{Geometric series}:\qquad ( I - A ) ^ { - 1 } = I + A + A ^ { 2 } + A ^ { 3 } + \cdots$$

设上述级数为S，如果将A再乘以S,得到 $AS = A+A^2+....$,也就是只少了第1个元素 I 不同，可得 :$S- AS = I$,也就是 $(I - A)S = I$,又可得到 $S = (I - A)^{-1}$.这个级数在A的所有特征值 $|\lambda<1|$ 时收敛。

在我们的模型当中， $A\ge 0$，也就是所有元素非负。要求它的和 $(I - A)^{-1}\ge 0$

例4