Разветвленный процесс

Вид стохастического процесса

В теории вероятностей ветвящийся процесс — это тип математического объекта, известного как стохастический процесс , который состоит из наборов случайных величин, индексированных некоторым набором, обычно натуральными или неотрицательными действительными числами. Первоначальной целью ветвящихся процессов было служить математической моделью популяции, в которой каждая особь в поколении  производит некоторое случайное число особей в поколении  , в соответствии, в простейшем случае, с фиксированным распределением вероятностей , которое не меняется от особи к особи. ^[1] Ветвящиеся процессы используются для моделирования воспроизводства; например, особи могут соответствовать бактериям, каждая из которых производит 0, 1 или 2 потомков с некоторой вероятностью за одну единицу времени. Ветвящиеся процессы также могут использоваться для моделирования других систем с похожей динамикой, например, распространения фамилий в генеалогии или распространения нейтронов в ядерном реакторе . ${\displaystyle n}$ ${\displaystyle n+1}$

Центральным вопросом в теории ветвящихся процессов является вероятность окончательного вымирания , когда не существует ни одной особи после некоторого конечного числа поколений. Используя уравнение Вальда , можно показать, что, начиная с одной особи в нулевом поколении, ожидаемый размер поколения  n равен  μ ^n, где μ — ожидаемое число детей каждой особи. Если μ < 1, то ожидаемое число особей быстро стремится к нулю, что подразумевает окончательное вымирание с вероятностью 1 по неравенству Маркова . В качестве альтернативы, если μ > 1, то вероятность окончательного вымирания меньше 1 (но не обязательно равна нулю; рассмотрим процесс, в котором каждая особь имеет либо 0, либо 100 детей с равной вероятностью. В этом случае μ = 50, но вероятность окончательного вымирания больше 0,5, поскольку это вероятность того, что первая особь имеет 0 детей). Если μ  = 1, то окончательное вымирание происходит с вероятностью 1, если только каждая особь всегда не имеет ровно одного ребенка.

В теоретической экологии параметр μ ветвящегося процесса называется базовой скоростью размножения .

Математическая формулировка

Наиболее распространенной формулировкой ветвящегося процесса является формула процесса Гальтона–Уотсона . Пусть Z _n обозначает состояние в периоде n (часто интерпретируемое как размер поколения  n ), а X _n,i — случайная величина, обозначающая число прямых потомков элемента i в периоде n , где X _n,i — независимые и одинаково распределенные случайные величины по всем n  ∈{ 0, 1, 2, ...} и i  ∈ {1, ...,  Z _n }. Тогда рекуррентное уравнение имеет вид

${\displaystyle Z_{n+1}=\sum _{i=1}^{Z_{n}}X_{n,i}}$

при Z0 ₌ 1.

В качестве альтернативы, процесс ветвления можно сформулировать как случайное блуждание . Пусть S _i обозначает состояние в периоде i , а X _i — случайная величина, которая является iid по всем i . Тогда рекуррентное уравнение имеет вид

${\displaystyle S_{i+1}=S_{i}+X_{i+1}-1=\sum _{j=1}^{i+1}X_{j}-i}$

с S ₀ = 1. Чтобы получить некоторое интуитивное представление об этой формулировке, представьте себе прогулку, где цель состоит в посещении каждого узла, но каждый раз, когда посещается ранее не посещенный узел, открываются дополнительные узлы, которые также должны быть посещены. Пусть S _i представляет собой количество открытых, но не посещенных узлов в периоде i , а X _i представляет собой количество новых узлов, которые открываются при посещении узла i . Тогда в каждом периоде количество открытых, но не посещенных узлов равно количеству таких узлов в предыдущем периоде плюс новые узлы, которые открываются при посещении узла, минус посещенный узел. Процесс заканчивается, когда все открытые узлы посещены.

Непрерывные разветвленные процессы

Для дискретных по времени ветвящихся процессов «время ветвления» фиксируется равным 1 для всех индивидуумов. Для непрерывных по времени ветвящихся процессов каждый индивидуум ждет случайное время (которое является непрерывной случайной величиной), а затем делится в соответствии с заданным распределением. Время ожидания для разных индивидуумов независимы и независимы с числом потомков. В общем случае время ожидания является экспоненциальной переменной с параметром λ для всех индивидуумов, так что процесс является марковским.

Проблема вымирания для процесса Гальтона-Уотсона

Окончательная вероятность вымирания определяется по формуле

${\displaystyle \lim _{n\to \infty }\Pr(Z_{n}=0).}$

Для любых нетривиальных случаев (тривиальными являются случаи, в которых вероятность отсутствия потомства равна нулю для каждого члена популяции — в таких случаях вероятность окончательного вымирания равна 0) вероятность окончательного вымирания равна единице, если μ  ≤ 1, и строго меньше единицы, если μ  > 1.

Процесс можно проанализировать с помощью метода функции генерации вероятности . Пусть p ₀ ,  p ₁ ,  p ₂ , ... будут вероятностями производства 0, 1, 2, ... потомков каждой особью в каждом поколении. Пусть d _m будет вероятностью вымирания к m ^-му поколению. Очевидно, d ₀ = 0. Поскольку вероятности для всех путей, которые ведут к 0 к m ^-му поколению, должны быть сложены, вероятность вымирания не убывает в поколениях. То есть,

${\displaystyle 0=d_{0}\leq d_{1}\leq d_{2}\leq \cdots \leq 1.}$

Следовательно, d _m сходится к пределу d , а d — это конечная вероятность вымирания. Если в первом поколении есть j потомков, то для того, чтобы вымереть к m-му поколению, каждая из этих линий должна вымереть за m  − 1 поколений. Поскольку они развиваются независимо, вероятность равна ( d _{m −1} ) ^j . Таким образом,

${\displaystyle d_{m}=p_{0}+p_{1}d_{m-1}+p_{2}(d_{m-1})^{2}+p_{3}(d_{m-1})^{3}+\cdots .\,}$

Правая часть уравнения — это функция, производящая вероятность. Пусть h ( z ) — обычная функция, производящая для p _i :

${\displaystyle h(z)=p_{0}+p_{1}z+p_{2}z^{2}+\cdots .\,}$

Используя производящую функцию, предыдущее уравнение становится

${\displaystyle d_{m}=h(d_{m-1}).\,}$

Так как d _m → d , то d можно найти, решив

${\displaystyle d=h(d).\,}$

Это также эквивалентно нахождению точек пересечения линий y  =  z и y  =  h ( z ) для  z  ≥ 0. y = z — прямая линия. y  =  h ( z ) — возрастающая (так как ) и выпуклая (так как ) функция. Существует не более двух точек пересечения. Поскольку (1,1) всегда является точкой пересечения для двух функций, существует только три случая: ${\displaystyle h'(z)=p_{1}+2p_{2}z+3p_{3}z^{2}+\cdots \geq 0}$ ${\displaystyle h''(z)=2p_{2}+6p_{3}z+12p_{4}z^{2}+\cdots \geq 0}$

Три случая y = h ( z ) пересекаются с y = z .

Случай 1 имеет еще одну точку пересечения при z < 1 (см. красную кривую на графике).

Случай 2 имеет только одну точку пересечения при z = 1. (См. зеленую кривую на графике)

Случай 3 имеет еще одну точку пересечения при z > 1. (См. черную кривую на графике)

В случае 1 вероятность окончательного вымирания строго меньше единицы. Для случаев 2 и 3 вероятность окончательного вымирания равна единице.

Заметив, что h′ (1) =  p ₁  + 2 p ₂  + 3 p ₃  + ... =  μ — это в точности ожидаемое число потомков, которое может произвести родитель, можно сделать вывод, что для ветвящегося процесса с производящей функцией h ( z ) для числа потомков данного родителя, если среднее число потомков, произведенных одним родителем, меньше или равно единице, то окончательная вероятность вымирания равна единице. Если среднее число потомков, произведенных одним родителем, больше единицы, то окончательная вероятность вымирания строго меньше единицы.

Процессы ветвления, зависящие от размера

Наряду с обсуждением более общей модели процессов ветвления, известной как возраст-зависимые процессы ветвления Гримметта ^[2] , в которых люди живут более одного поколения, Кришна Атрея определил три различия между процессами ветвления, зависящими от размера, которые имеют общее применение. Атрея определяет три класса процессов ветвления, зависящих от размера, как докритические, стабильные и сверхкритические меры ветвления. Для Атрея центральные параметры имеют решающее значение для контроля того, следует ли избегать докритического и сверхкритического нестабильного ветвления. ^[3] Процессы ветвления, зависящие от размера, также обсуждаются в рамках темы процесса ветвления, зависящего от ресурсов ^[4].

Пример проблемы вымирания

Предположим, что родитель может произвести максимум двух потомков. Вероятность вымирания в каждом поколении составляет:

${\displaystyle d_{m}=p_{0}+p_{1}d_{m-1}+p_{2}(d_{m-1})^{2}.\,}$

при d ₀  = 0. Для определения предельной вероятности вымирания нам необходимо найти d , удовлетворяющее условию d  =  p ₀  +  p ₁ d +  p ₂ d ² .

Если взять в качестве примера вероятности для числа рожденных потомков p ₀  = 0,1, p ₁  = 0,6 и p ₂  = 0,3, то вероятность вымирания для первых 20 поколений будет следующей:

В этом примере мы можем алгебраически решить, что d  = 1/3, и это значение, к которому стремится вероятность вымирания с увеличением числа поколений.

Моделирование ветвящихся процессов

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

Многотипные ветвящиеся процессы

В многотипных ветвящихся процессах индивидуумы не идентичны, но могут быть классифицированы по n типам. После каждого временного шага индивидуум типа i будет производить индивидуумов разных типов, и , случайный вектор, представляющий количество детей разных типов, удовлетворяет распределению вероятностей на . ${\displaystyle \mathbf {X} _{i}}$ ${\displaystyle \mathbb {N} ^{n}}$

Например, рассмотрим популяцию раковых стволовых клеток (CSC) и нестволовых раковых клеток (NSCC). После каждого временного интервала каждая CSC имеет вероятность произвести две CSC (симметричное деление), вероятность произвести одну CSC и одну NSCC (асимметричное деление), вероятность произвести одну CSC (стагнация) и вероятность не произвести ничего (смерть); каждая NSCC имеет вероятность произвести две NSCC (симметричное деление), вероятность произвести одну NSCC (стагнация) и вероятность не произвести ничего (смерть). ^[8] ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{3}}$ ${\displaystyle 1-p_{1}-p_{2}-p_{3}}$ ${\displaystyle p_{4}}$ ${\displaystyle p_{5}}$ ${\displaystyle 1-p_{4}-p_{5}}$

Закон больших чисел для многотипных ветвящихся процессов

Для многотипных ветвящихся процессов, в которых популяции разных типов растут экспоненциально, пропорции разных типов почти наверняка сходятся к постоянному вектору при некоторых мягких условиях. Это усиленный закон больших чисел для многотипных ветвящихся процессов.

Для случаев непрерывного времени пропорции ожиданий популяции удовлетворяют системе ОДУ , которая имеет единственную притягивающую неподвижную точку. Эта неподвижная точка — просто вектор, к которому сходятся пропорции в законе больших чисел.

Монография Атрейи и Нея ^[9] суммирует общий набор условий, при которых этот закон больших чисел справедлив. Позже появились некоторые улучшения за счет отбрасывания различных условий. ^{[10] [11]}

Другие ветвящиеся процессы

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

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

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

• Процесс Гальтона-Уотсона
• Случайное дерево
• Случайное блуждание с ветвлениями
• Процесс ветвления, зависящий от ресурсов
• Теорема Брусса–Дюринкса
• Мартингейл (теория вероятностей)
• Суперпроцесс

Ссылки

1. Атрея, КБ (2006). «Процесс разветвления». Энциклопедия окружающей среды . дои : 10.1002/9780470057339.vab032. ISBN 978-0471899976.
2. GR Grimmett и DR Stirzaker, Вероятность и случайные процессы, 2-е изд., Clarendon Press, Оксфорд, 1992.
3. Кришна Атрея и Питер Джагерс. Ветвящиеся процессы . Спрингер. 1973.
4. Ф. Томас Брусс и М. Дюринкс (2015) «Ресурсозависимые ветвящиеся процессы и оболочка обществ», Annals of Applied Probability. 25: 324–372.
5. Хаген, О.; Хартманн, К.; Стил, М.; Штадлер, Т. (2015-05-01). «Видообразования, зависящие от возраста, могут объяснить форму эмпирических филогений». Systematic Biology . 64 (3): 432–440. doi :10.1093/sysbio/syv001. ISSN  1063-5157. PMC 4395845 . PMID  25575504. 
6. Хаген, Оскар; Андерманн, Тобиас; Квенталь, Тиаго Б.; Антонелли, Александр; Сильвестро, Даниэле (май 2018 г.). «Оценка вымирания, зависящего от возраста: сопоставление данных из ископаемых и филогений». Systematic Biology . 67 (3): 458–474. doi : 10.1093/sysbio/syx082 . PMC 5920349 . PMID  29069434. 
7. Хаген, Оскар; Штадлер, Таня (2018). «TreeSimGM: Моделирование филогенетических деревьев в рамках общих моделей Беллмана–Харриса со сдвигами видообразования и вымирания, специфичными для конкретной линии, в R». Методы в экологии и эволюции . 9 (3): 754–760. doi :10.1111/2041-210X.12917. ISSN  2041-210X. PMC 5993341. PMID 29938014  . 
8. Чэнь, Сюфан; Ван, Юэ; Фэн, Тяньцюань; И, Мин; Чжан, Синган; Чжоу, Да (2016). «Выход за пределы и фенотипическое равновесие в характеристике динамики рака обратимой фенотипической пластичности». Журнал теоретической биологии . 390 : 40–49. arXiv : 1503.04558 . doi : 10.1016/j.jtbi.2015.11.008. PMID  26626088. S2CID  15335040.
9. Атрея, Кришна Б.; Ней, Питер Э. (1972). Ветвящиеся процессы . Берлин: Springer-Verlag. стр. 199–206. ISBN 978-3-642-65371-1.
10. Янсон, Сванте (2003). «Функциональные предельные теоремы для многотипных ветвящихся процессов и обобщенных урн Полиа». Стохастические процессы и их приложения . 110 (2): 177–245. doi : 10.1016/j.spa.2003.12.002 .
11. Цзян, Да-Куан; Ван, Юэ; Чжоу, Да (2017). «Фенотипическое равновесие как вероятностная конвергенция в динамике популяции клеток с несколькими фенотипами». PLOS ONE . 12 (2): e0170916. Bibcode : 2017PLoSO..1270916J. doi : 10.1371/journal.pone.0170916 . PMC 5300154. PMID  28182672 . 

• CM Grinstead и JL Snell, Введение в вероятность Архивировано 27 июля 2011 г. в Wayback Machine , 2-е изд. В разделе 10.3 подробно обсуждаются ветвящиеся процессы вместе с применением производящих функций для их изучения.
• GR Grimmett и DR Stirzaker, Probability and Random Processes , 2nd ed., Clarendon Press, Oxford, 1992. Раздел 5.4 обсуждает модель ветвящихся процессов, описанную выше. Раздел 5.5 обсуждает более общую модель ветвящихся процессов, известную как зависимые от возраста ветвящиеся процессы , в которых индивидуумы живут более одного поколения.