Процесс рождения – смерти - Birth–death process

В процесс рождения – смерти (или же процесс рождения и смерти) является частным случаем марковский процесс с непрерывным временем где переходы между состояниями бывают только двух типов: «рождения», которые увеличивают переменную состояния на единицу, и «смерти», которые уменьшают состояние на единицу. Название модели происходит от общего приложения, использования таких моделей для представления текущего размера популяции, где переходы - это буквальные рождения и смерти. Процессы рождения и смерти находят множество приложений в демография, теория массового обслуживания, инженерия производительности, эпидемиология, биология и другие области. Их можно использовать, например, для изучения эволюции бактерии, количество людей с заболеванием в популяции или количество покупателей в очереди в супермаркете.

Когда происходит рождение, процесс уходит из состояния п к п + 1. Когда наступает смерть, процесс уходит из состояния п заявитьп - 1. Процесс определяется рождаемостью. ${\displaystyle \{\lambda _{i}\}_{i=0\dots \infty }}$ и уровень смертности ${\displaystyle \{\mu _{i}\}_{i=1\dots \infty }}$.

Повторяемость и быстротечность

О повторяемости и быстротечности в марковских процессах см. Раздел 5.3. Цепь Маркова.

Условия повторения и быстротечности

Условия повторения и быстротечности были установлены Сэмюэл Карлин и Джеймс МакГрегор.^[1]

Процесс рождения и смерти повторяющийся если и только если

${\displaystyle \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\mu _{n}}{\lambda _{n}}}=\infty .}$

Процесс рождения и смерти эргодический если и только если

${\displaystyle \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\mu _{n}}{\lambda _{n}}}=\infty \quad {\text{and}}\quad \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\lambda _{n-1}}{\mu _{n}}}<\infty .}$

Процесс рождения и смерти нуль-повторяющийся если и только если

${\displaystyle \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\mu _{n}}{\lambda _{n}}}=\infty \quad {\text{and}}\quad \sum _{i=1}^{\infty }\prod _{n=1}^{i}{\frac {\lambda _{n-1}}{\mu _{n}}}=\infty .}$

Используя Расширенная проба Бертрана (см. раздел 4.1.4 из Соотношение тест ) условия повторения, быстротечности, эргодичности и нулевого повторения могут быть получены в более явной форме.^[2]

Для целого числа ${\displaystyle K\geq 1,}$ позволять ${\displaystyle \ln _{(K)}(x)}$ обозначить ${\displaystyle K}$th повторять из натуральный логарифм, т.е. ${\displaystyle \ln _{(1)}(x)=\ln(x)}$ и для любого ${\displaystyle 2\leq k\leq K}$, ${\displaystyle \ln _{(k)}(x)=\ln _{(k-1)}(\ln(x))}$.

Тогда условия повторения и быстротечности процесса рождения и смерти заключаются в следующем.

Процесс рождения и смерти преходящ, если существует ${\displaystyle c>1,}$ ${\displaystyle K\geq 1}$ и ${\displaystyle n_{0}}$ такой, что для всех ${\displaystyle n>n_{0}}$

${\displaystyle {\frac {\lambda _{n}}{\mu _{n}}}\geq 1+{\frac {1}{n}}+{\frac {1}{n}}\sum _{k=1}^{K-1}{\frac {1}{\prod _{j=1}^{k}\ln _{(j)}(n)}}+{\frac {c}{\prod _{j=1}^{K}\ln _{(j)}(n)}},}$

где пустая сумма для ${\displaystyle K=1}$ предполагается равным 0.

Процесс рождения и смерти повторяется, если существует ${\displaystyle K\geq 1}$ и ${\displaystyle n_{0}}$ такой, что для всех ${\displaystyle n>n_{0}}$

${\displaystyle {\frac {\lambda _{n}}{\mu _{n}}}\leq 1+{\frac {1}{n}}+{\frac {1}{n}}\sum _{k=1}^{K}{\frac {1}{\prod _{j=1}^{k}\ln _{(j)}(n)}}.}$

Заявление

Учитывать одномерный случайная прогулка ${\displaystyle S_{t},\ t=0,1,\ldots ,}$ что определяется следующим образом. Позволять ${\displaystyle S_{0}=1}$, и ${\displaystyle S_{t}=S_{t-1}+e_{t},\ t\geq 1,}$ куда ${\displaystyle e_{t}}$ принимает значения ${\displaystyle \pm 1}$, а распределение ${\displaystyle S_{t}}$ определяется следующими условиями:

${\displaystyle {\mathsf {P}}\{S_{t+1}=S_{t}+1|S_{t}>0\}={\frac {1}{2}}+{\frac {\alpha _{S_{t}}}{S_{t}}},\quad {\mathsf {P}}\{S_{t+1}=S_{t}-1|S_{t}>0\}={\frac {1}{2}}-{\frac {\alpha _{S_{t}}}{S_{t}}},\quad {\mathsf {P}}\{S_{t+1}=1|S_{t}=0\}=1,}$

куда ${\displaystyle \alpha _{n}}$ удовлетворять условию ${\displaystyle 0<\alpha _{n}<\min\{C,n/2\},C>0}$.

Описанное здесь случайное блуждание представляет собой дискретное время аналог процесса рождения и смерти (см. Цепь Маркова ) с рождаемостью

${\displaystyle \lambda _{n}={\frac {1}{2}}+{\frac {\alpha _{n}}{n}},}$

и уровень смертности

${\displaystyle \mu _{n}={\frac {1}{2}}-{\frac {\alpha _{n}}{n}}}$.

Таким образом, повторяемость или быстротечность случайного блуждания связана с повторяемостью или быстротечностью процесса рождения и смерти.^[2]

Случайное блуждание является временным, если существуют ${\displaystyle c>1}$, ${\displaystyle K\geq 1}$ и ${\displaystyle n_{0}}$ такой, что для всех ${\displaystyle n>n_{0}}$

${\displaystyle \alpha _{n}\geq {\frac {1}{4}}\left(1+\sum _{k=1}^{K-1}\prod _{j=1}^{k}{\frac {1}{\ln _{(j)}(n)}}+c\prod _{j=1}^{K}{\frac {1}{\ln _{(j)}(n)}}\right),}$

где пустая сумма для ${\displaystyle K=1}$ предполагается равным нулю.

Случайное блуждание является повторяющимся, если существует ${\displaystyle K\geq 1}$ и ${\displaystyle n_{0}}$ такой, что для всех ${\displaystyle n>n_{0}}$

${\displaystyle \alpha _{n}\leq {\frac {1}{4}}\left(1+\sum _{k=1}^{K}\prod _{j=1}^{k}{\frac {1}{\ln _{(j)}(n)}}\right).}$

Стационарное решение

Если процесс рождения и смерти эргодичен, то существует устойчивое состояние вероятности ${\displaystyle \pi _{k}=\lim _{t\to \infty }p_{k}(t),}$ куда ${\displaystyle p_{k}(t)}$ вероятность того, что процесс рождения и смерти находится в состоянии ${\displaystyle k}$ вовремя ${\displaystyle t.}$ Предел существует, независимо от начальных значений ${\displaystyle p_{k}(0),}$ и рассчитывается по соотношениям:

${\displaystyle \pi _{k}=\pi _{0}\prod _{i=1}^{k}{\frac {\lambda _{i-1}}{\mu _{i}}},\quad k=1,2,\ldots ,}$

${\displaystyle \pi _{0}={\frac {1}{1+\sum _{k=1}^{\infty }\prod _{i=1}^{k}{\frac {\lambda _{i-1}}{\mu _{i}}}}}.}$

Эти предельные вероятности получаются из бесконечной системы дифференциальные уравнения за ${\displaystyle p_{k}(t):}$

${\displaystyle p_{0}^{\prime }(t)=\mu _{1}p_{1}(t)-\lambda _{0}p_{0}(t)\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda _{k-1}p_{k-1}(t)+\mu _{k+1}p_{k+1}(t)-(\lambda _{k}+\mu _{k})p_{k}(t),k=1,2,\ldots ,\,}$

и начальное условие ${\displaystyle \sum _{k=0}^{\infty }p_{k}(t)=1.}$

В свою очередь, последняя система дифференциальные уравнения выводится из системы разностные уравнения который описывает динамику системы за малое время ${\displaystyle \Delta t}$. За это короткое время ${\displaystyle \Delta t}$ только три типа переходов считаются одной смертью, или одним рождением, или отсутствием рождения и смерти. Вероятность первых двух из этих переходов равна получатель чего-то ${\displaystyle \Delta t}$. Другие переходы в течение этого небольшого интервала ${\displaystyle \Delta t}$ Такие как более одного рождения, или же больше чем одна смерть, или же хотя бы одно рождение и хотя бы одна смерть имеют вероятности, которые меньшего порядка, чем ${\displaystyle \Delta t}$, и поэтому пренебрежимо малы при выводе. Если система в состоянии k, то вероятность рождения в промежутке ${\displaystyle \Delta t}$ является ${\displaystyle \lambda _{k}\Delta t+o(\Delta t)}$, вероятность смерти составляет ${\displaystyle \mu _{k}\Delta t+o(\Delta t)}$, а вероятность отсутствия рождения и смерти равна ${\displaystyle 1-\lambda _{k}\Delta t-\mu _{k}\Delta t+o(\Delta t)}$. Для демографического процесса «рождение» - это переход к увеличению численность населения на 1, а «смерть» - это переход к уменьшению численность населения Автор: 1.

Примеры процессов рождения-смерти

А чистый процесс рождения это процесс рождения-смерти, где ${\displaystyle \mu _{i}=0}$ для всех ${\displaystyle i\geq 0}$.

А чистый процесс смерти это процесс рождения-смерти, где ${\displaystyle \lambda _{i}=0}$ для всех ${\displaystyle i\geq 0}$.

Модель M / M / 1 и Модель M / M / c, оба используются в теория массового обслуживания, - процессы рождения и смерти, используемые для описания клиентов в бесконечной очереди.

Использование в теории массового обслуживания

В теории очередей процесс рождения и смерти является наиболее фундаментальным примером модель массового обслуживания, то M / M / C / K /${\displaystyle \infty }$/ FIFO (полностью Обозначения Кендалла ) очередь. Это очередь с Пуассоновские прибытия, взятый из бесконечной популяции, и C серверы с экспоненциально распределенный время обслуживания с K места в очереди. Несмотря на предположение о бесконечности населения, эта модель является хорошей моделью для различных телекоммуникационных систем.

M / M / 1 очередь

Основная статья: M / M / 1 очередь

В M / M / 1 это одиночная серверная очередь с бесконечным размером буфера. В неслучайной среде процесс рождения и смерти в моделях очередей, как правило, является долгосрочным средним значением, поэтому средняя скорость прибытия определяется как ${\displaystyle \lambda }$ а среднее время обслуживания как ${\displaystyle 1/\mu }$. Процесс рождения и смерти представляет собой очередь M / M / 1, когда,

${\displaystyle \lambda _{i}=\lambda {\text{ and }}\mu _{i}=\mu {\text{ for all }}i.\,}$

В дифференциальные уравнения для вероятность что система в состоянии k вовремя т находятся

${\displaystyle p_{0}^{\prime }(t)=\mu p_{1}(t)-\lambda p_{0}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+\mu p_{k+1}(t)-(\lambda +\mu )p_{k}(t)\quad {\text{for }}k=1,2,\ldots \,}$

Чистый процесс рождения, связанный с очередью M / M / 1

Чистый процесс рождения с ${\displaystyle \lambda _{k}\equiv \lambda }$ является частным случаем процесса массового обслуживания M / M / 1. У нас есть следующая система дифференциальные уравнения:

${\displaystyle p_{0}^{\prime }(t)=-\lambda p_{0}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)-\lambda p_{k}(t)\quad {\text{for }}k=1,2,\ldots \,}$

При начальном условии ${\displaystyle p_{0}(0)=1}$ и ${\displaystyle p_{k}(0)=0,\ k=1,2,\ldots }$, решение системы

${\displaystyle p_{k}(t)={\frac {(\lambda t)^{k}}{k!}}\mathrm {e} ^{-\lambda t}.}$

То есть (однородный) Пуассоновский процесс это чистый процесс рождения.

M / M / c очередь

Основная статья: M / M / c очередь

M / M / C - это многосерверная очередь с C сервера и бесконечный буфер. Характеризуется следующими параметрами рождения и смерти:

${\displaystyle \mu _{i}=i\mu \quad {\text{ for }}i\leq C-1,\,}$

и

${\displaystyle \mu _{i}=C\mu \quad {\text{ for }}i\geq C,\,}$

с

${\displaystyle \lambda _{i}=\lambda \quad {\text{ for all }}i.\,}$

Система дифференциальных уравнений в этом случае имеет вид:

${\displaystyle p_{0}^{\prime }(t)=\mu p_{1}(t)-\lambda p_{0}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+(k+1)\mu p_{k+1}(t)-(\lambda +k\mu )p_{k}(t)\quad {\text{for }}k=1,2,\ldots ,C-1,\,}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+C\mu p_{k+1}(t)-(\lambda +C\mu )p_{k}(t)\quad {\text{for }}k\geq C.\,}$

Чистый процесс смерти, связанный с очередью M / M / C

Чистый процесс смерти с ${\displaystyle \mu _{k}=k\mu }$ является частным случаем процесса массового обслуживания M / M / C. У нас есть следующая система дифференциальные уравнения:

${\displaystyle p_{C}^{\prime }(t)=-C\mu p_{C}(t),\,}$

${\displaystyle p_{k}^{\prime }(t)=(k+1)\mu p_{k+1}(t)-k\mu p_{k}(t)\quad {\text{for }}k=0,1,\ldots ,C-1.\,}$

При начальном условии ${\displaystyle p_{C}(0)=1}$ и ${\displaystyle p_{k}(0)=0,\ k=0,1,\ldots ,C-1,}$ получаем решение

${\displaystyle p_{k}(t)={\binom {C}{k}}\mathrm {e} ^{-k\mu t}\left(1-\mathrm {e} ^{-\mu t}\right)^{C-k},}$

это представляет версию биномиальное распределение в зависимости от параметра времени ${\displaystyle t}$ (видеть Биномиальный процесс ).

Очередь M / M / 1 / K

Очередь M / M / 1 / K - это очередь одного сервера с размером буфера K. У этой очереди есть приложения в телекоммуникациях, а также в биологии, когда у населения есть предел пропускной способности. В телекоммуникации мы снова используем параметры из очереди M / M / 1 с,

${\displaystyle \lambda _{i}=\lambda \quad {\text{ for }}0\leq i<K,\,}$

${\displaystyle \lambda _{i}=0\quad {\text{ for }}i\geq K,\,}$

${\displaystyle \mu _{i}=\mu \quad {\text{ for }}1\leq i\leq K.\,}$

В биологии, особенно рост бактерий, когда популяция равна нулю, нет возможности расти так,

${\displaystyle \lambda _{0}=0.\,}$

Кроме того, если вместимость представляет собой предел, при котором человек умирает из-за перенаселенности,

${\displaystyle \mu _{K}=0.\,}$

Дифференциальные уравнения для вероятности того, что система находится в состоянии k вовремя т находятся

${\displaystyle p_{0}^{\prime }(t)=\mu p_{1}(t)-\lambda p_{0}(t),}$

${\displaystyle p_{k}^{\prime }(t)=\lambda p_{k-1}(t)+\mu p_{k+1}(t)-(\lambda +\mu )p_{k}(t)\quad {\text{ for }}k\leq K-1,\,}$

${\displaystyle p_{K}^{\prime }(t)=\lambda p_{K-1}(t)-(\lambda +\mu )p_{K}(t),\,}$

${\displaystyle p_{k}(t)=0\quad {\text{ for }}k>K.\,}$

Равновесие

Очередь называется равновесной, если устойчивое состояние вероятности ${\displaystyle \pi _{k}=\lim _{t\to \infty }p_{k}(t),\ k=0,1,\ldots ,}$ существовать. Условие существования этих устойчивое состояние вероятности в случае M / M / 1 очередь является ${\displaystyle \rho =\lambda /\mu <1}$ а в случае Очередь M / M / C является ${\displaystyle \rho =\lambda /(C\mu )<1}$. Параметр ${\displaystyle \rho }$ обычно называется нагрузка параметр или использование параметр. Иногда его еще называют интенсивность движения.

На примере очереди M / M / 1 устойчивое состояние уравнения

${\displaystyle \lambda \pi _{0}=\mu \pi _{1},\,}$

${\displaystyle (\lambda +\mu )\pi _{k}=\lambda \pi _{k-1}+\mu \pi _{k+1}.\,}$

Это можно свести к

${\displaystyle \lambda \pi _{k}=\mu \pi _{k+1}{\text{ for }}k\geq 0.\,}$

Итак, учитывая, что ${\displaystyle \pi _{0}+\pi _{1}+\ldots =1}$, мы получаем

${\displaystyle \pi _{k}=(1-\rho )\rho ^{k}.}$

Смотрите также

• Единица Эрланга
• Теория массового обслуживания
• Модели очередей
• Квази-рождение – смерть
• Процесс Морана

Примечания

1. Карлин, Сэмюэл; МакГрегор, Джеймс (1957). «Классификация процессов рождения и смерти» (PDF). Труды Американского математического общества. 86 (2): 366–400.
2. Абрамов, Вячеслав М. (2020). «Расширение теста Бертрана – Де Моргана и его применение». Американский математический ежемесячник. 127 (5): 444--448. arXiv:1901.05843. Дои:10.1080/00029890.2020.1722551.

Рекомендации

• Latouche, G .; Рамасвами, В. (1999). «Процессы квази-рождения и смерти». Введение в матричные аналитические методы стохастического моделирования (1-е изд.). ASA SIAM. ISBN  0-89871-425-7.
• Новак, М. А. (2006). Эволюционная динамика: изучение уравнений жизни. Издательство Гарвардского университета. ISBN  0-674-02338-2.
• Виртамо, Дж. «Процессы рождения-смерти» (PDF). 38.3143 Теория массового обслуживания. Получено 2 декабря 2019.