Límite de la energía de la matriz de Markov

Question

Recientemente, un amigo me dio el siguiente problema:

Que $$M = \begin{pmatrix} p & q & r \\ q & r & p \\ r & p & q \end{pmatrix}$$ where $p, q, r > 0 $ and $p + q + r = 1$. Prove that $% $ $\lim_{n \rightarrow \infty} M^n = \begin{pmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{pmatrix}$

Algunas de mis observaciones son que $M^{2^n}$ sigue siendo cíclica, así que intenté ligados (sin suerte) máximo y mínimo para ver si ambos convergieron para $1/3$.

Sería bueno si alguien pudiera publicar una elemental solución a este problema.

Answer 1

Este un problema que es, probablemente, la intención de ser resuelto mediante cadenas de Markov. Voy a suponer que usted tiene un conocimiento básico de la materia.

---

Supongamos $(X_n)_{n\in\mathbb{N}}$ es homogénea de la cadena de markov con matriz de transición dada por $$P=\begin{pmatrix} p & q & r\\ q & r & p\\ r & p & q \end{pmatrix}$$ donde$p+q+r=1$$p,q,r>0$. Entonces, claramente, la cadena es irreducible y ergodic.

Ergodic teorema: Si $(X_n)_{n\in\mathbb{N}}$ es una irreductible y ergodic de la cadena de Markov, entonces, se admite un único stationnary de distribución que satisfaga $$\pi_j=\lim_{n\to \infty} p_{i,j}^{(n)}\qquad \forall i,j.$$

La solución de la ecuación de $\pi P=\pi$ para su cadena de da $$\pi=(1/3,1/3,1/3)$$ y así, por el citado teorema, $$\lim_{n\to \infty} P^{(n)}=\begin{pmatrix} \pi_1 & \pi_2 & \pi_3\\ \pi_1 & \pi_2 & \pi_3\\ \pi_1 & \pi_2 & \pi_3 \end{pmatrix}=\begin{pmatrix} 1/3 & 1/3 & 1/3\\ 1/3 & 1/3 & 1/3\\ 1/3 & 1/3 & 1/3 \end{pmatrix}$$ cual es el resultado que estábamos buscando.

Answer 2

Vamos $$ \sigma = p^2 + q^2 + r^2 - qr - rp - pq = \frac{1}{2} \left( (q-r)^2 + (r-p)^2 + (p-q)^2 \right) \geq 0. $$ Nota: $ \sigma = (p+q+r) \sigma = p^3 + q^3 + r^3 - 3 pqr.$ Es por eso que el polinomio característico de la matriz es $$ \lambda^3 - \lambda^2 - \sigma \lambda + \sigma = (\lambda - 1)(\lambda^2 - \sigma) $$ En el otro lado $$ 1 = p^2 + q^2 + r^2 +2 qr +2 rp +2 pq, $$ lo $$ \sigma = 1 - 3 (qr + rp + pq) < 1. $$ Los valores propios son $1, \sqrt \sigma, -\sqrt \sigma.$ El diagonalized matriz $ D = P^T MP$ (donde $P$ es ortogonal) elevado a una forma arbitraria de gran potencia, converge a la matriz diagonal con entradas de $1,0,0.$ Inversa de la diagonalización, obtenemos un simétrica rango de una matriz.. dame un minuto

¿Dónde estaba yo? $$ P = \left( \begin{array}{rr} \frac{1}{\sqrt 3} & a & b \\ \frac{1}{\sqrt 3} & c & d \\ \frac{1}{\sqrt 3} & e & f \end{array} \right) $$ $$ D_\infty = \left( \begin{array}{rr} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array} \right) $$ Luego nos acaba de multiplicar $$ M_\infty = P D_\infty P^T = \left( \begin{array}{rr} \frac{1}{ 3} & \frac{1}{ 3} & \frac{1}{ 3} \\ \frac{1}{ 3} & \frac{1}{ 3} & \frac{1}{ 3} \\ \frac{1}{ 3} & \frac{1}{ 3} & \frac{1}{ 3} \end{array} \right) $$

Answer 3

en primer lugar observamos que todos, incluso los poderes de $M$ se encuentran dentro de una de dos dimensiones subalgebra cuyos miembros se denota $A(x,y)$$x,y \in \mathbb{R}$, desde $$ M^2 = \begin{pmatrix} x_2 & y_2 & y_2 \\ y_2 & x_2 & y_2 \\ y_2 & y_2 & x_2 \end{pmatrix} = A(x_2,y_2) $$ donde $$ x_2=p^2+q^2+r^2 $$ y $$ y_2 = pq+qr+rp $$ con $$ x_2+2y_2 = (p+q+r)^2 =1 $$ para su posterior squarings (de $M$) tendremos: $$ x_{2^{n+1}} = x_{2^n}^2+2y_{2^n}^2 \\ y_{2^{n+1}} = 2x_{2^n}y_n+y_{2^n}^2 $$ a partir de los cuales tenemos: $$ x_{2^{n+1}}+ 2y_{2^{n+1}} = (x_{2^n}+ 2y_{2^n})^2 = 1\etiqueta{1} $$ y $$ x_{2^{n+1}}-y_{2^{n+1}} = (x_{2^n}-y_{2^n})^2 = \lambda^{2^n} \etiqueta{2} $$ donde $0 \le \lambda = x_2-y_2 \lt 1$

se puede comprobar con facilidad que si $$ A(X,Y) = a(x,y)a(x',y') $$ entonces $$ X-Y = (x-y)(x'-y') $$ cualquier número $2N$ puede ser escrito $$ 2N = \sum_{k=1} a_k2^k $$ con $a_k \in \{0,1\}$, por lo que $$ M^{2N} = \prod_{a_k=1} M^{2k} $$ así que, usando (2) $$ x_{2N}-y_{2N} = \lambda^N $$ esto muestra que el subsequence $M^2,M^4,M^6,\dots$ converge a $A(\frac13,\frac13)$# para lidiar con los extraños poderes de los que nos tenga en cuenta que $$ M^{2N+1} = M(M^{2N}) = M\bigg(Un(\frac13,\frac13) + \frac13\lambda^N a(2,-1)\bigg) = A(\frac13,\frac13) +O(\lambda^N) $$

Answer 4

Aquí es un poco enfoque racionalizado. Deje $E$ la matriz con todas las entradas igual a $1$ y deje $A=M^2$. Para demostrar que $M^n$ converge a $\frac13E$, es suficiente para mostrar que $A^n$ converge a $\frac13E$, debido a que dicha convergencia implica también que $M^{2n+1}=A^nM$ converge a $\frac13EM=\frac13E$.

Como otra respuesta ha señalado, $A=M^2$ es en forma de $$ A=M^2=\pmatrix{x&y&y\\ y&x&y\\ y&y&x}, $$ donde $y=pq+qr+rp$. Dado que todos los de la fila de sumas de $M$ son igual a $1$, fila sumas de $A$ debe ser igual a$1$, es decir,$x+2y=1$. Además, como $p+q+r=1$, si sustituimos la igualdad de $p^2+q^2+r^2=1-2(pq+qr+rp)$ en la desigualdad de $(p-q)^2+(q-r)^2+(r-p)^2\ge0$, obtenemos $y=pq+qr+pr\le\frac13$. Así $$ A=(1-3y)I+os, $$ donde $0\le 1-3y<1$.

Deje $U$ ser real ortogonal de la matriz cuya primera columna es el vector unitario $\frac1{\sqrt{3}}(1,1,1)^T$. A continuación,$E=3U\operatorname{diag}(1,0,0)U^T$. En consecuencia, $$ \begin{align} \lim_{n\to\infty}A^n &=\lim_{n\to\infty}U\,[\,(1-3y)I+3y\operatorname{diag}(1,0,0)\,]^n\,U^T\\ &=\lim_{n\to\infty}U\operatorname{diag}(1,\,1-3y,\,1-3y)^nU^T\\ &=U\operatorname{diag}(1,0,0)U^T=\frac13E. \end{align} $$

Answer 5

A excepción de la última línea, esto es puramente algebraica respuesta, ya que hay un montón de estructura especial en este problema. (Nota Gerschgorin discos son de una escuela primaria y poderosa, pero subutilizadas herramienta para acotar autovalores. Ellos también tienen una buena imagen asociada con ellos.)

usted tiene un verdadero valorado simétrica la matriz de transición. Por lo tanto es diagonalizable con el real de los autovalores, y mutuamente vectores propios ortonormales.

$M = U \Lambda U^T$

Es de filas y columnas tanto suma a uno, es decir, el doble de la estocástica. Por eso sabemos $\lambda_1 = 1$$\mathbf u_1 \propto \mathbf 1$. (De hecho,$\mathbf u_1 = \frac{1}{\sqrt{3}}\mathbf 1$)

$trace(M) = p + q + r = 1 = \lambda_1 + \lambda_2 + \lambda_3 = 1 +\lambda_2 + \lambda_3$

Por eso sabemos $\lambda_2 + \lambda_3 = 0$. Dicho de otra manera: $\lambda_2 = - \lambda_3$.

El uso de Gerschgorin discos para que el mínimo autovalor $\gt -1$.

I. e. cada disco tiene un punto de centro $\gt 0$ y un radio de $\lt 1$. (Es realmente más de un segmento de línea que un disco que ya sabemos que los valores propios son reales, pero todavía podemos sacar el disco como un límite superior.)

Por lo tanto $\vert\lambda_2\vert \lt 1$ $\vert\lambda_3\vert \lt 1$

$M^n = U \Lambda^n U^T = \big(\lambda_1^n \mathbf u_1 \mathbf u_1^T + \lambda_2^n \mathbf u_2 \mathbf u_2^T + \lambda_3^n \mathbf u_3 \mathbf u_3^T \big) = \big(1^n \mathbf u_1 \mathbf u_1^T + \lambda_2^n \mathbf u_2 \mathbf u_2^T + \lambda_3^n \mathbf u_3 \mathbf u_3^T \big)$

ahora, al final, tomar un límite:

$\lim_{n \to \infty} M^n = \lim_{n \to \infty}\big(1^n \mathbf u_1 \mathbf u_1^T + \lambda_2^n \mathbf u_2 \mathbf u_2^T + \lambda_3^n \mathbf u_3 \mathbf u_3^T\big) = 1 \mathbf u_1 \mathbf u_1^T + 0 \mathbf u_2 \mathbf u_2^T + 0 \mathbf u_3 \mathbf u_3^T = \mathbf u_1 \mathbf u_1^T $