7.10: Markov Caminatas Aleatorias Moduladas

Frecuentemente es útil generalizar caminatas aleatorias para permitir cierta dependencia entre las variables que se suman. La forma particular de dependencia aquí es la misma que los procesos de recompensa de Markov de la Sección 3.5. El tratamiento en la Sección 3.5 discutió solo las recompensas esperadas, mientras que el tratamiento aquí se enfoca en las propias variables aleatorias. Sea {\(Y_m; m ≥ 0\)} una secuencia de rv (posiblemente dependientes), y deje

\[ \{ S_n; n\geq 1\} \qquad \text{where } S_n=\sum^{n-1}_{m=0} Y_m \nonumber \]

ser el proceso de sumas sucesivas de estas variables aleatorias. Que {\(X_n; n ≥ 0\)} sea una cadena de Markov, y supongamos que cada uno\(Y_n\) puede depender de\(X_n\) y\(X_{n+1}\). Condicional\(X_n\) y\(X_{n+1}\), sin embargo,\(Y_n\) es independiente de\(Y_{n−1}, . . . , Y_1\), y de\(X_i\) para todos\(i \neq n, n−1\). Supongamos que\(Y_n\), condicional\(X_n\) y\(X_{n+1}\) tiene una función de distribución\(F_{ij} \ref{y} = \text{Pr}\{Y_n ≤ y | X_n = i, X_{n+1} = j\}\). Así, cada rv\(Y_n\) depende únicamente de la transición asociada en la cadena de Markov, y esta dependencia es la misma para todos\(n\).

El proceso {\(S_n; n ≥ 1\)} se llama una caminata aleatoria modulada de Markov. Si cada uno\(Y_m\) es positivo, también es la secuencia de épocas en un proceso semi-Markov. Para cada uno\(m\),\(Y_m\) se asocia con la transición en la cadena de Markov de vez\(m\) en cuando\(m + 1\), y\( S_n\) es la recompensa agregada hasta pero sin incluir el tiempo\(n\). Dejar\(\overline{Y}_{ij}\) denotar\(\mathsf{E} [Y_n | X_n = i, X_{n+1} = j]\) y\(\overline{Y}_i\) denotar\(\mathsf{E} [Y_n | X_n = i]\). Sea {\(P_{ij} \)} el conjunto de probabilidades de transición para la cadena de Markov, así\(\overline{Y}_i = \sum_j P_{ij} \overline{Y}_{ ij} \). Podemos pensar que el proceso {\(Y_n; n ≥ 0\)} evoluciona junto con la cadena Markov. Las distribuciones de las variables\(Y_n\) están asociadas con las transiciones de\(X_n\) a\(X_{n+1}\), pero por lo demás\(Y_n\) son variables aleatorias independientes.

Para definir una martingala relacionada con el proceso {\(S_n; n ≥ 1\)}, debemos restar la recompensa media de {\(S_n\)} y también hay que compensar el efecto del estado de la cadena Markov. El factor de compensación apropiado resulta ser el vector de ganancia relativa definido en la Sección 3.5.

Por simplicidad, considere solo cadenas de Markov irreducibles de estado finito con\(\mathsf{M}\) estados. Dejar\(π = (π_1, . . . , π_{\mathsf{M}})\) ser el vector de probabilidad de estado estacionario para la cadena, dejar\(\overline{\boldsymbol{Y}} = (\overline{Y}_1, . . . , \overline{Y}_{\mathsf{M}} )^{\mathsf{T}}\) ser el vector de recompensas esperadas, dejar\(g = π\overline{Y}\) ser la ganancia en estado estacionario por unidad de tiempo, y dejar\(\boldsymbol{w} = (w_1, . . . , w_{\mathsf{M}})^{\mathsf{T}}\) ser el vector de ganancia relativa. Del Teorema 3.5.1,\(\boldsymbol{w}\) es la solución única para

\[ \boldsymbol{w} +ge = \overline{\boldsymbol{Y}} + [P]\boldsymbol{w} \quad ; \quad w_1 =0 \nonumber \]

Asumimos un estado de inicio fijo\(X_0 = k\). Como ahora mostramos, el proceso\(Z_n; n ≥ 1\) dado por

\[Z_n = S_n -ng +w_{X_n}-w_k \quad ; \quad n\geq 1 \nonumber \]

es una martingala. Primera condición en un estado dado,\(X_{n−1} = i\).

\[ \mathsf{E} [Z_n| Z_{n-1},Z_{n-2},...,Z_1, X_{n-1} =i ] \nonumber \]

Ya que\(S_n = S_{n−1} + Y_{n−1}\), podemos expresarnos\(Z_n\) como

\[ Z_n = Z_{n-1} + Y_{n-1}-g+w_{X_n}-w_{X_{n-1}} \nonumber \]

Desde\(\mathsf{E} [Y_{n−1} | X_{n−1} = i] = \overline{Y}_i\) y\(\mathsf{E} [w_{X_n} | X_{n−1} = i] = \sum_j P_{ij} w_j \), tenemos

\[ \mathsf{E} [Z_n|Z_{n-1},Z_{n-2},...,Z_1,X_{n-1} =i] = Z_{n-1}+\overline{Y}_i -g+\sum_j P_{ij}w_j-w_i \nonumber \]

De (7.10.2) los últimos cuatro términos en (7.10.6) suma a 0, así

\[ \mathsf{E} [Z_n|Z_{n-1},...,Z_1,X_{n-1} =i]=Z_{n-1} \nonumber \]

Dado que esto es válido para todas las opciones de\( X_{n−1}\), tenemos\(\mathsf{E} [Z_n | Z_{n−1}, . . . , Z_1] = Z_{n−1}\). Dado que\(\overline{Y}_i\) existen los valores esperados de todas las variables de recompensa, vemos eso\(\mathsf{E} [|Y_n|] <\infty\), así\(\mathsf{E} [|Z_n|] < \infty\) también. Esto verifica que {\(Z_n; n ≥ 1\)} es una martingala. Se puede verificar de manera similar que\(\mathsf{E} [Z_1] = 0\), así\(\mathsf{E} [Z_n] = 0\) para todos\(n ≥ 1\).

Al mostrar que {\(Z_n; n ≥ 1\)} es una martingala, en realidad mostramos algo un poco más fuerte. Es decir, (7.10.7) está condicionado así\(X_{n−1}\) como\(Z_{n−1}, . . . , Z_1\). De la misma manera, se deduce que para todos\(n > 1\),

\[\mathsf{E}[Z_n|Z_{n-1},X_{n-1},Z_{n-2},X_{n-2},...,Z_1,X_1 ] = Z_{n-1} \nonumber \]

En términos de la analogía del juego, esto dice que {\(Z_n; n ≥ 1\)} es justo para cada posible secuencia pasada de estados. Se dice que una martingala {\(Z_n; n ≥ 1\)} con esta propiedad (\(i.e.\), satisfactoria (7.10.8)) es una martingala relativa al proceso conjunto {\(Z_n, X_n; n ≥ 1\)}. Utilizaremos esta martingala más adelante para discutir los problemas de cruce de umbrales para las caminatas aleatorias moduladas por Markov. Veremos que la propiedad añadida de ser una martingala relativa a {\(Z_n, X_n\)} nos da mayor flexibilidad en la definición de los tiempos de parada.

Como bono agregado a este ejemplo, tenga en cuenta que si {\(X_n; n ≥ 0\)} se toma como la cadena incrustada de un proceso de Markov (o proceso semi-Markov), y si\(Y_n\) se toma como el intervalo de tiempo desde la transición\(n\) a\(n + 1\), entonces\(S_n\) se convierte en la época de la transición\(n\) th en el proceso.

Generando funciones para caminatas aleatorias de Markov

Consideremos las mismas variables de cadena y recompensa de Markov que en el ejemplo anterior, y supongamos que para cada par de estados,\(i, \, j\), la función generadora de momento

\[ \mathsf{g}_{ij}(r) = \mathsf{E}[\exp(rY_n)|X_n=i,X_{n+1} =j ] \nonumber \]

existe a lo largo de algún intervalo abierto (\(r_−, r_+\)) que contiene 0. \([Γ(r)]\)Déjese ser la matriz con términos\(P_{ij} \mathsf{g}_{ij} (r)\). Dado que\([Γ(r)]\) es una matriz no negativa irreducible, el Teorema 3.4.1 muestra que\([Γ(r)]\) tiene un valor propio real más grande\(ρ(r) > 0\),, y un vector propio derecho positivo asociado,\(\nu \ref{r} = (\nu_1(r), . . . , \nu_{\mathsf{M}}(r))^{\mathsf{T}}\) que es único dentro de un factor de escala. Ahora demostramos que el proceso {\(M_n(r); n ≥ 1\)} definido por

\[ M_n(r) = \dfrac{\exp (rS_n)\nu_{X_n}(r) }{\rho (r)^n\nu_k(r)} \nonumber \]

es un tipo de producto Martingala para cada uno\(r ∈ (r_−, r_+)\). Ya que\(S_n = S_{n−1} + Y_{n−1}\), podemos expresarnos\(M_n(r)\) como

\[ M_n(r)=M_{n-1}(r) \dfrac{\exp (rY_{n-1}) \nu_{X_n} (r)}{\rho \ref{r} \nu_{X_{n-1}} (r)} \nonumber \]

El valor esperado de la relación en (7.10.11), condicional\(X_{n−1} = i\), es

\[ E \left[ \dfrac{\exp (rY_{n-1})\nu_{X_n} (r)}{\rho (r)\nu_i (r)} | X_{n-1}=i \right] \quad = \quad \dfrac{\sum_{j} P_{ij} \mathsf{g}_{ij} \ref{r} \nu_j (r)}{\rho \ref{r} \nu_i (r)} =1 \nonumber \]

donde, en el último paso, hemos utilizado el hecho de que\(\nu (r)\) es un vector propio de\([Γ(r)]\). Por lo tanto,\(\mathsf{E} [M_n(r) | M_{n-1}(r), . . . , M_1(r), X_{n-1} = i] = M_{n−1}(r)\). Dado que esto es cierto para todas las opciones de\(i\), la condición en se\(X_{n−1} = i\) puede quitar y {\(M_n(r); n ≥ 1\)} es una martingala. También, para\(n > 1\),

\[ \mathsf{E} [M_n \ref{r} | M_{n-1} \ref{r} , X_{n-1}, ..., M_1(r), X_1] = M_{n-1} \ref{r} \nonumber \]

de manera que {\(M_n(r); n ≥ 1\)} es también una martingala relativa al proceso conjunto {\(M_n(r), X_n; n ≥ 1\)}.

Se puede verificar por el mismo argumento que en (7.10.12) que\(\mathsf{E} [M_1(r)] = 1\). Entonces se deduce eso\(\mathsf{E} [M_n(r)] = 1\) para todos\(n ≥ 1\).

Uno de los usos de esta martingala es proporcionar límites superiores exponenciales, similares a (7.18), a las probabilidades de cruces de umbral para las caminatas aleatorias moduladas de Markov. Definir

\[ \widetilde{M}_n(r) = \dfrac{\exp (rS_n)\min_j (\nu_j (r))}{\rho(r)^n\nu_k(r) } \nonumber \]

Entonces\(\widetilde{M}_n(r) ≤ M_n(r)\), entonces\(\mathsf{E}\left[ \widetilde{M}_n(r) \right] ≤ 1\). Para cualquiera\(μ > 0\), se puede aplicar la desigualdad de Markov\(\widetilde{M}_n (r)\) para obtener

\[ \text{Pr}\left\{ \widetilde{M}_n(r) \geq \mu \right\} \leq \dfrac{1}{\mu} \mathsf{E} \left[ \widetilde{M}_n \ref{r} \right] \leq \dfrac{1}{\mu} \nonumber \]

Para cualquier dado\(α\), y cualquier dado\(r\)\(0 ≤ r < r_+\),, podemos elegir\(μ = \exp(rα)ρ(r)^{−n} \min_j (\nu_j (r))/\nu_k(r)\), y para\(r > 0\). Combinando (7.10.14) y (7.10.15),

\[ \text{Pr} \{ S_n \geq \alpha \} \leq \rho (r)^n\exp(-r\alpha )\nu_k(r)/\min_j(\nu_j (r)) \nonumber \]

Esto se puede optimizar\(r\) para obtener el límite más ajustado de la misma manera que (7.18).

detener los ensayos para martingales en relación con un proceso

Una martingala {\(Z_n; n ≥ 1\)} relativa a un proceso conjunto {\(Z_n, X_n; n ≥ 1\)} se definió como una martingala para la cual (7.10.8) se satisface,\(i.e.\),\(\mathsf{E} [Z_n | Z_{n−1}, X_{n−1}, . . . , Z_1, X_1] = Z_{n−1}\). De la misma manera, podemos definir una submartingala o supermartingala {\(Z_n; n ≥ 1\)} relativa a un proceso conjunto {\(Z_n, X_n; n ≥ 1\)} como una submartingala o supermartingala satisfactoria (7.10.8) con el\(=\) signo reemplazado por\(≥\) o\(≤\) respectivamente. El propósito de esta complicación añadida es facilitar la definición de reglas de parada útiles.

Como se generaliza en la Definición 4.5.2, un ensayo de detención generalizada\(\mathbb{I}_{J≥n}\) para una secuencia de pares de rv\((Z_1, X_1), (Z_2, X_2) . . . ,\) es un rv de valor entero positivo tal que, para cada uno\(n ≥ 1, \mathbb{I}_{\{J=n\}}\) es una función de\(Z_1, X_1, Z_2, X_2, . . . , Z_n, X_n\).

Los teoremas 7.8.1, 7.8.2 y Lema 7.8.1 se trasladan todos a martingales (submartingales o supermartingales) en relación con un proceso conjunto. Estos teoremas se enuncian con mayor precisión en los Ejercicios 7.23 a 7.26. Para resumirlos aquí, supongamos que {\(Z_n; n ≥ 1\)} es una martingala (submartingala o supermartingala) relativa a un proceso conjunto {\(Z_n, X_n; n ≥ 1\)} y asumir que\(J\) es un juicio de detención para {\(Z_n; n ≥ 1\)} relativo a {\(Z_n, X_n; n ≤ 1\)}. Entonces el proceso detenido es una martingala (submartingala o supermartingala) respectivamente, (7.8.3 — 7.8.5) se satisfacen, y, para una martingala,\(\mathsf{E}[Z_J ] = \mathsf{E} [Z_1]\) se satisface iff (7.8.9) se satisface.

Markov moduló caminatas aleatorias con umbrales

Ahora hemos desarrollado dos martingales para las caminatas aleatorias moduladas de Markov, ambas condicionadas a un estado inicial fijo\(X_0 = k\). El primero, dado en (7.10.3), es {\(Z_n = S_n − ng + w_{X_n} − w_k; n ≥ 1\)}. Recordemos eso\(\mathsf{E} [Z_n] = 0\)\(n ≥ 1\) para todos por esta martingala. Dados dos umbrales,\(α> 0\) y\(β< 0\), definir\(J\) como el más pequeño\(n\) para el cual\(S_n ≥ α\) o\(S_n ≤ β\). La función indicadora\(\mathbb{I}_{J=n}\) de\(\{J = n\}\), es 1 iff\(β< S_i < α\) para\(1 ≤ i ≤ n − 1\) y cualquiera\(S_n ≥ α\) o\(S_n ≤ β\). Ya que\(S_i = Z_i + ig − w_{X_i} + w_k, \, S_i\) es una función de\( Z_i\) y\(X_i\), por lo que el juicio de detención es una función de ambos\(Z_i\) y\(X_i\) para\(1 ≤ i ≤ n\). De ello se deduce que\(J\) es un juicio de detención para {\(Z_n; n ≥ 1\)} relativo a {\(Z_n, X_n; n ≥ 1\)}. Desde Lemma 7.8.1, podemos afirmar que\(\mathsf{E} [Z_J ] = \mathsf{E} [Z_1] = 0\) si (7.8.9) está satisfecho,\(i.e.\), si\(\lim_{n→\infty} \mathsf{E} [Z_n | J > n] \text{Pr}\{J > n\} = 0\) está satisfecho. Usando el mismo argumento que en Lemma 7.5.1, podemos ver que\(\text{Pr}\{ J > n\}\) va a 0 al menos geométricamente en\(n\). Condicional a\(J > n\)\(β< S_n < α\),, así\(S_n\) se limita independiente de\(n\). También\(w_{X_n}\) está acotada, ya que la cadena es de estado finito, y\(ng\) es lineal en\(n\). Por lo tanto,\(\mathsf{E} [Z_n | J > n]\) varía a lo sumo linealmente con\(n\), por lo que (7.8.9) se satisface, y

\[ 0 = \mathsf{E}[Z_J]=\mathsf{E}[S_J]-\mathsf{E}[J]g+\mathsf{E}[w_{X_n}] -w_k \nonumber \]

Recordemos que la igualdad de Wald para las caminatas aleatorias es\(\mathsf{E} [S_J ] = \mathsf{E} [J] \overline{X}\). Para las caminatas aleatorias moduladas de Markov, ésta se modifica, como se muestra en (7.10.17), por los términos vectoriales de ganancia relativa.

Los mismos argumentos se pueden aplicar a la función generadora martingala de (7.10.10). Nuevamente, dejemos\( J\) ser los más pequeños\(n\) para los cuales\(S_n ≥ α\) o\(S_n ≤ β\). Como antes,\(S_i\) es una función de\(M_i(r)\) y\(X_i\), así\(\mathbb{I}_n\) es una función de\(M_i(r)\) y\(X_i\) para\(1 ≤ i ≤ n − 1\). De ello se deduce que\(J\) es un juicio de detención para {\(M_n(r); n ≥ 1\)\(M_n(r), X_n; n ≥ 1\)} relativo a {} A continuación necesitamos el siguiente lema:

Lema 7.10.1. Para la martingala {\(M_n(r); n ≥ 1\)} relativa a {\(M_n(r), X_n; n ≥ 1\)} definida en (7.10.10), donde {\(X_n; n ≥ 0\)} es una cadena de Markov de estado finito, y para el juicio de detención anterior\(J\),

\[ \lim_{n\rightarrow \infty} \mathsf{E}[M_n \ref{r} | J>n] \text{Pr}\{ J>n\} =0 \nonumber \]

Prueba: Del lema 4, ligeramente modificado para el caso aquí, hay\(δ> 0\) tal que para todos los estados\(i\),\(j\), y todos\(n > 1\) tales que\(\mathsf{Pr}\{J = n, X_{n−1} = i, X_n = j\} > 0\),

\[ \mathsf{E}[\exp(rS_n|J=n,X_{n-1}=i,X_n=j] \geq \delta \nonumber \]

Ya que el proceso detenido, {\(M^∗_n(r); n ≥ 1\)}, es una martingala, tenemos para cada uno\(m\),

\[ 1=\mathsf{E}[M_m^*(r)] \geq \sum^m_{n=1} \dfrac{\mathsf{E}[\exp (rS_n)\nu_{X_n}(r) | J=n]}{\rho(r)^n\nu_k(r)} \nonumber \]

De (7.10.19), vemos que hay algunos\(δ' > 0\) tales que

\[ \mathsf{E}[\exp(rS_n)\nu_{X_n}(r)]/\nu_k(r)|J=n] \geq \delta' \nonumber \]

para todos\( n\) tales que\(\text{Pr}\{J = n\} > 0\). Así (7.10.20) está delimitado por

\[ 1\geq \delta' \sum_{n\leq m}\rho(r)^n\text{Pr}\{J=n\} \nonumber \]

Dado que esto es válido para todos\(m\), se desprende por el argumento en la prueba del teorema 7.5.1 que\(\lim_{n→\infty} ρ(r)^n\text{Pr}\{J > n\} = 0\). Esto, junto con (7.10.19), establece (7.10.18), completando la prueba.

\(\square \)

Desde Lemma 7.8.1, tenemos el resultado deseado:

\[ \mathsf{E}[M_J(r)] =\mathsf{E} \left[ \dfrac{\exp (rS_J)\nu_{X_J} (r)}{[\rho(r)]^J\nu_j (r)} \right] =1 ; \qquad r_-<r<r_+ \nonumber \]

Esta es la extensión de la identidad de Wald a los paseos aleatorios modulados de Markov, y se utiliza de la misma manera que la identidad de Wald. Como se muestra en el Ejercicio 7.28, la derivada de (7.10.21), evaluada en\(r = 0\), es la misma que (7.10.17).