Solución de forma de producto

Forma de solución en la teoría de la probabilidad

En teoría de probabilidad , una solución en forma de producto es una forma particularmente eficiente de solución para determinar alguna métrica de un sistema con subcomponentes distintos, donde la métrica para el conjunto de componentes se puede escribir como un producto de la métrica a lo largo de los diferentes componentes. Usando la notación Pi mayúscula, una solución en forma de producto tiene forma algebraica

${\displaystyle {\text{P}}(x_{1},x_{2},x_{3},\ldots ,x_{n})=B\prod _{i=1}^{n}{\text{P}}(x_{i})}$

donde B es una constante. Las soluciones de esta forma son interesantes porque su evaluación para valores grandes de n es económica desde el punto de vista computacional . Estas soluciones en redes de colas son importantes para encontrar métricas de rendimiento en modelos de sistemas informáticos multiprogramados y de tiempo compartido.

Distribuciones de equilibrio

Las primeras soluciones en forma de producto se encontraron para distribuciones de equilibrio de cadenas de Markov . Trivialmente, los modelos compuestos de dos o más subcomponentes independientes exhiben una solución en forma de producto por la definición de independencia. Inicialmente, el término se utilizó en redes de colas donde los subcomponentes serían colas individuales. Por ejemplo, el teorema de Jackson da la distribución de equilibrio conjunta de una red de colas abierta como el producto de las distribuciones de equilibrio de las colas individuales. ^[1] Después de numerosas extensiones, principalmente la red BCMP, se pensó que el equilibrio local era un requisito para una solución en forma de producto. ^{[2] [3]}

El modelo de red G de Gelenbe fue el primero en demostrar que esto no es así. Motivado por la necesidad de modelar neuronas biológicas que tienen un comportamiento de picos similar al de un proceso puntual, introdujo el precursor de las redes G, llamándolo red neuronal aleatoria . ^[4] Al introducir "clientes negativos" que pueden destruir o eliminar a otros clientes, generalizó la familia de redes de forma de producto. ^[5] Luego, esto se amplió en varios pasos, primero con los "desencadenantes" de Gelenbe, que son clientes que tienen el poder de mover a otros clientes de una cola a otra. ^[6] Otra nueva forma de cliente que también condujo a la forma de producto fue la "eliminación por lotes" de Gelenbe. ^[7] Erol Gelenbe y Jean-Michel Fourneau ampliaron esta idea con tipos de clientes llamados "restablecimientos", que pueden modelar la reparación de fallos: cuando una cola llega al estado vacío, lo que representa (por ejemplo) un fallo, la longitud de la cola puede retroceder o "restablecerse" a su distribución de estado estable cuando llega un cliente restablecido, lo que representa una reparación. Todos estos tipos de clientes anteriores en G-Networks pueden existir en la misma red, incluso con múltiples clases, y todos juntos dan como resultado la solución en forma de producto, lo que nos lleva mucho más allá de las redes reversibles que se habían considerado antes. ^[8]

Las soluciones en forma de producto a veces se describen como "estaciones independientes en equilibrio". ^[9] Las soluciones en forma de producto también existen en redes de colas masivas . ^[10]

JM Harrison y RJ Williams señalan que "prácticamente todos los modelos que se han analizado con éxito en la teoría clásica de redes de colas son modelos que tienen una denominada distribución estacionaria en forma de producto" ^[9] Más recientemente, se han publicado soluciones en forma de producto para álgebras de procesos de Markov (por ejemplo, RCAT en PEPA ^{[11] [12]} ) y redes de Petri estocásticas . ^{[13] [14]} El teorema de deficiencia cero de Martin Feinberg proporciona una condición suficiente para que las redes de reacciones químicas exhiban una distribución estacionaria en forma de producto. ^[15]

El trabajo de Gelenbe también muestra que las redes G en forma de producto se pueden utilizar para modelar redes neuronales aleatorias con picos y, además, que dichas redes se pueden utilizar para aproximar funciones de valor real acotadas y continuas. ^{[16] [17]}

Distribuciones del tiempo de estancia

El término forma de producto también se ha utilizado para referirse a la distribución del tiempo de estancia en un sistema de colas cíclicas, donde el tiempo empleado por los trabajos en M nodos se da como el producto del tiempo empleado en cada nodo. ^[18] En 1957, Reich mostró el resultado para dos colas M/M/1 en tándem, ^[19] extendiendo más tarde esto a n colas M/M/1 en tándem ^[20] y se ha demostrado que se aplica a caminos sin adelantamiento en redes de Jackson . ^[21] Walrand y Varaiya sugieren que la no adelantamiento (donde los clientes no pueden adelantar a otros clientes tomando una ruta diferente a través de la red) puede ser una condición necesaria para que el resultado sea válido. ^[21] Mitrani ofrece soluciones exactas para algunas redes simples con adelantamiento, mostrando que ninguna de ellas exhibe distribuciones de tiempo de estancia en forma de producto. ^[22]

Para redes cerradas, Chow demostró que un resultado es válido para dos nodos de servicio ^[23] , que luego se generalizó a un ciclo de colas ^[24] y a caminos sin adelantamientos en redes Gordon-Newell . ^{[25] [26]}

Extensiones

• Las soluciones aproximadas en forma de producto se calculan asumiendo distribuciones marginales independientes, que pueden dar una buena aproximación a la distribución estacionaria en algunas condiciones. ^{[27] [28]}
• Las soluciones en forma de semiproducto son soluciones en las que una distribución puede escribirse como un producto donde los términos tienen una dependencia funcional limitada del espacio de estados global, que puede aproximarse. ^[29]
• Las soluciones en forma de cuasi-producto son:
  • soluciones que no son el producto de densidades marginales, sino que las densidades marginales describen la distribución de una manera de tipo producto ^[30] o
  • forma aproximada para distribuciones de probabilidad transitoria que permite aproximar los momentos transitorios. ^[31]

Referencias

1. Jackson, James R. (1963). "Sistemas de colas tipo Jobshop". Management Science . 10 (1): 131–142. doi :10.1287/mnsc.10.1.131.
2. Boucherie, Richard J.; van Dijk, NM (1994). "Equilibrio local en redes de colas con clientes positivos y negativos". Anales de investigación de operaciones . 48 (5): 463–492. doi :10.1007/BF02033315. hdl : 1871/12327 . S2CID  15599820.
3. Chandy, K. Mani ; Howard, JH Jr; Towsley, DF (1977). "Forma del producto y equilibrio local en redes de colas". Revista de la ACM . 24 (2): 250–263. doi : 10.1145/322003.322009 . S2CID  6218474.
4. Gelenbe, Erol (1989). "Redes neuronales aleatorias con señales negativas y positivas y solución en forma de producto". Neural Computation . 1 (4): 502–510. doi :10.1162/neco.1989.1.4.502. S2CID  207737442.
5. Gelenbe, Erol (1991). "Redes de colas de productos con clientes negativos y positivos". Journal of Applied Probability . 28 (3): 656–663. doi :10.2307/3214499. JSTOR  3214499.
6. Gelenbe, Erol (1993). "Redes G con movimiento de clientes activado". Journal of Applied Probability . 30 (3): 742–748. doi :10.2307/3214781. JSTOR  3214781.
7. Gelenbe, Erol (1993). "Redes G con movimiento de clientes activado". Probabilidad en la ingeniería y las ciencias de la información . 7 (3): 335–342. doi :10.1017/S0269964800002953.
8. Gelenbe, Erol ; Fourneau, Jean-Michel (2002). "Redes G con restablecimientos". Evaluación del rendimiento . 49 (1): 179–191. doi :10.1016/S0166-5316(02)00127-X.
9. Harrison, JM ; Williams, RJ (1992). "Modelos brownianos de redes de colas de avance: soluciones de cuasi-reversibilidad y forma de producto". Anales de probabilidad aplicada . 2 (2): 263–293. CiteSeerX 10.1.1.56.1572 . doi :10.1214/aoap/1177005704. 
10. Henderson, W.; Taylor, PG (1990). "Forma del producto en redes de colas con llegadas de lotes y servicios de lotes". Queueing Systems . 6 : 71–87. doi :10.1007/BF02411466. S2CID  30949152.
11. Hillston, J. ; Thomas, N. (1999). "Solución de forma de producto para una clase de modelos PEPA" (PDF) . Evaluación del desempeño . 35 (3–4): 171–192. doi :10.1016/S0166-5316(99)00005-X. hdl : 20.500.11820/13c57018-5854-4f34-a4c9-833262a71b7c .
12. Harrison, PG (2003). «Volviendo atrás en el tiempo en el álgebra de procesos markovianos». Theoretical Computer Science . 290 (3): 1947–2013. doi : 10.1016/S0304-3975(02)00375-4 . Archivado desde el original el 15 de octubre de 2006 . Consultado el 29 de agosto de 2015 .
13. Marin, A.; Balsamo, S.; Harrison, PG (2012). "Análisis de redes de Petri estocásticas con señales". Evaluación del rendimiento . 69 (11): 551–572. doi :10.1016/j.peva.2012.06.003. hdl : 10044/1/14180 .
14. Mairesse, J.; Nguyen, HT (2009). "Redes de Petri de deficiencia cero y forma del producto". Aplicaciones y teoría de las redes de Petri . Apuntes de clase en informática. Vol. 5606. pág. 103. CiteSeerX 10.1.1.745.1585 . doi :10.1007/978-3-642-02424-5_8. ISBN .  978-3-642-02423-8.
15. Anderson, DF; Craciun, G.; Kurtz, TG (2010). "Distribuciones estacionarias en forma de producto para redes de reacciones químicas de deficiencia cero". Boletín de biología matemática . 72 (8): 1947–1970. arXiv : 0803.3042 . doi :10.1007/s11538-010-9517-4. PMID  20306147. S2CID  2204856.
16. Gelenbe, Erol (1993). "Aprendizaje en la red neuronal aleatoria recurrente". Computación neuronal . 5 (1): 154–164. doi :10.1162/neco.1993.5.1.154. S2CID  38667978.
17. Gelenbe, Erol ; Mao, Zhi-Hong; Li, Yan-Da (1991). "Aproximación de funciones con la red neuronal aleatoria". IEEE Transactions on Neural Networks . 10 (1): 3–9. CiteSeerX 10.1.1.46.7710 . doi :10.1109/72.737488. PMID  18252498. 
18. Boxma, OJ ; Kelly, FP ; Konheim, AG (enero de 1984). "La forma del producto para distribuciones de tiempo de estancia en colas exponenciales cíclicas". Journal of the ACM . 31 (1): 128–133. doi : 10.1145/2422.322419 . S2CID  6770615.
19. Reich, Edgar (1957). "Tiempos de espera cuando las colas están en tándem". Anales de estadística matemática . 28 (3): 768–773. doi : 10.1214/aoms/1177706889 .
20. Reich, E. (1963). "Nota sobre colas en tándem". Anales de estadística matemática . 34 : 338–341. doi : 10.1214/aoms/1177704275 .
21. Walrand, J. ; Varaiya, P. (1980). "Tiempos de permanencia y condición de adelantamiento en redes jacksonianas". Avances en probabilidad aplicada . 12 (4): 1000–1018. doi :10.2307/1426753. JSTOR  1426753.
22. Mitrani, I. (1985). "Problemas de tiempo de respuesta en redes de comunicación". Revista de la Royal Statistical Society. Serie B (Metodológica) . 47 (3): 396–406. doi :10.1111/j.2517-6161.1985.tb01368.x. JSTOR  2345774.
23. Chow, We-Min (abril de 1980). "La distribución del tiempo de ciclo de colas cíclicas exponenciales". Revista de la ACM . 27 (2): 281–286. doi : 10.1145/322186.322193 . S2CID  14084475.
24. Schassberger, R.; Daduna, H. (1983). "El tiempo para un viaje de ida y vuelta en un ciclo de colas exponenciales". Revista de la ACM . 30 : 146–150. doi : 10.1145/322358.322369 . S2CID  33401212.
25. Daduna, H. (1982). "Tiempos de paso para caminos sin adelantamiento en redes Gordon-Newell". Avances en probabilidad aplicada . 14 (3): 672–686. doi :10.2307/1426680. JSTOR  1426680.
26. Kelly, FP ; Pollett, PK (1983). "Tiempos de permanencia en redes de colas cerradas". Avances en probabilidad aplicada . 15 (3): 638–656. doi :10.2307/1426623. JSTOR  1426623.
27. Baynat, B.; Dallery, Y. (1993). "Una visión unificada de las técnicas de aproximación de forma de producto para redes de colas cerradas generales". Evaluación del rendimiento . 18 (3): 205–224. doi :10.1016/0166-5316(93)90017-O.
28. Dallery, Y.; Cao, XR (1992). "Análisis operativo de redes de colas cerradas estocásticas". Evaluación del rendimiento . 14 : 43–61. doi :10.1016/0166-5316(92)90019-D.
29. Thomas, Nigel; Harrison, Peter G. (2010). "Tasas dependientes del estado y forma de semiproducto mediante el proceso inverso". Ingeniería del rendimiento informático . Apuntes de clase en informática. Vol. 6342. pág. 207. doi :10.1007/978-3-642-15784-4_14. ISBN 978-3-642-15783-7.
30. Dębicki, K.; Dieker, AB; Rolski, T. (2007). "Formas de cuasidiproducto para redes de fluidos impulsadas por Levy". Matemáticas de la investigación de operaciones . 32 (3): 629–647. arXiv : math/0512119 . doi :10.1287/moor.1070.0259. S2CID  16150704.
31. Angius, A.; Horváth, AS; Wolf, V. (2013). "Análisis transitorio aproximado de redes de colas mediante formas de cuasiproducto". Técnicas y aplicaciones de modelado analítico y estocástico . Apuntes de clase en informática. Vol. 7984. pág. 22. doi :10.1007/978-3-642-39408-9_3. ISBN 978-3-642-39407-2.