16.2: Elementos de las Secuencias de Markov
- Page ID
- 150886
Elementos de las secuencias de Markov
Las secuencias de Markov (cadenas de Markov) a menudo se estudian a un nivel muy elemental, utilizando herramientas algebraicas como el análisis matricial. En esta sección, mostramos que la propiedad fundamental de Markov es una expresión de independencia condicional de “pasado” y “futuro”, dado el “presente”. La ecuación esencial de Chapman-Kolmogorov es vista como consecuencia de esta independencia condicional. En el caso habitual de tiempo homogéneo con espacio de estados finitos, la ecuación de Chapman-Kolmogorov conduce a la formulación algebraica que es ampliamente estudiada en una variedad de niveles de sofisticación matemática. Con el fondo puesto, solo esbozamos algunos de los resultados más comunes. Esto debería proporcionar una perspectiva probabilística para un estudio más completo del análisis algebraico.
Secuencias de Markov
Queremos modelar un sistema caracterizado por una secuencia de estados tomados en instantes discretos que llamamos tiempos de transición. En cada momento de transición, hay o bien un cambio a un nuevo estado o una renovación del estado inmediatamente antes de la transición. Cada estado se mantiene sin cambios durante el periodo o etapa entre transiciones. En cualquier momento de transición, el paso al siguiente estado se caracteriza por una distribución de probabilidad de transición condicional. Suponemos que el sistema carece de memoria, en el sentido de que las probabilidades de transición dependen del estado actual (y quizás del número de periodo), pero no de la manera en que se alcanzó ese estado. El pasado influye en el futuro sólo a través del presente. Esta es la propiedad de Markov, que modelizamos en términos de independencia condicional.
Para periodo\(i\), el estado está representado por un valor de una variable aleatoria\(X_i\), cuyo valor es uno de los miembros de un conjunto E, conocido como el espacio de estado. Consideramos solo un espacio de estado finito e identificamos los estados por enteros de 1 a\(M\). Tenemos así una secuencia
\(X_N = \{X_n: n \in N\}\), donde\(N = \{0, 1, 2, \cdot\cdot\cdot\}\)
Consideramos una observación del sistema como un ensayo compuesto. Cada uno\(\omega\) produce una secuencia de estados\(\{X_0 (\omega), X_1 (\omega), \cdot\cdot\cdot\}\) que se conoce como una realización de la secuencia, o una trayectoria. Suponemos que el sistema está evolucionando en el tiempo. En instantes discretos de tiempo\(t_1, t_2, \cdot\cdot\cdot\) el sistema realiza una transición de un estado al siguiente (que puede ser el mismo).
Periodo inicial: | \(n = 0\),\(t \in [0, t_1)\), | estado es\(X_0 (\omega)\); en\(t_1\) la transición es a\(X_1 (\omega)\) |
Periodo uno: | \(n = 1\),\(t \in [t_1, t_2)\), | estado es\(X_1 (\omega)\); en\(t_2\) la transición es a\(X_2 (\omega)\) |
... | ||
Periodo\(k\): | \(n = k\),\(t \in [t_k, t_{k = 1})\), | estado es\(X_k (\omega)\); en\(t_{k +1}\) movimiento a\(X_{k +1} (\omega)\) |
... |
El parámetro\(n\) indica el periodo\(t \in [t_n, t_{n + 1})\). Si los periodos son de longitud unitaria, entonces\(t_n = n\). At\(t_{n + 1}\), hay una transición del estado\(X_n (\omega)\) al estado\(X_{n + 1} (\omega)\) para el siguiente periodo. Para simplificar la escritura, adoptamos la siguiente convención:
\(U_n = (X_0, X_1, \cdot\cdot\cdot, X_n) \in E_n\)\(U_{m,n} = (X_m, \cdot\cdot\cdot, X_n)\)y\(U^{n} = (X_n, X_{n + 1}, \cdot\cdot\cdot) \in E^n\)
El vector aleatorio\(U_n\) se llama el pasado en\(n\) de la secuencia\(X_N\) y\(U^n\) es el futuro en\(n\). Para captar la noción de que el sistema está sin memoria, para que el futuro se vea afectado por el presente, pero no por cómo se alcanza el presente, utilizamos la noción de independencia condicional, dado un vector aleatorio, en lo siguiente
Definición
La secuencia\(X_N\) es Markov iff
(M)\(\{X_{n + 1}, U_n\}\) ci\(|X_n\) para todos\(n \ge 0\)
Varias condiciones equivalentes a la condición de Markov (M) pueden obtenerse con la ayuda de propiedades de independencia condicional. Observamos primero que (M) es equivalente a
\(P(X_{n + 1} = k|X_n = j, U_{n - 1} \in Q) = P(X_{n + 1} = k|X_n = j)\)para cada uno\(n \ge 0\),\(j, k \in E\), y\(Q \subset E^{n - 1}\)
El estado en el siguiente periodo está condicionado por el pasado sólo a través del estado presente, y no por la manera en que se alcanza el estado presente. Las estadísticas del proceso están determinadas por las probabilidades de estado iniciales y las probabilidades de transición
\(P(X_{n + 1} = k|X_n = j)\)\(\forall j, k \in E\),\(n \ge 0\)
Los siguientes ejemplos muestran un patrón que implica la condición de Markov y que puede ser explotado para obtener las probabilidades de transición.
Ejemplo\(\PageIndex{1}\) One-dimensional random walk
Un objeto comienza en una posición inicial dada. En instantes discretos,\(t_1, t_2, \cdot\cdot\cdot\) el objeto se mueve una distancia aleatoria a lo largo de una línea. Los diversos movimientos son independientes entre sí. Vamos
\(Y_0\)ser la posición inicial
\(Y_k\) sea la cantidad que el objeto se mueve en el momento\(t = t_k\)\(\{Y_k: 1 \le k\}\) iid
\(X_n = \sum_{k =0}^{n} Y_k\) ser la posición después de los\(n\) movimientos
Tomamos nota de eso\(X_{n + 1} = g(X_n, Y_{n + 1})\). Dado que la posición después de la transición en\(t_{n + 1}\) se ve afectada por el pasado solo por el valor de la posición\(X_n\) y no por la secuencia de posiciones que condujo a esta posición, es razonable suponer que el proceso\(X_N\) es Markov. Verificamos esto a continuación.
Ejemplo\(\PageIndex{2}\) A class of branching processes
Cada miembro de una población es capaz de reproducirse. Por simplicidad, suponemos que en ciertos instantes discretos se produce toda la siguiente generación. Algún mecanismo limita cada generación a una población máxima de\(M\) integrantes. Vamos
\(Z_{in}\)ser el número propagado por el miembro\(i\) th de la generación\(n\) th.
\(Z_{in} = 0\)indica muerte y ninguna descendencia,\(Z_{in} = k\) indica una red de\(k\) propagada por el miembro\(i\) th (ya sea muerte y\(k\) descendencia o supervivencia y\(k - 1\) descendencia).
La población en generación\(n + 1\) viene dada por
\(X_{n + 1} = \text{min } \{M, \sum_{i = 1}^{X_n} Z_{in}\}\)
Suponemos que la clase\(\{Z_{in}: 1 \le i \le M, 0 \le n\}\) es iid. Vamos\(Y_{n + 1} = (Z_{in}, Z_{2n}, \cdot\cdot\cdot, Z_{Mn})\). Thne\(\{Y_{n + 1}, U_n\}\) es independiente. Parece razonable suponer que la secuencia\(X_N\) es Markov.
Ejemplo\(\PageIndex{3}\) An inventory problem
Un determinado artículo se abastece de acuerdo con una política\((m, M)\) de inventario, de la siguiente manera:
- Si el stock al final de un periodo es menor que\(m\), ordene hasta\(M\).
- Si el stock al final de un periodo es\(m\) o mayor, no ordene.
Dejar\(X_0\) ser el stock inicial, y\(X_n\) ser el stock al final del periodo\(n\) th (antes de la repoblación), y dejar\(D_n\) ser la demanda durante el\(n\) th periodo. Entonces para\(n \ge 0\),
\(X_{n + 1} = \begin{cases} \text{max } \{M - D_{n + 1}, 0\} & \text{if } 0 \le X_n < m \\ \text{max } \{X_n - D_{n + 1}, 0\} & \text{if } m \le X_n \end{cases} = g(X_n, D_{n + 1})\)
Si suponemos que\(\{D_n: 1 \le n\}\) es independiente, entonces\(\{D_{n = 1}, U_n\}\) es independiente para cada uno\(n \ge 0\), y parece indicarse la condición de Markov.
Observación. En este caso, la transición real se lleva a cabo a lo largo del periodo. Sin embargo, para fines de análisis, examinamos el estado solo al final del periodo (antes de la repoblación). Así, las transiciones se dispersan en el tiempo, pero las observaciones se encuentran en instantes discretos.
Ejemplo\(\PageIndex{4}\) Remaining lifetime
Una pieza de equipo tiene una vida útil que es un número integral de unidades de tiempo. Cuando una unidad falla, se reemplaza inmediatamente por otra unidad del mismo tipo. Supongamos
- \(X_n\)es la vida útil restante de la unidad en servicio en el momento\(n\)
- \(Y_{n + 1}\)es la vida útil de la unidad instalada en el momento\(n\), con\(\{Y_n: 1 \le n\}\) iid
Entonces\(X_{n + 1} = \begin{cases} X_n - 1 & \text{if } X_n \ge 1 \\ Y_{n + 1} - 1 & \text{if } X_n = 0 \end{cases} = g(X_n, Y_{n + 1})\)
Observación. Cada uno de estos cuatro ejemplos exhibe el patrón
\(\{X_0, Y_n: 1 \le n\}\)es independiente
\(X_{n + 1} = g_{n + 1} (X_n, Y_{n + 1})\),\(n \ge 0\)
Ahora verificamos la condición de Markov y obtenemos un método para determinar las probabilidades de transición.
Un patrón que produce secuencias de Markov
Supongamos que\(\{Y_n : 0 \le n\}\) es independiente (llame a estas las variables aleatorias de conducción). Set
\(X_0 = g_0 (Y_0)\)y\(X_{n + 1} = g_{n + 1} (X_n, Y_{n + 1})\)\(\forall n \ge 0\)
Entonces
\(X_N\)es Markov
\(P(X_{n+1} \in Q|X_n = u) = P[g_{n + 1} (u, Y_{n + 1}) \in Q]\) para todos\(n, u\), y cualquier conjunto de Borel\(Q\).
VERIFICACIÓN
Es evidente que si\(Y_0, Y_1, \cdot\cdot\cdot, Y_n\) se conocen, entonces\(U_n\) se conoce. Así\(U_n = h_n (Y_0, Y_1, \cdot\cdot\cdot, Y_n)\), lo que asegura que cada par\(\{Y_{n + 1}, U_n\}\) sea independiente. Por propiedad (CI13)\(X = Y_{n +1}\), con\(Y = X_n\), y\(Z = U_{n - 1}\), tenemos
\(\{Y_{n + 1}, U_{n - 1}\}\)ci\(|X_n\)
Desde\(X_{n + 1} = g_{n + 1} (Y_{n + 1}, X_n)\) y\(U_n = h_n (X_n, U_{n - 1})\), propiedad (CI9) asegura
\(\{X_{n + 1}, U_n\}\)ci\(|X_n\)\(\forall n \ge 0\)
que es la propiedad de Markov.
\(P(X_{n + 1} \in Q|X_n = u) = E\{I_Q [g_{n + 1} (X_n,Y_{n + 1})]|X_n = u\}\)a.s.\(= E\{I_Q [g_{n + 1} (u, Y_{n + 1})]\}\) a.s.\([P_X]\) por (CE10b)
\(= P[g_{n + 1} (u, Y_{n + 1}) \in Q]\) por (E1a)
— □
La aplicación de esta proposición, a continuación, a los ejemplos anteriores muestra que las probabilidades de transición son invariantes con\(n\). Este caso es lo suficientemente importante como para justificar una clasificación separada.
Definición
Si\(P(X_{n + 1} \in Q|X_n = u)\) es invariante con\(n\), para todos los conjuntos de Borel\(Q\), todos\(u \in E\),\(X_N\) se dice que el proceso de Markov es homogéneo.
De hecho, este es el único caso que suele tratarse en los textos elementales. Al respecto, señalamos el siguiente caso especial de la proposición anterior.
Secuencias homogéneas de Markov
Si\(\{Y_n: 1 \le n\}\) es iid y\(g_{n + 1} = g\) para todos\(n\), entonces el proceso es un proceso homogéneo de Markov, y
\(P(X_{n + 1} \in Q|X_n = u) = P[g(u, Y_{n + 1}) \in Q]\), invariante con\(n\)
— □
Observación.
En el caso homogéneo, las probabilidades de transición son invariantes con\(n\). En este caso, escribimos
\(P(X_{n + 1} = j|X_n = i) = p(i, j)\)o\(p_{ij}\) (invariante con\(n\))
Estas se llaman las probabilidades de transición (de un solo paso).
Las probabilidades de transición pueden estar dispuestas en una matriz P llamada matriz de probabilidad de transición, generalmente denominada matriz de transición,
P =\([p(i, j)]\)
El elemento\(p(i, j)\) en fila\(i\) y columna\(j\) es la probabilidad\(P(X_{n + 1} = j|X_n = i)\). Así, los elementos de la fila\(i\) th constituyen la distribución condicional para\(X_{n + 1}\), dada\(X_n = i\). La matriz de transición tiene así la propiedad de que cada fila suma a una. Tal matriz se llama matriz estocástica. Volvemos a los ejemplos. De las proposiciones sobre las probabilidades de transición, es evidente que cada una es Markov. Dado que la función\(g\) es la misma para todos\(n\) y las variables aleatorias conductoras correspondientes a la\(Y_i\) forma una clase iid, las secuencias deben ser homogéneas. Podemos utilizar la parte (b) de las proposiciones para obtener las probabilidades de transición de un solo paso.
Ejemplo\(\PageIndex{5}\) Random walk continued
\(g_n (u, Y_{n + 1}) = u + Y_{n + 1}\). así que\(g_n\) es invariante con\(n\). Dado que\(\{Y_n: 1 \le n\}\) es iid,
\(P(X_{n+1} = k|X_n = j) = P(j + Y = k) = P(Y = k - j) = p_{k - j}\)donde\(p_k = P(Y = k)\)
Ejemplo\(\PageIndex{6}\) Branching process continued
\(g(j, Y_{n + 1}) = \text{min } \{M, \sum_{i = 1}^{j} Z_{in}\}\)y E =\(\{0, 1, \cdot\cdot\cdot, M\}\). Si\(\{Z_{in}: 1 \le i \le M\}\) es iid, entonces
\(W_{jn} = \sum_{i = 1}^{j} Z_{in}\)asegura\(\{W_{jn}: 1 \le n\}\) es iid para cada\(j \in\) E
Así tenemos
\(P(X_{n + 1} = k|X_n = j) = \begin{cases} P(W_{jn} = k) & \text{for } 0 \le k < M \\ P(W_{jn} \ge M) & \text{for } k \ge M \end{cases} 0 \le j \le M\)
Con la ayuda de funciones de generación de momentos, se pueden determinar distribuciones para
\(W_1 = Z_1, W_2 = Z_1 + Z_2, \cdot\cdot\cdot, W_{M} = Z_1 + \cdot\cdot\cdot + Z_M\)
Estos cálculos se implementan en un procedimiento m llamado branchp. Simplemente necesitamos la distribución para el iid\(Z_{in}\).
% file branchp.m % Calculates transition matrix for a simple branching % process with specified maximum population. disp('Do not forget zero probabilities for missing values of Z') PZ = input('Enter PROBABILITIES for individuals '); M = input('Enter maximum allowable population '); mz = length(PZ) - 1; EZ = dot(0:mz,PZ); disp(['The average individual propagation is ',num2str(EZ),]) P = zeros(M+1,M+1); Z = zeros(M,M*mz+1); k = 0:M*mz; a = min(M,k); z = 1; P(1,1) = 1; for i = 1:M % Operation similar to genD z = conv(PZ,z); Z(i,1:i*mz+1) = z; [t,p] = csort(a,Z(i,:)); P(i+1,:) = p; end disp('The transition matrix is P') disp('To study the evolution of the process, call for branchdbn') PZ = 0.01*[15 45 25 10 5]; % Probability distribution for individuals branchp % Call for procedure Do not forget zero probabilities for missing values of Z Enter PROBABILITIES for individuals PZ Enter maximum allowable population 10 The average individual propagation is 1.45 The transition matrix is P To study the evolution of the process, call for branchdbn disp(P) % Optional display of generated P Columns 1 through 7 1.0000 0 0 0 0 0 0 0.1500 0.4500 0.2500 0.1000 0.0500 0 0 0.0225 0.1350 0.2775 0.2550 0.1675 0.0950 0.0350 0.0034 0.0304 0.1080 0.1991 0.2239 0.1879 0.1293 0.0005 0.0061 0.0307 0.0864 0.1534 0.1910 0.1852 0.0001 0.0011 0.0075 0.0284 0.0702 0.1227 0.1623 0.0000 0.0002 0.0017 0.0079 0.0253 0.0579 0.1003 0.0000 0.0000 0.0003 0.0020 0.0078 0.0222 0.0483 0.0000 0.0000 0.0001 0.0005 0.0021 0.0074 0.0194 0.0000 0.0000 0.0000 0.0001 0.0005 0.0022 0.0068 0.0000 0.0000 0.0000 0.0000 0.0001 0.0006 0.0022 Columns 8 through 11 0 0 0 0 0 0 0 0 0.0100 0.0025 0 0 0.0705 0.0315 0.0119 0.0043 0.1481 0.0987 0.0559 0.0440 0.1730 0.1545 0.1179 0.1625 0.1381 0.1574 0.1528 0.3585 0.0832 0.1179 0.1412 0.5771 0.0406 0.0698 0.1010 0.7591 0.0169 0.0345 0.0590 0.8799 0.0062 0.0147 0.0294 0.9468
Tenga en cuenta que\(p(0, 0) = 1\). Si alguna vez la población llega a cero, se extingue y no se pueden dar más nacimientos. Además, si se alcanza la población máxima (10 en este caso), existe una alta probabilidad de regresar a ese valor y muy pequeña probabilidad de extinguirse (alcanzar el estado cero).
Ejemplo\(\PageIndex{7}\) Inventory problem (continued)
En este caso,
\(g(j, D_{n + 1}) = \begin{cases} \text{max } \{M - D_{n + 1}, 0\} & \text{for } 0 \le j < m \\ \text{max } \{j - D_{n + 1}, 0\} & \text{for } m \le j \le M \end{cases}\)
Ejemplo numérico
\(m = 1\)\(M = 3\)\(D_n\)es Poisson (1)
Para simplificar la escritura, utilice\(D\) para\(D_n\). Debido a la invarianza con\(n\), set
\(P(X_{n + 1} = k|X_n = j) = p(j, k) = P(g(j, D_{n + 1}) = k]\)
Los diversos casos rinden
\(g(0, D) = \text{max } \{3 - D, 0\}\)
\(g(0, D) = 0\)iff\(D \ge 3\) implora\(p(0, 0) = P(D \ge 3)\)
\(g(0, D) = 1\) iff\(D = 2\) implora\(p(0, 1) = P(D = 2)\)
\(g(0, D) = 2\) iff\(D = 1\) implora\(p(0, 2) = P(D = 1)\)
\(g(0, D) = 3\) iff\(D = 0\) imples\(p(0, 3) = P(D = 0)\)
\(g(1, D) = \text{max } \{1 - D, 0\}\)
\(g(1, D) = 0\)iff\(D \ge 1\) implora\(p(1, 0) = P(D \ge 1)\)
\(g(1, D) = 1\) iff\(D = 0\) imples\(p(1, 1) = P(D = 0)\)
\(g(1, D) = 2, 3\) es imposible
\(g(2, D) = \text{max } \{2 - D, 0\}\)
\(g(2, D) = 0\)iff\(D \ge 2\) implora\(p(2, 0) = P(D \ge 2)\)
\(g(2, D) = 1\) iff\(D = 1\) imples\(p(2, 1) = P(D = 1)\)
\(g(2, D) = 2\) iff\(D = 0\) imples\(p(2, 2) = P(D = 0)\)
\(g(2, D) = 3\) es imposible
\(g(3, D) = \text{max } \{3 - D, 0\} = g(0, D)\)para que\(p(3, k) = p(0, k)\)
Las diversas probabilidades para se\(D\) pueden obtener de una tabla (o se pueden calcular fácilmente con cpoisson) para dar la matriz de probabilidad de transición
P =\(\begin{bmatrix} 0.0803 & 0.1839 & 0.3679 & 0.3679 \\ 0.6321 & 0.3679 & 0 & 0 \\ 0.2642 & 0.3679 & 0.3679 & 0 \\ 0.0803 & 0.1839 & 0.3679 & 0.3679 \end{bmatrix}\)
Los cálculos se realizan “a mano” en este caso, para exhibir la naturaleza de los cálculos. Este es un problema estándar en la teoría de inventarios, que involucra costos y recompensas. Se ha escrito un inventario1 de procedimiento m para implementar la función\(g\).
% file inventory1.m % Version of 1/27/97 % Data for transition probability calculations % for (m,M) inventory policy M = input('Enter value M of maximum stock '); m = input('Enter value m of reorder point '); Y = input('Enter row vector of demand values '); PY = input('Enter demand probabilities '); states = 0:M; ms = length(states); my = length(Y); % Calculations for determining P [y,s] = meshgrid(Y,states); T = max(0,M-y).*(s < m) + max(0,s-y).*(s >= m); P = zeros(ms,ms); for i = 1:ms [a,b] = meshgrid(T(i,:),states); P(i,:) = PY*(a==b)'; end P
Consideramos el caso\(M = 5\), el punto de reordenamiento\(m = 3\). y la demanda es Poisson (3). Aproximamos la distribución de Poisson con valores de hasta 20.
inventory1 Enter value M of maximum stock 5 % Maximum stock Enter value m of reorder point 3 % Reorder point Enter row vector of demand values 0:20 % Truncated set of demand values Enter demand probabilities ipoisson(3,0:20) % Demand probabilities P = 0.1847 0.1680 0.2240 0.2240 0.1494 0.0498 0.1847 0.1680 0.2240 0.2240 0.1494 0.0498 0.1847 0.1680 0.2240 0.2240 0.1494 0.0498 0.5768 0.2240 0.1494 0.0498 0 0 0.3528 0.2240 0.2240 0.1494 0.0498 0 0.1847 0.1680 0.2240 0.2240 0.1494 0.0498
Ejemplo\(\PageIndex{8}\) Remaining lifetime (continued)
\(g(0, Y) = Y - 1\), de manera que\(p(0, k) = P(Y - 1 = k) = P(Y = k + 1)\)
\(g(j, Y) = j - 1\)para\(j \ge 1\), para que\(p(j, k) = \delta_{j - 1, k}\) para\(j \ge 1\)
La matriz de probabilidad de transición resultante es
P =\(\begin{bmatrix} p_1 & p_2 & p_3 & \cdot\cdot\cdot \\ 1 & 0 & 0 & \cdot\cdot\cdot \\ 0 & 1 & 0 & \cdot\cdot\cdot \\ \cdot\cdot\cdot & & & \cdot\cdot\cdot \\ \cdot\cdot\cdot \\ \cdot\cdot\cdot & & & \cdot\cdot\cdot \end{bmatrix}\)
La matriz es una matriz infinita, a menos que\(Y\) sea simple. Si el rango de\(Y\) es\(\{1, 2, \cdot\cdot\cdot, M\}\) entonces el espacio de estado E es\(\{0, 1, \cdot\cdot\cdot, M - 1\}\).
Diversas propiedades de independencia condicional, particularmente (CI9), (CI10) y (CI12), pueden ser utilizadas para establecer lo siguiente. El futuro inmediato\(X_{n + 1}\) podrá ser sustituido por cualquier futuro finito\(U_{n, n+p}\) y el presente\(X_n\) puede ser sustituido por cualquier presente extendido\(U_{m,n}\). Algunos resultados de la teoría de medidas abstractas muestran que el futuro finito\(U_{n, n+p}\) puede ser reemplazado por el futuro completo\(U^n\). Así, podemos afirmar
Propiedad extendida de Markov
\(X_N\)es Markov iff
(M*)\(\{U^n, U_m\}\) ci\(|U_{m,n}\)\(\forall 0 \le m \le n\)
— □
La ecuación de Chapman-Kolmogorov y la matriz de transición
Como caso especial de la propiedad extendida de Markov, tenemos
\(\{U^{n + k}, U_n\}\)ci\(|X_{n + k}\) para todos\(n \ge 0\),\(k \ge 1\)
Ajuste\(g(U^{n + k}, X_{n + k}) = X_{n + k + m}\) y\(h(U_n, X_{n + k}) = X_n\) en (CI9), obtenemos
\(\{X_{n + k + m}, X_n\}\)ci\(|X_{n + k}\) para todos\(n \ge 0\),\(k, m \ge 1\)
Se trata de la ecuación de Chapman-Kolmogorov, que juega un papel central en el estudio de las secuencias de Markov. Para un espacio de estado discreto E, con
\(P(X_n = j|X_m = i) = p_{m, n} (i, j)\)
esta ecuación toma la forma
(\(CK'\))\(p_{m, q} (i, k) = \sum_{j \in E} p_{m,n} (i, j) p_{n,q} (j, k)\)\(0 \le m < n < q\)
Para ver que esto es así, considere
\(P(X_q = k|X_m = i) = E[I_{\{k\}} (X_q)|X_m = i] = E\{E[I_{\{k\}} (X_q)|X_n] |X_m = i\}\)
\(= \sum_{j} E[I_{\{k\}} (X_q)|X_n = j] p_{m, n} (i, j) = \sum_{j} p_{n, q} (j, k) p_{m, n} (i, j)\)
Estuche homogéneo
Para este caso, podemos poner (\(CK'\)) en forma de matriz útil. Las probabilidades condicionales\(p^m\) de la forma
\(p^m (i, k) = P(X_{n + m} = k|X_n = i)\)invariante en\(n\)
se conocen como las probabilidades de transición de paso m. La ecuación Chapman-Kolmogorov en este caso se convierte
(\(CK''\))\(p^{m + n} (i, k) = \sum_{j \in E} p^m (i, j) p^n (j, k)\)\(\forall i, j \in\) E
En términos de la matriz de transición de m pasos P\(^{(m)} = [p^m (i, k)]\), este conjunto de sumas es equivalente al producto de la matriz
(\(CK''\)) P\(^{(m + n)}\) = P\(^{(m)}\) P\(^{(n)}\)
Ahora
P\(^{(2)}\) = P\(^{(1)}\) P\(^{(1)}\) = PP = P\(^{2}\), P\(^{(3)}\) = \(^{(2)}\)P P\(^{(1)}\) = P\(^{3}\), etc.
Un simple argumento inductivo basado en (\(CK''\)) establece
La regla del producto para las matrices de transición
La matriz de probabilidad de m -paso P\(^{(m)}\) = P\(^{m}\), la potencia\(m\) th de la matriz de transición P
— □
Ejemplo\(\PageIndex{9}\) The inventory problem (continued)
Para el problema de inventario en el Ejemplo 16.2.7, la matriz de probabilidad de transición de tres pasos P\(^{(3)}\) se obtiene elevando P a la tercera potencia para obtener
P\(^{(3)}\) = P\(^{3}\) =\(\begin{bmatrix} 0.2930 & 0.2917 & 0.2629 & 0.1524 \\ 0.2619 & 0.2730 & 0.2753 & 0.1898 \\ 0.2993 & 0.2854 & 0.2504 & 0.1649 \\ 0.2930 & 0.2917 & 0.2629 & 0.1524 \end{bmatrix}\)
— □
Consideramos a continuación las probabilidades estatales para las distintas etapas. Es decir, examinamos las distribuciones para las diversas\(X_n\), dejando\(p_k (n) = P(X_n = k)\) por cada\(k \in\) E. Para simplificar la escritura, consideramos un espacio de estado finito E =\(\{1, \cdot\cdot\cdot, M\}\), Utilizamos\(\pi(n)\) para la matriz de filas
\(\pi(n) = [p_1 (n) p_2 (n) \cdot\cdot\cdot p_M (n)]\)
Como consecuencia de la regla del producto, tenemos
Distribuciones de probabilidad para cualquier periodo
Para una secuencia homogénea de Markov, la distribución para cualquiera\(X_n\) está determinada por la distribución inicial (es decir, for\(X_0\)) y la matriz de probabilidad de transición P
VERIFICACIÓN
Supongamos que la secuencia homogénea\(X_N\) tiene estado-espacio finito E =\(\{1, 2, \cdot\cdot\cdot, M\}\). Para cualquiera\(n \ge 0\), vamos\(p_j (n) P(X_n = j)\) por cada\(j \in\) E. Poner
\(\pi(n) = [p_1 (n) p_2 (n) \cdot\cdot\cdot p_M (n)]\)
Entonces
\(\pi(0) =\)la distribución inicial de probabilidad
\(\pi(1) = \pi(0)\) P
...
\(\pi(n) = \pi(n - 1)\)P =\(\pi(0)\) P\(^{(n)} = \pi (0)\) P\(^{n}\) = la distribución\(n\) del periodo th
La última expresión es una consecuencia inmediata de la regla del producto.
Ejemplo\(\PageIndex{10}\) Inventory problem (continued)
En el sistema de inventario para los Ejemplos 3, 7 y 9, supongamos que el stock inicial es\(M = 3\). Esto significa que
\(\pi (0) =\)[0 0 0 1]
El producto de\(\pi (0)\) y\(P^3\) es la cuarta fila de\(P^3\), por lo que la distribución para\(X_3\) es
\(\pi(3) = [p_0 (3)\ \ p_1 (3)\ \ p_2 (3)\ \ p_3 (3)] = [0.2930\ \ 0.2917\ \ 0.2629\ \ 0.1524]\)
Así, dado un stock de\(M = 3\) al inicio, la probabilidad es de 0.2917 eso\(X_3 = 1\). Esta es la probabilidad de una unidad en stock al final del periodo número tres.
Observaciones
- Un tratamiento similar muestra que para el caso no homogéneo la distribución en cualquier etapa está determinada por la distribución inicial y la clase de matrices de transición de un solo paso. En el caso no homogéneo, las probabilidades de transición\(p_{n, n+1} (i, j)\) dependen de la etapa\(n\).
- Un proceso de Markov de parámetros discretos, o secuencia de Markov, se caracteriza por el hecho\(X_{n + 1}\) de que cada miembro de la secuencia está condicionado por el valor del miembro anterior de la secuencia. Este enlace estocástico de un solo paso ha hecho costumbre referirse a una secuencia de Markov como una cadena de Markov. En el caso de Markov con parámetros discretos, usamos los términos proceso, secuencia o cadena indistintamente.
El diagrama de transición y la matriz de transición
Los ejemplos anteriores sugieren que una cadena de Markov es un sistema dinámico, evolucionando en el tiempo. Por otro lado, el comportamiento estocástico de una cadena homogénea está determinado completamente por la distribución de probabilidad para el estado inicial y las probabilidades de transición de un solo paso\(p(i, j)\) tal como se presentan en la matriz de transición P. La matriz de transición invariable en el tiempo puede transmitir una impresión estática del sistema. Sin embargo, una representación geométrica simple, conocida como diagrama de transición, permite vincular la estructura inmutable, representada por la matriz de transición, con la dinámica del comportamiento del sistema en evolución.
Definición
Un diagrama de transición para una cadena homogénea de Markov es un gráfico lineal con un nodo para cada estado y un borde dirigido para cada posible transición de un paso entre estados (nodos).
Ignoramos, como esencialmente imposible, cualquier transición que tenga una probabilidad de transición cero. Así, los bordes en el diagrama corresponden a probabilidades positivas de transición de un paso entre los nodos conectados. Ya que para algún par\((i, j)\) de estados, podemos tener\(p(i, j) > 0\) pero\(p(j, i) = 0\) podemos tener un borde de conexión entre dos nodos en una dirección, pero ninguno en la otra. El sistema puede ser visto como un objeto saltando de estado a estado (nodo a nodo) en los sucesivos tiempos de transición. A medida que seguimos la trayectoria de este objeto, logramos un sentido de la evolución del sistema.
Ejemplo\(\PageIndex{11}\) Transition diagram for inventory example
Consideremos, nuevamente, la matriz de transición P para el problema de inventario (redondeada a tres decimales).
P =\(\begin{bmatrix} 0.080 & 0.184 & 0.368 & 0.368 \\ 0.632 & 0.368 & 0 & 0 \\ 0.264 & 0.368 & 0.368 & 0 \\ 0.080 & 0.184 & 0.368 & 0.368 \end{bmatrix}\)
La Figura 16.2.1 muestra el diagrama de transición para este sistema. En cada nodo correspondiente a uno de los estados posibles, se muestra el valor de estado. En este ejemplo, el valor de estado es uno menor que el número de estado. Por conveniencia, nos referimos al nodo para estado\(k + 1\). que tiene valor de estado\(k\), como nodo\(k\). Si el valor del estado es cero, existen cuatro posibilidades: permanecer en esa condición con probabilidad 0.080; moverse al nodo 1 con probabilidad 0.184; moverse al nodo 2 con probabilidad 0.368; o pasar al nodo 3 con probabilidad 0.368. Estos están representados por el “self loop” y un borde dirigido a cada uno de los nodos que representan estados. Cada uno de estos bordes dirigidos se marca con la probabilidad de transición (condicional). Por otro lado, las probabilidades de alcanzar el valor de estado 0 de cada uno de los otros se representan por bordes dirigidos al nodo para el valor de estado 0. Una situación similar se mantiene para cada otro nodo. Tenga en cuenta que las probabilidades en los bordes que dejan un nodo (incluyendo un bucle propio) deben ser totales a uno, ya que éstas corresponden a la distribución de probabilidad de transición de ese nodo. No hay borde dirigido desde el nodo 2 al nodo 3, ya que la probabilidad de una transición del valor 2 al valor 3 es cero. De manera similar, no hay borde dirigido desde el nodo 1 al nodo 2 o al nodo 3.
Figura 16.2.1. Diagrama de transición para el sistema de inventario del Ejemplo 16.2.11
Existe una relación uno-uno entre el diagrama de transición y la matriz de transición P. El diagrama de transición no solo ayuda a visualizar la evolución dinámica de una cadena, sino que también muestra ciertas propiedades estructurales. A menudo, una cadena puede descomponerse útilmente en subcadenas. Las preguntas de comunicación y recurrencia pueden ser respondidas en términos del diagrama de transición. Algunos subconjuntos de estados están esencialmente cerrados, en el sentido de que si el sistema llega a cualquier estado en el subconjunto nunca podrá alcanzar un estado fuera del subconjunto. A veces se pueden ver periodicidades, aunque suele ser más fácil usar el diagrama para mostrar que las periodicidades no pueden ocurrir.
Clasificación de estados
Muchas características importantes de una cadena de Markov se pueden estudiar considerando el número de visitas a un estado arbitrariamente elegido, pero fijo.
Definición
Para un estado fijo\(j\), vamos
\(T_1\)= el tiempo (número de etapa) de la primera visita al estado\(j\) (después del periodo inicial).
\(F_{k} (i, j) = P(T_i = k|X_0 = i)\), la probabilidad de alcanzar estado\(j\) por primera vez a partir del estado\(i\) en\(k\) pasos.
\(F(i, j) = P(T_i < \infty|X_0 = i) = \sum_{k = 1}^{\infty} F_k (i, j)\), la probabilidad de llegar alguna vez al estado\(j\) desde el estado\(i\).
Se pueden desarrollar una serie de teoremas importantes para\(F_k\) y\(F\), aunque no los desarrollamos en este tratamiento. Simplemente los citamos según sea necesario. Se hace una clasificación importante de los estados en términos de\(F\).
Definición
Estado\(j\) se dice que es transitorio iff\(F(j, j) < 1\),
y se dice que es recurrente iff\(F(j, j) = 1\).
Observación. Si el espacio de estados E es infinito, los estados recurrentes caen en una de dos subclases: positiva o nula. Solo el caso positivo es común en el caso infinito, y ese es el único caso posible para sistemas con espacio de estado finito.
A veces hay una regularidad en la estructura de una secuencia de Markov que da como resultado periodicidades.
Definición
Para el estado\(j\), vamos
\(\delta = \text{greatest common denominatior of } \{n: p^n (j, j) > 0\}\)
Si\(\delta > 1\), entonces el estado\(j\) es periódico con periodo\(\delta\); de lo contrario, el estado\(j\) es aperiódico.
Por lo general, si hay algún bucle propio en el diagrama de transición (probabilidades positivas en la diagonal de la matriz de transición P) el sistema es aperiódico. A menos que se indique lo contrario, limitamos la consideración al caso aperiódico.
Definición
Un estado\(j\) se llama ergódica si es positivo, recurrente y aperiódico.
Se llama iff absorbente\(F(j, j) = 1\).
Un estado recurrente es aquel al que finalmente regresa el sistema, de ahí que se visite infinidad de veces. Si está absorbiendo, entonces una vez que se alcanza devuelve cada paso (es decir, nunca se va).
Se utiliza una notación de flecha para indicar relaciones importantes entre estados.
Definición
Nosotros decimos
Estado\(i\) alcanza\(j\), denotado\(i \to j\), iff\(p^n (i, j) > 0\) para algunos\(n > 0\).
Estado\(i\) y\(j\) comunicar, denotado\(i \leftrightarrow j\) iff tanto\(i\) alcances\(j\) como\(j\) alcances\(i\).
Al incluir\(j\) alcances\(j\) en todos los casos, la relación\(\leftrightarrow\) es una relación de equivalencia (es decir, es reflexiva, transitiva e idempotente). Con esta relación, podemos definir clases importantes.
Definición
Una clase de estados se está comunicando si cada estado de la clase puede ser alcanzado desde cualquier otro estado en la clase (es decir, cada par se comunica). Una clase se cierra si no se puede llegar a ningún estado fuera de la clase desde dentro de la clase.
Las siguientes condiciones importantes son intuitivas y pueden establecerse rigurosamente:
\(i \leftrightarrow j\)implica\(i\) es recurrente si\(j\) es recurrente
\(i \to j\) y\(i\) recurrente implica\(i \leftrightarrow j\)
\(i \to j\) y\(i\) recurrente implica\(j\) recurrente
Teoremas de límite para secuencias de espacio de estado finito
Se pueden establecer las siguientes proposiciones para las secuencias de Markov con espacio de estado finito:
- No hay estados nulos, y no todos los estados son transitorios.
- Si una clase de estados es irreducible (es decir, no tiene subconjuntos cerrados adecuados), entonces
- Todos los estados son recurrentes
- Todos los estados son aperiódicos o todos son periódicos con el mismo periodo.
- Si una clase C es cerrada, irreducible, e i es un estado transitorio (necesariamente no en\(C\)).
entonces\(F(i, j) = F(i, k)\) para todos\(j, k \in C\)
Un teorema de límite
Si los estados en una cadena de Markov son ergódicos (es decir, positivos, recurrentes, aperiódicos), entonces
\(\text{lim}_{n} p^n (i, j) = \pi_j > 0\)\(\sum_{j = 1}^{M} \pi_j = 1\)\(\pi_j = \sum_{i = 1}^{M} \pi_i p(i, j)\)
Si, como arriba, dejamos
\(\pi (n) = [p_1 (n)\ p_2(n) \cdot\cdot\cdot p_M (n)]\)para que\(\pi (n) = \pi (0)\) P\(^{n}\)
el resultado anterior puede ser escrito
\(\pi (n) = \pi (0)\)P\(^{n}\)\(\to\)\(\pi (0)\) P\(_{0}\)
donde
P\(_{0}\) =\(\begin{bmatrix} \pi_1 & \pi_2 & \cdot\cdot\cdot & \pi_m \\ \pi_1 & \pi_2 & \cdot\cdot\cdot & \pi_m \\ \cdot\cdot\cdot & \cdot\cdot\cdot & \cdot\cdot\cdot & \cdot\cdot\cdot \\ \pi_1 & \pi_2 & \cdot\cdot\cdot & \pi_m \end{bmatrix}\)
Cada fila de P\(_0 = \text{lim}_n\) P\(^n\) es la distribución a largo plazo\(\pi = \text{lim}_n \pi (n)\).
Definición
Una distribución es estacionaria iff
\(\pi = \pi\)P
El resultado anterior puede afirmarse diciendo que la distribución a largo plazo es la distribución estacionaria. Un análisis de función generadora muestra que la convergencia es exponencial en el siguiente sentido
| P\(^n\) - P\(_0\) |\(\le\)\(\alpha |\lambda|^n\)
donde\(|\lambda|\) es el mayor valor absoluto de los valores propios para P distintos de\(\lambda = 1\).
Ejemplo\(\PageIndex{12}\) The long run distribution for the inventory example
Utilizamos MATLAB para verificar los valores propios para la probabilidad de transición P y para obtener potencias crecientes de P. El proceso de convergencia es fácilmente evidente.
P = 0.0803 0.1839 0.3679 0.3679 0.6321 0.3679 0 0 0.2642 0.3679 0.3679 0 0.0803 0.1839 0.3679 0.3679 E = abs(eig(P)) E = 1.0000 0.2602 0.2602 0.0000 format long N = E(2).^[4 8 12] N = 0.00458242348096 0.00002099860496 0.00000009622450 >> P4 = P^4 P4 = 0.28958568915950 0.28593792666752 0.26059678211310 0.16387960205989 0.28156644866011 0.28479107531968 0.26746979455342 0.16617268146679 0.28385952806702 0.28250048636032 0.26288737107246 0.17075261450021 0.28958568915950 0.28593792666752 0.26059678211310 0.16387960205989 >> P8 = P^8 P8 = 0.28580046500309 0.28471421248816 0.26315895715219 0.16632636535655 0.28577030590344 0.28469190218618 0.26316681807503 0.16637097383535 0.28581491438224 0.28471028095839 0.26314057837998 0.16633422627939 0.28580046500309 0.28471421248816 0.26315895715219 0.16632636535655 >> P12 = P^12 P12 = 0.28579560683438 0.28470680858266 0.26315641543927 0.16634116914369 0.28579574073314 0.28470680714781 0.26315628010643 0.16634117201261 0.28579574360207 0.28470687626748 0.26315634631961 0.16634103381085 0.28579560683438 0.28470680858266 0.26315641543927 0.16634116914369 >> error4 = max(max(abs(P^16 - P4))) % Use P^16 for P_0 error4 = 0.00441148012334 % Compare with 0.0045824... >> error8 = max(max(abs(P^16 - P8))) error8 = 2.984007206519035e-05 % Compare with 0.00002099 >> error12 = max(max(abs(P^16 - P12))) error12 = 1.005660185959822e-07 % Compare with 0.00000009622450
El proceso de convergencia es claro, y el acuerdo con el error se acerca a lo previsto. No hemos determinado el factor\(a\), y hemos aproximado la matriz de largo plazo\(P_0\) con\(P^{16}\). Esto exhibe un criterio práctico para una convergencia suficiente. Si las filas de\(P^n\) acuerdan dentro de una precisión aceptable, entonces\(n\) es suficientemente grande. Por ejemplo, si consideramos suficiente el acuerdo con cuatro decimales, entonces
P10 = P^10 P10 = 0.2858 0.2847 0.2632 0.1663 0.2858 0.2847 0.2632 0.1663 0.2858 0.2847 0.2632 0.1663 0.2858 0.2847 0.2632 0.1663
muestra que\(n = 10\) es bastante suficiente.
Simulación de secuencias finitas homogéneas de Markov
En la sección, "La función cuantil", la función cuantil se utiliza con un generador de números aleatorios para obtener una muestra aleatoria simple a partir de una distribución poblacional dada. En esta sección, adaptamos ese procedimiento al problema de simular una trayectoria para secuencias homogéneas de Markov con espacio de estado finito.
Elementos y terminología
- Estados y números estatales. Suponemos que hay m estados, generalmente llevando un valor numérico. Para fines de análisis y simulación, numeramos los estados del 1 al m. El cálculo se lleva a cabo con números de estado; si se desea, estos pueden traducirse a los valores de estado reales después de que se complete el cálculo.
- Etapas, transiciones, números de periodo, trayectorias y tiempo. Usamos el término etapa y periodo indistintamente. Se acostumbra numerar los periodos o etapas comenzando con cero para la etapa inicial. El número de periodo es el número de transiciones para llegar a esa etapa desde la inicial. Se requieren transiciones cero para alcanzar la etapa original (periodo cero), una transición para alcanzar la siguiente (periodo uno), dos transiciones para alcanzar el periodo dos, etc. llamamos a la secuencia de estados encontrados a medida que el sistema evoluciona una trayectoria o una cadena. También se utilizan en la literatura los términos “ruta muestral” o “realización del proceso”. Ahora bien, si los periodos son de igual duración, el número de transiciones es una medida del tiempo transcurrido desde que se originó la cadena. Nos resulta conveniente referirnos al tiempo de esta manera. En\(k\) el momento la cadena ha alcanzado el periodo numerado\(k\). La trayectoria es de\(k + 1\) etapas largas, por lo que el número de tiempo o periodo es uno menos que el número de etapas.
- La matriz de transición y las distribuciones de transición. Para cada estado, existe una distribución de probabilidad de transición condicional para el siguiente estado. Estos están dispuestos en una matriz de transición. La fila\(i\) th consiste en la distribución de transición para seleccionar el estado del siguiente periodo cuando el número de estado actual es\(i\). \(P\)Por lo tanto, la matriz de transición tiene elementos no negativos, con cada fila sumando a uno. Tal matriz se conoce como matriz estocástica.
La estrategia fundamental de simulación
- Una estrategia fundamental para el muestreo de una distribución poblacional dada se desarrolla en la unidad sobre la Función Cuantil. Si\(Q\) es la función cuantil para la distribución poblacional y\(U\) es una variable aleatoria distribuida uniformemente en el intervalo [0, 1], entonces\(X = Q(U)\) tiene la distribución deseada. Para obtener una muestra a partir de la distribución uniforme utilice un generador de números aleatorios. Esta muestra es “transformada” por la función cuantil en una muestra de la distribución deseada.
- Para una cadena homogénea, si estamos en estado\(k\), tenemos una distribución para seleccionar el siguiente estado. Si usamos la función quantile para esa distribución y un número producido por un generador de números aleatorios, hacemos una selección del siguiente estado basado en esa distribución. Una sucesión de estas elecciones, con la selección del siguiente estado realizada en cada caso a partir de la distribución para el estado actual, constituye una simulación válida de una trayectoria.
Horarios de llegada y tiempos de recurrencia
La simulación básica produce una o más trayectorias de una longitud especificada. A veces nos interesa continuar hasta la primera llegada a (o visitar) un estado objetivo específico o cualquiera de un conjunto de estados objetivo. El tiempo (en transiciones) para alcanzar un estado objetivo es uno menos que el número de etapas en la trayectoria que comienza con el estado inicial y termina con el estado objetivo alcanzado.
- Si el estado inicial no está en el objetivo establecido, hablamos de la hora de llegada.
- Si el estado inicial está en el conjunto objetivo, la hora de llegada sería cero. En este caso, no nos detenemos en cero sino que continuamos hasta la siguiente visita a un estado objetivo (posiblemente el mismo que el estado inicial). Llamamos al número de transiciones en este caso el tiempo de recurrencia.
- En algunos casos, puede ser conveniente conocer el tiempo para completar las visitas a un número prescrito de los estados objetivo. Nuevamente hay una elección de tratamiento en el caso de que el conjunto inicial esté en el conjunto objetivo.
Archivos de datos
Para el uso de MATLAB en simulación, nos resulta conveniente organizar los datos adecuados en un archivo m.
- En todos los casos, necesitamos la matriz de transición\(P\). Su tamaño indica el número de estados (digamos por la longitud de cualquier fila o columna).
- Si los estados van a tener valores distintos de los números de estado, estos pueden incluirse en el archivo de datos, aunque pueden agregarse posteriormente, en respuesta a un prompt.
- Si se van a producir trayectorias largas, puede ser deseable determinar la fracción de veces que se realiza cada estado. Una comparación con las probabilidades a largo plazo para la cadena puede ser de interés. En este caso, el archivo de datos puede contener la distribución de probabilidad a largo plazo. Por lo general, esto se obtiene tomando una fila de una potencia suficientemente grande de la matriz de transición. Esta operación se puede realizar después de que se llame al archivo de datos pero antes de que comience el procedimiento de simulación.
A continuación se muestra un archivo de datos de ejemplo utilizado para ilustrar los diversos procedimientos. Estos datos fueron generados artificialmente y no tienen interpretaciones obvias en términos de sistemas específicos a modelar. Sin embargo, son lo suficientemente complejos como para proporcionar ilustraciones no triviales de los procedimientos de simulación.
% file markovp1.m % Artificial data for a Markov chain, used to % illustrate the operation of the simulation procedures. P = [0.050 0.011 0.155 0.155 0.213 0.087 0.119 0.190 0.008 0.012 0.103 0.131 0.002 0.075 0.013 0.081 0.134 0.115 0.181 0.165 0.103 0.018 0.128 0.081 0.137 0.180 0.149 0.051 0.009 0.144 0.051 0.098 0.118 0.154 0.057 0.039 0.153 0.112 0.117 0.101 0.016 0.143 0.200 0.062 0.099 0.175 0.108 0.054 0.062 0.081 0.029 0.085 0.156 0.158 0.011 0.156 0.088 0.090 0.055 0.172 0.110 0.059 0.020 0.212 0.016 0.113 0.086 0.062 0.204 0.118 0.084 0.171 0.009 0.138 0.140 0.150 0.023 0.003 0.125 0.157 0.105 0.123 0.121 0.167 0.149 0.040 0.051 0.059 0.086 0.099 0.192 0.093 0.191 0.061 0.094 0.123 0.106 0.065 0.040 0.035]; states = 10:3:37; PI = [0.0849 0.0905 0.1125 0.1268 0.0883 0.1141 ... 0.1049 0.0806 0.0881 0.1093]; % Long-run distribution
El mayor valor absoluto de los valores propios (distintos de uno) es 0.1716. Ya que\(0.1716^{16} \approx 5.6 \cdot 10^{-13}\), tomamos cualquier fila de\(P^{16}\) como las probabilidades a largo plazo. Estos se incluyen en la matriz PI en el archivo m, arriba. Los ejemplos para los diversos procedimientos a continuación utilizan este conjunto de datos artificiales, ya que el propósito es ilustrar el funcionamiento de los procedimientos.
La configuración y los m-procedimientos de generación
El juego de cadenas de procedimiento m se configura para la simulación de cadenas de Markov. Solicita la entrada de la matriz de transición P, los estados (si es diferente de los números de estado), la distribución a largo plazo (si está disponible) y el conjunto de estados objetivo si se desea obtener tiempos de llegada o recurrencia. El procedimiento determina el número de estados a partir del tamaño de P y calcula la información necesaria para la función cuantil. A continuación, solicita una convocatoria para uno de los procedimientos generadores.
El mchain del procedimiento m, al igual que los demás procedimientos de generación a continuación, asume que se ha ejecutado chainset, de manera que los datos de uso común están disponibles en la forma apropiada. El procedimiento solicita el número de etapas (longitud de la trayectoria a formar) y para el estado inicial. Cuando se produce la trayectoria, se muestran los diversos estados en la trayectoria y la fracción o frecuencia relativa de cada uno. Si la distribución de largo plazo ha sido suministrada por el juego de cadenas, esta distribución se incluye para su comparación. En los ejemplos a continuación, reiniciamos el generador de números aleatorios (establecemos la “semilla” a cero) para fines de comparación. Sin embargo, en la práctica, puede ser deseable hacer varias corridas sin resetear la semilla, para permitir una mayor “aleatoriedad” efectiva.
Ejemplo\(\PageIndex{13}\)
markovp1 % Call for data chainset % Call for setup procedure Enter the transition matrix P Enter the states if not 1:ms states % Enter the states States are 1 10 2 13 3 16 4 19 5 22 6 25 7 28 8 31 9 34 10 37 Enter the long-run probabilities PI % Enter the long-run distribution Enter the set of target states [16 22 25] % Not used with mchain Call for for appropriate chain generating procedure rand('seed',0) mchain % Call for generating procedure Enter the number n of stages 10000 % Note the trajectory length Enter the initial state 16 State Frac P0 % Statistics on the trajectory 10.0000 0.0812 0.0849 13.0000 0.0952 0.0905 16.0000 0.1106 0.1125 19.0000 0.1226 0.1268 22.0000 0.0880 0.0883 25.0000 0.1180 0.1141 28.0000 0.1034 0.1049 31.0000 0.0814 0.0806 34.0000 0.0849 0.0881 37.0000 0.1147 0.1093 To view the first part of the trajectory of states, call for TR disp(TR') 0 1 2 3 4 5 6 7 8 9 10 16 16 10 28 34 37 16 25 37 10 13
El hecho de que las fracciones o frecuencias relativas se aproximen a las probabilidades a largo plazo es una expresión de una propiedad límite fundamental de la teoría de la probabilidad. Esta propiedad límite, que requiere una técnica algo sofisticada para establecer, justifica una interpretación de frecuencia relativa de la probabilidad.
La llegada del procedimiento asume la configuración proporcionada por el juego de cadenas, incluyendo un conjunto\(E\) de estados objetivo. El procedimiento solicita el número r de repeticiones y el estado inicial. Luego produce\(r\) trayectorias sucesivas, cada una comenzando con el estado inicial prescrito y terminando en uno de los estados objetivo. Los horarios de llegada varían de una carrera a otra. Diversas estadísticas son calculadas y mostradas o puestas a disposición. En el caso de ejecución única (\(r = 1\)), se puede mostrar la trayectoria. Se puede utilizar un procedimiento auxiliar plotdbn en el caso multirun para trazar la distribución de los tiempos de llegada.
Ejemplo\(\PageIndex{14}\) Arrival time to a target set of states
rand('seed',0) arrival % Assumes chainset has been run, as above Enter the number of repetitions 1 % Single run case The target state set is: 16 22 25 Enter the initial state 34 % Specified initial state The arrival time is 6 % Data on trajectory The state reached is 16 To view the trajectory of states, call for TR disp(TR') % Optional call to view trajectory 0 1 2 3 4 5 6 34 13 10 28 34 37 16 rand('seed',0) arrival Enter the number of repetitions 1000 % Call for 1000 repetitions The target state set is: 16 22 25 Enter the initial state 34 % Specified initial state The result of 1000 repetitions is: % Run data (see optional calls below) Term state Rel Freq Av time 16.0000 0.3310 3.3021 22.0000 0.3840 3.2448 25.0000 0.2850 4.3895 The average arrival time is 3.59 The standard deviation is 3.207 The minimum arrival time is 1 The maximum arrival time is 23 To view the distribution of arrival times, call for dbn To plot the arrival time distribution, call for plotdbn plotdbn % See Figure 16.2.2
Figura 16.2.2. Distribución del tiempo para el Ejemplo 16.2.14
Sería difícil establecer analíticamente estimaciones de los tiempos de llegada. El procedimiento de simulación da una “sensación” razonable para estos tiempos y cómo varían.
La recurrencia del procedimiento es similar a la llegada del procedimiento. Si el estado inicial no está en el conjunto de objetivos, se comporta como lo hace la llegada del procedimiento y se detiene en la primera visita al conjunto objetivo. No obstante, si el estado inicial está en el conjunto objetivo, los procedimientos son diferentes. La llegada del procedimiento se detiene con cero transiciones, ya que siente que ha “llegado”. Normalmente nos interesa tener al menos una transición, de vuelta al mismo estado o a otro estado en el conjunto de objetivos. A estos tiempos los llamamos tiempos de recurrencia.
Ejemplo\(\PageIndex{15}\)
rand('seed',0) recurrence Enter the number of repititions 1 The target state set is: 16 22 25 Enter the initial state 22
Figura 16.2.3. Distribución del tiempo de transición para el Ejemplo 16.2.15
The recurrence time is 1 The state reached is 16 To view the trajectory of state numbers, call for TR disp(TR') 0 1 22 16 recurrence Enter the number of repititions 1000 The target state set is: 16 22 25 Enter the initial state 25 The result of 1000 repetitions is: Term state Rel Freq Av time 16.0000 0.3680 2.8723 22.0000 0.2120 4.6745 25.0000 0.4200 3.1690 The average recurrence time is 3.379 The standard deviation is 3.0902 The minimum recurrence time is 1 The maximum recurrence time is 20 To view the distribution of recurrence times, call for dbn To plot the recurrence time distribution, call for plotdbn % See Figure 16.2.3
El procedimiento kvis se detiene cuando se visita un número designado\(k\) de estados. Si\(k\) es mayor que el número de estados objetivo, o si\(k\) se designa no, el procedimiento se detiene cuando todos han sido visitados. Porque\(k = 1\), el comportamiento es el mismo que la llegada. No obstante, ese caso es mejor manejado por la llegada del procedimiento, que proporciona más estadísticas sobre los resultados.
Ejemplo\(\PageIndex{16}\)
rand('seed',0) kvis % Assumes chainset has been run Enter the number of repetitions 1 The target state set is: 16 22 25 Enter the number of target states to visit 2 Enter the initial state 34 The time for completion is 7 To view the trajectory of states, call for TR disp(TR') 0 1 2 3 4 5 6 7 34 13 10 28 34 37 16 25 rand('seed',0) kvis Enter the number of repetitions 100 The target state set is: 16 22 25 Enter the number of target states to visit % Default-- visit all three Enter the initial state 31 The average completion time is 17.57 The standard deviation is 8.783 The minimum completion time is 5 The maximum completion time is 42 To view a detailed count, call for D. The first column shows the various completion times; the second column shows the numbers of trials yielding those times
El primer objetivo de esta introducción algo superficial a los procesos de Markov es proporcionar un entorno general que permita conocer el carácter esencial y la estructura de dichos sistemas. El importante caso de cadenas homogéneas se introduce de tal manera que su estructura algebraica aparece como consecuencia lógica de la propiedad de Markov. La teoría general se utiliza para obtener algunas herramientas para formular cadenas homogéneas en casos prácticos. Algunas herramientas de MATLAB para estudiar su comportamiento se aplican a un ejemplo artificial, lo que demuestra su utilidad general en el estudio de muchos problemas prácticos aplicados.