Przybliżenie ruchu ciężkiego

W teorii kolejek , dyscyplinie w ramach matematycznej teorii prawdopodobieństwa , przybliżenie dużego ruchu (czasami twierdzenie o granicy dużego ruchu lub przybliżenie dyfuzji ) to dopasowanie modelu kolejkowania do procesu dyfuzji w pewnych warunkach ograniczających parametry modelu. Pierwszy taki wynik opublikował John Kingman , który wykazał, że kiedy parametr wykorzystania kolejki M/M/1 jest blisko 1, przeskalowaną wersję procesu długości kolejki można dokładnie przybliżyć za pomocą odbitego ruchu Browna .

Warunki ruchu ciężkiego

Przybliżenia dużego natężenia ruchu są zazwyczaj określane dla procesu X ( t ) opisującego liczbę klientów w systemie w czasie t . Uzyskuje się je, rozważając model pod granicznymi wartościami niektórych parametrów modelu, dlatego aby wynik był skończony, model musi zostać przeskalowany o współczynnik n , oznaczony

${\ Displaystyle {\ kapelusz {X}} _ {n} (t) = {\ Frac {X (nt) - \ mathbb {E} (X(nt))}{\sqrt {n}}}}$

a granicę tego procesu przyjmuje się jako n → ∞.

Istnieją trzy klasy reżimów, w których takie przybliżenia są ogólnie brane pod uwagę.

1. Liczba serwerów jest stała, a natężenie ruchu (wykorzystanie) zwiększa się do 1 (od dołu). Przybliżenie długości kolejki jest odbitym ruchem Browna .
2. Natężenie ruchu jest stałe, a liczba serwerów i wskaźnik przybycia są zwiększane do nieskończoności. Tutaj granica długości kolejki jest zbieżna z rozkładem normalnym .
3. Wielkość β jest ustalona gdzie

$_$

. s reprezentuje _ _ Natężenie ruchu i liczba serwerów są zwiększane do nieskończoności, a proces ograniczania jest hybrydą powyższych wyników. Ten przypadek, opublikowany po raz pierwszy przez Halfina i Whitta, jest często nazywany reżimem Halfina-Whitta lub reżimem opartym na jakości i wydajności (QED).

Wyniki dla kolejki G/G/1

Twierdzenie 1. Rozważ sekwencję kolejek G/G/1 indeksowanych przez ${\ displaystyle j}$ . Dla kolejki $displaystyle S_$ oznacza losowy czas między przyjazdami, $j}}$$\$ oznacza losowy czas obsługi niech ${\ Displaystyle \ rho _ {j} = {\ Frac {\ lambda _ {j}}} {\ mu _ {j}}}}$ oznaczyć natężenie ruchu za pomocą ${\ Displaystyle {\ Frac {1} {\ lambda _ {j}}} = E (T_ {j})}$ i ${\ Displaystyle {\ Frac {1}{\mu _{j}}}=E(S_{j})}$ ; niech ${\ displaystyle W_ {q, j}}$ oznacza czas oczekiwania w kolejce na klienta w stanie ustalonym; Niech ${\ Displaystyle \ alfa _ {j} = - E [S_ {j} -T_ {j}]}$ i ${\ Displaystyle \ beta _ {j} ^ {2} = \ nazwa operatora {var} [S_ {j} -T_ {j}];}$

Załóżmy, że ${\ Displaystyle T_ {j} {\ xrightarrow {d}} T}$ , ${\ Displaystyle S_ {j} {\ xrightarrow {d}} S}$ i ${\ Displaystyle \ rho _ {j} \ rightarrow 1}$ . Następnie

${\ Displaystyle {\ Frac {2 \ alfa _ {j}}} {\ beta _ {j} ^ {2}}} W_ {q, j }{\xrightarrow {d}}\exp(1)}$

pod warunkiem że:

(a) ${\ Displaystyle \ nazwa operatora {Var} [ST]> 0}$

(b) dla niektórych ${\ Displaystyle \ delta > 0}$ , ${\ Displaystyle E [S_ {j} ^ {2+ \ delta}]}$ i ${\ Displaystyle E [T_ {j} ^ {2+ \ delta}]}$ oba są mniejsze niż pewna stała $displaystyle$ wszystkich $j}$ .

Argument heurystyczny

• Czas oczekiwania w kolejce

Niech ${\ Displaystyle U ^ {(n)} = S ^ {(n)} -T ^ {(n)}}$ będzie różnicą między n-tym czasem obsługi i n-ty czas między przyjazdami; Niech ${\ Displaystyle W_ {q} ^ {(n)}}$ będzie czasem oczekiwania w kolejce n-tego klienta;

Wtedy z definicji:

${\ Displaystyle W_ {q} ^ {(n)} = \ max (W_ {q} ^ {(n- 1)}+U^{(n-1)},0)}$

Po obliczeniu rekurencyjnym mamy:

${\ Displaystyle W_ {q} ^ {(n)} = \ max (U ^ {(1)} + \ cdots + U ^ {(n-1)}, U ^ {(2)} + \ cdots + U ^{(n-1)},\ldots ,U^{(n-1)},0)}$

• Spacer losowy

Niech ${\ Displaystyle P ^ {(k)} = \ suma _ {i = 1} ^ {k} U ^ {(ni)}}$ z ${\ Displaystyle U ^ {(i)}}$ są id; Zdefiniuj $_$ _ ${\ Displaystyle \ beta ^ {2} = \ nazwa operatora {var} [U ^ {(i)}]}$ ;

Następnie mamy

${\ Displaystyle E [P ^ {(k)}] = - k \ alfa}$

${\ Displaystyle \ operatorname {var} [P^{(k)}]=k\beta ^{2}}$

${\ Displaystyle W_ {q} ^ {(n)} = \ max _ {n-1 \ geq k \ geq 0} P ^ {(k)};}$

$= \ sup _ {k \ geq 0} P ^ {(k)}}$ sup biorąc limit nad ${\ displaystyle n}$ .

Zatem czas oczekiwania w kolejce n-tego klienta $z$ najwyższą wartością spaceru

• Przybliżenie ruchów Browna

Spacer losowy można przybliżyć ruchem Browna , gdy rozmiary skoków zbliżają się do 0, a czasy między skokami zbliżają się do 0.

Mamy ${\ Displaystyle P ^ {(0)} = 0}$ i ${\ Displaystyle P ^ {(k)}}$ ma niezależne i stacjonarne przyrosty . natężenie ruchu zbliża się 1 i ma tendencję do $\ infty}$$Displaystyle$$,$ mamy ${\ Displaystyle P ^ {(t)} \ \ sim \ \ mathbb {N} (- \ alfa t, \ beta ^ {2} t)} po zastąpieniu$ k $\ Displaystyle k}$ ciągłą wartością ${\ displaystyle t}$ zgodnie z funkcjonalnym centralnym twierdzeniem granicznym . Zatem czas oczekiwania w kolejce tego $.$ można przybliżyć supremum ruchu Browna z ujemnym dryfem

• Supremum ruchów Browna

Twierdzenie 2. Niech $będzie$ ruchem Browna z dryfem $się$$niech$ standardowym od początku i ${\ Displaystyle M_ {t} = \ sup _ {0 \ równoważnik s \ równoważnik t} X (s)}$

jeśli ${\ Displaystyle \ mu \ równoważnik 0}$

${\ Displaystyle \ lim _ {t \ strzałka w prawo \ infty} P (M_ {t}> x) = \ exp (2 \ mu x / \ sigma ^ {2}), x \ geq 0;}$

W przeciwnym razie

${\ Displaystyle \ lim _ {t \ strzałka w prawo \ infty} P (M_ {t} \ geq x) = 1, x \ geq 0.}$

Wniosek

${\ Displaystyle W_ {q} ^ {(\ infty)} \ gruby \ exp \ lewo ({\ Frac {2 \ alfa}} {\ beta ^ {2} }}\right)}$ w warunkach dużego natężenia ruchu

Zatem twierdzenie o ograniczeniu ruchu ciężkiego (Twierdzenie 1) jest argumentowane heurystycznie. Dowody formalne zwykle przebiegają według innego podejścia, które obejmuje funkcje charakterystyczne .

Przykład

Rozważ kolejkę M / G / 1 ze wskaźnikiem przybycia $=$ średnim czasem obsługi . ${\ Frac {1} {\ mu} }}$ i wariancja czasu obsługi ${\ Displaystyle \ nazwa operatora {var} [S] = \ sigma _ {B} ^ {2}}$ . Jaki jest średni czas oczekiwania w kolejce w stanie ustalonym ?

Dokładny średni czas oczekiwania w kolejce w stanie ustalonym jest określony wzorem:

${\ Displaystyle W_ {q} = {\ Frac {\ rho ^ {2} + \ lambda ^ {2} \ sigma _ {B} ^ {2}}{2\lambda (1-\rho )}}}$

Odpowiednie przybliżenie ruchu ciężkiego:

${\ Displaystyle W_ {q} ^ {(H)} = {\ Frac {\ lambda ({\ Frac {1} {\ lambda ^ {2}}} + \ sigma _ {B} ^ {2})} 2(1-\rho )}}.}$

Względny błąd aproksymacji ruchu ciężkiego:

${\ Displaystyle {\ Frac {W_ {q} ^ {(H)} -W_ {q}} {W_ {q }}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}}$

Tak więc, gdy mamy: ${\ Displaystyle \ rho \ rightarrow 1}$

${\ Displaystyle {\ Frac {W_ {q} ^ {(H)} -W_ {q}} {W_ {q}}} \ rightarrow 0.}$

Linki zewnętrzne

• Kolejka G/G/1 autorstwa Siergieja Fossa