О вычислении свертки экспоненциальных распределений

О вычислении свертки экспоненциальных распределений

Запропоновано рекурентний алгоритм обчислення розподілу суми експоненціально розподілених випадкових величин. Алгоритм можна застосовувати як для різнорозподілених випадкових величин, так і при збігові параметрів деяких випадкових величин....

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2013
Hauptverfasser: Кузнецов, Н.Ю., Шумская, А.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schriftenreihe:Проблемы управления и информатики
Schlagworte:
Методы обработки информации
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/207649
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:О вычислении свертки экспоненциальных распределений / Н.Ю. Кузнецов, А.А. Шумская // Проблемы управления и информатики. — 2013. — № 5. — С. 103-105. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-207649
record_format dspace
spelling irk-123456789-2076492025-10-12T00:05:32Z О вычислении свертки экспоненциальных распределений Про обчислення згортки експоненціальних розподілів On convolution calculation for exponential distributions Кузнецов, Н.Ю. Шумская, А.А. Методы обработки информации Запропоновано рекурентний алгоритм обчислення розподілу суми експоненціально розподілених випадкових величин. Алгоритм можна застосовувати як для різнорозподілених випадкових величин, так і при збігові параметрів деяких випадкових величин. A recurrence algorithm enabling to evaluate the distribution of the sum of exponentially distributed random variables is proposed. This algorithm can be used both for differently distributed random variables and for the case when parameters of some random variables coincide. 2013 Article О вычислении свертки экспоненциальных распределений / Н.Ю. Кузнецов, А.А. Шумская // Проблемы управления и информатики. — 2013. — № 5. — С. 103-105. — Бібліогр.: 3 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207649 519.873 10.1615/JAutomatInfScien.v45.i10.10 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Методы обработки информации
Методы обработки информации
spellingShingle Методы обработки информации
Методы обработки информации
Кузнецов, Н.Ю.
Шумская, А.А.
О вычислении свертки экспоненциальных распределений
Проблемы управления и информатики
description Запропоновано рекурентний алгоритм обчислення розподілу суми експоненціально розподілених випадкових величин. Алгоритм можна застосовувати як для різнорозподілених випадкових величин, так і при збігові параметрів деяких випадкових величин.
format Article
author Кузнецов, Н.Ю.
Шумская, А.А.
author_facet Кузнецов, Н.Ю.
Шумская, А.А.
author_sort Кузнецов, Н.Ю.
title О вычислении свертки экспоненциальных распределений
title_short О вычислении свертки экспоненциальных распределений
title_full О вычислении свертки экспоненциальных распределений
title_fullStr О вычислении свертки экспоненциальных распределений
title_full_unstemmed О вычислении свертки экспоненциальных распределений
title_sort о вычислении свертки экспоненциальных распределений
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2013
topic_facet Методы обработки информации
url https://nasplib.isofts.kiev.ua/handle/123456789/207649
citation_txt О вычислении свертки экспоненциальных распределений / Н.Ю. Кузнецов, А.А. Шумская // Проблемы управления и информатики. — 2013. — № 5. — С. 103-105. — Бібліогр.: 3 назв. — рос.
series Проблемы управления и информатики
work_keys_str_mv AT kuznecovnû ovyčisleniisvertkiéksponencialʹnyhraspredelenij
AT šumskaâaa ovyčisleniisvertkiéksponencialʹnyhraspredelenij
AT kuznecovnû proobčislennâzgortkieksponencíalʹnihrozpodílív
AT šumskaâaa proobčislennâzgortkieksponencíalʹnihrozpodílív
AT kuznecovnû onconvolutioncalculationforexponentialdistributions
AT šumskaâaa onconvolutioncalculationforexponentialdistributions
first_indexed 2025-10-12T01:13:29Z
last_indexed 2025-10-13T01:12:18Z
_version_ 1845827142761316352
fulltext © Н.Ю. КУЗНЕЦОВ, А.А. ШУМСКАЯ, 2013 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 5 103 МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ УДК 519.873 Н.Ю. Кузнецов, А.А. Шумская О ВЫЧИСЛЕНИИ СВЕРТКИ ЭКСПОНЕНЦИАЛЬНЫХ РАСПРЕДЕЛЕНИЙ В настоящей статье рассматривается достаточно узкий, но весьма важный для практических приложений вопрос о вычислении распределения суммы независи- мых случайных величин, имеющих экспоненциальное распределение. Подобные вероятности часто возникают при исследовании марковских моделей теории надежности. Если речь идет об оценке вероятности отказа марковской системы в фиксированном промежутке времени ],,0[ t то достаточно моделировать перехо- ды вложенной цепи Маркова и вычислять вероятность ее попадания в множество отказовых состояний одним из известных методов (например, методом существен- ной выборки). Несмещенность оценки вероятности отказа системы в ],0[ t достига- ется за счет дополнительного множителя, представляющего собой вероятность того, что переход в множество отказовых состояний произошел до момента t, а это и есть свертка независимых экспоненциальных распределений, вообще говоря, с различ- ными параметрами. Подобный подход не новый и использовался в работах [1–3] при исследовании надежности сетей методом Монте-Карло. Пусть },,1,{ nii  — последовательность независимых экспоненциально распределенных случайных величин с параметрами }.{ i Задача состоит в вы- числении вероятности }.{)( 1 ttQ n  P Если случайные величины оди- наково распределены, т.е. ,1  n то для вычисления )(tQ существует аналитическая формула . ! )( ! )( 1)( 1 0            nk k t n k k t k t e k t etQ Если же }{ i могут быть различными, то аналитическую формулу в явном виде для произвольного n вывести не удается. Можно использовать моделирова- ние, однако это приводит к возрастанию дисперсии оценки, что также нежела- тельно. В [1] получены рекуррентные формулы для вычисления )(tQ в случае, когда все }{ i являются различными ).( 21 n  Это предположение является обоснованным, когда не допускается восстановление отказавших эле- ментов. В случае же восстанавливаемых элементов системы некоторые интенсив- ности могут совпадать, что не позволяет использовать упомянутый рекуррентный алгоритм, поскольку возникают неопределенности типа деления ноль на ноль. Если даже i и j различны, но близки, то алгоритм не является устойчивым, и погрешность вычисления может существенно влиять на результат. В настоящей статье предложен простой алгоритм вычисления вероятности )(tQ для произвольных значений }.{ i Справедливо следующее утверждение. 104 ISSN 0572-2691 Теорема. Вероятность )(tQ вычисляется по формуле ,}{ ! )( )( 1       nk n t k nke k t tQ P (1) где ,max 1 i ni   а }{ i — независимые случайные величины, имеющие геометри- ческое распределение с вероятностями успеха .}/{  iip Если обозначить ,0,,,1},{ 1  jnijc iij P= то ,}{ 0 1     nk j njn cnkP ,0,)1( 111  jppc j j (2) .0,1,,1,)1( 11 0 ,1       jnippcc kj ii j k ikji  (3) Доказательство. Рассмотрим пуассоновский поток требований с интенсив- ностью . Предположим, что поток «просеивается», причем каждое требование потока остается (успех) с вероятностью .ip Обозначим через i количество не- удач до первого успеха. Поскольку i имеет геометрическое распределение с па- раметром ,ip то распределение времени i между требованиями, которые оста- ются, вычисляется по формуле                              11 11 ! )( }1{ ! )( }{ k k ix k k i x k i e k x ke k x x PP .1 ! ])[( 1 1 x k k ixx ie k x ee         Таким образом, распределения случайных величин i и i совпадают. Ес- ли же рассмотреть сумму ,1 n  то событие }{ 1 tn   произойдет тогда и только тогда, когда в промежутке ],0[ t поступят )( nkk  требований потока с интенсивностью , причем суммарное количество неудач не должно превышать nk  (см. формулу (1)). Распределение суммы геометрически распре- деленных случайных величин вычисляется рекуррентными формулами (2), (3). Теорема доказана. Формула (1) содержит бесконечное число слагаемых. Обозначим .}{ ! )( )( 1 1       Nn nk n t k N nke k t tQ P (4) Подберем N таким, чтобы абсолютная погрешность аппроксимации )(tQ ко- нечной суммой )(tQN не превосходила заданную величину . Предполагая, что ,1 ntN имеем                      0 1 1)!( )( }{ ! )( k k t nN nNk n t k nN t e nN t nke k t P . 1 1 )!( )( tnN nN e nN t t nN        Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 5 105 Обозначим . 1 1 )!( )( ,1:min*                 tnN nN e nN t ntNNN t nN Тогда .)()()( **  tQtQtQ NN Количество операций, необходимое для вычис- ления )(tQ с заданной точностью, оценивается величиной ).( 2NnO Проиллюстрируем приведенный алгоритм на численном примере. Предположим, что ,10n 1t и ,1,021  ,2,043  ,5,065  ,187  .2109  В этом случае .2 t Результаты вычислений N и )(* tQN в зависимости от требуемой абсолютной погрешности  приведены в таблице. Таблица  910 1010 1110 1210 1310 1410 N 6 7 8 9 10 11 )(* tQN 5,61551011 5,62951011 5,63241011 5,63291011 5,63301011 5,63301011 Численные данные показывают, что с возрастанием N сумма )(tQN быстро сходится к ),(tQ т.е. высокая точность оценки достигается даже при небольших значениях .N Предложенный в настоящей статье алгоритм позволяет с наперед заданной точностью аналитически вычислять распределение суммы экспоненциально рас- пределенных случайных величин, что дает возможность уменьшить дисперсию оценок при моделировании марковских систем методом Монте-Карло. М.Ю. Кузнєцов, А.А. Шумська ПРО ОБЧИСЛЕННЯ ЗГОРТКИ ЕКСПОНЕНЦІАЛЬНИХ РОЗПОДІЛІВ Запропоновано рекурентний алгоритм обчислення розподілу суми експоненці- ально розподілених випадкових величин. Алгоритм можна застосовувати як для різнорозподілених випадкових величин, так і при збігові параметрів деяких випадкових величин. N.Yu. Kuznetsov, А.А. Shumskaya ON THE EVALUATION OF THE CONVOLUTION OF EXPONENTIAL DISTRIBUTIONS A recurrence algorithm enabling to evaluate the distribution of the sum of exponen- tially distributed random variables is proposed. This algorithm can be used both for differently distributed random variables and for the case when parameters of some random variables coincide. 1. Elperin T., Gertsbakh I., Lomonosov M. Estimation of network reliability using graph evolution models // IEEE Trans. Reliab. — 1991. — 40, N 5. — P. 572–581. 2. Elperin T., Gertsbakh I., Lomonosov M. An evolution model for Monte Carlo estimation of equi- librium network renewal parameters // Prob. Eng. Inf. Sci. — 1992. — 6. — P. 457–469. 3. Lomonosov M. On Monte Carlo estimates in network reliability // Ibid. — 1994. — 8. — P. 245–264. Получено 28.02.2013

Ähnliche Einträge