2 votos

Convergencia en serie de potencia de la matriz de transición del paseo aleatorio

Me gustaría saber si

$$ \sum_{t=0}^\infty P^t = \left( I- P \right)^{-1} ~,$$

où $P = D^{-1}W ~ $ es una matriz de transición de paseo aleatorio.

$W$ es una matriz que describe los pesos en un gráfico y $D$ es la matriz de grados con $ d_{ii} = \sum_{j \sim i} w_{ij}$ . Si no me equivoco, para la convergencia de una serie de potencias como la anterior, todos los valores propios de $P$ debe ser menor que $1$ :

$$ | \lambda_i| \lt 1 $$

Sin embargo, también he leído en la literatura que el mayor valor propio de P es $1$ .

¿Puede alguien ayudarme a averiguar si la primera ecuación es cierta, y a demostrarlo? Si la información dada es demasiado general, supongamos que la gráfica está conectada.

Gracias.

3voto

wxs Puntos 1546

Me gustaría ofrecer una interpretación alternativa de por qué la serie de potencias anterior no converge, a través de su relación con la transitoriedad/recurrencia del paseo aleatorio. Después les daré algunas sugerencias de cómo se puede dar sentido a la ecuación.

Recordemos que la función de Green de un paseo aleatorio es la matriz $G(x,y)$ definido como el número esperado de visitas del paseo aleatorio $(X_t)_{t \geq 0}$ , hace a $y$ , comenzó a partir de $x$ . Esto se puede escribir como

\begin{align*} G(x,y) &= \mathbf E_x \left[ \sum_{t \geq 0} \mathbf 1\{X_t = y\} \right] \\ & = \sum_{t \geq 0}P_x[X_t = y], \end{align*} où $x,y$ son vértices, y $\mathbf P_x, \mathbf E_x$ denotan la ley y la expectativa del paseo aleatorio iniciado desde $x$ . La ecuación de Chapman-Kolmogorov garantiza que

\begin{align*} \mathbf P_x[X_t = y] = P^t_{x,y}. \end{align*}

Entonces se deduce que la función de Green viene dada por la serie de potencias del lado izquierdo de su ecuación

\begin{align} G(x,y) & = \sum_{t \geq 0} P^t_{x,y}. \end{align}

Ahora podemos proceder con algunas observaciones:

  • A priori no podemos decir si $G(x,y)$ es finito o no; sin embargo, suponiendo que lo sea, entonces por lo anterior $G(x,y) = (I - P_{x,y})^{-1}$ .

  • Si $G(x,y)$ es finito o no es exactamente la cuestión de la transitoriedad/recurrencia del paseo aleatorio. Un paseo es recurrente en $x$ si $G(x,x) = \infty$ . Se puede demostrar que para un grafo conectado finito sin estados absorbentes que $G(x,x) = \infty$ si $G(y,z) = \infty$ para todos los vértices $y,z$ .

  • Ahora podemos argumentar por qué $G(x,y) = \infty$ ; supongamos que no, entonces $G(x,z) < \infty$ para todos $z$ (como consecuencia de la observación anterior). En particular, esto implica $P^t_{x,z} \rightarrow 0$ , y así se fija $\epsilon < |G|^{-1}$ existe $T \geq 0$ tal que para todo z \begin{align*} P^t_{x,z} < \epsilon, \qquad t >T. \end{align*} Pero entonces \begin{align*} \sum_{z}P^t_{x,z} < \epsilon |G| < 1, \end{align*} lo que contradice que $\sum_{z}P^t_{x,z} = 1$ . Y así $G(x,y) = \infty$ .

Hay entonces dos maneras de dar sentido a la primera ecuación.

En primer lugar, podrías trabajar con un gráfico infinito: todavía tienes que averiguar si este gráfico es transitorio o no, esta pregunta no es tan fácil de responder en el entorno de los gráficos infinitos. También hay que entender la noción de matriz infinita, $P$ .

Como alternativa, se puede introducir una tasa de mortalidad $\kappa_i \geq 0$ en cada sitio, y redefinir la matriz de grados diagonal $D$ por $D_{i,i} = \kappa_i + \sum_{j}W_{i,j}$ . Mientras haya un sitio $i$ para lo cual $\kappa_i > 0$ la matriz $P = D^{-1}W$ es ahora subestocástica, y corresponde a un paseo que en cada paso puede morir (es decir, el proceso se detiene). Hasta el momento en que el proceso se detiene, la dinámica es exactamente la misma que la del proceso original sin muerte. Dado que el tiempo de vida de este proceso es casi seguramente finito, la función de Green $G(x,y) < \infty$ .

Una última observación es que esta construcción a través de la matanza es lo mismo que si se tiene un paseo aleatorio con un vértice absorbente (es decir, uno que nunca se abandona), y entonces se mira sólo la matriz de transición $P$ restringido a los estados no absorbentes.

2voto

user2566092 Puntos 19546

$1$ es un valor propio de multiplicidad $1$ de una matriz estocástica siempre que las aristas de su gráfico den un camino entre cada par de vértices $(v,w)$ y la suma de matrices no converge si $1$ es un valor propio. En realidad, la suma matricial no convergería para ninguna matriz estocástica. Se puede ver esto observando que toda potencia de una matriz estocástica es de nuevo una matriz estocástica, lo que significa que en alguna columna debe haber al menos un elemento que sea mayor o igual que $1/n$ si su matriz es $n \times n$ . Por lo tanto, la serie no converge de forma elemental.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X