5.8: Ejercicios

Ejercicio 5.1

$\left\{P_{i j} ; i, j \geq 0\right\}$Sea el conjunto de probabilidades de transición para una cadena de Markov de estado contable. Para cada uno$i$,$j$, deja$\mathrm{F}_{i j}(n)$ ser la probabilidad de que el estado$j$ ocurra en algún momento entre el tiempo 1 y n inclusive, dado$X_{0}=i$. Para algunos dados$j$, supongamos que$\left\{x_{k} ; k \geq 0\right\}$ es un conjunto de números no negativos satisfactorios$x_{i}=P_{i j}+\sum_{k \neq j} P_{i k} x_{k}$. Demostrar eso$x_{i} \geq \mathrm{F}_{i j}(n)$ para todos$n$ y$i$, y de ahí eso$x_{i} \geq \mathrm{F}_{i j}(\infty)$ para todos$i$. Pista: usar inducción.

Ejercicio 5.2

1. Para la cadena Markov en la Figura 5.2, mostrar eso, para$p \geq 1 / 2, \mathrm{~F}_{00}(\infty)=2(1-p)$ y mostrar eso$\mathrm{F}_{i 0}(\infty)=[(1-p) / p]^{i}$ para$i \geq 1$. Pista: primero mostrar que esta solución satisface\ ref {5.9} y luego mostrar que\ ref {5.9} no tiene una solución más pequeña (ver Ejercicio 5.1). Tenga en cuenta que ha demostrado que la cadena es transitoria para$p>1 / 2$ y que es recurrente para$p=1 / 2$.
2. Bajo las mismas condiciones que la parte a), mostrar que$\mathrm{F}_{i j}(\infty)$ es igual a$2(1-p)$ para$j=i$, igual a$[(1-p) / p]^{i-j}$ para$i>j$, y es igual a 1 para$i<j$.

Ejercicio 5.3

1. Mostrar que las probabilidades de transición de orden$n$ th, comenzando en el estado 0, para la cadena de Markov en la Figura 5.2 satisfacen

   $P_{0 j}^{n}=p P_{0, i-1}^{n-1}+q P_{0, i+1}^{n-1} \quad j \neq 0 ; \quad P_{00}^{n}=q P_{00}^{n-1}+q P_{01}^{n-1}$

   Pista: Usa la igualdad Chapman-Kolmogorov, (3.8).

2. Para$p=1 / 2$, use esta ecuación para calcular$P_{0 j}^{n}$ iterativamente para$n=1,2,3,4$. Verifique\ ref {5.3} para estos valores y luego use inducción para verificar\ ref {5.3} en general. Nota: esto se convierte en un lío absoluto para$p \neq 1 / 2$, así que no intentes esto en general.
3. Como un enfoque más interesante, que pone de manifiesto la relación de las Figuras 5.2 y 5.1, señalar que (5.3), con$j+n$ par, es la probabilidad de que$S_{n}=j$ para la cadena en 5.1 y\ ref {5.3} con$j+n$ impar es la probabilidad que$S_{n}=-j-1$ para la cadena en 5.1. Al ver cada transición sobre el bucle self en el estado 0 como una inversión de signo para la cadena en 5.1, explique por qué este sorprendente resultado es cierto. (Nuevamente, esto no funciona para$p \neq 1 / 2$, ya que las inversiones de signo también invierten las transiciones +1, -1).

Ejercicio 5.4

Dejar$j$ ser un estado transitorio en una cadena de Markov y dejar que$j$ sea accesible desde$i$. Demostrar que también$i$ es transitorio. Interpretar esto como una forma de ley de Murphy (si algo malo puede suceder, lo hará, donde lo malo es la falta de un eventual retorno). Nota: dar una demostración directa en lugar de usar Lemma 5.1.3.

Ejercicio 5.5

Considera una cadena irreducible de Markov positivo-recurrente. Considera el proceso de renovación$\left\{N_{j j}(t) ; t \geq 0\right\}$ donde, dado$X_{0}=j, N_{j j}(t)$ es el número de veces que$j$ se visita ese estado desde el tiempo 1 hasta$t$. Para cada uno$i \geq 0$, considere una función de renovación-recompensa$R_{i}(t)$ igual a 1 siempre que la cadena esté en estado$i$ e igual a 0 de lo contrario. Deja$\pi_{i}$ ser la recompensa promedio de tiempo.

1. Demostrar que$\pi_{i}=1 / \overline{T}_{i i}$ para cada uno$i$ con probabilidad 1.
2. $\sum_{i} \pi_{i}=1$Demuéstralo. Pista: considerar$\sum_{i \leq M} \pi_{i}$ para cualquier entero$M$.
3. Considera una función de renovación-recompensa$R_{i j}(t)$ que sea 1 siempre que la cadena esté en estado$i$ y el siguiente estado sea estado$j$. $R_{i j}(t)=0$de lo contrario. Demostrar que la recompensa promedio de tiempo es igual a$\pi_{i} P_{i j}$ con probabilidad 1. $p_{k}=\sum_{i} \pi_{i} P_{i k}$Demuéstralo para todos$k$.

Ejercicio 5.6

Dejar$\left\{X_{n} ; n \geq 0\right\}$ ser un proceso de ramificación con$X_{0}=1$. $\overline{Y}, \sigma^{2}$Sea la media y varianza del número de crías de un individuo.

1. Argumentan que$\lim _{n \rightarrow \infty} X_{n}$ existe con probabilidad 1 y o bien tiene el valor 0 (con probabilidad$\left.\mathrm{F}_{10}(\infty)\right)$ o el valor$\infty$ (con probabilidad$1-\mathrm{F}_{10}(\infty)$).
2. Demuestre eso$\operatorname{VAR}\left[X_{n}\right]=\sigma^{2} \overline{Y}^{n-1}\left(\overline{Y}^{n}-1\right) /(\overline{Y}-1)$ y$\operatorname{VAR}\left[X_{n}\right]=n \sigma^{2}$ para$\overline{Y}=1$.

Ejercicio 5.7

Hay$n$ estados y para cada par de estados$i$ y$j$,$d_{i j}=d_{j i}$ se da un número positivo. Una partícula se mueve de estado a estado de la siguiente manera: Dado que la partícula está en cualquier estado$i$, luego se moverá a cualquiera$j \neq i$ con probabilidad$P_{i j}$ dada por

$P_{i j}=\frac{d_{i j}}{\sum_{j \neq i} d_{i j}}$

Asumir eso$P_{i i}=0$ para todos$i$. Demostrar que la secuencia de posiciones es una cadena reversible de Markov y encontrar las probabilidades limitantes.

Ejercicio 5.8

Considere una cadena reversible de Markov con probabilidades de transición$P_{i j}$ y probabilidades limitantes$\pi_i$. También considere la misma cadena truncada a los estados 0, 1,.,.,$M$. Es decir, las probabilidades$\left\{P_{i j}^{\prime}\right\}$ de transición de la cadena truncada son

\ (P_ {i j} ^ {\ prime} =\ izquierda\ {\ begin {array} {ll}
\ frac {P_ {i j}} {\ sum_ {k=0} ^ {m} P_ {i k}} &; & 0\ leq i, j\ leq M\\
\} 0 &; &\ text {en otra parte}
\ end {array}\ derecha.

Demostrar que la cadena truncada también es reversible y tiene probabilidades limitantes dadas por

$\overline{\pi}_{i}=\frac{\pi_{i} \sum_{j=0}^{M} P_{i j}}{\sum_{k=0}^{M} \pi_{i} \sum_{m=0}^{M} P_{k m}}$

Ejercicio 5.9

Una cadena de Markov (con estados$\{0,1,2, \ldots, J-1\}$ donde$J$ es finita o infinita) tiene probabilidades de transición$\left\{P_{i j} ; i, j \geq 0\right\}$. Asumir eso$P_{0 j}>0$ para todos$j>0$ y$P_{j 0}>0$ para todos$j>0$. También supongamos que para todos$i, j, k$, tenemos$P_{i j} P_{j k} P_{k i}=P_{i k} P_{k j} P_{j i}$.

1. Suponiendo también que todos los estados son recurrentes positivos, muestran que la cadena es reversible y encuentran las probabilidades de estado estacionario$\left\{\pi_{i}\right\}$ en la forma más simple.
2. Encontrar una condición encendida$\left\{P_{0 j} ; j \geq 0\right\}$ y$\left\{P_{j 0} ; j \geq 0\right\}$ que sea suciente para asegurar que todos los estados sean positivos recurrentes.

Ejercicio 5.10

1. Utilice el modelo de nacimiento y muerte descrito en la figura 5.4 para encontrar la función de masa de probabilidad de estado estacionario para el número de clientes en el sistema (cola más instalación de servicio) para las siguientes colas:
   1. M/M/1 con probabilidad de llegada$\lambda \delta$, probabilidad de finalización del servicio$\mu \delta$.
   2. M/m/m con probabilidad de llegada$\lambda \delta$, probabilidad de finalización del servicio$i \mu \delta$ para$i$ servidores ocupados,$1 \leq i \leq m$.
   3. M/M/$\infty$ con probabilidad de llegada$\lambda \delta$, probabilidad de servicio$i \mu \delta$ para$i$ servidores. Asumir$\delta$ tan pequeño que$i \mu \delta<1$ para todos$i$ los intereses.

Supongamos que el sistema es recurrente positivo.

2. Para cada una de las colas anteriores dar las condiciones necesarias (si las hubiera) para que los estados de la cadena sean i) transitorios, ii) recurrentes nulos, iii) recurrentes positivos.
3. Para cada una de las colas encontrar:

L= (\ text {steady-state}) número medio de clientes en el sistema.

$L^{q}=\text { (steady-state) }$número medio de clientes en la cola.

$W=(\text { steady-state })$tiempo medio de espera en el sistema.

$W^{q}=(\text { steady-state })$tiempo de espera medio en la cola.

Ejercicio 5.11

1. Dado que se produce una llegada en el intervalo$(n \delta,(n+1) \delta)$ para el modelo de tiempo muestreado M/M/1 en la figura 5, encontrar el PMF condicional del estado del sistema en el tiempo$n \delta$ (asumir n arbitrariamente grande y asumir recurrencia positiva).
2. Para el mismo modelo, nuevamente en estado estacionario pero no condicionado a una llegada en$(n \delta,(n+1)\delta)$, encontrar la probabilidad de$Q(i, j)(i \geq j>0)$ que el sistema esté en estado$i$ en$n \delta$ y que las$i-j$ salidas ocurran antes de la siguiente llegada.
3. Encuentre el número esperado de clientes vistos en el sistema para la primera llegada después del tiempo$n \delta$. (Nota: el propósito de este ejercicio es hacerte cauteloso sobre el significado de “el estado visto por una llegada aleatoria”).

Ejercicio 5.12

Encuentra las probabilidades de transición hacia atrás para el modelo de la cadena de Markov de edad en la figura 2. Dibuja la gráfica para la cadena hacia atrás de Markov, e interpretarla como un modelo para la vida residual.

Ejercicio 5.13

Considere la aproximación del tiempo de muestreo a la cola M/M/1 en la figura 5.5.

1. Dar las probabilidades de estado estacionario para esta cadena (no se requieren explicaciones ni cálculos, solo la respuesta).

En las partes b) a g) no use reversibilidad y no use el teorema de Burke. Dejar$X_{n}$ ser el estado del sistema en el momento$n \delta$ y dejar$D_{n}$ ser una variable aleatoria tomando el valor 1 si se produce una salida entre$n \delta$ y$(n+1) \delta$, y el valor 0 si no ocurre salida. Supongamos que el sistema está en estado estacionario en el momento$n \delta$.

2. Buscar$\operatorname{Pr}\left\{X_{n}=i, D_{n}=j\right\}$ para$i \geq 0, j=0,1$
3. Encuentra$\operatorname{Pr}\left\{D_{n}=1\right\}$
4. Buscar$\operatorname{Pr}\left\{X_{n}=i \mid D_{n}=1\right\}$ para$i \geq 0$
5. Encontrar$\operatorname{Pr}\left\{X_{n+1}=i \mid D_{n}=1\right\}$ y mostrar que$X_{n+1}$ es estadísticamente independiente de$D_{n}$. Pista: Usar la parte d); también mostrar que$\operatorname{Pr}\left\{X_{n+1}=i\right\}=\operatorname{Pr}\left\{X_{n+1}=i \mid D_{n}=1\right\}$ para todos$i \geq 0$ es suciente mostrar independencia.
6. Encontrar$\operatorname{Pr}\left\{X_{n+1}=i, D_{n+1}=j \mid D_{n}\right\}$ y mostrar que el par de variables$\left(X_{n+1}, D_{n+1}\right)$ es estadísticamente independiente de$D_{n}$.
7. Para cada uno$k>1$, encuentra$\operatorname{Pr}\left\{X_{n+k}=i, D_{n+k}=j \mid D_{n+k-1}, D_{n+k-2}, \ldots, D_{n}\right\}$ y demuestra que el par$\left(X_{n+k}, D_{n+k}\right)$ es estadísticamente independiente de$\left(D_{n+k-1}, D_{n+k-2}, \ldots, D_{n}\right)$. Pista: usar inducción en$k$; como subpaso, encontrar$\operatorname{Pr}\left\{X_{n+k}=i \mid D_{n+k-1}=1, D_{n+k-2}, \ldots, D_{n}\right\}$ y mostrar que$X_{n+k}$ es independiente de$D_{n+k-1}, D_{n+k-2}, \ldots, D_{n}$.
8. ¿Qué significan tus resultados en relación con el teorema de Burke?

Ejercicio 5.14

Dejar$\left\{X_{n}, n \geq 1\right\}$ denotar una cadena recurrente irreducible de Markov que tiene un espacio estatal contable. Consideremos ahora un nuevo proceso estocástico$\left\{Y_{n}, n \geq 0\right\}$ que sólo acepta valores de la cadena de Markov que están entre 0 y algún entero$m$. Por ejemplo, si$m=3$ y$X_{1}=1, X_{2}=3, X_{3}=5, X_{4}=6, X_{5}=2$, entonces$Y_{1}=1, Y_{2}=3, Y_{3}=2$.

1. ¿Es$\left\{Y_{n}, n \geq 0\right\}$ una cadena de Markov? Explique brevemente.
2. Vamos a$p_{j}$ denotar la proporción de tiempo que$\left\{X_{n}, n \geq 1\right\}$ está en estado$j$. Si$p_{j}>0$ por todos$j$, qué proporción de tiempo hay$\left\{Y_{n}, n \geq 0\right\}$ en cada uno de los estados 0, 1,.,.,$m$?
3. Supongamos que$\left\{X_{n}\right\}$ es nulo recurrente y vamos a$p_{i}(m), i=0,1, \ldots, m$ denotar las proporciones a largo plazo para$\left\{Y_{n}, n \geq 0\right\}$. Demostrar que$p_{j}(m)=p_{i}(m) E[\text { time the } X \text { process spends in } j \text { between return to }i],j \neq i.\}$

Ejercicio 5.15

Verificar que\ ref {5.53} esté satisfecho por la solución hipotética a$p$ in (5.57). También muestran que las ecuaciones que involucran el estado inactivo$f$ están satisfechas.

Ejercicio 5.16

Reemplazar el estado$\mathbf{m}=\left(m, z_{1}, \ldots, z_{m}\right)$ en la Sección 5.6 por un estado ampliado$\mathbf{m}=\left(m, z_{1}, w_{1}, z_{2}, w_{2}, \ldots, z_{m}, w_{m}\right)$ donde$m$ y$\left\{z_{i} ; 1 \leq i \leq m\right\}$ son como antes y$w_{1}, w_{2}, \ldots, w_{m}$ son los requisitos de servicio originales de los$m$ clientes.

1. Hipótesis del mismo sistema de round-robin hacia atrás que se hipotetizó en la Sección 5.6, encuentre las probabilidades de transición hacia atrás y dé las ecuaciones correspondientes a (5.51 5.54) para la descripción del estado expandido.
2. Resuelve las ecuaciones resultantes para mostrar que

   $\pi_{\mathbf{m}}=\pi+\phi\left(\frac{\lambda \delta}{1-\lambda \delta}\right)^{m} \prod_{j=1}^{m} f\left(w_{j}\right)$

3. Demostrar que la probabilidad de que haya m clientes en el sistema, y que esos clientes tengan requisitos de servicio originales dados por$w_{1}, \ldots, w_{m}$, es

   $\left.\operatorname{Pr}\left\{m, w_{1}, \ldots, w_{m}\right\}=\pi_{\phi} \quad \frac{\lambda \delta}{1-\lambda \delta}\right)^{m} \prod_{j=1}^{m}\left(w_{j}-1\right) f\left(w_{j}\right)$

4. Dado que un cliente tiene requisito de servicio original$w$, encuentre el tiempo esperado que el cliente pasa en el sistema.