Por qué las matrices de Markov siempre tienen 1 como valor propio

Question

También llamada matriz estocástica. Sea

• $A=[a_{ij}]$ - matriz sobre $\mathbb{R}$

• $0\le a_{ij} \le 1 \forall i,j$

• $\sum_{j}a_{ij}=1 \forall i$

es decir, la suma a lo largo de cada columna de $A$ es 1. Quiero mostrar $A$ tiene un valor propio de 1. La forma en que he visto esto es que $A^T$ tiene claramente un valor propio de 1, y los valores propios de $A^T$ son los mismos que los de $A$ . Esta prueba, sin embargo, utiliza determinantes, transposiciones de matrices y el polinomio característico de una matriz, ninguno de los cuales es un concepto especialmente intuitivo. ¿Alguien tiene una prueba intuitiva alternativa (o un esbozo de prueba)?

Mi objetivo es entender intuitivamente por qué, si $A$ define las probabilidades de transición de alguna cadena de Markov, entonces $A$ tiene un valor propio de 1. Estoy estudiando el algoritmo PageRank de Google.

Answer 1

Acabo de encontrar el mismo problema que tú, aquí está mi solución.

Subo mi solución por imagen

Answer 2

Mi intuición es que como $A$ describe una transición de algún vector que codifica la distribución de probabilidad a otro vector que también codifica la distribución de probabilidad, $A$ no se permite aumentar o reducir la escala del vector en la misma dirección, porque de lo contrario ese vector dejará de tener todas sus entradas sumando $1$ y ya no sería una distribución de probabilidad.

En otras palabras, supongamos que $A$ es una matriz de Markov, y $v$ es un vector que representa alguna distribución de probabilidad. Esto significa que todas las entradas de $v$ tienen que sumar uno.

Ahora dejemos que $v'= vA$ . Si $v$ fuera un vector propio, eso significa que $v' = \lambda v$ . Desde $v'$ es también una distribución de probabilidad, todas sus entradas deben sumar también $1$ y esto sólo puede ocurrir si $\lambda = 1$ .

Answer 3

Supongamos que $M$ tiene un vector propio izquierdo, $u$ con valor propio $\lambda$ : $$ u^T(M-I\lambda)=0\tag{1} $$ Dejemos que $\{v_j\}_{j=1}^n$ sean las columnas de $M-I\lambda$ . Ecuación $(1)$ dice que para todos $j$ , $u\perp v_j$ .

En $n+1$ vectores en $\mathbb{R}^n$ , $u$ y $\{v_j\}_{j=1}^n$ debe ser linealmente dependiente. Es decir, hay $a$ y $\{b_j\}_{j=1}^n$ no todos $0$ para que $$ au+\sum_{j=1}^nb_jv_j=0\tag{2} $$ Si tomamos el producto punto de $u$ con $(2)$ obtenemos $$ \|u\|^2a+\sum_{j=1}^n0\,b_j=0\tag{3} $$ Eso es, $a=0$ . Así, $(2)$ se convierte en $$ \sum_{j=1}^nb_jv_j=0\tag{4} $$ donde no todos $b_j$ son $0$ . $(4)$ puede reescribirse como $$ M\begin{bmatrix}b_1\\b_2\\b_3\\\vdots\\b_n\end{bmatrix} =\lambda\begin{bmatrix}b_1\\b_2\\b_3\\\vdots\\b_n\end{bmatrix}\tag{5} $$ Por lo tanto, $M$ tiene un vector propio derecho con valor propio $\lambda$ .

Answer 4

Para una matriz de Markov A, conocemos el j-ésimo elemento diagonal de $(A-I)$ puede expresarse como $-\sum^n_{i \neq j} a_{ji}$ .

Puede que no sea demasiado obvio ver que $det(A-I)=0$ mientras que es más fácil demostrar $det((A-I)^T)=0$ . Esto se debe a que, para $(A-I)^T x =0$ tenemos una solución no nula $x=(1,1,\cdots,1)$ , indicando $(A-I)^T$ es singular. Para una matriz cuadrada $(A-I)$ tenemos $det(A-I)=det((A-I)^T)=0$ Por lo tanto, sabemos que $1$ es un valor propio de la matriz de Markov A.

Answer 5

Dejemos que $A$ sea una matriz estocástica, tal y como ha indicado en su pregunta. Sea $\mathbf{1}$ sea un vector columna de todos los $1$ s. Entonces el $j$ El componente de $A1$ es la suma de los $j$ La fila de $A$ . Esto da $A1 = 1$ . Así, $\lambda = 1$ es un valor propio correspondiente al vector propio 1.

También cuando intentas diagonalizar una matriz estocástica que todas las filas suman 1 el polinomio característico se factoriza $(\lambda -1)$ sin importar el resto del polinomio.