Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження

Розглядається система обслуговування GI/G/∞ в умовах великого завантаження. Для перевiрки гiпотези про асимптотично нормальний розподiл кiлькостi вимог у системi пропонується застосовувати статистичний пiдхiд, який грунтується на методi Монте-Карло. Використання χ²-критерiю дозволяє встановити мiнi...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2016
1. Verfasser: Кузнєцов, І.М.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Видавничий дім "Академперіодика" НАН України 2016
Schriftenreihe:Доповіді НАН України
Schlagworte:
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/104755
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:Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження / І.М. Кузнєцов // Доповіді Національної академії наук України. — 2016. — № 5. — С. 30-35. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-104755
record_format dspace
spelling irk-123456789-1047552018-03-12T15:47:54Z Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження Кузнєцов, І.М. Інформатика та кібернетика Розглядається система обслуговування GI/G/∞ в умовах великого завантаження. Для перевiрки гiпотези про асимптотично нормальний розподiл кiлькостi вимог у системi пропонується застосовувати статистичний пiдхiд, який грунтується на методi Монте-Карло. Використання χ²-критерiю дозволяє встановити мiнiмальне завантаження системи, починаючи з якого статистичнi данi не суперечать цiй гiпотезi. Рассматривается система обслуживания GI/G/∞ в условиях большой загрузки. Для проверки гипотезы об асимптотически нормальном распределении количества требований в системе предлагается использовать статистический подход, основанный на методе Монте-Карло. Использование χ²-критерия позволяет установить минимальную загрузку системы, начиная с которой статистические данные не противоречат этой гипотезе. The queueing system GI/G/∞ in a heavy traffic is considered. A statistical testing of the hypothesis that a steady-state distribution of the number of customers tends to the normal distribution is proposed. The χ²-criterion enables us to determine a minimal load, from which the statistical data don’t contradict this hypothesis. 2016 Article Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження / І.М. Кузнєцов // Доповіді Національної академії наук України. — 2016. — № 5. — С. 30-35. — Бібліогр.: 11 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/104755 519.872 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
topic Інформатика та кібернетика
Інформатика та кібернетика
spellingShingle Інформатика та кібернетика
Інформатика та кібернетика
Кузнєцов, І.М.
Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження
Доповіді НАН України
description Розглядається система обслуговування GI/G/∞ в умовах великого завантаження. Для перевiрки гiпотези про асимптотично нормальний розподiл кiлькостi вимог у системi пропонується застосовувати статистичний пiдхiд, який грунтується на методi Монте-Карло. Використання χ²-критерiю дозволяє встановити мiнiмальне завантаження системи, починаючи з якого статистичнi данi не суперечать цiй гiпотезi.
format Article
author Кузнєцов, І.М.
author_facet Кузнєцов, І.М.
author_sort Кузнєцов, І.М.
title Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження
title_short Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження
title_full Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження
title_fullStr Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження
title_full_unstemmed Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження
title_sort використання методу монте-карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі gi/g/∞ у випадку великого завантаження
publisher Видавничий дім "Академперіодика" НАН України
publishDate 2016
topic_facet Інформатика та кібернетика
url http://dspace.nbuv.gov.ua/handle/123456789/104755
citation_txt Використання методу Монте-Карло для статистичної перевірки асимптотичної нормальності стаціонарного розподілу кількості вимог у системі GI/G/∞ у випадку великого завантаження / І.М. Кузнєцов // Доповіді Національної академії наук України. — 2016. — № 5. — С. 30-35. — Бібліогр.: 11 назв. — укр.
series Доповіді НАН України
work_keys_str_mv AT kuznêcovím vikoristannâmetodumontekarlodlâstatističnoíperevírkiasimptotičnoínormalʹnostístacíonarnogorozpodílukílʹkostívimogusistemígiguvipadkuvelikogozavantažennâ
first_indexed 2025-07-07T15:46:54Z
last_indexed 2025-07-07T15:46:54Z
_version_ 1837003666126536704
fulltext http://dx.doi.org/10.15407/dopovidi2016.05.030 УДК 519.872 I.М. Кузнєцов Iнститут кiбернетики iм. В. М. Глушкова НАН України, Київ E-mail: sea_hawk@icloud.com Використання методу Монте-Карло для статистичної перевiрки асимптотичної нормальностi стацiонарного розподiлу кiлькостi вимог у системi GI/G/∞ у випадку великого завантаження (Представлено академiком НАН України I.М. Коваленком) Розглядається система обслуговування GI/G/∞ в умовах великого завантаження. Для перевiрки гiпотези про асимптотично нормальний розподiл кiлькостi вимог у систе- мi пропонується застосовувати статистичний пiдхiд, який грунтується на методi Монте-Карло. Використання χ2-критерiю дозволяє встановити мiнiмальне заванта- ження системи, починаючи з якого статистичнi данi не суперечать цiй гiпотезi. Ключовi слова: система обслуговування, велике завантаження, метод Монте-Карло, гiпотеза, нормальнiй розподiл, χ2-критерiй. Останнiми роками пiдвищена увага придiляється розвитку, дослiдженню та впровадженню телекомунiкацiйних мереж. Це є однiєю з найбiльш перспективних областей використання новiтнiх iнформацiйних технологiй. Вiдомо, що процес, який описує кiлькiсть вимог у мере- жi, моделюється тiєю чи iншою системою масового обслуговування з одним чи декiлькома вхiдними потоками. Як правило, цi потоки вважаються пуасонiвськими. Це iстотно спрощує розрахунки, оскiльки тодi стацiонарнi ймовiрностi станiв системи обслуговування вдається обчислити в явному виглядi за допомогою формул Ерланга. Але далеко не завжди припуще- ння про пуасонiвський характер вхiдних потокiв пiдтверджується статистичними даними. У цьому випадку застосовують наближенi методи, зокрема асимптотичнi методи та методи прискореного моделювання. Значна частина дослiджень зосереджена на системах обслуго- вування в умовах малого завантаження [1–4]. Але для сучасних телекомунiкацiйних мереж бiльш характерним є випадок високого завантаження, коли в мережi одночасно присутнi декiлька сотень викликiв [5–8]. Останнiм часом все бiльш поширеними стають спецiальнi методи Монте-Карло (методи прискореного моделювання), якi дозволяють на декiлька по- рядкiв зменшити дисперсiю оцiнки, а тим самим досягти бажаної точностi при вiдносно невеликих затратах часу на обчислення [9–11]. У даному повiдомленнi розглядається система обслуговування GI/G/∞ (рекурентний вхiдний потiк, який визначається функцiєю розподiлу F (x), нескiнчена кiлькiсть обслуго- вуючих пристроїв, час обслуговування має функцiю розподiлу G(x)). Метою дослiдження є вивчення асимптотичної поведiнки стацiонарного розподiлу кiлькостi вимог у системi за умови, що вiдношення середнього часу обслуговування до середнього часу мiж момента- ми надходження вимог необмежено зростає. При цьому зростає i середня кiлькiсть вимог © I.М. Кузнєцов, 2016 30 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №5 у системi. Академiк НАН України I.М. Коваленко висунув гiпотезу, що за вiдповiдного нормування розподiл кiлькостi вимог у системi буде наближатися до нормального розподi- лу. На чисельних прикладах покажемо, як метод Монте-Карло може бути застосованим не тiльки до перевiрки цiєї гiпотези, але й до з’ясування мiнiмального завантаження системи, починаючи з якого статистичнi данi не суперечать гiпотезi. При цьому використовується χ2-критерiй. Збiр статистичних даних методом Монте-Карло. Загальну схему збору статисти- чних даних та їх перевiрки на вiдповiднiсть нормальному розподiлу сформулюємо насту- пним чином. Позначимо через {ξi, i = 1, 2, . . .} та {ηi, i = 1, 2, . . .} незалежнi послiдовностi незалежних у кожнiй послiдовностi випадкових величин, якi мають розподiли F (x) та G(x) вiдповiдно. Припустимо, що F (+0) < 1, τF = ∞∫ 0 [1−F (u)] du < ∞ та τG = ∞∫ 0 [1−G(u)] du < ∞. Нехай в момент часу t = 0 система обслуговування GI/G/∞ знаходиться у стацiонар- ному режимi. Якщо момент t = 0 розглядати як момент надходження вимоги, то кiлькiсть вимог Z в цей момент визначається рiвнiстю Z = ∞∑ n=1 I(ηn > ξ1 + . . .+ ξn), де I(·) — iндикатор вiдповiдної подiї. Якщо ж дослiджується кiлькiсть вимог Z(0) в до- вiльний стацiонарний момент часу, то вiдповiдний рекурентний процес надходження вимог (який направлений у минуле) є стацiонарним, тобто у цьому випадку Z(0) = ∞∑ n=1 I(ηn > ξ (0) 1 + ξ2 + . . .+ ξn), (1) де P{ξ(0)1 < x} = 1/τF x∫ 0 [1− F (u)] du, x > 0. Саме на дослiдженнi випадкової величини Z(0) зосередимо основну увагу. Очевидно, що зi збiльшенням n кожний доданок ряду (1) все менш впливає на загаль- не його значення. Нехай ε > 0 — це деякий пороговий рiвень, який визначає значення ймовiрностей, якими будемо нехтувати. Позначимо β = inf{t : 1−G(t) < ε}, N = min{n : ξ(0)1 + ξ2 + . . .+ ξn > β}. Замiсть випадкової величини Z(0), яка визначається рядом (1), будемо дослiджувати випадкову величину Y (0) = N∑ n=1 I(ηn > ξ (0) 1 + ξ2 + . . .+ ξn), (2) яка визначається сумою iз випадковою кiлькiстю доданкiв (кожна подiя {ηn > ξ (0) 1 + ξ2 + + . . . + ξn}, n > N , має ймовiрнiсть, меншу за ε). Моделюючи методом Монте-Карло послiдовностi випадкових величин {ηn}, ξ(0)1 , {ξi, i > > 2}, за формулою (2) знаходимо реалiзацiї y(0)1 , . . . , y(0)m випадкової величини Y (0), а також вибiрковi значення математичного сподiвання та дисперсiї: y(m) = 1 m m∑ i=1 y (0) i , σ2(m) = 1 m− 1 { m∑ i=1 [y (0) i ]2 −my2(m) } . ISSN 1025-6415 Доп. НАН України, 2016, №5 31 Утворимо нову послiдовнiсть x (0) i = (y (0) i − y(m))/σ(m), i = 1, 2, . . . ,m. Метою дослiд- ження є перевiрка гiпотези H0: спостереження {x(0)i } — це реалiзацiї нормально розподiленої випадкової величини з математичним сподiванням 0 та дисперсiєю 1. Для перевiрки цiєї гiпотези скористаємось χ2-критерiєм Пiрсона. Нехай K — це деяке натуральне число. Область значень випадкової величини Y (0) розiб’ємо на областi таким чином, щоб у кожну область попало щонайменше K спостережень. Якщо в останню область попало менш, нiж K спостережень, то цю область об’єднуємо з попередньою. Припустимо, що таких областей виявилось r: A1 = {0, 1, . . . , l1}, Ai = {li−1 + 1, . . . , li}, i = 2, 3, . . . , r − 1, Ar = {lr−1 + 1, lr−1 + 2, . . .}, де 0 6 l1 < l2 < . . . < lr−1 < ∞. Позначимо через νi кiлькiсть спостережень, якi мi- стить область Ai. Обчислимо теоретичну ймовiрнiсть потрапляння випадкової величини в область Ai за умови, що виконується гiпотеза H0 : p1 = Φ(v1), pi = Φ(vi)− Φ(vi−1), i = 2, . . . , r − 1, pr = 1− Φ(vr−1), (3) де vi = (li + 0,5 − y(m))/σ(m), i = 1, . . . , r − 1, Φ(z) = 1/ √ 2π z∫ −∞ e−u2/2du. Далi утворюємо мiру Пiрсона ∆(r) m = r∑ i=1 (νi −mpi) 2 mpi . (4) Згiдно з теоремою Пiрсона асимптотичний (при m → ∞) розподiл випадкової величини ∆(r) m є χ2-розподiлом з r−1 ступенем свободи. Позначимо цей розподiл Tr−1(z). Якщо γ — це рiвень значущостi критерiя, то за таблицями знаходимо z(r−1) γ з рiвняння: Tr−1(z) = 1− γ. Якщо за результатами обчислення ∆(r) m згiдно з (4) виявилось, що ∆(r) m 6 z(r−1) γ , (5) то статистична гiпотеза H0 не суперечить отриманим статистичним даним. Якщо ж нерiв- нiсть (5) не виконується, то гiпотезу H0 слiд вiдкинути. Результати числового експерименту. Продемонструємо запропонований пiдхiд на прикладi розподiлiв Вейбулла. Нехай F (x) = 1− exp{−(ρx)α}, G(x) = 1− exp{−xα}, де ρ > 0, α > 0, τF = 1/ρΓ(1 + 1/α), τG = Γ(1 + 1/α), Γ(µ) = ∞∫ 0 xµ−1e−xdx. Дослiдимо асим- птотичну поведiнку стацiонарного розподiлу кiлькостi вимог у системi, коли завантаження τG/τF = ρ зростає. Розглянемо три випадки: a) α = 1 (марковська модель; стацiонарний розподiл знаходиться за явними аналiтичними формулами); b) α = 2; c) α = 0,5. З’ясує- мо, при яких значеннях ρ отриманi статистичнi данi не суперечать гiпотезi H0. Виберемо ε = 10−6, m = 100000, K = 2000 та γ = 0,05. Значення m та K пiдiбранi таким чином, щоб ймовiрнiсть потрапляння у кожну з областей Ai була не нижчою за 0,02 за умови, що 32 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №5 виконується гiпотеза H0. Результати обчислення наведено у табл. 1–3. У випадку α = 1, ко- ли стацiонарний розподiл знаходиться у явному виглядi (розподiл Пуасона), обчислюються також точнi значення ймовiрностей {pi}. Якщо їх пiдставити у формулу (4), то отримаємо вiдповiдне значення ∆∗(r) m , яке має задовольняти нерiвнiсть (5) для будь-якого ρ > 0. Якщо вiдомий стацiонарний розподiл {pi}, то χ2-критерiй цiлком пiдтверджує вiдповiд- нiсть статистичних спостережень цьому розподiлу (див. табл. 1), оскiльки ∆∗(r) m 6 z(r−1) γ для всiх розглянутих значень ρ. Якщо ж використовувати наближення нормальним розподiлом згiдно з формулами (3), то можно стверджувати, що швидкiсть збiжностi суттєво залежить вiд виду функцiй розподiлу F (x) i G(x). Найбiльшою швидкiсть збiжностi є у випадку α = 2 (так званi “старiючi” розподiли). Вже при ρ > 300 статистичнi данi не суперечать гiпотезi H0 (див. табл. 2). У випадку α = 0,5 (так званi “молодiючi” розподiли) швидкiсть збiжностi Таблиця 1. Випадок α = 1 ρ y(m) σ2(m) r − 1 ∆∗(r) m ∆(r) m z(r−1) γ 100 100,0 100,2 30 29,46 108,6 43,77 200 200,0 200,9 36 29,03 77,72 50,00 300 300,0 299,8 38 36,09 88,49 53,38 400 400,1 396,7 33 29,44 51,03 47,40 500 500,1 499,2 34 24,03 51,28 48,60 600 600,0 598,0 37 29,18 38,31 52,19 700 700,0 698,5 38 25,85 36,66 53,38 800 800,0 800,3 39 29,76 35,89 54,57 900 899,7 901,2 40 39,41 37,28 55,76 1000 1000,0 1000,6 42 38,38 54,31 58,12 Таблиця 2. Випадок α = 2 ρ y(m) σ2(m) r − 1 ∆∗(r) m ∆(r) m z(r−1) γ 100 100,0 49,09 24 73,49 36,42 200 200,7 97,14 31 63,49 44,99 300 300,6 145,7 35 43,78 49,80 400 400,6 193,7 37 39,69 52,19 500 500,6 241,5 38 39,95 53,38 600 600,7 293,1 39 46,43 54,57 700 700,6 339,7 37 40,91 52,19 800 800,7 390,4 33 34,97 47,40 900 900,6 437,5 33 37,71 47,40 1000 1000 486,5 34 28,42 48,60 Таблиця 3. Випадок α = 0,5 ρ y(m) σ2(m) r − 1 ∆∗(r) m ∆(r) m z(r−1) γ 100 102,7 194,8 37 184,2 52,19 200 202,7 393,5 33 80,80 47,40 300 302,8 591,8 36 87,50 50,00 400 402,7 793,7 39 87,79 54,57 500 502,8 988,7 41 65,88 56,94 600 602,8 1190 42 81,82 58,12 700 702,8 1380 42 56,68 58,12 800 803,0 1578 40 55,03 55,76 900 902,9 1796 40 47,83 55,76 1000 1003 1998 41 48,16 56,94 ISSN 1025-6415 Доп. НАН України, 2016, №5 33 є найменшою: пороговим значенням є ρ = 700. У випадку марковської моделi (α = 1) гiпотезу H0 можна приймати при ρ > 600 (див. табл. 1). Цитована лiтература 1. Kovalenko I. N. Approximation of queues via small-parameter method // Advances in Queueing. – Boca Raton: CRC Press, 1995. – P. 481–506. 2. Blaszczyszyn B., Frey A., Schmidt V. Light-traffic approximations for Markov-modulated multi-server queues // Commun. Statist. Stoch. Models. – 1995. – 11, No 3. – P. 423–445. 3. Wang C. L. Light-traffic approximations for regenerative queueing processes // Adv. Appl. Probab. – 1997. – 29, No 3. – P. 532–541. 4. Kovalenko I. N., Atkinson J. B., Mikhalevich K.V. Three cases of light-traffic insensitivity of the loss probability in a GI/G/M/0 loss system to the shape of the service time distribution // Queueing Systems. – 2003. – 45, No 3. – P. 245–271. 5. Ross K.W. Multiservice loss models for broadband telecommunication networks. – London: Springer, 1995. – 288 p. 6. Simonian A., Roberts J.W., Theberge F., Mazumdar R. Asymptotic estimates for blocking probabilities in a large multi-rate loss network // Adv. Appl. Probab. – 1997. – 29, No 4. – P. 806–829. 7. Ливинская А.В., Лебедев Е.А. Предельная теорема для перегруженных многоканальных сетей // Кибернетика и систем. анализ. – 2012. – № 6. – С. 106–113. 8. Lebedev E., Livinska G. Gaussian approximation of multi-channel networks in heavy traffic // Communi- cations in Computer and Information Science. – 2013. – No 356. – P. 122–130. 9. Mandjes M. Fast simulation of blocking probabilities in loss networks // Europ. J. Oper. Res. – 1997. – 101, No 2. – P. 393–405. 10. Lassila P. E., Virtamo J.T. Efficient importance sampling for Monte Carlo simulation of loss systems // Proc. of the ITC – 16, Teletraffic Engineering in a Competitive World. – Edinburgh: Elsevier, 1999. – P. 787–796. 11. Шумская А.А. Оценка стационарной вероятности потери в системе массового обслуживания с ре- куррентными потоками требований // Кибернетика и систем. анализ. – 2004. – No 2. – С. 133–145. References 1. Kovalenko I. N. Advances in Queueing, Boca Raton, CRC Press, 1995: 481–506. 2. Blaszczyszyn B., Frey A., Schmidt V. Commun. Statist. Stoch. Models, 1995, 11, No 3: 423–445. 3. Wang C. L. Adv. Appl. Probab., 1997, 29, No 3: 532–541. 4. Kovalenko I. N., Atkinson J. B., Mikhalevich K.V. Queueing Systems, 2003, 45, No 3: 245–271. 5. Ross K.W. Multiservice loss models for broadband telecommunication networks, London, Springer, 1995. 6. Simonian A., Roberts J.W., Theberge F., Mazumdar R. Adv. Appl. Probab., 1997, 29, No 4: 806–829. 7. Livinskaya A.V., Lebedev E.A. Cybernetics and System Analysis, 2012, No 6: 106–113. 8. Lebedev E., Livinska G. Communications in Computer and Information Science, 2013, No 356: 122–130. 9. Mandjes M. Europ. J. Oper. Res., 1997, 101, No 2: 393–405. 10. Lassila P. E., Virtamo J.T. Proc. of the ITC-16, Teletraffic Engineering in a Competitive World, Edi- nburgh, Elsevier, 1999: 787–796. 11. Shumskaya А.А. Cybernetics and System Analysis, 2004, No 2: 133–145. Надiйшло до редакцiї 17.11.2015 34 ISSN 1025-6415 Dopov. Nac. akad. nauk Ukr., 2016, №5 И.Н. Кузнецов Институт кибернетики им. В. М. Глушкова НАН Украины, Киев E-mail: sea_hawk@icloud.com Использование метода Монте-Карло для статистической проверки асимптотической нормальности стационарного распределения количества требований в системе GI/G/∞ в случае большой загрузки Рассматривается система обслуживания GI/G/∞ в условиях большой загрузки. Для про- верки гипотезы об асимптотически нормальном распределении количества требований в си- стеме предлагается использовать статистический подход, основанный на методе Монте- Карло. Использование χ2-критерия позволяет установить минимальную загрузку систе- мы, начиная с которой статистические данные не противоречат этой гипотезе. Ключевые слова: система обслуживания, большая загрузка, метод Монте-Карло, гипотеза, нормальное распределение, χ2-критерий. I. N. Kuznetsov V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kiev E-mail: sea_hawk@icloud.com Application of the Monte-Carlo simulation for the statistical testing of the hypothesis that a steady-state distribution of the number of customers in the queueing system GI/G/∞ tends to the normal distribution in the case of heavy traffic The queueing system GI/G/∞ in a heavy traffic is considered. A statistical testing of the hypothesis that a steady-state distribution of the number of customers tends to the normal distribution is proposed. The χ2-criterion enables us to determine a minimal load, from which the statistical data don’t contradict this hypothesis. Keywords: queueing system, heavy traffic, Monte-Carlo method, hypothesis, normal distribution, χ2-criterion. ISSN 1025-6415 Доп. НАН України, 2016, №5 35