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

редактировать

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

A центральным вопросом теории ветвящихся процессов является вероятность окончательного вымирания, когда не существует особей после некоторого конечного числа поколений. Используя уравнение Вальда, можно показать, что, начиная с одного человека в нулевом поколении, ожидаемый размер поколения n равен μ, где μ - ожидаемое количество детей каждого человека. Если μ < 1, then the expected number of individuals goes rapidly to zero, which implies ultimate extinction с вероятностью 1 по неравенству Маркова. В качестве альтернативы, если μ>1, то вероятность окончательного исчезновения меньше 1 (но не обязательно равна нулю; рассмотрим процесс, в котором у каждого человека либо 0, либо 100 детей с равной вероятностью. В этом случае μ = 50, но вероятность окончательное вымирание больше 0,5, поскольку это вероятность того, что у первой особи будет 0 детей). Если μ = 1, то окончательное вымирание происходит с вероятностью 1, если у каждого человека всегда есть ровно один ребенок.

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

Содержание

1 Математическая формулировка
- 1.1 Непрерывное разветвление процессы
2 Проблема затухания для процесса Гальтона-Ватсона
3 Ветвящиеся процессы, зависящие от размера
4 Пример задачи затухания
5 Моделирование ветвящихся процессов
6 Многотипные ветвящиеся процессы
- 6.1 Закон больших чисел для многотипных ветвящихся процессов
7 Другие ветвящиеся процессы
8 См. также
9 Ссылки

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

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

Z n + 1 = ∑ i = 1 Z n X n, i {\ displaystyle Z_ {n + 1} = \ sum _ {i = 1} ^ {Z_ {n}} X_ { n, i}}

Z _ {{n + 1}} = \ sum _ {{i = 1}} ^ {{Z_ {n} }} X _ {{n, i}}

с Z 0 = 1.

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

S i + 1 = S i + X i + 1-1 = ∑ j = 1 i + 1 X j - i {\ displaystyle S_ {i + 1} = S_ {i} + X_ {i + 1} -1 = \ sum _ {j = 1} ^ {i + 1} X_ {j} -i}

S _ {{i + 1}} = S_ {i} + X _ {{i + 1}} - 1 = \ sum _ {{j = 1}} ^ {{i + 1}} X_ {j} -i

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

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

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

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

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

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

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

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

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

0 = d 0 ≤ d 1 ≤ d 2 ≤ ⋯ ≤ 1. {\ displaystyle 0 = d_ {0} \ leq d_ {1} \ leq d_ {2} \ leq \ cdots \ leq 1. }

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

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

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

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:

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

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

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

дм = ч (дм - 1). {\ displaystyle d_ {m} = h (d_ {m-1}). \,}

d_ {m} = h (d _ {{m-1}}). \,

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

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

d = h (d). \,

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

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

Случай 1 имеет другую точку пересечения в z < 1 (see the red curve in the graph).

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

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

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

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

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

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

Пример проблемы исчезновения

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

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

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

с d 0 = 0. Для максимальной вероятности исчезновения нам нужно найти d, которое удовлетворяет d = p 0 + p 1 d + p 2 d.

Взяв в качестве примера вероятности количества произведенного потомства p 0 = 0,1, p 1 = 0,6 и p 2 = 0,3, вероятность вымирания для первых 20 поколений следующая:

Поколение № (1–10)	Вероятность вымирания	Поколение № (11–20)	Вероятность исчезновения
1	0,1	11	0,3156
2	0,163	12	0,3192
3	0,2058	13	0,3221
4	0,2362	14	0,3244
5	0,2584	15	0,3262
6	0,2751	16	0,3276
7	0,2878	17	0,3288
8	0,2975	18	0,3297
9	0,3051	19	0,3304
10	0,3109	20	0,331

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

Ссылки

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