Substochastic Matriz espectral de la radio

Question

Deje $M$ ser una fila substochastic de la matriz, con al menos una fila de tener suma menor que 1. También, supongamos $M$ es irreductible, en el sentido de una cadena de markov. Hay una manera fácil de mostrar el mayor autovalor debe ser estrictamente menor que 1? Espero que este resultado es cierto como se dice. Sé que Cauchy entrelazado teorema da a me $\leq$,

Answer 1

Un poco tarde para el juego, pero pensé que de esta prueba.

Supongamos $A$ es una irreductible sub-matriz estocástica y $\lambda$ es el Perron-Frobenius autovalor de a $A$ ( $\rho\left(A\right) = \lambda$ ) $v$ el correspondiente vector propio normalizado tal que $\|v\|_{1} = 1$. Por el Perron-Frobenius teorema para irreductible no negativa de matrices, en las entradas de $v$ debe ser positivo. Con esto, tenemos la siguiente.

\begin{align} |\lambda| &= \|\lambda v\|_{1} \\ &= \|vA\|_{1} \\ &= \sum_j\sum_k v_jA_{jk} \end{align} Deje $\epsilon_j \doteq \frac{1}{N}\left(1 - \sum_{k=1}^N A_{jk}\right)$. Si añadimos $\epsilon_j$ a cada elemento de la $j$ésima fila de A, la fila suma que se convierten en uno. Deje $\boldsymbol\epsilon$ ser el vector fila que contiene los valores de $\{\epsilon_j\}$. \begin{align} |\lambda| &= \sum_j \sum_k v_j\left(A_{jk} + \epsilon_j - \epsilon_j\right) \\ &= \sum_j \sum_k v_j\left(A_{jk} + \epsilon_j\right) -\sum_j \sum_k v_j \epsilon_j \\ &= \left\|v\left(A + \boldsymbol\epsilon^T\mathbf{1}\right)\right\|_1 - N \left(\boldsymbol\epsilon\cdot v\right) \end{align}

Definimos $\hat A \doteq A + \boldsymbol\epsilon^T\mathbf{1}$ y se nota que es una matriz estocástica. Desde $v$ es positiva y $\boldsymbol\epsilon$ es no negativo, con al menos uno de los efectos positivos de la entrada tenemos $\boldsymbol\epsilon\cdot v > 0$. \begin{align} |\lambda| &= \left\| v \hat A \right\|_{1} - N \left(\boldsymbol\epsilon\cdot v\right) \\ &= 1 - N \left(\boldsymbol\epsilon\cdot v\right) \\ &< 1 \end{align}

Answer 2

Usted puede tratar de completar la matriz para una cadena de Markov, la adición de un auto de bucle en el adicional del estado. La nueva cadena de Markov es irreducible y aperiódica por lo que tiene una única distribución estacionaria, que se concentra en el adicional del estado. También es el único vector propio con autovalor al menos $1$.

Ahora tome un supuesto vector propio de su matriz original con autovalor $1$, y añadir un cero de coordenadas. El resultado es un vector propio para la cadena de Markov, contradiciendo las propiedades que se enumeran más arriba.

En efecto, usted tiene una cadena de Markov con un invisible absorción de estado, que en realidad es accesible desde cualquier otro estado. Esto asegura que en el largo plazo, el estado será alcanzado, y en consecuencia la aplicación de la matriz muchas veces, sobre cualquier vector dado producirá el vector cero. Así que todos los autovalores debe ser menor que 1 en magnitud.

Answer 3

Esta es, esencialmente, Yuval del argumento probabilístico con la probabilidad de quitar. El objetivo es mostrar que los poderes de $M$ converge a cero.

Para cualquier estado $i$ e integer $n\geq 0$, vamos a $r^n_i=\sum_k M^n_{i k}$ el valor del $i$th fila suma de $M^n$. Para $n=1$, escribimos $r_i$ en lugar de $r^1_i$. Desde $M$ es substochastic tenemos $0\leq r^n_i\leq 1$.

Deje $k^*$ ser un índice con $r_{k^*}<1$, y tenga en cuenta que para $n\geq 1$
$$r^n_{k^*}=\sum_k M_{k^* k}\ r_k^{n-1}\leq \sum_k M_{k^* k} =r_{k^*}<1.$$

Por irreductibilidad, para cualquier $i$, hay un $m$$M_{i k^*}^m>0$. De hecho, si $M$ $N\times N$ matriz, y $i\neq k^*$, entonces podemos suponga $m<N$. (Tomar el camino más corto de $i$ $k^*$con un resultado positivo de la "probabilidad").
Desde $M_{i k}^m$ pone positivo de peso en el índice de $k=k^*$, tenemos $$r^N_i=\sum_k M^m_{i k}\ r^{N-m}_k < r^m_i \leq 1.$$

Es decir, cada fila suma de $M^N$ es estrictamente menor que uno. Ahora usted puede mostrar que $M^{jN}\to 0$ $j\to \infty$ y esto demuestra que $M^N$ (y, por tanto,$M$) no tienen ningún valor propio con el módulo 1.