Процесс рождения–смерти

Специальный тип непрерывного во времени марковского процесса

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

Определение

Когда происходит рождение, процесс переходит из состояния n в состояние n  + 1. Когда происходит смерть, процесс переходит из состояния n в состояние  n  − 1. Процесс определяется положительными показателями рождаемости и положительными показателями смертности . Количество особей в процессе в момент времени обозначается как . Процесс обладает свойством Маркова и описывает, как изменяется со временем. Для малых предполагается, что функция удовлетворяет следующим свойствам: ${\displaystyle \{\lambda _{i}\}_{i=0\dots \infty }}$ ${\displaystyle \{\mu _{i}\}_{i=1\dots \infty }}$ ${\displaystyle t}$ ${\displaystyle X(t)}$ ${\displaystyle P_{i,j}(t)={\mathsf {P}}\{X(t+s)=j|X(s)=i\}}$ ${\displaystyle X(t)}$ ${\displaystyle \triangle t>0}$ ${\displaystyle P_{i,j}(\triangle t)}$

${\displaystyle P_{i,i+1}(\triangle t)=\lambda _{i}\triangle t+o(\triangle t),\quad i\geq 0,}$

${\displaystyle P_{i,i-1}(\triangle t)=\mu _{i}\triangle t+o(\triangle t),\quad i\geq 1,}$

${\displaystyle P_{i,i}(\triangle t)=1-(\lambda _{i}+\mu _{i})\triangle t+o(\triangle t),\quad i\geq 1.}$

Этот процесс представлен на следующем рисунке, где состояния процесса (т. е. количество особей в популяции) изображены кружками, а переходы между состояниями обозначены стрелками.

Повторяемость и мимолетность

О повторяемости и неустойчивости в марковских процессах см. раздел 5.3 из «Цепи Маркова» .

Условия повторяемости и преходящести

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

Процесс рождения и смерти повторяется тогда и только тогда, когда

${\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 из теста отношения ), можно вывести условия повторяемости, транзитивности, эргодичности и нулевой повторяемости в более явной форме. ^[3]

Для целых чисел обозначим -ю итерацию натурального логарифма , т.е. и для любого , . ${\displaystyle K\geq 1,}$ ${\displaystyle \ln _{(K)}(x)}$ ${\displaystyle K}$ ${\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}{n\prod _{j=1}^{K}\ln _{(j)}(n)}},}$

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

Процесс рождения и смерти является повторяющимся, если существуют и такие, что для всех ${\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)}}.}$

Более широкие классы процессов рождения и смерти, для которых могут быть установлены условия повторяемости и преходящести, можно найти в ^{[4] .}

Приложение

Рассмотрим одномерное случайное блуждание , которое определяется следующим образом. Пусть , и где принимает значения , а распределение определяется следующими условиями: ${\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}}}$.

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

Случайное блуждание является преходящим, если существуют , и такие, что для всех ${\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.}$

В свою очередь, последняя система дифференциальных уравнений выводится из системы разностных уравнений , описывающих динамику системы за малое время . В течение этого малого времени рассматриваются только три типа переходов: одна смерть, или одно рождение, или отсутствие рождения и смерти. Вероятность первых двух из этих переходов имеет порядок . Другие переходы в течение этого малого интервала, такие как более одного рождения , или более одной смерти , или по крайней мере одно рождение и по крайней мере одна смерть, имеют вероятности, которые имеют меньший порядок, чем , и, следовательно, пренебрежимо малы при выводах. Если система находится в состоянии k , то вероятность рождения в течение интервала равна , вероятность смерти равна , а вероятность отсутствия рождения и смерти равна . Для процесса популяции «рождение» — это переход к увеличению численности популяции на 1, тогда как «смерть» — это переход к уменьшению численности популяции на 1. ${\displaystyle \Delta t}$ ${\displaystyle \Delta t}$ ${\displaystyle \Delta t}$ ${\displaystyle \Delta t}$ ${\displaystyle \Delta t}$ ${\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)}$

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

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

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

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

Использование в филодинамике

Процессы рождения-смерти используются в филодинамике в качестве априорного распределения для филогений , то есть двоичного дерева, в котором события рождения соответствуют ветвям дерева, а события смерти соответствуют узлам листьев. ^[5] В частности, они используются в вирусной филодинамике ^[6] для понимания процесса передачи и того, как число инфицированных людей меняется с течением времени. ^[7]

Использование обобщенных процессов рождения-смерти в филодинамике стимулировало исследования степени, в которой показатели рождаемости и смертности могут быть идентифицированы из данных. ^[8] Хотя модель в целом неидентифицируема, подмножество моделей, которые обычно используются, идентифицируемы. ^[9]

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

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

Очередь М/М/1

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

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

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

${\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

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

${\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 — это многосерверная очередь с серверами 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

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

${\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}$

Очередь М/М/1/К

Очередь 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 в момент времени t, имеют вид

${\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.\,}$

Равновесие

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

Двусторонний процесс рождения и смерти

Двусторонний процесс рождения и смерти определяется аналогично стандартному, с той лишь разницей, что коэффициенты рождаемости и смертности определяются для значений индексного параметра . ^[10] После этого двусторонний процесс рождения и смерти является рекуррентным тогда и только тогда, когда ${\displaystyle \lambda _{i}}$ ${\displaystyle \mu _{i}}$ ${\displaystyle i=0,\pm 1,\pm 2,\ldots }$

${\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}}{\mu _{-n}}}=\infty .}$

Понятия эргодичности и нулевой повторяемости определяются аналогичным образом путем расширения соответствующих понятий стандартного процесса рождения и смерти.

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

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

Примечания

1. Феллер, Уильям (1939). «Die Grundlagen der Volterraschen Theorie des Kampfes ums Dasein in wahrscheinlichkeitstheoretischer Behandlung». Acta Biotheoretica . 5 (1): 11–40. дои : 10.1007/BF01602932.
2. Карлин, Сэмюэл ; МакГрегор, Джеймс (1957). «Классификация процессов рождения и смерти» (PDF) . Труды Американского математического общества . 86 (2): 366–400. doi :10.1090/S0002-9947-1957-0094854-8.
3. Абрамов, Вячеслав М. (2020). «Расширение теста Бертрана–Де Моргана и его применение». The American Mathematical Monthly . 127 (5): 444–448. arXiv : 1901.05843 . doi : 10.1080/00029890.2020.1722551. S2CID  199552015.
4. Абрамов, Вячеслав М. (2022). «Необходимые и достаточные условия сходимости положительных рядов» (PDF) . Журнал классического анализа . 19 (2): 117–125. arXiv : 2104.01702 . doi :10.7153/jca-2022-19-09. S2CID  233025219.
5. Stadler T (декабрь 2010 г.). «Выборка через время в деревьях рождения-смерти». Журнал теоретической биологии . 267 (3): 396–404. Bibcode : 2010JThBi.267..396S. doi : 10.1016/j.jtbi.2010.09.010. PMID  20851708.
6. Kühnert D, Wu CH, Drummond AJ (декабрь 2011 г.). «Филогенетическое и эпидемическое моделирование быстро развивающихся инфекционных заболеваний». Infection, Genetics and Evolution . 11 (8): 1825–41. doi : 10.1016/j.meegid.2011.08.005 . PMC 7106223. PMID  21906695 . 
7. Zarebski AE, du Plessis L, Parag KV, Pybus OG (февраль 2022 г.). «Вычислительно поддающаяся обработке модель рождения-смерти, которая объединяет филогенетические и эпидемиологические данные». PLOS Computational Biology . 18 (2): e1009805. Bibcode : 2022PLSCB..18E9805Z . doi : 10.1371/journal.pcbi.1009805 . PMC 8903285. PMID  35148311. 
8. Louca S, Pennell MW (апрель 2020 г.). «Существующие временные деревья согласуются с множеством историй диверсификации» (PDF) . Nature . 508 (7804): 502–505. Bibcode :2020Natur.580..502L. doi :10.1038/s41586-020-2176-1. PMID  32322065. S2CID  215775763.
9. Легрид Б., Терхорст (август 2022 г.). «Класс идентифицируемых филогенетических моделей рождения–смерти». PNAS . 119 (35): e2119513119. Bibcode :2022PNAS..11919513L. doi :10.1073/pnas.2119513119. PMC 9436344 . PMID  35994663. 
10. Прюитт, Уильям Э. (1963). «Двусторонние процессы рождения и смерти» (PDF) . Труды Американского математического общества . 107 (3): 508–525. doi :10.1090/S0002-9947-1963-0150858-0.

Ссылки

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