Ecuaciones de Kolmogorov para Cadenas de Markov Continuas

Objetivos

• Demostrar las ecuaciones diferenciales de Kolmogorov

• Modelar las ecuaciones de “Backward” & “Forward” para una CMTC

• Modelar ejemplos de una CMTC

Preliminares

Recordemos que la probabilidad de que un proceso que se encuentra a tiempo \(s\) en el estado \(i \in S\), haga una transición al estado \(j\in S\) para \(i\neq j\) durante las siguientes \(t\) unidades de tiempo viene dada por:

\[ P_{ij}(t) = P\left(X(t+s)=j\left|\right.X(s)=i\right) \] Queremos saber cómo calcular dicha probabilidad para cualquier cadena de Markov a tiempo continuo. ¿Cómo lo hacemos?

Ejemplo: Proceso de Poisson con tasa \(\lambda\)

Sea \(\{N(t),t\geq 0\}\) un proceso de Poisson Homogéneo. Entonces, note que para \(i, j\geq 0\),

\[\begin{align*} P_{ij}(t) =& P\left(N(t+s)=j\left|\right.N(s)=i\right) \\ =& P\left(N(t+s) - N(s) = j-i\right) \\ =&\begin{cases} e^{-\lambda t\frac{(\lambda t)^{j-i}}{(j-i)!}} & \text{ si } j\geq i \\ 0 & \text{ si } j < i \end{cases} \end{align*}\]

¿Qué necesitamos para formular ecuaciones diferenciales para dichas probabilidades de transición en un contexto general de Cadenas de Markov contínuas?

Notación y tres resultados

Necesitamos algo de notación y un par de resultados a los que llamaremos lemas.

Para cada par de estados \(i\) y \(j\), sea

\[q_{ij}\equiv\upsilon_{i}P_{ij}\] recordando que \(\nu_{i}\) es la tasa a la que la cadena deja el estado \(i\) y \(P_{ij}\) es la probabilidad de que dicha transición ocurra al estado \(j\). De esta forma,\(q_{ij}\) es la tasa a la que la cadena estando en el estado \(i\) hace una transición al estado \(j\).

Tasas instantáneas de transición

A las \(q_{ij}\) se les llama tasas de transición instantáneas pues

\[\begin{align*} &\upsilon_{i}=\sum_{j}\upsilon_{i}P_{ij}=\sum_{j}q_{ij}\\ &P_{ij}=\frac{q_{ij}}{\upsilon_{i}}=\frac{q_{ij}}{\sum_{j}q_{ij}} \end{align*}\]

Nota. Especificar las tasas instantáneas de transición determina unívocamente los parámetros de la cadena de Markov continua.

Lema 1: Analogía Continua de las ecuaciones de Chapman-Kolmogorov

Sea:

\[\begin{align*} P_{ij}(t+s) =& \sum_{k\in S}P_{ik}(t)P_{kj}(s) \qquad \forall s\geq 0 , t\geq0 \end{align*}\]

Lema 2:

Sea:

\[ \lim_{h \to 0} \frac{1- P_{ii}(h)}{h}=\upsilon_{i} \]

Lema 3.

\[ \lim_{h\to 0}\frac{P_{ij}(h)}{h}= q_{ij} \qquad (i \neq j) \]

donde \(q_{ij}\) es la tasa instantánea a la que la cadena hace una transición del estado \(i\) al estado \(j\).

Demostración Lema 3:

Note que \(P_{ij}(h)\) es la probabilidad de que la cadena haga una transición del estado \(i\) al estado \(j\) en un intervalo de longitud \(h\). Sabemos que el tiempo que la cadena pasa en el estado \(i\) es una variable aleatoria exponencial con tasa \(\upsilon_{i}\) y desde dicho estado hay una probabilidad \(P_{ij}\) de que dicha transición ocurra al estado \(j\) (Piense en bifurcación). Así que la tasa a la cual la cadena deja el estado \(i\) para hacer una transición específicamente al estado \(j\) es \(\upsilon_{i}P_{ij}\equiv q_{ij}\). En lenguaje matemático, esto es equivalente a:

\[\begin{align*} &P_{ij}(h)=h\upsilon_{i}P_{ij}+o(h)= hq_{ij}+o(h)\\ & \implies \lim_{h \to 0} \frac{P_{ij}(h)}{h}=q_{ij}\\ \end{align*}\]

Ecuaciones Backward de Kolmogorov

Para todo \(i,j\in S\) y tiempos \(t\geq0\)

\[ P'_{ij}(t) = \left[\sum_{k\neq i}q_{ik}P_{kj}(t)-\upsilon_iP_{ij}(t) \right] \]

Prueba: Usando el lema 1 sabemos que:

\[ P_{ij}(h+t) = \sum_{k\in S}P_{ik}(h)P_{kj}(t) \]

por lo tanto,

\[\begin{align*} P_{ij}(h+t) - P_{ij}(t) =& \sum_{k\in S}P_{ik}(h)P_{kj}(t) - P_{ij}(t) \\ =& \sum_{k\neq i}P_{ik}(h)P_{kj}(t) + P_{ii}(h)P_{ij}(t) - P_{ij}(t) \\ =& \sum_{k\neq i}P_{ik}(h)P_{kj}(t) +P_{ij}(t)(1 - P_{ii}(h)) \end{align*}\]

Ejemplo: Procesos de nacimiento puro.

• \(\upsilon_i = \lambda_i\) \(P_{i,i+1} = 1\) \(P_{ij} = 0\) \(\forall j \neq i+1\)

Las ecuaciones Backward son:

\[ P'_{ij}(t) = \upsilon_i\sum_{k \neq i}P_{kj}(t)P_{ik}-P_{ij}(t) \\ = \lambda_i[P_{i+1,j}(t)-P_{ij}(t)] \]

Ejemplo: Procesos de nacimiento y muerte.

• \(\upsilon_0 = \lambda_0\) \(\upsilon_i = \lambda_i + \mu_i\) \(P_{01}= 1\) \(P_{i,i+1} = \frac{\lambda_i}{\upsilon_i}\) \(P_{i,i-1} = \frac{\mu_i}{\upsilon_i}\) \(i>0\)

Para \(i=0\)

\[ P'_{0j}(t) = \upsilon_0[P_{01}P_{1j}(t) - P_{0j}(t)] \\ = \lambda_0 [P_{ij}(t) - P_{0j}(t)] \]

Para \(i>0\)

\[ P'_{ij}(t) = \upsilon_i[P_{i,i+1}P_{i+1,j}(t)+P_{i,i-1}P_{i-1,j}(t) - P_{ij}(t)] \\ \lambda_iP_{i+1,j}(t) + \mu_iP_{i-1,j}(t)-(\lambda_i + \mu_i)P_{ij}(t) \]

¿Por qué las ecuaciones Backward son útiles?

Para obtener formas explícitas de \(P_{ij}(t)\)

Ejemplo: CMTC con dos estados

Suponga que \(X\) = La cantidad de tiempo que una máquina opera hasta que esta se malogre \(\sim exp(\lambda)\), donde \(Y\) = tiempo de reparación \(\sim exp(\mu)\)

Esto es un proceso de nacimiento y muerte con \(\lambda_0 = \lambda\) \(\lambda_1 = 0\) \(\mu_1 = \mu\)

Suponga que la máquina está operando a tiempo 0. Encuentre la probabilidad de que esté trabajando a tiempo 10. \(P_{00}(10)\)

Solución

Debido a que se trata de un proceso de nacimiento y muerte:

\[ P'_{00}(t) = \lambda_0[P_{10}(t) - P_{00}(t)] = \lambda[P_{10}(t) - P_{00}(t)] \]

\[ P'_{10}(t) = \lambda_1P_{20}(t) +\mu_1 P_{00}(t) - (\lambda_1+\mu_1)P_{10}(t)\\ = \mu[P_{00}(t) - P_{10}(t)] \qquad \text{ya que no existe un estado 2} \]

entonces,

\[ \mu P'_{00}(t) =\mu \lambda[P_{10}(t) - P_{00}(t)] \\ \lambda P'_{10}(t) = \mu \lambda[P_{00}(t) - P_{10}(t)] \\ \mu P'_{00}(t) + \lambda P'_{10}(t) = 0 \]

Integrando

\(\mu P'_{00}(t) + \lambda P'_{10}(t) = c\)

ya que \(P_{00}(0)=1\) y \(P_{10}(0)=0\), se tiene que \(\mu * 1 + \lambda*0=c \to c=\mu\)

\[ \mu P'_{00}(t) + \lambda P'_{10}(t) = \mu \\ \lambda P_{10}(t) = \mu [1- P_{00}(t)] \]

Ahora calculemos

\[ P'_{00}(t) = \lambda[P_{10}(t) - P_{00}(t)] \\ = \mu[1-P_{00}(t)] - \lambda P_{00}(t) \\ =\mu - (\mu + \lambda) P_{00}(t) \]

Solo necesitamos resolver la ecuación diferencial!

Sea \(h(t) \equiv P_{00}(t) - ○\frac{\mu}{\mu + \lambda}\)

\[ h'(t) = P'_{00}(t) = \mu - (\mu + \lambda)[h(t) + \frac{\mu}{\mu + \lambda}] \\ h'(t) = -(\mu + \lambda)h(t) \\ \frac{h'(t)}{h(t)} = - (\mu + \lambda) \\ \int \frac{h'(t)}{h(t)}dt = -\int (\mu + \lambda)dt \\ \log(h(t)) = -(\mu + \lambda)t + c \\ h(t) = e^{-(\mu+ \lambda)t + c}=ke^{-(\mu + \lambda)t} \]

Finalmente

\[ P_{00}(0) = 1 = k + \frac{\mu}{\mu + \lambda} \to k=\frac{\lambda}{\mu + \lambda} \]

\[ P_{00}(t) = \frac{\lambda}{\mu + \lambda}e^{-(\mu + \lambda)t}+\frac{\mu}{\mu + \lambda} \\ P_{10}(t) = \frac{\lambda}{\mu + \lambda}e^{-(\mu + \lambda)10}+\frac{\mu}{\mu + \lambda} \]

Ecuaciones “Forward” de Kolmogorov

\[P'_{ij}(t) = \sum_{k\neq j}P_kP_{kj}P_{ik}(t) - \upsilon_kP_{ij}(t)\]

La prueba es similar a las ecuaciones “Backward”

Escrito en notación matricial:

\[ R=\begin{bmatrix}-\upsilon_0 & \upsilon_0P_{01} & \dots & \dots &\upsilon_nP_{0n}\\ \upsilon_1P_{10} &-\upsilon_1 & \upsilon_1P_{12} & \dots & \upsilon_1P_{1n}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ \upsilon_nP_{n0} & \dots &\dots & \upsilon_nP_{n,n-1} &-\upsilon_n\end{bmatrix} \]

Es llamado también el generador infinitesimal o simplemente generador de una CMTC.

Donde:

\[ \begin{equation*} r_{ij} = \begin{cases}q_{ij} &\text{ si } i \neq j \\ -\upsilon_i & \text{ si } i=j \end{cases} \end{equation*} \]

\(q_{ij} = \upsilon_iP_{ij}\) es la tasa a la que CMTC va de un estado \(i\) a un estado \(j\) .

Veamos algunas observaciones

Primera observación

Primer que nada, note que:

\[ \sum_{j \in S, j\neq i}\upsilon_iP_{ij} = \upsilon_i\sum_{j \in S, j\neq i}P_{ij} = \upsilon_i*1 = \upsilon_i \]

Entonces las filas de R suman cero.

Segunda y tercera observación

(2) Las ecuaciones “Backward” pueden ser escritas como \(P'(t) = RP(t)\) y las ecuaciones “Forward” pueden ser escritos como \(P'(t) = P(t)R\) donde \(P(t)\) es la matriz cuyas entradas son \(P_{ij}(t)\)

(3) \(P(t)\) es continua a \(t=0\) (Consecuencias del Lema anterior)

Cuarta y quinta observación

(4) \(P(t)\) es continua \(\forall t \geq0\)

Esto se sigue de (3) y \(P(t+h) = P(t)P(h)\) la matriz de las ecuaciones de Chapman - Kolmogorov para una CMTC.

(5) \(P(t)\) es diferenciable y es la única solución de \(P'(t)=P(t)Q = QP(t)\)

Sexta y séptima observación

(6) \(Q(t)\) describe también la CMTC por completo

(7) En general, no es fácil computar \(P(t)\) .

¿Qué hacemos para computar \(P(T)\)?

¿Forward o Backward?

Veamos nuestro ejemplo

\[ R=\begin{bmatrix} - \lambda & \lambda\\\mu & -\mu\end{bmatrix} \]

\[ P(t)=\begin{bmatrix} P_{00}(t) & P_{01}(t)\\ P_{10}(t) & P_{11}(t)\end{bmatrix} \]

\[ P(t)=\begin{bmatrix} P'_{00}(t) & P'_{01}(t)\\ P'_{10}(t) & P'_{11}(t)\end{bmatrix} \]

Ecuaciones Backward

\(P'(t) = RP(t)\)

esto es: \[ \begin{bmatrix} P'_{00}(t) & P'_{01}(t)\\ P'_{10}(t) & P'_{11}(t)\end{bmatrix} = \begin{bmatrix} - \lambda & \lambda\\\mu & -\mu\end{bmatrix}\begin{bmatrix} P_{00}(t) & P_{01}(t)\\ P_{10}(t) & P_{11}(t)\end{bmatrix} \\ =\begin{bmatrix} -\lambda P_{00}(t) + \lambda P_{10}(t) & -\lambda P_{01}(t) + \lambda P_{11}(t) \\ \mu P_{00}(t) - \mu P_{10}(t) & \mu P_{01}(t) - \mu P_{11}(t)\end{bmatrix} \]

Ecuaciones Forward

\(P'(t) = RP(t)\)

esto es:

\[ \begin{bmatrix} P'_{00}(t) & P'_{01}(t)\\ P'_{10}(t) & P'_{11}(t)\end{bmatrix} = \begin{bmatrix} P_{00}(t) & P_{01}(t)\\ P_{10}(t) & P_{11}(t)\end{bmatrix}\begin{bmatrix} - \lambda & \lambda\\\mu & -\mu\end{bmatrix} \\ =\begin{bmatrix} -\lambda P_{00}(t) + \mu P_{01}(t) & \lambda P_{00}(t) - \mu P_{01}(t) \\ -\lambda P_{10}(t) + \mu P_{11}(t) & \lambda P_{10}(t) - \mu P_{11}(t)\end{bmatrix} \]

Tenga en cuenta que no necesitamos resolver cuatro ecuaciones simultáneas; necesitamos resolver solo dos a la vez como lo hicimos en el ejemplo. Por lo tanto, si nuestro estado inicial es fijo y queremos obtener la distribución condicional de \(X(t)\) , debemos usar las ecuaciones “Forward”. Por otro lado, si queremos encontrar la probabilidad de que \(X(t)\) se encuentre en un estado dado \(j\) para varios estados iniciales, debemos resolver ecuaciones “Backward”.\[ P(t)=\begin{bmatrix} \frac{\lambda}{\lambda+\mu}e^{-(\lambda + \mu)t}+\frac{\mu}{\lambda + \mu} & \frac{\lambda}{\lambda+\mu}(1-e^{-(\lambda + \mu)t}) \\ \frac{\mu}{\lambda+\mu}(1-e^{-(\lambda + \mu)t})& \frac{\mu}{\lambda+\mu}e^{-(\lambda + \mu)t}+\frac{\lambda}{\lambda + \mu} \end{bmatrix} \]

Algunos ejemplos de modelamiento

Considere un taller mecánico que tiene dos máquinas que son independientes, idénticas y pueden estar en funcionamiento o malogradas. Si una máquina está en funcionamiento, esta falla después de una cantidad de tiempo \(exp(\mu)\). Si está malograda, se necesita una cantidad de tiempo \(exp(\lambda)\) para arreglarlo. Una vez arreglada, estará como nueva. Los tiempos sucesivos de avería y reparación son independientes. Sea \(X(t)\) el número de máquinas en funcionamiento en el tiempo \(t\). ¿Es \(\lbrace X(t),t\geq0 \rbrace\) una CMTC? (Cada máquina posee su propio técnico)

Solución

Definamos \(S = \lbrace 0,1,2\rbrace\)

Analicemos los estados uno a uno:

Estado 0: Ambas máquinas están malogradas, cuando una de estas es reparada, el sistema se mueve al estado 1. Esto ocurrirá después de \(\min\big(exp(\lambda),exp(\lambda)\big) = exp(2\lambda)\). Entonces, \(\upsilon_0 = 2\lambda\)

¿Cómo obtenemos \(\mathbb{P}\) para \(R\)?

Recuerde que \(\mathbb{P}\) tiene ceros en su diagonal, y que \(r_{ij}=\upsilon_iP_{ij} \qquad i\neq j\). Entonces, dividiendo \(r_{ij}\) por \(\upsilon_i\) nos dará \(\mathbb{P}\).

\[ \mathbb{P}=\begin{bmatrix} 0 & 1 & 0 \\ \frac{\mu}{\mu+\lambda}&0&\frac{\lambda}{\mu + \lambda}\\ 0 & 1 & 0\end{bmatrix} \]

Cambiando el ejemplo

Ahora suponga que solo hay un técnico y las máquinas son reparadas según el orden “primera malograda, primera reparada”. Sea \(X(t)\) el número de máquinas en funcionamiento a tiempo \(t\). ¿Cuál es el generador?

\[ R=\begin{bmatrix} -\lambda & \lambda &0\\ \mu & -(\mu+\lambda)&\lambda \\ 0& 2\mu & -2\mu\end{bmatrix} \]

Ejemplo: Clientes en una estación de dos servidores.

Suponga que los clientes llegan a una estación de 2 servidores como \(PPH(\lambda)\). No hay sala de espera en la estación. Si un cliente entrante encuentra al menos un servidor vacío, inmediatamente comienza a ser atendido. Los tiempos de servicio son \(exp(\mu)\) para ambos servidores. Si encuentra ambos servidores ocupados, se va y decimos que el cliente se ha perdido. Modele esto como un CMTC. Encuentre R.

Solución

Sea \(X(t)\) el número de servidores ocupados a tiempo \(t\). \(S = \lbrace0,1,2\rbrace\)

\[ R=\begin{bmatrix} -\lambda & \lambda &0\\ \mu & -(\mu+\lambda)&\lambda \\ 0& 2\mu & -2\mu\end{bmatrix} \]

Ejemplo: Cola de reintento.

Suponga que los clientes llegan a una estación de un solo servidor como \(PPH(\lambda)\). No hay sala de espera en el servidor. Si un cliente entrante encuentra el servidor vacío, inmediatamente comienza a ser atendido. Los tiempos de servicio son variables aleatorias independientes e indénticamente distribuídas \(exp(\mu)\). Si encuentra el servidor ocupado, se va (decimos que se une a una órbita) y vuelve a probar suerte después de una cantidad de tiempo \(exp(\theta)\) independiente de todo lo demás. Persiste de esta manera hasta que es atendido. Todos los clientes se comportan de esta manera. Modele esto como un CMTC

¿Qué aprendimos hoy?