¿Existe alguna forma de calcular analíticamente el tiempo de recurrencia de un proceso de Markov finito?

Question

Sea $X_t$ sea un proceso de Markov ergódico (homogéneo en el tiempo) (en tiempo discreto o continuo) en un espacio de estados finito $\{1,\dots,n\}$ . Sea $T(X_0)$ es el tiempo de parada dado por el mínimo de los tiempos tales que $X$ ha cubierto el espacio (es decir, para todos los $j$ con $1 \le j \le n$ existe algún $t_j \le T(X_0)$ s.t. $X_{t_j} = j$ ) y $X_{T(X_0)} = X_0$ . Claramente $T(X_0)$ domina el tiempo de cobertura de $X$ . Yo esperaría que estuviera dominado a su vez por la suma del tiempo de cobertura y el esperado tiempo de golpeo de $X_0$ partiendo de un estado elegido con respecto a la distribución invariante $p$ .

Definir el tiempo de recurrencia como $\sum_{X_0} p(X_0) \cdot \mathbb{E}_{X_0} T(X_0)$ donde de nuevo el primer término es la distribución invariante de $X$ .

Hace ya bastante tiempo (principios de la década de 2000) que no miro los tiempos de cobertura y golpeo, pero recuerdo que mientras que el matriz fundamental (en tiempo discreto) o el "matriz de desviación" (en tiempo continuo) dan mucha información sobre los tiempos de acierto, calcular el tiempo de cobertura es difícil. Conozco el Con destino a Matthews , pero no conozco una forma más sencilla de calcular el tiempo de cobertura que simulando la cadena. En particular, no conozco una aproximación analítica a esta cantidad.

Estoy en la misma situación con respecto al tiempo de recurrencia, y es esta cantidad la que me interesa mucho más que el tiempo de cobertura. propiamente dicho . Pero ambos me resultan de cierto interés/utilidad.

Así que mis preguntas son:

1. ¿Se ha tratado en algún sitio el tiempo de recurrencia (o una cantidad similar además del tiempo de cobertura o el tiempo de primer retorno)?
2. ¿Se conocen resultados analíticos sobre la computación o al menos (además de los Matthews tiempos de cobertura o de recurrencia? tiempos de recurrencia?

Answer 1

Esta es una respuesta a un comentario.

El cupón de coleccionista problema es elemental. No tengo una en particular académica de referencia en la mente, sino más bien la técnica de las pruebas. Hay un par de pruebas de la $n H_n$ tiempo de espera para recoger todos los cupones. Una posibilidad es que usted puede calcular el tiempo de espera para recoger el $k$th nuevo cupón, $n/(n-k+1)$. Que utiliza una gran cantidad de simetría no tiene para un general de proceso de Markov. Aquí, usted tiene probabilidades de transición y a veces en (ubicación actual, subconjunto visitado hasta ahora).

De forma análoga a lo que yo hice aquí, usted puede usar la inclusión-exclusión. El tiempo de espera para cubrir todo (con tiempo discreto) es la suma de la probabilidad de que no se han cubierto todo, por el tiempo $t-1$, que se puede expresar como

$$\sum_t \sum_{S\subset V} -1^{|S|+1}Prob(\{X_i\}_{i\lt t}\cap S = \emptyset) $$

donde $V$ = $\{1,...,n\}$. Usted puede cambiar el orden de la suma de obtener la $2^n$ analíticamente la solución de los problemas que trata de evitar subconjuntos particulares.

$$\sum_{S\subset V} -1^{|S|+1} A(S)$$

donde $A(S)$ = tiempo de espera antes de entrar por primera vez a $S$.

Lo mismo vale para los de tiempo continuo.

Answer 2

http://arxiv.org/abs/1004.4371 podría ser útil.

Una nota con respecto a tu comentario: "Claramente T(X0) domina la tapa tiempo de X. yo esperaría a ser dominada a su vez por la suma de la cubierta del tiempo y la espera de golpear tiempo de X0 a partir de un estado elegido w/r/t el invariante de la distribución de p".

Esto es falso (a menos que yo estoy malinterpretando). Si empiezas desde 0 en el discreta del intervalo de {0,1,..,n}, entonces después de cubrir tienes que volver a 0 de n, que toma más tiempo de regresar a 0 de manera uniforme un punto al azar.