CBMS-2024A-08
题目来源：Question 8 日期：2024-07-31 题目主题：Math-线性代数/概率论-马尔可夫链
解题思路
这道题目涉及马尔可夫链的转移矩阵、特征向量、矩阵幂运算、极限计算以及矩阵迹的性质。我们需要运用线性代数的知识来分析转移矩阵的特征值和特征向量，利用这些来计算矩阵的幂和极限。最后，我们还需要证明关于矩阵迹的一些性质。
Solution
1. Eigenvector Proof
To show that is an eigenvector of , we need to find a scalar such that .
Let’s compute:
\mathbf{P}\begin{pmatrix} p \\ -q \end{pmatrix} &= \begin{pmatrix} 1 - p & p \\ q & 1 - q \end{pmatrix}\begin{pmatrix} p \\ -q \end{pmatrix} \\ &= \begin{pmatrix} (1-p)p + p(-q) \\ qp + (1-q)(-q) \end{pmatrix} \\ &= \begin{pmatrix} p - p^2 - pq \\ qp - q + q^2 \end{pmatrix} \\ &= \begin{pmatrix} p(1 - p - q) \\ -q(1 - p - q) \end{pmatrix} \\ &= (1 - p - q)\begin{pmatrix} p \\ -q \end{pmatrix} \end{aligned}$$ Therefore, $\begin{pmatrix} p \\ -q \end{pmatrix}$ is indeed an eigenvector of $\mathbf{P}$ with eigenvalue $\lambda = 1 - p - q$. ### 2. n-th Order Transition Matrix To find $\mathbf{P}^n$, we'll use the eigen-decomposition of $\mathbf{P}$. We already found one eigenpair. Let's find the other: The characteristic equation is: $\det(\mathbf{P} - \lambda\mathbf{I}) = (1-p-\lambda)(1-q-\lambda) - pq = 0$ Solving this, we get: $\lambda_1 = 1$ and $\lambda_2 = 1 - p - q$ The eigenvector corresponding to $\lambda_1 = 1$ is $\mathbf{v}_1 = \begin{pmatrix} q \\ p \end{pmatrix}$ Now we can write $\mathbf{P} = \mathbf{S}\mathbf{\Lambda}\mathbf{S}^{-1}$, where: $$\mathbf{S} = \begin{pmatrix} q & p \\ p & -q \end{pmatrix}, \quad \mathbf{\Lambda} = \begin{pmatrix} 1 & 0 \\ 0 & 1-p-q \end{pmatrix}$$ Therefore, $$\mathbf{P}^n = \mathbf{S}\mathbf{\Lambda}^n\mathbf{S}^{-1} = \frac{1}{p^2 + q^2}\begin{pmatrix} q & p \\ p & -q \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & (1-p-q)^n \end{pmatrix} \begin{pmatrix} q & p \\ p & -q \end{pmatrix}$$ After multiplication, we get: $$\mathbf{P}^n = \begin{pmatrix} \frac{q^2 + p^2(1-p-q)^n}{p^2 + q^2} & \frac{pq - pq(1-p-q)^n}{p^2 + q^2} \\ \frac{pq - pq(1-p-q)^n}{p^2 + q^2} & \frac{p^2 + q^2(1-p-q)^n}{p^2 + q^2} \end{pmatrix}$$ ### 3. Limit of $\mathbf{P}^n$ as $n \to \infty$ As $n \to \infty$, $(1-p-q)^n \to 0$ since $|1-p-q| < 1$. Therefore, $$\lim_{n \to \infty} \mathbf{P}^n = \begin{pmatrix} \frac{q^2}{p^2+q^2} & \frac{pq}{p^2+q^2} \\ \frac{pq}{p^2+q^2} & \frac{p^2}{p^2+q^2} \end{pmatrix}$$ ### 4. Proof of $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i$ Let $\mathbf{A}$ be diagonalizable (if not, we can use the Jordan canonical form). Then $\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}$, where $\mathbf{D}$ is a diagonal matrix with eigenvalues on the diagonal. $$\begin{aligned} \mathrm{tr}\, \mathbf{A} &= \mathrm{tr}\, (\mathbf{P}\mathbf{D}\mathbf{P}^{-1}) \\ &= \mathrm{tr}\, (\mathbf{D}\mathbf{P}^{-1}\mathbf{P}) \quad \text{(cyclic property of trace)} \\ &= \mathrm{tr}\, \mathbf{D} \\ &= \sum_{i=1}^{n} \lambda_i \end{aligned}$$ ### 5. Proof: If $\mathbf{A}^m = \mathbf{O}$, then $\mathrm{tr}\, \mathbf{A} = 0$ We will prove this statement using the following steps: 1) Let $\lambda_1, \lambda_2, ..., \lambda_n$ be the eigenvalues of $\mathbf{A}$ (including algebraic multiplicities). 2) From the condition $\mathbf{A}^m = \mathbf{O}$, we know that $\mathbf{A}$ is nilpotent. For a nilpotent matrix, all its eigenvalues are zero. We can prove this as follows: If $\lambda$ is an eigenvalue of $\mathbf{A}$, then $\lambda^m$ is an eigenvalue of $\mathbf{A}^m$. Since $\mathbf{A}^m = \mathbf{O}$, all eigenvalues of $\mathbf{A}^m$ must be zero. Therefore, $\lambda^m = 0$, which implies $\lambda = 0$. 3) From the result in part 4, we know that $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i$. 4) Since all eigenvalues of $\mathbf{A}$ are zero, we have: $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i = 0 + 0 + ... + 0 = 0$ Therefore, we have proved that if $\mathbf{A}^m = \mathbf{O}$, then $\mathrm{tr}\, \mathbf{A} = 0$. ## 知识点 #马尔可夫链 #特征值和特征向量 #矩阵对角化 #矩阵极限 #矩阵迹 ## 难点思路 本题的难点在于第2问和第3问，需要利用矩阵的特征分解来计算矩阵的幂。关键是要认识到可以用特征值和特征向量将矩阵对角化，从而简化矩阵幂的计算。另外，在计算矩阵的逆时要特别注意，因为这里很容易出错。 ## 解题技巧和信息 1. 在处理马尔可夫链问题时，注意转移矩阵的特征值总有一个是1。 2. 计算矩阵的高次幂时，考虑使用特征分解方法。 3. 在证明矩阵性质时，考虑使用特征值的性质。 4. 矩阵迹的性质在很多证明中都很有用，要熟练掌握。 5. 在进行矩阵运算时，要仔细检查每一步，特别是在计算逆矩阵时。 ## 重点词汇 - Markov chain 马尔可夫链 - transition matrix 转移矩阵 - eigenvalue 特征值 - eigenvector 特征向量 - matrix diagonalization 矩阵对角化 - trace of a matrix 矩阵的迹 - characteristic equation 特征方程 - steady state 稳态 ## 参考资料 1. Strang, Gilbert. "Linear Algebra and Its Applications." Chapter 5: Eigenvalues and Eigenvectors. 2. Ross, Sheldon M. "Introduction to Probability Models." Chapter 4: Markov Chains. 3. Horn, Roger A., and Charles R. Johnson. "Matrix analysis." Chapter 1: Eigenvalues, Eigenvectors, and Similarity.