Ergodic componentes de la cadena de Markov por la matriz de transición

Question

Me gustaría encontrar un algoritmo para la obtención de todos los ergodic componentes de una finito de la cadena de Markov con tiempo discreto definido por su matriz de transición (es decir, ergodic subchains en el que la cadena se está descompuesto).

Sin duda, la tarea puede ser fácilmente resuelto por el cálculo de la matriz de adyacencia de la dígrafo correspondiente a la cadena y el consiguiente cálculo de la accesibilidad de la matriz de este dígrafo. Pero de esta manera es computacionalmente muy rentable. Tal vez, ¿existe algoritmo más eficiente?

Answer 1

Permítanme darles una respuesta en una dirección diferente: Su problema es encontrar el terminal fuertemente de los componentes conectados. La complejidad de este problema no es malo para cualquier sentido de mal utilizado en la informática, pero yo entiendo que quiere la mayoría de algoritmo eficiente. Trate de buscar en ciencias de la computación de la literatura, en particular de búsqueda en grafos.

Yo no soy un experto en este tipo de teoría de la complejidad, y las diferencias pueden ser sutiles, pero creo que tendrás que vivir con algo parecido a lineal en el tamaño del espacio de estado.

Answer 2

Esta es una explicación de Thomas comentario, pero demasiado largo para un comentario:

Cada fuertemente conectado componente de la transición gráfico que no tiene salida bordes admite una única distribución estacionaria que es ergodic. Por otro lado, cada distribución estacionaria es admitida en la unión de estos componentes fuertemente conectados (transitoria de los componentes no estacionarios de peso), y el acondicionamiento de una distribución estacionaria en estar en un solo componente, de nuevo da una distribución estacionaria. Por lo tanto, cada distribución estacionaria puede ser escrito como una combinación convexa de la ergodic distribuciones apoyado fuertemente en los componentes conectados sin salir de los bordes.

Por lo tanto, usted solo necesita encontrar la fuerza de los componentes conectados, y para cada componente de la única distribución estacionaria soportados en ese componente.