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

О процессе в теории представлений см. Ограниченное представление § Классические правила ветвления .

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

Центральным вопросом теории ветвящихся процессов является вероятность окончательного вымирания , при котором особи не существуют после некоторого конечного числа поколений. Используя уравнение Уолда , можно показать, что, начиная с одного человека в нулевом поколении, ожидаемый размер поколения 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 }. Тогда рекуррентное уравнение имеет вид

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

с Z ₀ = 1.

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

$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 для всех индивидуумов. В ветвящихся процессах с непрерывным временем каждый человек ждет случайное время (которое является непрерывной случайной величиной), а затем делится в соответствии с заданным распределением. Время ожидания у разных особей независимо и не зависит от количества детей. В общем, время ожидания является экспоненциальной переменной с параметром λ для всех людей, так что процесс является марковским.

процесса Гальтона

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

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

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

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

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

Правая часть уравнения представляет собой производящую функцию вероятности. Пусть h ( z будет обычной производящей функцией для pi ₎ :

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

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

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

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

$d=h(d).\,$

Это также эквивалентно нахождению точек пересечения линий y = z и y = h ( z ) для z ≥ 0. y = z — прямая линия. y = h ( z ) является возрастающим (поскольку $h'(z)=p_{1}+2p_{2}z+3p_{3}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 (см. красную кривую на графике).

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

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

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

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

процессы, зависящие

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

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

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

$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 поколений будет следующей:

Поколение № (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 будет производить особей разных типов, а $\mathbf {X} _{i}$, случайный вектор, представляющий количество детей разных типов, удовлетворяет распределению вероятностей на $\mathbb {N} ^{n}$.

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

больших чисел для многотипных

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

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

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

Другие

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

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

См. также

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

Ссылки

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