Процес Пуассона і теорія масового обслуговування — моделювання випадкових прибуттів

1. Процес Пуассона — аксіоми

Процес Пуассона з частотою λ (подій за одиницю часу) — це модель потоку подій, що відбуваються у випадкових точках на осі часу. Він визначається трьома аксіомами:

Простими словами: події відбуваються по одній, вони не "знають" одна про одну, а довгострокова середня частота λ не змінюється. N(t) позначає кількість подій, що відбулися до моменту t — процес є лічильним процесом.

2. Розподіл лічильника подій

Виходячи з наведених вище аксіом, можна вивести (через диференціальне рівняння для P(N(t) = k)), що кількість подій в інтервалі довжини t підпорядковується розподілу Пуассона:

Зверніть увагу: середнє і дисперсія обидва дорівнюють λt — характерна ознака пуассонівських даних. Якщо банк нарахував 45 клієнтів за 3-годинний проміжок (λ = 15/год), імовірність побачити рівно 20 клієнтів наступної години дорівнює P(N(1)=20) = 15²⁰e⁻¹⁵/20! ≈ 4,2%. Коли λt стає великим, розподіл Пуассона добре наближається нормальним розподілом з тими ж середнім і дисперсією (центральна гранична теорема).

3. Проміжки між подіями — експоненційні

Нехай T — час до наступної події. T > t саме тоді, коли за [0, t] не відбулося жодної події:

Це експоненційний розподіл. Отже, процес Пуассона еквівалентно визначається як послідовність проміжків між подіями T₁, T₂, T₃, …, які незалежні й однаково розподілені за експоненційним законом із частотою λ. Це часто найпростіший спосіб його засимулювати: генеруємо експоненційні проміжки й кумулятивно підсумовуємо їх, щоб отримати моменти прибуття.

4. Властивість відсутності пам'яті

Експоненційний розподіл — єдиний неперервний розподіл із властивістю відсутності пам'яті:

Якщо ви чекаєте вже 10 хвилин на автобус, що прибуває як процес Пуассона, розподіл решти вашого очікування абсолютно такий самий, як якби ви щойно прийшли — процес не пам'ятає, скільки часу вже минуло. Це контрінтуїтивно (здається, що автобус уже "запізнюється"), але саме це робить процес Пуассона математично зручним: це неперервний марковський ланцюг.

5. Суперпозиція і проріджування

Два незалежні процеси Пуассона з частотами λ₁ і λ₂, об'єднані в один потік подій, утворюють новий процес Пуассона з частотою λ₁ + λ₂ (суперпозиція). І навпаки, якщо кожна подія процесу з частотою λ незалежно зберігається з імовірністю p і відкидається з імовірністю 1−p, збережені події утворюють процес Пуассона з частотою λp (проріджування).

Проріджування — стандартний прийом для симуляції процесу Пуассона зі змінною в часі частотою λ(t): генеруємо однорідний процес із піковою частотою λ_max, а потім залишаємо кожну кандидатну подію з імовірністю λ(t)/λ_max.

6. Нотація черг і модель M/M/1

Теорія масового обслуговування вивчає системи, у яких об'єкти прибувають, чекають і обслуговуються. Нотація Кендалла A/S/c описує чергу: A — процес прибуттів, S — розподіл часу обслуговування, c — кількість серверів. "M" означає "марковський" (тобто експоненційний — без пам'яті). Найпростіша нетривіальна черга — M/M/1: пуассонівські прибуття з частотою λ, експоненційний час обслуговування з частотою μ, один сервер, порядок "перший прийшов — перший обслужений", необмежена черга очікування.

Система поводиться як марковський ланцюг народження–загибелі: "народження" — це прибуття (з частотою λ з будь-якого стану), "загибелі" — завершення обслуговування (з частотою μ з будь-якого непорожнього стану). Розв'язання рівнянь балансу πₙλ = πₙ₊₁μ і нормування Σπₙ = 1 дає геометричний розподіл, наведений вище.

7. Закон Літтла

Один з наймогутніших, вільних від припущень про розподіл, результатів у всій прикладній теорії ймовірностей, доведений Джоном Літтлом у 1961 році:

Закон Літтла виконується практично для будь-якої стійкої системи масового обслуговування, незалежно від процесу прибуттів, розподілу часу обслуговування чи кількості серверів — це твердження про збереження величини "об'єкт × час" (аргумент потоку), а зовсім не про пуассонівські чи експоненційні припущення. Він дозволяє визначити будь-яку з величин L, λ, W за двома іншими. Кафе, що обслуговує 30 клієнтів/год, у якому зазвичай присутньо 6 клієнтів, має середній час перебування W = L/λ = 6/30 = 0,2 год = 12 хвилин — без жодного вимірювання секундоміром.

8. Багатоканальні черги — M/M/c

Коли c однакових серверів обслуговують одну спільну чергу (M/M/c), інтенсивність навантаження на сервер дорівнює ρ = λ/(cμ), а формула Ерланга-C дає ймовірність того, що клієнт, який щойно прибув, змушений чекати:

Це саме та математика, що лежить в основі оригінальної роботи Ерланга 1917 року з розрахунку телефонних станцій, і вона й досі визначає, скільки серверів (операторів, машин) потрібно виділити кол-центрам і хмарним автомасштабувальникам, щоб час очікування залишався прийнятним.

9. JavaScript: симуляція дискретних подій

Замість того, щоб сліпо довіряти замкненим формулам, можна перевірити їх симуляцією дискретних подій черги M/M/1, просуваючи час від однієї події (прибуття чи завершення обслуговування) до наступної:

// Симуляція дискретних подій черги M/M/1
function expRandom(rate) {
  // вибірка за оберненою функцією розподілу: T = -ln(U) / rate
  return -Math.log(Math.random()) / rate;
}

function simulateMM1(lambda, mu, numArrivals) {
  let clock = 0;
  let serverFreeAt = 0;
  let totalWait = 0;
  let totalSystemTime = 0;
  let areaUnderQueue = 0;   // для середнього L у часі
  let lastEventTime = 0;
  let inSystem = 0;

  for (let i = 0; i < numArrivals; i++) {
    clock += expRandom(lambda);           // наступне прибуття
    areaUnderQueue += inSystem * (clock - lastEventTime);
    lastEventTime = clock;
    inSystem++;

    const serviceStart = Math.max(clock, serverFreeAt);
    const wait = serviceStart - clock;
    const service = expRandom(mu);
    serverFreeAt = serviceStart + service;

    totalWait += wait;
    totalSystemTime += wait + service;
    inSystem--;             // спрощення: FCFS, один сервер
  }

  return {
    Wq: totalWait / numArrivals,          // симульоване середнє очікування
    W:  totalSystemTime / numArrivals,   // симульований середній час у системі
    Wq_theory: (lambda / mu) / (mu - lambda),
    W_theory: 1 / (mu - lambda),
  };
}

// lambda = 4/хв прибуттів, mu = 5/хв обслуговування ⇒ ρ = 0.8
const result = simulateMM1(4, 5, 200000);
console.log(result);
// { Wq: ≈0.799, W: ≈1.0, Wq_theory: 0.8, W_theory: 1.0 }

За результатами симуляції 200 000 клієнтів емпіричні значення Wq і W щільно збігаються з теоретичними (λ/μ)/(μ−λ) і 1/(μ−λ) — хороша перевірка того, що виведення на основі процесу народження–загибелі відповідає реальності. Той самий каркас циклу подій (генеруємо наступну подію, просуваємо годинник, оновлюємо стан) масштабується до M/M/c, черг з пріоритетами й обмежених буферів шляхом розширення логіки оновлення стану.

10. Застосування

Окрім систем обслуговування, процес Пуассона — стандартна модель для підрахунку радіоактивних розпадів, падінь метеоритів, надходжень страхових позовів, мутацій уздовж ланцюга ДНК і спайкових потягів нейронів — будь-якого середовища, де дискретні події розсіяні незалежно в часі чи просторі з приблизно постійною частотою. Коли явище зводиться до "рідкісні події, багато можливостей", граничну теорему Пуассона (біноміальний розподіл з великим n і малим p збігається до Пуассона(np)) пояснює, чому та сама формула k^λ e^(-λ)/k! постійно з'являється знову.