Saltar al contenido principal
LibreTexts Español

6.8: Procesos Semi-Markov

  • Page ID
    86283
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Los procesos Semi-Markov son generalizaciones de procesos de Markov en los que los intervalos de tiempo entre transiciones tienen una distribución arbitraria más que una distribución exponencial. Para ser específicos, hay una cadena de Markov incrustada,\(\{X_n; n \geq 0\}\) con un espacio de estado finito o contablemente infinito, y una secuencia\(\{U_n; n \geq 1 \}\) de intervalos de retención entre transiciones de estado. Las épocas en las que ocurren las transiciones de estado se dan entonces, para\(n \geq 1\), como\(S_n = \sum_{m=1}^n U_n\). El proceso inicia en el tiempo 0 con\(S_0\) definido como 0. El proceso Semi-Markov es entonces el proceso de tiempo continuo\(\{X(t); t \geq 0\}\) donde, para cada uno\(n \geq 0\),\(X(t) = X_n\) para\(t\) en el intervalo\(S_n \leq X_n < S_{n+1}\). Inicialmente,\(X_0 = i\) donde\(i\) está algún elemento dado del espacio estatal.

    \(\{U_n; n \geq 1\}\)Los intervalos de retención son rv no negativos que dependen únicamente del estado actual\(X_{n-1}\) y del siguiente estado\(X_n\). Más precisamente, dado\(X_{n-1} = j\) y\(X_n = k\), digamos, el intervalo\(U_n\) es independiente\(\{U_m; m < n\}\) e independiente de\(\{X_m; m < n - 1\}\) La función de distribución condicional para tal intervalo\(U_n\) se denota por\(G_{ij} (u)\),\(i.e.\),

    \[ \text{Pr} \{ U_n\leq u | X_{n-1} = j,X_n = k \} = G_{jk} \ref{u} \nonumber \]

    Las dependencias entre los rv\(\{X_n; n \geq 0\}\) y\(\{U_n; n \geq 1\}\) se ilustran en la Figura 6.17.

    Se denota la\(U_n\) media condicional de\(X_{n-1} = j,\, X_n = k\), condicional\(\overline{U} (j, k)\)\(i.e.\),

    \[ \overline{U}(i,j) = \mathsf{E} [U_n | X_{n-1} =i ,X_n=j] = \int_{u\geq 0} [1-G_{ij}(u)] du \nonumber \]

    Un proceso semi-Markov evoluciona esencialmente de la misma manera que un proceso de Markov. Dado un estado inicial,\(X_0 = i\) en el tiempo 0,\(X_1 = j\) se selecciona un nuevo estado de acuerdo con la cadena incrustada con probabilidad\(P_{ij}\). Después\(U_1 = S_1\) se selecciona usando la distribución\(G_{ij} (u)\). A continuación\(X_2 = k\) se elige un nuevo estado de acuerdo a la probabilidad\(P_{jk}\); luego, dado\(X_1 = j\) y\(X_2 = k\),\(U_2\) se selecciona el intervalo con función de distribución\(G_{jk}(u)\). Las transiciones de estado sucesivas y los tiempos de transición se eligen de la misma manera.

    clipboard_e19f5b0a9933435f5b20ed6d2b31c7210.png

      Figura 6.17: Las dependencias estadísticas entre los rv de un proceso semi-Markov. Cada intervalo de retención\(U_n\), condicionado al estado actual\(X_{n-1}\) y al siguiente estado\(X_n\), es independiente de todos los demás estados e intervalos de retención. Tenga en cuenta que, condicional\(X_n\), los intervalos de retención\(U_n, U_{n-1} , . . . ,\) son estadísticamente independientes de\(U_{n+1}, X_{n+2}, . . .\).  

    El comportamiento en estado estacionario de los procesos semi-Markov se puede analizar prácticamente de la misma manera que los procesos de Markov. Esto lo esbozamos en lo que sigue, y a menudo omitimos pruebas donde son las mismas que la prueba correspondiente para los procesos de Markov. Primero, ya que los intervalos de retención\(U_n\),, son rv, las épocas de transición\(S_n = \sum^n_{m=1} U_n\),, también son rv. El siguiente lema sigue entonces de la misma manera que Lemma 6.2.1 para los procesos de Markov .

    Lema 6.8.1. \(M_i(t)\)Sea el número de transiciones en un proceso Semi-Markov en el intervalo\((0, t]\) para algún estado inicial dado\(X_0 = i\). Después\(\lim_{t\rightarrow\infty} M_i(t) = \infty\) WP1.

    En lo que sigue, asumimos que la cadena incrustada de Markov es irreducible y positivo-recurrente. Queremos encontrar la fracción limitante de tiempo que el proceso pasa en cualquier estado dado, digamos\(j\). Encontraremos que este límite existe WP1, y encontraremos que depende únicamente de las probabilidades de estado estacionario de la cadena incrustada de Markov y del intervalo de retención esperado en cada estado. Esto viene dado por

    \[ \overline{U}(j) = \mathsf{E}[U_n | X_{n-1} =j] = \sum_k P_{jk}\mathsf{E}[U_n|X_{n-1}=j,X_n=k] = \sum_k P_{jk}\overline{U} (j,k) \nonumber \]

    donde\(\overline{U} (j, k)\) se da en 6.87. Las probabilidades de estado estacionario\(\{\pi_i; i \geq 0\}\) para la cadena incrustada nos indican la fracción de transiciones que entran en cualquier estado dado\(i\). Dado que\(\overline{U} (i)\) es el intervalo de retención esperado en\(i\) por transición hacia\(i\), supondríamos que la fracción de tiempo pasado en estado\(i\) debería ser proporcional a\(\pi_i\overline{U} (i)\). Normalizando, supondríamos que la probabilidad promedio de tiempo de estar en estado\(i\) debería ser

    \[ p_j = \dfrac{\pi_j \overline{U} (j)}{\sum_k \pi_k\overline{U} (k)} \nonumber \]

    Identificar el intervalo medio de retención,\(\overline{U}_j\) con\(1/\nu_j\), este es el mismo resultado que establecimos para el caso del proceso de Markov. Usando los mismos argumentos, encontramos que esto es válido para el caso Semi-Markov. Es válido tanto en el caso convencional donde cada uno\(p_j\) es positivo como\(\sum_j p_j = 1\), y también en el caso donde\(\sum_k \pi_k\overline{U} \ref{k} = \infty\), donde cada uno\(p_j = 0\). El análisis se basa en el hecho de que las sucesivas transiciones a algún estado dado, digamos\(j\), dado\(X_0 = i\), forman un proceso de renovación retrasada.

    Lema 6.8.2. Considera un proceso Semi-Markov con una cadena incrustada recurrente irreducible\(\{X_n; n \geq 0\}\). Dado\(X_0 = i\), deja\(\{M_{ij} (t); t \geq 0\}\) ser el número de transiciones a un estado dado\(j\) en el intervalo\((0, t]\). Entonces\(\{M_{ij} (t); t \geq 0\}\) es un proceso de renovación retrasada (o, si\(j = i\), es un proceso de renovación ordinario).

    Esto es lo mismo que Lemma 6.2.2, pero no es tan obvio que los intervalos sucesivos entre visitas a estado\(j\) sean estadísticamente independientes. Esto se puede observar, sin embargo, de la Figura 6.17, que deja claro que, dados\(X_n = j\), los intervalos de retención futuros,\(U_n, U_{n+1}, . . . ,\) son independientes de los intervalos pasados\(U_{n-1}, U_{n-2},...\).

    A continuación, utilizando el mismo proceso de recompensa de renovación que en Lema 6.2.3, asignando recompensa 1 siempre que\(X(t) = j\), definimos\(W_n\) como el intervalo entre el\(n- 1\) st y el\(n\) th entrada al estado\(j\) y obtenemos el siguiente lema:

    Lema 6.8.3. Considere un proceso Semi-Markov con una cadena de Markov irreducible, recurrente e incrustada a partir de\(X_0 = i\). Entonces con probabilidad 1, el tiempo promedio limitante en estado\(j\) viene dado por\(p_j \ref{i} =\frac{\overline{U}_j}{\overline{W}(j)}\).

    Este lema ha omitido cualquier aseveración sobre la probabilidad limitante de conjunto de estado\(j\),\(i.e.\),\(\lim_{t\rightarrow \infty} \text{Pr}\{ X(t) = j\}\). Esto se desprende fácilmente del teorema de Blackwell, pero depende de si las entradas sucesivas a declarar\(j\),\(i.e.\)\(\{W_n; n \geq 1\}\), son aritméticas o no aritméticas. Esto se explora en el Ejercicio 6.33. El lema muestra (como se esperaba) que el promedio de tiempo limitante en cada estado es independiente del estado inicial, por lo que en adelante\(p_j (i)\) reemplazamos por\(p_j\).

    A continuación, deja\(M_i(t)\) ser el número total de transiciones en el proceso Semi-Markov hasta e incluyendo el tiempo\(n\), dado\(X_0 = i\). Este no es un proceso de conteo de renovación, sino que, como ocurre con los procesos de Markov, proporciona una manera de combinar los resultados promedio de tiempo para todos los estados\(j\). El siguiente teorema es el mismo que para los procesos de Markov, a excepción de la omisión de resultados promedio de conjunto.

    Teorema 6.8.1. Considere un proceso semi Markov con una cadena de Markov incrustada irreducible, positivo-recurrente. \(\{\pi_j ; j \geq 0\}\)Dejen ser las probabilidades de estado estacionario de la cadena incrustada y dejar\(X_0 = i\) ser el estado de partida. Luego, con probabilidad 1, la fracción limitante de tiempo promedio del tiempo pasado en cualquier estado arbitrario\(j\) viene dada por

    \[ p_j = \dfrac{\pi_j\overline{U}(j)}{\sum_k\pi_k \overline{U} (j)} \nonumber \]

    El tiempo esperado entre retornos al estado\(j\) es

    \[ \overline{W}(j) = \dfrac{\sum_k \pi_k \overline{U}(k)}{\pi_j} \nonumber \]

    y la velocidad a la que tienen lugar las transiciones es independiente\(X_0\) y dada por

    \[ \lim_{t\rightarrow \infty} \dfrac{M_i(t)}{t} = \dfrac{1}{\sum_k\pi_k \overline{U}(k)} \quad \text{WP1} \nonumber \]

    Para un proceso Semi-Markov, conocer la probabilidad de estado estacionario de\(X(t) = j\) para grandes\(t\) no especifica completamente el comportamiento en estado estacionario. Otra cuestión importante del estado estacionario es determinar la fracción de tiempo involucrada en\(i\) las\(j\) transiciones. Para precisar esta noción, defina\(Y (t)\) como el tiempo residual hasta la siguiente transición tras tiempo\(t\) (\(i e.\),\(t + Y (t)\) es la época de la siguiente transición tras tiempo\(t\)). Queremos determinar la fracción de tiempo\(t\) durante la cual\(X(t) = i\) y\(X(t + Y (t)) = j\). Equivalentemente, para un proceso no aritmético, queremos determinar\(\text{Pr}\{ X(t) = i,\, X(t + Y \ref{t} = j)\}\) en el límite como\(t \rightarrow \infty\). Llama a este límite\(Q(i, j)\).

    Considerar un proceso de renovación, comenzando en estado\(i\) y con renovaciones en transiciones a estado\(i\). Definir una recompensa\(R(t) = 1\) por\(X(t) = i\),\(X(t + Y (t)) = j\) y de\(R(t) = 0\) otra manera (ver Figura 6.18). Es decir, para cada\(n\) tal que\(X(S_n) = i\) y\(X(S_{n+1}) = j\),\(R(t) = 1\) para\(S_n \leq t < S_{n+1}\). La recompensa esperada en un intervalo entre renovaciones es entonces\(P_{ij} \overline{U} (i, j)\). De ello se deduce\(Q(i, j)\) que viene dada por

    \[Q(i,j) = \lim_{t\rightarrow \infty} \dfrac{\int^t_0 R(\tau) d\tau}{t} = \dfrac{P_{ij}\overline{U}(i,j)}{\overline{W}(i)} = \dfrac{p_iP_{ij}\overline{U}(i,j)}{\overline{U}(i) } \nonumber \]

    clipboard_ed142398859ded907833e844c9854403d.png

      Figura 6.18: El proceso de renovación-recompensa\(i\) para\(j\) las transiciones. El valor esperado de\(U_n\) si\(X_n = i\) y\(X_{n+1} = j\) es\(\overline{U} (i, j)\) y el intervalo esperado entre las entradas a\(i\) es\(\overline{W} (i)\).  

    Ejemplo: la cola M/G/1

    Como ejemplo de una cadena Semi-Markov, considere una cola M/G/1. Más que la interpretación habitual en la que el estado del sistema es el número de clientes en el sistema, vemos que el estado del sistema cambia solo en los horarios de salida; el nuevo estado a una hora de salida es el número de clientes que deja atrás la salida. Este estado entonces permanece fijo hasta la siguiente salida. Los nuevos clientes aún ingresan al sistema de acuerdo con el proceso de llegada de Poisson, pero estos nuevos clientes no son considerados como parte del estado hasta la siguiente hora de salida. El número de clientes en el sistema en épocas de llegada no constituye en general un “estado” para el sistema, ya que la antigüedad del servicio actual también es necesaria como parte de la caracterización estadística del proceso.

    Un propósito de este ejemplo es ilustrar que a menudo es más conveniente visualizar el intervalo de transición\(U_n = S_n - S_{n-1}\) como elegido primero y el nuevo estado\(X_n\) como elegido segundo en lugar de elegir el estado primero y el tiempo de transición segundo. Para la cola M/G/1, primero supongamos que el estado es algo\(i > 0\). En este caso, el servicio comienza en el siguiente cliente inmediatamente después de la salida del cliente anterior. Así,\(U_n\), condicional\(X_n = i\) para\(i > 0\), tiene la distribución del tiempo de servicio, digamos\(G(u)\). El intervalo medio hasta que ocurre una transición de estado es

    \[ \overline{U}(i) = \int^{\int}_0 [1-G(u)]du; \quad i>0 \nonumber \]

    Dado el intervalo\(u\) para una transición del estado\(i > 0\), el número de llegadas en ese periodo es una variable aleatoria de Poisson con media\(\lambda u\), donde\(\lambda\) está la tasa de llegada de Poisson. Dado que el siguiente estado\(j\) es el estado antiguo\(i\), más el número de recién llegados, menos la única salida,

    \[\text{Pr} \{ X_{n+1}=j|X_n =i,U_n=u\} = \dfrac{(\lambda u)^{j+i+1}\exp (-\lambda u)}{(j-i+1)!} \nonumber \]

    para\(j \geq i-1\). Para\(j < i -1\), la probabilidad anterior es 0. La probabilidad incondicional\(P_{ij}\) de una transición de\(i\) a se\(j\) puede encontrar multiplicando el lado derecho de\ ref {6.95} por la densidad\(g(u)\) de probabilidad del tiempo de servicio e integrando sobre\(u\).

    \[ P_{ij} = \int^{\infty}_0 \dfrac{G(u)(\lambda u)^{j-i+1}\exp (-\lambda u)}{(j-i+1)} du; \quad j \geq i-1, i>0 \nonumber \]

    Para el caso\(i = 0\), el servidor deberá esperar hasta la siguiente llegada antes de iniciar el servicio. Por lo tanto, el tiempo esperado desde entrar en el estado vacío hasta la finalización del servicio es

    \[ \overline{U} \ref{0} = (1/\lambda ) + \int^{\infty}_0 [1-G(u)]du \nonumber \]

    Podemos evaluar\(P_{0j}\) observando que la salida de esa primera llegada deja a\(j\) los clientes en este sistema si y solo si\(j\) los clientes llegan durante el tiempo de servicio de ese primer cliente;\(i.e.\), el nuevo estado no depende de cuánto tiempo espere el servidor para que un nuevo cliente servir, pero sólo en las llegadas mientras ese cliente está siendo atendido. Dejando\(g(u)\) ser la densidad del tiempo de servicio,

    \[ P_{0j} = \int^{\infty}_0 \dfrac{g(u)(\lambda u)^j \exp (-\lambda u)}{j!} du; \quad j\geq 0 \nonumber \]


    6.8: Procesos Semi-Markov is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.