En la teoría de la probabilidad , una solución en forma de producto es una forma de solución particularmente eficiente para determinar alguna métrica de un sistema con distintos subcomponentes, donde la métrica para la colección de componentes se puede escribir como un producto de la métrica en los diferentes componentes. . Usando la notación Pi mayúscula, una solución en forma de producto tiene forma algebraica
donde B es una constante. Las soluciones de esta forma son de interés ya que son computacionalmente económicas de evaluar para valores grandes de n . Estas soluciones en redes de cola 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 por dos o más subcomponentes independientes exhiben una solución en forma de producto según la definición de independencia. Inicialmente, el término se usó en redes de cola en las que los subcomponentes serían colas individuales. Por ejemplo, el teorema de Jackson da la distribución de equilibrio conjunta de una red de cola abierta como el producto de las distribuciones de equilibrio de las colas individuales. [1] Después de numerosas ampliaciones, principalmente la red BCMP , se pensó que el equilibrio local era un requisito para una solución de forma de producto. [2] [3]
El modelo de red G de Gelenbe fue el primero en demostrar que este no es el caso. Motivado por la necesidad de modelar neuronas biológicas que tienen un proceso puntual como comportamiento de picos, 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ó aún más en varios pasos, primero mediante 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 llevó a la forma del producto fue la "eliminación por lotes" de Gelenbe. [7] Esto fue ampliado aún más por Erol Gelenbe y Jean-Michel Fourneau con tipos de clientes llamados "restablecimientos" que pueden modelar la reparación de fallas: cuando una cola llega al estado vacío, lo que representa (por ejemplo) una falla, la longitud de la cola puede saltar hacia atrás o ser "restablecido" a su distribución de estado estable por un cliente de restablecimiento que llega, lo que representa una reparación. Todos estos tipos anteriores de clientes en G-Networks pueden existir en la misma red, incluso con múltiples clases, y todos juntos aún dan como resultado la solución de forma de producto, llevándonos 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 "las estaciones son independientes en equilibrio". [9] Las soluciones de 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 la denominada distribución estacionaria de forma de producto" [9]. Más recientemente, se han publicado soluciones de forma de producto para Álgebras del proceso 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 reacción química muestren una distribución estacionaria en forma de producto. [15]
El trabajo de Gelenbe también muestra que la forma de producto G-Networks se puede usar para modelar redes neuronales aleatorias con picos y, además, que tales redes se pueden usar para aproximar funciones de valor real limitadas y continuas. [16] [17]
Distribuciones de 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 cola cíclica, 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 de dos colas M / M / 1 en tándem, [19] luego lo extendió a n colas M / M / 1 en tándem [20] y se ha demostrado que se aplica a los adelantamientos libres caminos en las redes de Jackson . [21] Walrand y Varaiya sugieren que no adelantar (cuando 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 se mantenga. [21] Mitrani ofrece soluciones exactas para algunas redes simples con adelantamiento, mostrando que ninguna de estas exhibe distribuciones de tiempo de estadía en forma de producto. [22]
Para redes cerradas, Chow mostró un resultado para dos nodos de servicio, [23] que luego se generalizó a un ciclo de colas [24] y para adelantar rutas libres 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 se puede escribir como un producto en el que los términos tienen una dependencia funcional limitada del espacio de estados global, que se puede aproximar. [29]
- Las soluciones en forma de cuasi-producto son
- soluciones que no son el producto de densidades marginales, pero las densidades marginales describen la distribución en forma de tipo de producto [30] o
- forma aproximada para distribuciones de probabilidad transitoria que permite aproximar los momentos transitorios. [31]
Referencias
- ^ Jackson, James R. (1963). "Sistemas de colas tipo Jobshop". Ciencias de la gestión . 10 (1): 131-142. doi : 10.1287 / mnsc.10.1.131 .
- ^ Boucherie, Richard J .; van Dijk, NM (1994). "Equilibrio local en redes de colas con clientes positivos y negativos" . Anales de investigación operativa . 48 (5): 463–492. doi : 10.1007 / BF02033315 . hdl : 1871/12327 . S2CID 15599820 .
- ^ Chandy, K. Mani ; Howard, JH, Jr; Towsley, DF (1977). "Forma de producto y saldo local en redes de colas". Revista de la ACM . 24 (2): 250–263. doi : 10.1145 / 322003.322009 . S2CID 6218474 .
- ^ Gelenbe, Erol (1989). "Redes neuronales aleatorias con señales positivas y negativas y solución de forma de producto". Computación neuronal . 1 (4): 502–510. doi : 10.1162 / neco.1989.1.4.502 . S2CID 207737442 .
- ^ Gelenbe, Erol (1991). "Redes de colas en forma de producto con clientes negativos y positivos" . Revista de probabilidad aplicada . 28 (3): 656–663. doi : 10.2307 / 3214499 . JSTOR 3214499 .
- ^ Gelenbe, Erol (1993). "Redes G con movimiento de clientes desencadenado". Revista de probabilidad aplicada . 30 (3): 742–748. doi : 10.2307 / 3214781 . JSTOR 3214781 .
- ^ Gelenbe, Erol (1993). "G-Networks con movimiento de clientes desencadenado". Probabilidad en Ingeniería y Ciencias de la Información . 7 (3): 335–342. doi : 10.1017 / S0269964800002953 .
- ^ Gelenbe, Erol ; Fourneau, Jean-Michel (2002). "G-Networks con reinicios". Evaluación de desempeño . 49 (1): 179-191. doi : 10.1016 / S0166-5316 (02) 00127-X .
- ^ a b Harrison, JM ; Williams, RJ (1992). "Modelos brownianos de redes de colas feedforward: soluciones de cuasireversibilidad y forma de producto". Anales de probabilidad aplicada . 2 (2): 263-293. CiteSeerX 10.1.1.56.1572 . doi : 10.1214 / aoap / 1177005704 .
- ^ Henderson, W .; Taylor, PG (1990). "Forma de producto en redes de colas con llegadas por lotes y servicios por lotes". Sistemas de colas . 6 : 71–87. doi : 10.1007 / BF02411466 . S2CID 30949152 .
- ^ Hillston, J .; Thomas, N. (1999). "Solución de forma de producto para una clase de modelos PEPA" (PDF) . Evaluación de desempeño . 35 (3–4): 171–192. doi : 10.1016 / S0166-5316 (99) 00005-X . hdl : 20.500.11820 / 13c57018-5854-4f34-a4c9-833262a71b7c .
- ^ Harrison, PG (2003). "Retroceder en el tiempo en el álgebra de procesos de Markov" . Informática Teórica . 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 .
- ^ Marin, A .; Balsamo, S .; Harrison, PG (2012). "Análisis de redes de Petri estocásticas con señales". Evaluación de desempeño . 69 (11): 551–572. doi : 10.1016 / j.peva.2012.06.003 . hdl : 10044/1/14180 .
- ^ Mairesse, J .; Nguyen, HT (2009). "Deficiencia Cero Petri Nets y Formulario de Producto". Aplicaciones y teoría de las redes de Petri . Apuntes de conferencias en Ciencias de la Computación. 5606 . pag. 103. CiteSeerX 10.1.1.745.1585 . doi : 10.1007 / 978-3-642-02424-5_8 . ISBN 978-3-642-02423-8.
- ^ Anderson, DF; Craciun, G .; Kurtz, TG (2010). "Distribuciones estacionarias de forma de producto para redes de reacción química cero de deficiencia". 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 .
- ^ 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 .
- ^ Gelenbe, Erol ; Mao, Zhi-Hong; Li, Yan-Da (1991). "Aproximación de funciones con la red neuronal aleatoria". Transacciones IEEE en redes neuronales . 10 (1): 3–9. CiteSeerX 10.1.1.46.7710 . doi : 10.1109 / 72.737488 . PMID 18252498 .
- ^ Boxma, DO ; Kelly, FP ; Konheim, AG (enero de 1984). "La forma del producto para distribuciones de tiempo de estancia en colas exponenciales cíclicas". Revista de la ACM . 31 (1): 128-133. doi : 10.1145 / 2422.322419 . S2CID 6770615 .
- ^ Reich, Edgar (1957). "Tiempos de espera cuando las colas están en tándem" . Los Anales de Estadística Matemática . 28 (3): 768–773. doi : 10.1214 / aoms / 1177706889 .
- ^ Reich, E. (1963). "Nota sobre colas en tándem" . Los Anales de Estadística Matemática . 34 : 338–341. doi : 10.1214 / aoms / 1177704275 .
- ^ a b Walrand, J .; Varaiya, P. (1980). "Tiempos de estancia y la condición de adelantamiento en redes jacksonianas". Avances en probabilidad aplicada . 12 (4): 1000–1018. doi : 10.2307 / 1426753 . JSTOR 1426753 .
- ^ 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 .
- ^ Chow, We-Min (abril de 1980). "La distribución del tiempo de ciclo de las colas cíclicas exponenciales". Revista de la ACM . 27 (2): 281–286. doi : 10.1145 / 322186.322193 . S2CID 14084475 .
- ^ Schassberger, R .; Daduna, H. (1983). "El tiempo de 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 .
- ^ Daduna, H. (1982). "Tiempos de paso para caminos sin adelantar en redes Gordon-Newell". Avances en probabilidad aplicada . 14 (3): 672–686. doi : 10.2307 / 1426680 . JSTOR 1426680 .
- ^ Kelly, FP ; Pollett, PK (1983). "Tiempos de estancia en redes de colas cerradas". Avances en probabilidad aplicada . 15 (3): 638–656. doi : 10.2307 / 1426623 . JSTOR 1426623 .
- ^ Baynat, B .; Dallery, Y. (1993). "Una vista unificada de técnicas de aproximación de forma de producto para redes de colas cerradas en general". Evaluación de desempeño . 18 (3): 205–224. doi : 10.1016 / 0166-5316 (93) 90017-O .
- ^ Dallery, Y .; Cao, XR (1992). "Análisis operativo de redes estocásticas de colas cerradas". Evaluación de desempeño . 14 : 43–61. doi : 10.1016 / 0166-5316 (92) 90019-D .
- ^ Thomas, Nigel; Harrison, Peter G. (2010). "Tasas dependientes del estado y forma de semiproducto a través del proceso inverso". Ingeniería de rendimiento informático . Apuntes de conferencias en Ciencias de la Computación. 6342 . pag. 207. doi : 10.1007 / 978-3-642-15784-4_14 . ISBN 978-3-642-15783-7.
- ^ Debicki, K .; Dieker, AB; Rolski, T. (2007). "Formularios de cuasi-producto para redes de fluidos impulsadas por impuestos". Matemáticas de la investigación operativa . 32 (3): 629–647. arXiv : matemáticas / 0512119 . doi : 10.1287 / moor.1070.0259 . S2CID 16150704 .
- ^ Angius, A .; Horváth, AS; Wolf, V. (2013). "Análisis transitorio aproximado de redes de colas por formas de cuasi producto". Técnicas y aplicaciones de modelado analítico y estocástico . Apuntes de conferencias en Ciencias de la Computación. 7984 . pag. 22. doi : 10.1007 / 978-3-642-39408-9_3 . ISBN 978-3-642-39407-2.