Saltar al contenido principal
LibreTexts Español

6.1: Introducción

  • Page ID
    86278
  • \( \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}}\)

    Recordemos que una cadena de Markov es un proceso de tiempo discreto {\(X_n; n \geq 0\)} para el cual el estado en cada momento\(n\geq 1\) es una variable aleatoria de valor entero (rv) que depende estadísticamente de\(X_0, . . . X_{n-1}\) solo a través\(X_{n-1}\). Un proceso 1 de Markov de estado contable (proceso de Markov para abreviar) es una generalización de una cadena de Markov en el sentido de que, junto con la cadena de Markov {\(X_n; n\geq 1\)}, hay un intervalo de retención que varía aleatoriamente en cada estado el cual se distribuye exponencialmente con un parámetro determinado por el estado actual.

    Para ser más específicos, vamos\(X_0=i\),,\(X_1=j\)\(X_2 = k\),..,., denotar una ruta muestral de la secuencia de estados en la cadena de Markov (en adelante llamada la cadena incrustada de Markov). Entonces el intervalo de retención\(U_n\) entre el momento en que\(X_{n-1} = \ell\) se ingresa ese estado y se ingresa\(X_n\) es un rv exponencial no negativo con parámetro\(\nu_{\ell}\),\(i.e.\), para todos\(u \geq 0\),

    \[ \text{Pr}\{ U_n\leq u | X_{n-1}=\ell \} = 1-\exp (-\nu_{\ell}u) \nonumber \]

    Además\(U_n\), condicionada\(X_{n-1}\), es solidariamente independiente de\(X_m\) para todos\(m \neq n- 1\) y de\(U_m\) para todos\(m \neq n\).

    Si visualizamos iniciar este proceso en el tiempo 0 en estado\(X_0 = i\), entonces la primera transición de la cadena incrustada de Markov entra en estado\(X_1 = j\) con la probabilidad\(P_{ij}\) de transición de la cadena incrustada. Esta transición se produce en el momento\(U_1\), donde\(U_1\) es independiente\(X_1\) y exponencial con la tasa\(\nu_i\). A continuación, condicional\(X_1 = j\), la siguiente transición entra en estado\(X_2 = k\) con la probabilidad de transición\(P_{jk}\). Esta transición se produce después de un intervalo\(U_2\)\(i.e.\),, en el tiempo\(U_1 + U_2\), donde\(U_2\) es independiente\(X_2\) y exponencial con la tasa\(\nu_j\). Las transiciones posteriores ocurren de manera similar, con el nuevo estado, digamos\(X_n = i\), determinado a partir del estado antiguo, digamos\(X_{n-1} = \ell\), vía\(P_{\ell i}\), y el nuevo intervalo de retención\(U_n\) determinado a través de la tasa exponencial\(\nu_{\ell}\). La Figura 6.1 ilustra las dependencias estadísticas entre las rv {\(X_n; n \geq 0\)} y {\(U_n; n\geq 1\)}.

    clipboard_e963b6e193ff10921a4f2b3df6ce10911.png

      Figura 6.1: Las dependencias estadísticas entre los rv de un proceso de Markov. Cada intervalo de retención\(U_i\), condicionado al estado actual\(X_{i-1}\), es independiente de todos los demás estados e intervalos de retención.  

    Las épocas en las que ocurren transiciones sucesivas se denotan\(S_1, S_2, . . . \), así tenemos\(S_1 = U_1\),\(S_2 = U_1 + U_2\), y en general\(S_n = \sum^n_{m=1} U_m\) para\(n\geq 1\) wug\(S_0 = 0\). El estado de un proceso de Markov en cualquier momento\(t > 0\) se denota por\(X(t)\) y viene dado por

    \[ X(t) =X_n \text{ for } S_n\leq t<S_{n+1} \quad \text{for each } n\geq 0 \nonumber \]

    Esto define un proceso estocástico {\(X(t); t \geq 0\)} en el sentido de que cada punto de muestra se\(\omega \in \Omega\) mapea a una secuencia de valores de muestra de {\(X_n; n\geq 0\)} y {\(S_n; n \geq 1\)}, y así en una función de muestra de {\(X(t); t\geq 0\)}. Este proceso estocástico es lo que generalmente se conoce como un proceso de Markov, pero a menudo es más sencillo de ver {\(X_n; n\geq 0\)}, {\(S_n; n\geq 1\)} como una caracterización del proceso. La Figura 6.2 ilustra la relación entre todas estas cantidades.

    clipboard_eeb51103e4f6a1df762b5339f6d24f9de.png

      Figura 6.2: La relación de los intervalos de retención {\(U_n; n\geq 1\)} y las épocas {\(S_n;n\geq 1\)} en las que ocurren los cambios de estado. También se ilustra el estado\(X(t)\) del proceso de Markov y el estado correspondiente de la cadena incrustada de Markov. Tenga en cuenta que si\(X_n=i\), entonces\(X(t)=i\) para\(S_n \leq t< S_{n+1}\)  

    Esto se puede resumir en la siguiente definición.

    Definición 6.1.1. Un proceso de Markov de estado contable {\(X(t); t \geq 0\)} es un proceso estocástico que mapea cada número real no negativo\(t\) al rv de valor entero no negativo de tal\(X(t)\) manera que para cada uno\(t\geq 0\),

    \[ X(t)=X_n \quad for \, S_n\leq t<S_{n+1} ; \quad S_0=0; \, \, S_n=\sum^n_{m=1} U_m \quad for \, \, n\geq 1 \nonumber \]

    donde {\(X_n; n\geq 0\)} es una cadena de Markov con un espacio de estado contablemente infinito o finito y cada uno\(U_n\), dado\(X_{n-1} = i\), es exponencial con tasa\(\nu_i > 0\) y es condicionalmente independiente de todos los demás\(U_m\) y \(X_m\).

    Los supuestos tácitos de que el espacio estatal es el conjunto de enteros no negativos y que el proceso comienza en\(t = 0\) se toman sólo por simplicidad notacional pero servirán aquí a nuestras necesidades.

    Asumimos a lo largo de este capítulo (salvo en algunos lugares donde se especifique lo contrario) que la cadena incrustada de Markov no tiene autotransiciones,\(i.e.\),\(P_{ii} = 0\) para todos los estados\(i\). Una razón de esto es que tales transiciones son invisibles en {\(X(t); t\geq 0\)}. Otra es que con esta suposición, las funciones de muestra de {\(X(t); t\geq 0\)} y las funciones de muestra conjunta de {\(X_n; n\geq 0\)} y {\(U_n; n\geq 1\)} se especifican de manera única entre sí.

    No nos interesa por el momento explorar la distribución de probabilidad de\(X(t)\) para valores dados de\(t\), pero una característica importante de esta distribución es que para cualquier momento\(t > \tau > 0\) y cualquier estado\(i, j\),

    \[\text{Pr}\{X(t)=j|X(\tau)=i,\, \{X(s)=x(s); s<\tau\}\} = \text{Pr}\{X(t-\tau)=j|X(0)=i\} \nonumber \]

    Esta propiedad surge por la propiedad sin memoria de la distribución exponencial. Es decir, si\(X(\tau ) = i\), no hace diferencia cuanto tiempo ha estado el proceso en estado\(i\) antes\(\tau\); el tiempo hasta la siguiente transición sigue siendo exponencial con tasa\(\nu_i\) y los estados subsiguientes y los intervalos de retención se determinan como si el proceso se inicia en estado\(i\) en el tiempo 0. Esto se verá más claramente en la siguiente exposición. Esta propiedad es la razón por la que estos procesos se llaman Markov, y a menudo se toma como la propiedad definitoria de los procesos de Markov.

    Ejemplo 6.1.1. La cola M/M/1: Una cola M/M/1 tiene llegadas de Poisson a una tasa denotada por\(\lambda\) y tiene un solo servidor con una distribución exponencial de la tasa de servicio\(µ >\lambda\) (ver Figura 6.3). Los sucesivos tiempos de servicio son independientes, tanto entre sí como de llegadas. El estado\(X(t)\) de la cola es el número total de clientes ya sea en la cola o en servicio. Cuando\(X(t) = 0\), el tiempo para la siguiente transición es el tiempo hasta la próxima llegada,\(i.e.\),\(\nu_0 = \lambda\). Cuando\(X(t) = i\),\(i\geq 1\), el servidor está ocupado y el tiempo para la siguiente transición es el tiempo hasta que se produzca una nueva llegada o se produzca una salida. Así\(\nu_i = \lambda+ µ\). Para la cadena incrustada de Markov,\(P_{01} = 1\) ya que solo las llegadas son posibles en el estado 0, y aumentan el estado a 1. En los otros estados,\(P_{i,i-1} = µ/(\lambda+µ)\) y\(P_{i,i+1} = \lambda/(\lambda+µ)\).

    clipboard_ef1bf7e6cd1474a100621c82baba15937.png

      Figura 6.3: La cadena integrada de Markov para una cola M/M/1. Cada nodo\(i\) se etiqueta con la tasa correspondiente\(\nu_i\) del intervalo de retención distribuido exponencialmente a la siguiente transición. Cada transición, digamos\(i\) a\(j\), está etiquetada con la probabilidad de transición correspondiente\(P_{ij}\) en la cadena incrustada de Markov.  

    La cadena incrustada de Markov es una cadena de nacimiento-muerte, y sus probabilidades de estado estacionario se pueden calcular fácilmente usando (5.25). El resultado es

    \[ \begin{align} &\pi_0 \, = \, \dfrac{1-\rho}{2} \qquad \text{where } \rho=\dfrac{\lambda}{\mu}\nonumber \\ &\pi_n \, = \, \dfrac{1-\rho^2}{2}\rho^{n-1} \quad \text{for } n\geq 1\end{align} \nonumber \]

    Tenga en cuenta que si\(\lambda << µ\), entonces\(\pi_0\) y cada uno\(\pi_1\) está cerca de 1/2 (\(i.e.\), la cadena incrustada alterna principalmente entre los estados 0 y 1, y rara vez se ingresan estados ordenados más altos), mientras que debido al gran intervalo de retención en el estado 0, el proceso pasa la mayor parte de su tiempo en el estado 0 esperando llegadas. La probabilidad\(\pi_i\) de estado estacionario\(i\) en la cadena incrustada es la fracción a largo plazo de las transiciones totales que van al estado\(i\). En breve aprenderemos a encontrar la fracción a largo plazo del tiempo que se pasa en estado\(i\) frente a esta fracción de transiciones, pero por ahora volvemos al estudio general de los procesos de Markov.

    La evolución de un proceso de Markov se puede visualizar de varias maneras. Ya hemos mirado el primero, en el que para cada estado\(X_{n-1} = i\) de la cadena incrustada, el siguiente estado\(X_n\) está determinado por las probabilidades {\(P_{ij} ; j\geq 0\)} de la cadena incrustada de Markov, y el intervalo de retención\(U_n\) está determinado independientemente por la distribución exponencial con tasa \(\nu_i\).

    Para un segundo punto de vista, supongamos que un proceso independiente de Poisson de tasa\(\nu_i > 0\) está asociado a cada estado\(i\). Cuando el proceso de Markov entra en un estado dado\(i\), la siguiente transición ocurre en la siguiente época de llegada en el proceso de Poisson para estado\(i\). En esa época, se elige un nuevo estado de acuerdo a las probabilidades de transición\(P_{ij}\). Dado que la elección del siguiente estado, estado dado\(i\), es independiente del intervalo en estado\(i\), esta vista describe el mismo proceso que la primera vista.

    Para una tercera visualización, supongamos, para cada par de estados\(i\) y\(j\), que un proceso independiente de Poisson de tasa\(\nu_i P_{ij}\) se asocia con una posible transición a\(j\) condicional a estar en\(i\). Cuando el proceso de Markov entra en un estado dado\(i\), tanto el tiempo de la siguiente transición como la elección del siguiente estado están determinados por el conjunto de procesos\(i\) a\(j\) Poisson sobre todos los siguientes estados posibles\(j\). La transición ocurre en la época de la primera llegada, para lo dado\(i\), a cualquiera de los\(j\) procesos\(i\) a, y el siguiente estado es el\(j\) para el que ocurrió esa primera llegada. Dado que tal colección de procesos independientes de Poisson equivale a un proceso único de tasa\(\nu_i\) seguido de una selección independiente de acuerdo con las probabilidades de transición\(P_{ij}\), esta visión describe nuevamente el mismo proceso que las otras vistas.

    Es conveniente en esta tercera visualización definir la tasa de cualquier estado\(i\) a cualquier otro estado\(j\) como

    \[q_{ij} = \nu_i P_{ij} \nonumber \]

    Si sumamos más\(j\), lo vemos\(\nu_i\) y también\(P_{ij}\) estamos determinados de manera única por {\(q_{ij} ; i, j\geq 0\)} como

    \[ \nu_i = \sum_j q_{ij}; \qquad P_{ij}=q_{ij}/\nu_i \nonumber \]

    Esto significa que la caracterización fundamental del proceso de Markov en términos de la\(P_{ij}\) y la\(\nu_i\) puede ser reemplazada por una caracterización en términos del conjunto de tasas de transición\(q_{ij}\). En muchos casos, este es un enfoque más natural. Para la cola M/M/1, por ejemplo,\(q_{i,i+1}\) es simplemente la tasa de llegada\(\lambda\). De igual manera,\(q_{i,i-1}\) es la tarifa de salida\(µ\) cuando hay clientes a ser atendidos,\(i.e.\), cuándo\(i > 0\). La Figura 6.4 muestra la Figura 6.3 incorporando esta simplificación notacional.

    Obsérvese que la densidad entre llegadas para el proceso de Poisson, de cualquier estado dado\(i\) a otro estado\(j\), viene dada por\(q_{ij} \exp (-q_{ij}x)\). Por otra parte, dado que el proceso está en estado\(i\), la densidad de probabilidad para el intervalo hasta la siguiente transición, ya sea condicionada al siguiente estado o no, es\(\nu_i \exp(-\nu_ix)\) donde\(\nu_i = \sum_j q_{ij}\). Se podría argumentar, incorrectamente, que, condicionado a que la siguiente transición sea a estado\(j\), el tiempo hasta esa transición tiene densidad\(q_{ij} \exp (-q_{ij}x)\). El ejercicio 6.1 utiliza una cola M/M/1 para proporcionar una explicación guiada de por qué este argumento es incorrecto.

    clipboard_e279c3b67133f481f81288d15d8b8bda7.png

      Figura 6.4: El proceso de Markov para una cola M/M/1. Cada transición (\(i, j\)) se etiqueta con la tasa de transición correspondiente\(q_{ij}\).  

    Aproximación de tiempo muestreado a un proceso de Markov

    Como otra forma más de visualizar un proceso de Markov, considere aproximar el proceso viéndolo solo en momentos separados por un tamaño de incremento dado\(\delta\). Los procesos de Poisson anteriores son entonces aproximados por procesos de Bernoulli donde la probabilidad de transición de\(i\) a\(j\) en la cadena de tiempo muestreada se define como\(q_{ij}\delta\) para todos\(j \neq i\).

    El proceso de Markov es entonces aproximado por una cadena de Markov. Dado que cada uno\(\delta q_{ij}\) disminuye con la disminución\(\delta\), hay una probabilidad creciente de que no haya transición fuera de un estado dado en el incremento de tiempo\(\delta\). Estos deben modelarse con probabilidades de autotransición, digamos\(P_{ii}(\delta)\) que deben satisfacer

    \[ P_{ii}(\delta) =1-\sum_jq_{ij}\delta =1-\nu_i\delta \qquad \text{for each } i\geq 0 \nonumber \]

    Esto se ilustra en la Figura 6.5 para la cola M/M/1. Recordemos que esta cadena de Markov M/M/1 de tiempo muestreado se analizó en la Sección 5.4 y se demostró que las probabilidades de estado estacionario eran

    \[ p_i(\delta) = (1-\rho)\rho^i \qquad \text{for all } i\geq 0 \quad \text{where } \rho = \lambda/\mu \nonumber \]

    Hemos denotado aquí las probabilidades de estado estacionario\(p_i(\delta)\) para evitar confusiones con las probabilidades de estado estacionario para la cadena incrustada. Como se discutió más adelante, las probabilidades de estado estacionario en\ ref {6.6} no dependen de\(\delta\), siempre y cuando\(\delta \) sea lo suficientemente pequeña como para que las probabilidades de autotransición no sean negativas

    clipboard_e96db1096d6a4cbaa3bd933ce572f2a3f.png

      Figura 6.5: Aproximación de una cola M/M/1 por una cadena de Markov de tiempo muestreado.  

    Esta aproximación de tiempo muestreado es una aproximación de dos maneras. Primero, las transiciones ocurren solo en múltiplos enteros del incremento\(\delta\), y segundo,\(q_{ij}\delta\) es una aproximación a\(\text{Pr}\{X(\delta)=j | X(0)=i\}\). Desde (6.3),\(\text{Pr}\{ X(\delta)=j | X(0) = i\} = q_{ij}\delta + o(\delta)\), por lo que esta segunda aproximación es cada vez más buena como\(\delta \rightarrow 0\).

    Como se observó anteriormente, las probabilidades de estado estacionario para la aproximación de tiempo muestreado a una cola M/M/1 no dependen de ellas\(\delta\). Como se ve más adelante, siempre que la cadena incrustada es recurrente positiva y existe una aproximación de tiempo muestreado para un proceso de Markov, entonces la probabilidad de estado estacionario de cada estado\(i\) es independiente\(\delta\) y representa la fracción limitante del tiempo pasado en estado\(i\) con probabilidad 1.

    La Figura 6.6 ilustra la aproximación de tiempo muestreado de un proceso genérico de Markov. Tenga en cuenta que\(P_{ii}(\delta )\) es igual a\(1 -\delta \nu_i\) para cada uno\(i\) en cualquier aproximación de este tipo, y por lo tanto es necesario\(\delta\) que sea lo suficientemente pequeño como para satisfacer\(\nu_i\delta\leq 1\) para todos\(i\). Para un espacio de estado finito, esto se satisface para cualquiera\(\delta\leq [\max_i \nu_i]^{-1}\). Para un espacio de estado contablemente infinito, sin embargo, la aproximación de tiempo muestreado requiere la existencia de algunos finitos\(B\) tales que\(\nu_i\leq B\) para todos\(i\). En la siguiente sección se exploran las consecuencias de no tener tal vinculación.

    clipboard_ee842b014f96cd3bedc345c79f2f19317.png

      Figura 6.6: Aproximación a un proceso genérico de Markov por su cadena de Markov muestreada en el tiempo.  

    _______________________________________________

    1. A estos procesos se les suele llamar cadenas de Markov de tiempo continuo.

    This page titled 6.1: Introducción is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Robert Gallager (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.