Конспект: процессы Пуассона и марковские очереди

Понятия

Однородный процесс Пуассона N(t) имеет независимые стационарные приращения, N(0)=0, вероятность одного события λh+o(h) и нескольких o(h) на малом шаге h. Здесь o(h)/h→0. Сам счётчик не стационарен: среднее растёт со временем.

Генератор Q содержит интенсивности переходов qij вне диагонали и отрицательную суммарную интенсивность выхода на диагонали. Сумма строк 0. Это не таблица вероятностей.

Стационарные доли времени удовлетворяют глобальному балансу πQ=0, суммируются в 1 и неотрицательны. Доли среди скачков могут быть другими.

Что унести

N(t) ~ Pois(λt):
    P(N(t)=k) = exp(-λt)*(λt)^k/k!
    E[N(t)] = Var(N(t)) = λt
промежутки между событиями независимы, Exp(λ)
время до k-го события:
    E[Sk]=k/λ, Var(Sk)=k/λ²
    P(Sk≤t)=P(N(t)≥k)

Независимые потоки складывают интенсивности. Независимые постоянные метки делят поток λ на независимые потоки λpi. Метка, зависящая от очереди или чередования, под эту модель автоматически не попадает.

При условии N(t)=n неупорядоченные времена - независимые U[0,t], а хронологические - их зависимые порядковые статистики. E[Tk | N(t)=n]=tk/(n+1). Условно число событий на [0,s] имеет Bin(n,s/t) и связано с числом на оставшейся части.

В состоянии i:
    выход Exp(qi), qi = сумма qij по j≠i
    следующее j с вероятностью qij/qi
стационарный баланс j:
    сумма входов πi*qij = выход πj*qj

Попарное равновесие достаточно, но не обязательно: односторонний цикл может иметь одинаковые входящий и выходящий потоки без обратных дуг. Для конечного неразложимого процесса при конечных интенсивностях стационарный закон единственен и является пределом. В бесконечном пространстве проверяют нормировку и отсутствие взрыва числа скачков.

Очереди

λ - интенсивность прихода, μ - интенсивность обслуживания одного сервера. K включает обслуживаемую заявку. L - среднее число в системе, W - полное среднее время принятой заявки, Lq и Wq - только ожидание.

В M/M/1: L=λ/(μ−λ), W=1/(μ−λ), Lq=L−ρ, Wq=W−1/μ. У конечной системы доля отказов πK, принятый поток λэфф=λ(1−πK). При λ=μ конечные состояния равновероятны: πk=1/(K+1). У M/M/∞ при k заявках суммарная скорость уходов kμ. Для пустого старта в момент t закон Pois((λ/μ)(1−exp(−μt))).

Закон Литтла: L=λэффW при устойчивом режиме и существующих средних. PASTA объясняет, почему независимый пуассоновский приход видит стационарные доли времени: поток приходов из состояния k равен λπk.

Ловушки джокера

Одна интенсивность на любой интервал. Параметр счётчика - λt, а λt само по себе не равно точной вероятности одного события.

Сложить зависимые потоки. Копирование одной ленты даёт двойные события, а не обычный процесс Пуассона с удвоенной интенсивностью.

Встроенная цепь вместо времени. Одинаковые числа посещений не учитывают разные средние времена пребывания в состояниях.

Применить бесконечную нормировку конечной очереди. При λ≥μ бесконечная M/M/1 не имеет стационара, конечная теряет заявки.

Подставить входящие попытки в Литтла. При потерях нужны принятые заявки, иначе W не относится к тем, кто действительно проходит обслуживание.