Ветвящийся процесс - Branching process

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

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

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

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

Наиболее распространенная формулировка процесса ветвления - это Процесс Гальтона – Ватсона. Позволять Z_п обозначают состояние в периоде п (часто интерпретируется как размер поколенияп), и разреши Икс_{п, я} быть случайной величиной, обозначающей количество прямых наследников члена я в период п, где Икс_{п, я} находятся независимые и одинаково распределенные случайные величины в общем и целом п ∈ {0, 1, 2, ...} и я ∈ {1, ..., Z_п}. Тогда рекуррентное уравнение имеет вид

${ Displaystyle Z_ {п + 1} = сумма _ {я = 1} ^ {Z_ {п}} X_ {п, я}}$

с участием Z₀ = 1.

В качестве альтернативы процесс ветвления можно сформулировать как случайная прогулка. Позволять S_я обозначают состояние в периоде я, и разреши Икс_я быть случайной величиной, которая iid в общем и целом я. Тогда рекуррентное уравнение имеет вид

${ Displaystyle S_ {я + 1} = S_ {я} + X_ {я + 1} -1 = сумма _ {j = 1} ^ {я + 1} X_ {j} -i}$

с участием S₀ = 1. Чтобы получить некоторую интуицию в этой формулировке, представьте себе прогулку, цель которой - посетить каждый узел, но каждый раз, когда посещается ранее не посещенный узел, открываются дополнительные узлы, которые также необходимо посетить. Позволять S_я представляют количество обнаруженных, но не посещенных узлов за период я, и разреши Икс_я представляют количество новых узлов, которые обнаруживаются, когда узел я посещается. Затем в каждом периоде количество обнаруженных, но не посещенных узлов равно количеству таких узлов в предыдущем периоде плюс новые узлы, обнаруженные при посещении узла, минус узел, который был посещен. Процесс завершается после посещения всех обнаруженных узлов.

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

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

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

Конечная вероятность вымирания определяется выражением

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

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

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

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

Следовательно, d_м сходится к пределу d, а d - предельная вероятность вымирания. Если в первом поколении есть j потомков, то, чтобы вымереть к m-му поколению, каждая из этих линий должна вымереть через m-1 поколение. Поскольку они действуют независимо, вероятность равна (d_{м − 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. ,}$

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

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

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

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

поскольку d_м → d, d можно найти, решив

${ Displaystyle д = час (д). ,}$

Это также эквивалентно нахождению точки (точек) пересечения линий у = z и у = час(z) дляz ≥ 0. у = z прямая линия. у = час(z) возрастает (поскольку ${ 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}$) функция. Есть не более двух точек пересечения. Поскольку (1,1) всегда является точкой пересечения двух функций, существует только три случая:

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

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

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

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

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

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

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

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

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

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

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

с участием d₀ = 0. Для предельной вероятности вымирания нам нужно найти d что удовлетворяет d = п₀ + п₁d +п₂d².

Взяв в качестве примера вероятности количества произведенного потомства п₀ = 0.1, п₁ = 0,6 и п₂ = 0,3, вероятность вымирания первых 20 поколений такова:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

• К. М. Гринстед и Дж. Л. Снелл, Введение в вероятность 2-е изд. В разделе 10.3 подробно обсуждаются процессы ветвления вместе с применением производящих функций для их изучения.
• Г. Р. Гриммет и Д. Р. Стирзакер, Вероятность и случайные процессы, 2-е изд., Clarendon Press, Oxford, 1992. В разделе 5.4 обсуждается модель ветвящихся процессов, описанная выше. В разделе 5.5 обсуждается более общая модель ветвящихся процессов, известная как возрастные ветвящиеся процессы, в котором особи живут не одно поколение.