Продукт-форма решения

Форма решения в теории вероятностей

В теории вероятностей решение в форме произведения является особенно эффективной формой решения для определения некоторой метрики системы с различными подкомпонентами, где метрика для набора компонентов может быть записана как произведение метрики по различным компонентам. Используя заглавную нотацию Пи, решение в форме произведения имеет алгебраическую форму

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

где B — некоторая константа. Решения такого вида представляют интерес, поскольку они вычислительно недороги для оценки больших значений n . Такие решения в сетях очередей важны для поиска показателей производительности в моделях многопрограммных и разделяемых по времени компьютерных систем.

Равновесные распределения

Первые решения в форме произведения были найдены для равновесных распределений цепей Маркова . Тривиально, модели, состоящие из двух или более независимых подкомпонентов, демонстрируют решение в форме произведения по определению независимости. Первоначально этот термин использовался в сетях очередей , где подкомпонентами были отдельные очереди. Например, теорема Джексона дает совместное равновесное распределение открытой сети очередей как произведение равновесных распределений отдельных очередей. ^[1] После многочисленных расширений, в основном сети BCMP, считалось, что локальный баланс является требованием для решения в форме произведения. ^{[2] [3]}

Модель G-сети Геленбе была первой, показавшей, что это не так. Мотивированный необходимостью моделирования биологических нейронов, которые имеют точечно-процессное поведение, подобное спайковому, он представил предшественника G-сетей, назвав его случайной нейронной сетью . ^[4] Введя «отрицательных клиентов», которые могут уничтожать или устранять других клиентов, он обобщил семейство сетей формы продукта. ^[5] Затем это было дополнительно расширено в несколько этапов, сначала «триггерами» Геленбе, которые являются клиентами, которые имеют право перемещать других клиентов из одной очереди в другую. ^[6] Другой новой формой клиента, которая также привела к форме продукта, было «удаление партии» Геленбе. ^[7] Это было дополнительно расширено Эролом Геленбе и Жаном-Мишелем Фурно с типами клиентов, называемыми «сбросами», которые могут моделировать исправление сбоев: когда очередь достигает пустого состояния, представляя (например) сбой, длина очереди может вернуться назад или быть «сброшена» до своего устойчивого распределения прибывающим сброшенным клиентом, представляющим исправление. Все эти предыдущие типы клиентов в G-сетях могут существовать в одной и той же сети, в том числе с несколькими классами, и все они вместе по-прежнему приводят к решению в форме продукта, выводя нас далеко за пределы обратимых сетей, которые рассматривались ранее. ^[8]

Решения в форме продукта иногда описываются как «станции независимы в равновесии». ^[9] Решения в форме продукта также существуют в сетях массовых очередей . ^[10]

Дж. М. Харрисон и Р. Дж. Уильямс отмечают, что «практически все модели, которые были успешно проанализированы в классической теории сетей массового обслуживания, являются моделями, имеющими так называемое стационарное распределение в форме произведения» ^[9]. Совсем недавно были опубликованы решения в форме произведения для алгебр марковских процессов (например, RCAT в PEPA ^{[11] [12]} ) и стохастических сетей Петри . ^{[13] [14] Теорема} Мартина Файнберга о нулевом дефиците дает достаточное условие для того, чтобы сети химических реакций демонстрировали стационарное распределение в форме произведения. ^[15]

Работа Геленбе также показывает, что продукт G-сетей может быть использован для моделирования импульсных случайных нейронных сетей , и, более того, такие сети могут быть использованы для аппроксимации ограниченных и непрерывных функций с действительными значениями. ^{[16] [17]}

Распределение времени пребывания

Термин «форма произведения» также использовался для обозначения распределения времени пребывания в циклической системе массового обслуживания, где время, проведенное заданиями в узлах M , задается как произведение времени, проведенного в каждом узле. ^[18] В 1957 году Райх показал результат для двух очередей M/M/1 в тандеме, ^[19] позже расширив его до n очередей M/M/1 в тандеме ^[20] , и было показано, что он применим к путям без обгона в сетях Джексона . ^[21] Уолранд и Варайя предполагают, что отсутствие обгона (когда клиенты не могут обогнать других клиентов, выбрав другой маршрут через сеть) может быть необходимым условием для сохранения результата. ^[21] Митрани предлагает точные решения для некоторых простых сетей с обгоном, показывая, что ни одна из них не демонстрирует распределения времени пребывания в форме произведения. ^[22]

Для закрытых сетей Чжоу показал, что результат справедлив для двух узлов обслуживания ^[23] , который позже был обобщен на цикл очередей ^[24] и на пути без обгона в сетях Гордона–Ньюэлла . ^{[25] [26]}

Расширения

• Приближенные решения в форме произведения вычисляются с учетом независимых предельных распределений, что может дать хорошее приближение к стационарному распределению при некоторых условиях. ^{[27] [28]}
• Решения в форме полупродукта — это решения, в которых распределение можно записать в виде продукта, где члены имеют ограниченную функциональную зависимость от глобального пространства состояний, которое можно аппроксимировать. ^[29]
• Решения в форме квазипродукта являются либо
  • решения, которые не являются произведением предельных плотностей, но предельные плотности описывают распределение в стиле произведения ^[30] или
  • Приближенная форма для распределений вероятностей переходных процессов, которая позволяет аппроксимировать переходные моменты. ^[31]

Ссылки

1. Джексон, Джеймс Р. (1963). «Системы очередей типа Jobshop». Management Science . 10 (1): 131–142. doi :10.1287/mnsc.10.1.131.
2. Бушери, Ричард Дж.; ван Дейк, Н. М. (1994). «Локальный баланс в сетях очередей с положительными и отрицательными клиентами». Annals of Operations Research . 48 (5): 463–492. doi :10.1007/BF02033315. hdl : 1871/12327 . S2CID  15599820.
3. Чанди, К. Мани ; Говард, Дж. Х. Мл.; Тоусли, Д. Ф. (1977). «Форма продукта и локальный баланс в сетях массового обслуживания». Журнал ACM . 24 (2): 250–263. doi : 10.1145/322003.322009 . S2CID  6218474.
4. Геленбе, Эрол (1989). «Случайные нейронные сети с отрицательными и положительными сигналами и решение в форме продукта». Neural Computation . 1 (4): 502–510. doi :10.1162/neco.1989.1.4.502. S2CID  207737442.
5. Геленбе, Эрол (1991). «Сети очередей в форме произведения с отрицательными и положительными клиентами». Журнал прикладной вероятности . 28 (3): 656–663. doi :10.2307/3214499. JSTOR  3214499.
6. Геленбе, Эрол (1993). «G-сети с инициированным движением клиентов». Журнал прикладной вероятности . 30 (3): 742–748. doi :10.2307/3214781. JSTOR  3214781.
7. Геленбе, Эрол (1993). «G-сети с инициированным движением клиентов». Вероятность в инженерных и информационных науках . 7 (3): 335–342. doi :10.1017/S0269964800002953.
8. Геленбе, Эрол ; Фурно, Жан-Мишель (2002). «G-сети со сбросами». Оценка производительности . 49 (1): 179–191. doi :10.1016/S0166-5316(02)00127-X.
9. Harrison, JM ; Williams, RJ (1992). «Броуновские модели сетей очередей прямого распространения: квазиобратимость и решения в форме произведения». Annals of Applied Probability . 2 (2): 263–293. CiteSeerX 10.1.1.56.1572 . doi :10.1214/aoap/1177005704. 
10. Хендерсон, У.; Тейлор, П. Г. (1990). «Форма продукта в сетях очередей с пакетным прибытием и пакетным обслуживанием». Системы очередей . 6 : 71–87. doi :10.1007/BF02411466. S2CID  30949152.
11. Хиллстон, Дж.; Томас, Н. (1999). "Решение формы продукта для класса моделей PEPA" (PDF) . Оценка производительности . 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). «Возвращение времени вспять в алгебре марковских процессов». Теоретическая информатика . 290 (3): 1947–2013. doi : 10.1016/S0304-3975(02)00375-4 . Архивировано из оригинала 2006-10-15 . Получено 2015-08-29 .
13. Марин, А.; Бальзамо, С.; Харрисон, П. Г. (2012). «Анализ стохастических сетей Петри с сигналами». Оценка производительности . 69 (11): 551–572. doi :10.1016/j.peva.2012.06.003. hdl : 10044/1/14180 .
14. Mairesse, J.; Nguyen, HT (2009). "Deficiency Zero Petri Networks and Product Form". Applications and Theory of Petri Nets . Lecture Notes in Computer Science. Vol. 5606. p. 103. CiteSeerX 10.1.1.745.1585 . doi :10.1007/978-3-642-02424-5_8. ISBN  978-3-642-02423-8.
15. Андерсон, ДФ; Крачун, Г.; Курц, ТГ (2010). «Стационарные распределения в форме продукта для сетей химических реакций с нулевым дефицитом». Бюллетень математической биологии . 72 (8): 1947–1970. arXiv : 0803.3042 . doi : 10.1007/s11538-010-9517-4. PMID  20306147. S2CID  2204856.
16. Геленбе, Эрол (1993). «Обучение в рекуррентной случайной нейронной сети». Neural Computation . 5 (1): 154–164. doi :10.1162/neco.1993.5.1.154. S2CID  38667978.
17. Gelenbe, Erol ; Mao, Zhi-Hong; Li, Yan-Da (1991). «Аппроксимация функций с помощью случайной нейронной сети». 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 (январь 1984). «Форма продукта для распределений времени пребывания в циклических экспоненциальных очередях». Журнал ACM . 31 (1): 128–133. doi : 10.1145/2422.322419 . S2CID  6770615.
19. Райх, Эдгар (1957). «Время ожидания, когда очереди расположены тандемом». Анналы математической статистики . 28 (3): 768–773. doi : 10.1214/aoms/1177706889 .
20. Райх, Э. (1963). «Заметка об очередях в тандеме». Анналы математической статистики . 34 : 338–341. doi : 10.1214/aoms/1177704275 .
21. Walrand, J. ; Varaiya, P. (1980). «Времена пребывания и условие обгона в сетях Джексона». Advances in Applied Probability . 12 (4): 1000–1018. doi :10.2307/1426753. JSTOR  1426753.
22. Митрани, И. (1985). «Проблемы времени отклика в сетях связи». Журнал Королевского статистического общества. Серия B (Методологическая) . 47 (3): 396–406. doi :10.1111/j.2517-6161.1985.tb01368.x. JSTOR  2345774.
23. Chow, We-Min (апрель 1980 г.). «Распределение времени цикла экспоненциальных циклических очередей». Журнал ACM . 27 (2): 281–286. doi : 10.1145/322186.322193 . S2CID  14084475.
24. Шассбергер, Р.; Дадуна, Х. (1983). «Время кругового обхода в цикле экспоненциальных очередей». Журнал ACM . 30 : 146–150. doi : 10.1145/322358.322369 . S2CID  33401212.
25. Дадуна, Х. (1982). «Время прохождения для путей без обгона в сетях Гордона-Ньюэлла». Advances in Applied Probability . 14 (3): 672–686. doi :10.2307/1426680. JSTOR  1426680.
26. Келли, Ф. П.; Поллетт, П. К. (1983). «Время пребывания в закрытых сетях очередей». Advances in Applied Probability . 15 (3): 638–656. doi :10.2307/1426623. JSTOR  1426623.
27. Baynat, B.; Dallery, Y. (1993). "Единый взгляд на методы аппроксимации в форме произведения для общих замкнутых сетей очередей". Оценка производительности . 18 (3): 205–224. doi :10.1016/0166-5316(93)90017-O.
28. Dallery, Y.; Cao, XR (1992). «Операционный анализ стохастических замкнутых сетей очередей». Оценка производительности . 14 : 43–61. doi :10.1016/0166-5316(92)90019-D.
29. Томас, Найджел; Харрисон, Питер Г. (2010). "Зависящие от состояния ставки и полупродуктовая форма через обратный процесс". Computer Performance Engineering . Lecture Notes in Computer Science. Vol. 6342. p. 207. doi :10.1007/978-3-642-15784-4_14. ISBN 978-3-642-15783-7.
30. Дебицкий, К.; Дикер, А. Б.; Рольски, Т. (2007). «Квазипродуктовые формы для сетей жидкости, управляемых Леви». Математика исследования операций . 32 (3): 629–647. arXiv : math/0512119 . doi : 10.1287/moor.1070.0259. S2CID  16150704.
31. Angius, A.; Horváth, AS; Wolf, V. (2013). "Approximate Transient Analysis of Queuing Networks by Quasi Product Forms". Analytical and Stochastic Modeling Techniques and Applications . Lecture Notes in Computer Science. Vol. 7984. p. 22. doi :10.1007/978-3-642-39408-9_3. ISBN 978-3-642-39407-2.