Método analítico matricial

Técnica de cálculo en teoría de la probabilidad

En teoría de probabilidad , el método analítico matricial es una técnica para calcular la distribución de probabilidad estacionaria de una cadena de Markov que tiene una estructura repetitiva (después de cierto punto) y un espacio de estados que crece ilimitadamente en no más de una dimensión. ^{[1] [2]} Estos modelos a menudo se describen como cadenas de Markov de tipo M/G/1 porque pueden describir transiciones en una cola M/G/1. ^{[3] [4]} El método es una versión más complicada del método geométrico matricial y es el método de solución clásico para cadenas M/G/1. ^[5]

Descripción del método

Una matriz estocástica de tipo M/G/1 es una de la forma ^[3]

${\displaystyle P={\begin{pmatrix}B_{0}&B_{1}&B_{2}&B_{3}&\cdots \\A_{0}&A_{1}&A_{2}&A_{3}&\cdots \\&A_{0}&A_{1}&A_{2}&\cdots \\&&A_{0}&A_{1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}$

donde B _i y A _i son matrices k  ×  k . (Tenga en cuenta que las entradas de matriz sin marcar representan ceros). Una matriz de este tipo describe la cadena de Markov incrustada en una cola M/G/1. ^{[6] [7]} Si P es irreducible ^{[ ancla rota ]} y recurrente positiva , entonces la distribución estacionaria está dada por la solución de las ecuaciones ^[3]

${\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1}$

donde e representa un vector de dimensión adecuada con todos los valores iguales a 1. Coincidiendo con la estructura de P , π se divide en π ₁ , π ₂ , π ₃ , …. Para calcular estas probabilidades, se calcula la matriz estocástica de columnas G de modo que ^[3]

${\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}$

G se denomina matriz auxiliar. ^[8] Las matrices se definen ^[3]

${\displaystyle {\begin{aligned}{\overline {A}}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\\{\overline {B}}_{i}&=\sum _{j=i}^{\infty }G^{j-i}B_{j}\end{aligned}}}$

entonces π ₀ se encuentra resolviendo ^[3]

${\displaystyle {\begin{aligned}{\overline {B}}_{0}\pi _{0}&=\pi _{0}\\\quad \left(\mathbf {e} ^{\text{T}}+\mathbf {e} ^{\text{T}}\left(I-\sum _{i=1}^{\infty }{\overline {A}}_{i}\right)^{-1}\sum _{i=1}^{\infty }{\overline {B}}_{i}\right)\pi _{0}&=1\end{aligned}}}$

y los π _i se dan por la fórmula de Ramaswami , ^[3] una relación numéricamente estable publicada por primera vez por Vaidyanathan Ramaswami en 1988. ^[9]

${\displaystyle \pi _{i}=(I-{\overline {A}}_{1})^{-1}\left[{\overline {B}}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}}_{i+1-j}\pi _{j}\right],i\geq 1.}$

Cálculo deGRAMO

Hay dos métodos iterativos populares para calcular G , ^{[10] [11]}

• iteraciones funcionales
• reducción cíclica .

Herramientas

• Solución MAMSolver ^[12]

Referencias

1. Harchol-Balter, M. (2012). "Distribuciones de tipo fase y métodos de análisis matriciales". Modelado y diseño de rendimiento de sistemas informáticos . págs. 359–379. doi :10.1017/CBO9781139226424.028. ISBN . 9781139226424.
2. Neuts, MF (1984). "Métodos de análisis matricial en la teoría de colas". Revista Europea de Investigación Operativa . 15 : 2–12. doi :10.1016/0377-2217(84)90034-1.
3. Meini, B. (1997). "Una versión mejorada basada en FFT de la fórmula de Ramaswami". Comunicaciones en Estadística. Modelos Estocásticos . 13 (2): 223–238. doi :10.1080/15326349708807423.
4. Stathopoulos, A.; Riska, A.; Hua, Z.; Smirni, E. (2005). "Uniendo la fórmula de ETAQA y Ramaswami para la solución de procesos tipo M/G/1". Evaluación de Desempeño . 62 (1–4): 331–348. CiteSeerX 10.1.1.80.9473 . doi :10.1016/j.peva.2005.07.003. 
5. Riska, A.; Smirni, E. (2002). "Procesos de Markov de tipo M/G/1: un tutorial" (PDF) . Evaluación del rendimiento de sistemas complejos: técnicas y herramientas . Apuntes de clase en informática. Vol. 2459. págs. 36. doi :10.1007/3-540-45798-4_3. ISBN 978-3-540-44252-3.
6. Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Redes de colas y cadenas de Markov: modelado y evaluación del rendimiento con aplicaciones informáticas (2.ª ed.). John Wiley & Sons, Inc., pág. 250. ISBN 978-0471565253.
7. Artalejo, Jesús R.; Gómez-Corral, Antonio (2008). "El formalismo analítico matricial". Sistemas de colas de nuevo juicio . págs. 187-205. doi :10.1007/978-3-540-78725-9_7. ISBN 978-3-540-78724-2.
8. Riska, A.; Smirni, E. (2002). "Soluciones agregadas exactas para procesos de Markov de tipo M/G/1". Revisión de evaluación del desempeño de ACM SIGMETRICS . 30 : 86. CiteSeerX 10.1.1.109.2225 . doi :10.1145/511399.511346. 
9. Ramaswami, V. (1988). "Una recursión estable para el vector de estado estacionario en cadenas de Markov de tipo m/g/1". Comunicaciones en Estadística. Modelos Estocásticos . 4 : 183–188. doi :10.1080/15326348808807077.
10. Bini, DA; Latouche, G.; Meini, B. (2005). Métodos numéricos para cadenas de Markov estructuradas . doi :10.1093/acprof:oso/9780198527688.001.0001. ISBN 9780198527688.
11. Meini, B. (1998). "Resolución de cadenas de Markov de tipo m/g/l: avances y aplicaciones recientes". Communications in Statistics. Modelos estocásticos . 14 (1–2): 479–496. doi :10.1080/15326349808807483.
12. Riska, A.; Smirni, E. (2002). "MAMSolver: una herramienta de métodos analíticos de matrices". Evaluación del rendimiento informático: técnicas y herramientas de modelado . Apuntes de clase en informática. Vol. 2324. pág. 205. CiteSeerX 10.1.1.146.2080 . doi :10.1007/3-540-46029-2_14. ISBN .  978-3-540-43539-6.