16.12: Ланцюги черг дискретного часу

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

Основна теорія

Вступ

У моделі черги клієнти прибувають на станцію для обслуговування. Як завжди, терміни є загальними; ось кілька типових прикладів:

• Клієнтами є особи, а СТО - магазин.
• Клієнти - це запити файлів, а станція технічного обслуговування - веб-сервер.
• Клієнтами є пакети, а СТО - це переробний об'єкт.

Малюнок\(\PageIndex{1}\): Десять клієнтів і сервер

Моделі черги можуть бути досить складними, залежно від таких факторів, як розподіл ймовірностей, що регулює прибуття клієнтів, розподіл ймовірностей, який регулює обслуговування клієнтів, кількість серверів та поведінку клієнтів, коли всі сервери зайняті. Дійсно, теорія черг має свій власний лексикон для позначення деяких з цих факторів. У цьому розділі ми вивчимо одну з найпростіших, дискретних моделей черги. Однак, як ми побачимо, цей дискретний ланцюжок часу вбудований у набагато більш реалістичний процес безперервної черги часу, відомий як черга M/G/1. У загальному сенсі основний інтерес до будь-якої моделі черги - це кількість клієнтів в системі як функція часу, і зокрема, чи можуть сервери адекватно обробляти потік клієнтів.

Наші основні припущення полягають у наступному:

1. Якщо черга порожня в даний момент часу, то в наступний раз прибуває випадкова кількість нових клієнтів.
2. Якщо черга непорожня в даний момент часу, то обслуговується один клієнт і випадкове число нових клієнтів прибуває в наступний раз.
3. Кількість клієнтів, які прибувають в кожен часовий період, утворюють незалежну, однаково розподілену послідовність.

Таким чином, нехай\( X_n \) позначають кількість клієнтів в системі в момент часу\( n \in \N \), а нехай\( U_n \) позначають кількість нових клієнтів, які прибувають вчасно\( n \in \N_+ \). Потім\( \bs{U} = (U_1, U_2, \ldots) \) послідовність незалежних випадкових величин, з загальною функцією щільності ймовірності\( f \) включена\( \N \), і\[ X_{n+1} = \begin{cases} U_{n+1}, & X_n = 0 \\ (X_n - 1) + U_{n+1}, & X_n \gt 0 \end{cases}, \quad n \in \N \]

\( \bs{X} = (X_0, X_1, X_2, \ldots) \)є марковським ланцюгом дискретного часу з простором стану\( \N \) та матрицею ймовірностей переходу,\( P \) заданою\ begin {align} P (0, y) & = f (y),\ quad y\ in\ N\\ P (x, y) & = f (y - x + 1),\ quad x\ in\ N_+,\; y\ in\ {x - 1, x, x + 1,\ ldots\} end {align} Ланцюг\( \bs{X} \) є ланцюг черги з розподілом прибуття, визначеним\( f \).

Доказ

Властивість Маркова і форма матриці переходу випливають з побудови процесу стану\( \bs{X} \) в терміні послідовності ІІД\( \bs{U} \). Починаючи зі стану 0 (порожня черга), випадкова кількість нових клієнтів надходить до наступного блоку часу, що регулюється PDF-файлом\( f \). Звідси ймовірність переходу від стану 0 до стану\( y \) за один крок є\( f(y) \). Починаючи з штату\( x \in \N_+ \), один клієнт обслуговується і випадкова кількість нових клієнтів прибуває до наступного блоку часу, знову регулюється PDF\( f \). Звідси ймовірність переходу від держави\( x \) до держави\( y \in \{x - 1, x, x + 1, \ldots\} \) є\( f[y - (x - 1)] \).

Повторення і швидкоплинність

Відтепер будемо вважати, що\( f(0) \gt 0 \) і\( f(0) + f(1) \lt 1 \). Таким чином, у кожному одиниці часу можливо, що нові клієнти не прибувають або прибувають щонайменше 2 нових клієнтів. Крім того, ми\( m \) дозволимо позначити середнє значення розподілу прибуття, так\( m \) що\[ m = \sum_{x = 0}^\infty x f(x) \] Таким чином середня кількість нових клієнтів, які прибувають протягом періоду часу.

Ланцюг\( \bs{X} \) нескорочувана і аперіодична.

Доказ

У позитивному стані ланцюг може переміщатися хоча б на одну одиницю вправо і може переміщати одну одиницю вліво на наступному кроці. З стану 0 ланцюг може переміщати дві або більше одиниць вправо або залишитися в 0 на наступному кроці. Таким чином, кожен стан призводить до будь-якого іншого стану, тому ланцюг є незвідним. Оскільки 0 веде назад до 0, ланцюг є аперіодичним.

Наша мета в цьому розділі - обчислити ймовірність того, що ланцюг досягає 0, як функція початкового стану (щоб сервер міг обслуговувати всіх клієнтів). Як ми побачимо, між цією проблемою та проблемою обчислення ймовірності вимирання в розгалуженому ланцюжку є деякі цікаві та несподівані паралелі. Як наслідок, ми також зможемо класифікувати ланцюг черг як перехідний або рецидивуючий. Наш основний цікавий параметр\( q = H(1, 0) = \P(\tau_0 \lt \infty \mid X_0 = 1) \), де, як зазвичай,\( H \) є матрицею ймовірності удару і\( \tau_0 = \min\{n \in \N_+: X_n = 0\} \) є першим позитивним часом, коли ланцюг знаходиться в стані 0 (можливо, нескінченно). Таким чином,\( q \) є ймовірність того, що черга з часом спорожніє, починаючи з одного клієнта.

Параметр\( q \) задовольняє такі властивості:

1. \( q = H(x, x - 1) \)для кожного\( x \in \N_+ \).
2. \( q^x = H(x, 0) \)для кожного\( x \in \N_+ \).

Доказ

1. Критичне спостереження полягає в тому, що якщо\( x \in \N_+ \) тоді\( P(x, y) = P(1, y - x + 1) = f(y - x + 1) \) для\( y \in \{x - 1, x, x + 1, \ldots\} \). Таким чином, ланцюг, починаючи і аж до того часу\( x \), коли він досягає\( x - 1 \) (якщо це так), поводиться стохастично, як ланцюг, що починається в стані 1, і до тих пір, поки не досягне 0.
2. Для того, щоб досягти 0, починаючи в стані\( x \in \N_+ \), ланцюг повинен спочатку досягти,\( x - 1 \) а потім від\( x - 1 \) повинен досягти\( x - 2 \), поки остаточно не досягне 0 зі стану 1. Кожна з цих проміжних поїздок має ймовірність\( q \) по частині (а) і є незалежними за властивістю Маркова.

Параметр\( q \) задовольняє рівнянню:\[ q = \sum_{x = 0}^\infty f(x) q^x \]

Доказ

Це випливає з попередньої теореми, обумовлюючи перший стан. \[ \P(\tau_0 \lt \infty \mid X_0 = 1) = \sum_{x=0}^\infty \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = x) \P(X_1 = x \mid X_0 = 1) \]Зверніть увагу спочатку, що\( \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = 0) = 1 = q^0 \). З іншого боку, за властивістю Маркова і попереднім результатом,\[ \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = x) = \P(\tau_0 \lt \infty \mid X_1 = x) = q^x, \quad x \in \N_+ \] звичайно ж\( \P(X_1 = x \mid X_0 = 1) = P(1, x) = f(x) \) для\( x \in \N \).

Зауважте, що це точно таке ж рівняння, яке ми розглядали для розгалуженого ланцюга\( \Phi(q) = q \), а саме, де\( \Phi \) є функція генерації ймовірності розподілу, яка регулює кількість нових клієнтів, які надходять протягом кожного періоду.

Малюнок\(\PageIndex{2}\): Графік\(\phi\) в рецидивуючому випадку

Малюнок\(\PageIndex{3}\): Графік\(\phi\) в перехідному випадку

\( q \)є найменшим\( (0, 1] \) розв'язком рівняння\( \Phi(t) = t \). Більше того

1. Якщо\( m \le 1 \) потім\( q = 1 \) і ланцюг рецидивна.
2. Якщо\( m \gt 1 \) тоді\( 0 \lt q \lt 1 \) і ланцюг перехідний..

Доказ

Це випливає з нашого аналізу розгалужених ланцюгів. Наведені вище графіки показують два випадки. Зверніть увагу, що умова в (а) означає, що в середньому один або менше нових клієнтів прибувають для кожного обслуговуваного клієнта. Умова в (b) означає, що в середньому на кожного обслуговуваного клієнта прибуває більше одного нового клієнта.

Позитивний рецидив

Наша наступна мета - знайти умови для того, щоб ланцюг черг був позитивним повторюваним. Нагадаємо, що\( m \) це середнє значення функції щільності ймовірності\( f \); тобто очікувана кількість нових клієнтів, які прибувають протягом періоду часу. Як і раніше, давайте\( \tau_0 \) позначимо перший позитивний час, що ланцюг знаходиться в стані 0. Припускаємо, що ланцюг рецидивна, значить\( m \le 1 \) і\( \P(\tau_0 \lt \infty) = 1 \).

\( \Psi \)Дозвольте позначити ймовірність генеруючої функції\( \tau_0 \), починаючи з стану 1. Тоді

1. \( \Psi \)також є імовірністю генеруючої функції\( \tau_0 \) запуску в стані 0.
2. \( \Psi^x \)є імовірністю генеруючої функції\( \tau_0 \) запуску в стані\( x \in \N_+ \).

Доказ

1. Імовірності переходу, що починаються в стані 1, такі ж, як ті, що починаються в стані 0:\( P(0, x) = P(1, x) = f(x) \) for\( x \in \N \).
2. Починаючи з стану\( x \in \N_+ \), випадковий час досягнення 0 - це сума часу досягнення\( x - 1 \), додаткового часу,\( x - 2 \) з якого потрібно досягти\( x - 1 \), і так далі, закінчуючи часом досягнення 0 від стану 1. Ці випадкові часи не залежать від властивості Маркова, і кожен має такий же розподіл, як і час досягнення 0 від стану 1 за нашим аргументом вище. Нарешті, нагадаємо, що PGF суми незалежних змінних є добутком відповідних PGF.

\( \Psi(t) = t \Phi[\Psi(t)] \)для\( t \in [-1, 1] \).

Доказ

Ще раз, хитрість полягає в тому, щоб умовити перший стан:\[ \Psi(t) = \E\left(t^{\tau_0} \bigm| X_0 = 1\right) = \sum_{x = 0}^\infty \E\left(t^{\tau_0} \bigm| X_0 = 1, X_1 = x\right) \P(X_1 = x \mid X_0 = 1) \] Спочатку зауважте, що\( \E\left(t^{\tau_0} \bigm| X_0 = 1, X_1 = 0\right) = t^1 = t \Psi^0(t) \). З іншого боку, за властивістю Маркова і попередньою теоремою,\[ \E\left(t^{\tau_0} \bigm| X_0 = 1, X_1 = x\right) = \E\left(t^{1 + \tau_0} \bigm| X_0 = x\right) = t \E\left(t^{\tau_0} \bigm| X_0 = x\right) = t \Psi^x(t), \quad x \in \N_+ \] Звичайно\( \P(X_1 = x \mid X_0 = 1) = P(1, x) = f(x) \). Отже, ми маємо\[ \Psi(t) = \sum_{x=0}^\infty t \Psi^x(t) f(x) = t \Phi[\Psi(t)] \] PGF будь-якої змінної, яка приймає позитивні цілі значення визначається на\( [-1, 1] \), і відображає цей інтервал назад у себе. Отже, представництво дійсне принаймні для\( t \in [-1, 1] \).

Похідне від\( \Psi \) є\[ \Psi^\prime(t) = \frac{\Phi[\Psi(t)]}{1 - t \Phi^\prime[\Psi(t)]}, \quad t \in (-1, 1) \]

Доказ

Нагадаємо, що ПГФ є нескінченно диференційованим на відкритому інтервалі збіжності. Отже, використовуючи результат в попередній теоремі і правила продукту і ланцюга,\[ \Psi^\prime(t) = \Phi[\Psi(t)] + t \Phi^\prime[\Psi(t)] \Psi^\prime(t) \] Рішення для\( \Psi^\prime(t) \) дає результат.

Як завжди, нехай\( \mu_0 = \E(\tau_0 \mid X_0 = 0) \), середній час повернення до стану 0 починаючи з стану 0. Тоді

1. \( \mu_0 = \frac{1}{1 - m} \)якщо\( m \lt 1 \) і тому ланцюг позитивний рецидивний.
2. \( \mu_0 = \infty \)якщо\( m = 1 \) і тому ланцюг є нульовим повторюваним.

Доказ

Нагадаємо,\( \Psi \) що імовірність генерує функцію\( \tau_0 \), починаючи з 0. З основних властивостей PGF ми знаємо\( \Phi(t) \uparrow 1 \), що\( \Psi(t) \uparrow 1 \),\( \Phi^\prime(t) \uparrow m \), і\( \Psi^\prime(t) \uparrow \mu_0 \) як\( t \uparrow 1 \). Таким чином, вводячи\( t \uparrow 1 \) в результаті попередньої теореми, у нас є\( \mu_0 = 1 \big/ (1 - m) \) якщо\( m \lt 1 \) і\( \mu_0 = \infty \) якщо\( m = 1 \).

Таким чином, підсумовуючи, ланцюг черги є позитивним повторюваним якщо\( m \lt 1 \), нульовий повторюваний якщо\( m = 1 \), і перехідний, якщо\( m > 1 \). Оскільки\( m \) очікувана кількість нових клієнтів, які прибувають протягом періоду обслуговування, результати, безумовно, є розумними.

Обчислювальні вправи

Розглянемо ланцюжок черги з функцією щільності ймовірності прибуття\( f(0) = 1 - p \),\( f \) заданої\( f(2) = p \), де\( p \in (0, 1) \) є параметром. Таким чином, в кожен період часу або не приїжджають нові клієнти, або прибувають двоє.

1. Знайдіть матрицю переходу\( P \).
2. Знайдіть середнє\( m \) значення розподілу прибуття.
3. Знайдіть генеруючу функцію\( \Phi \) розподілу прибуття.
4. Знайдіть ймовірність того\( q \), що черга з часом спорожніє, починаючи з одного клієнта.
5. Класифікуйте ланцюг як перехідний, нульовий рекуррентний або позитивний рекуррент.
6. У позитивному повторюваному випадку знайдіть\( \mu_0 \), середній час повернення 0.

Відповідь

1. \( P(0, 0) = 1 - p \),\( P(0, 2) = p \). Для\( x \in \N_+ \),\( P(x, x - 1) = 1 - p \),\( P(x, x + 1) = p \).
2. \( m = 2 p \).
3. \(\Phi(t) = p t^2 + (1 - p)\)для\( t \in \R \).
4. \( q = 1 \)якщо\(0 \lt p \le \frac{1}{2} \) і\( q = \frac{1 - p}{p} \) якщо\( \frac{1}{2} \lt p \lt 1 \).
5. Ланцюг є перехідним if\( p \gt \frac{1}{2} \), null повторюваним if\( p = \frac{1}{2} \) і позитивним рецидивуючим if\( p \lt \frac{1}{2} \).
6. \( \mu_0 = \frac{1}{1 - 2 p} \)для\( p \lt \frac{1}{2} \).

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{1}{3} \)

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{2}{3} \)

Розглянемо ланцюжок черги, розподіл прибуття якого є геометричним розподілом на\( \N \) з параметром\( 1 - p \), де\( p \in (0, 1) \). Таким чином\( f(n) = (1 - p) p^n \) для\( n \in \N \).

1. Знайдіть матрицю переходу\( P \).
2. Знайдіть середнє\( m \) значення розподілу прибуття.
3. Знайдіть генеруючу функцію\( \Phi \) розподілу прибуття.
4. Знайдіть ймовірність того\( q \), що черга з часом спорожніє, починаючи з одного клієнта.
5. Класифікуйте ланцюг як перехідний, нульовий рекуррентний або позитивний рекуррент.
6. У позитивному повторюваному випадку знайдіть\( \mu_0 \), середній час повернення 0.

Відповідь

1. \( P(0, y) = (1 - p) p^y \)для\( y \in \N \). Для\( x \in \N_+ \),\( P(x, y) = (1 - p) p^{y - x + 1} \) для\( y \in \{x - 1, x, x + 1, \ldots\} \).
2. \( m = \frac{p}{1 - p} \).
3. \(\Phi(t) = \frac{1 - p}{1 - p t}\)для\( \left|t\right| \lt \frac{1}{p} \).
4. \( q = 1 \)якщо\(0 \lt p \le \frac{1}{2} \) і\( q = \frac{1 - p}{p} \) якщо\( \frac{1}{2} \lt p \lt 1 \).
5. Ланцюг є перехідним if\( p \gt \frac{1}{2} \), null повторюваним if\( p = \frac{1}{2} \) і позитивним рецидивуючим if\( p \lt \frac{1}{2} \).
6. \( \mu_0 = \frac{1 - p}{1 - 2 p} \)для\( p \lt \frac{1}{2} \).

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{1}{3} \)

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{2}{3} \)

Цікаво, що параметр\( q \) і класифікація ланцюга однакові у двох останніх моделей.

Розглянемо ланцюжок черги, розподіл прибуття якого є розподілом Пуассона з параметром\( m \in (0, \infty) \). Таким чином\( f(n) = e^{-m} m^n / n! \) для\( n \in \N \). Знайдіть кожне з наведених нижче варіантів:

1. матриця переходу\( P \)
2. Середнє\( m \) значення розподілу прибуття.
3. Генеруюча функція\( \Phi \) розподілу прибуття.
4. Орієнтовне значення\( q \) коли\( m = 2 \) і коли\( m = 3 \).
5. Класифікуйте ланцюг як перехідний, нульовий рекуррентний або позитивний рекуррент.
6. У позитивному повторюваному випадку знайдіть\( \mu_0 \), середній час повернення 0.

Відповідь

1. \( P(0, y) = e^{-m} m^y / y! \)для\( y \in \N \). Для\( x \in \N_+ \),\( P(x, y) = e^{-m} m^{y - x + 1} \big/ (y - x + 1)! \) для\( y \in \{x - 1, x, x + 1, \ldots\} \).
2. Параметр\( m \) - це середнє значення розподілу Пуассона, тому позначення узгоджені.
3. \(\Phi(t) = e^{m (t - 1)}\)для\( t \in \R \).
4. \( q = 1 \)якщо\(0 \lt m \le 1 \). Якщо\( m \gt 1 \) тоді\( q \) є розв'язком рівняння,\( e^{m (q - 1)} = q \) яке може бути виражене через спеціальну функцію, відому як \( W \)функція Ламберта:\[ q = -\frac{1}{m} W\left(-m e^{-m}\right) \] For\( m = 2 \),\( q \approx 0.20319 \).\( (0, 1) \) Для\( m = 3 \),\( q \approx 0.059520 \).
5. Ланцюг є перехідним if\( m \gt 1 \), null повторюваним if\( m = 1 \) і позитивним рецидивуючим if\( m \lt 1 \).
6. \( \mu_0 = \frac{1}{1 - m} \)для\( m \lt 1 \).

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( m = \frac{1}{2} \)

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( m = 2 \)