У теорії ймовірностей процес з розгалуженням — це тип стохастичного процесу, тобто математичного об’єкта який складається з сімейств випадкових змінних, індексованих деякою множиною, зазвичай натуральними або невід’ємними дійсними числами. Початкова мета, задля якої процеси з розгалуженням були вперше сформульовані як клас випадкових процесів - це моделювання популяції, в якій кожна особина в поколінні породжує випадкову кількість особин у поколінні , згідно, у найпростішому випадку, з фіксованим розподілом ймовірностей, який не змінюється від особини до особини. Процеси з розгалуженням використовуються для моделювання розмноження; наприклад, особини можуть відповідати бактеріям, кожна з яких породжує або нащадків з певною ймовірністю за одиницю часу. Процеси з розгалуженням також застосовуються у моделюванні й інших систем з подібною динамікою, наприклад, поширення прізвищ у генеалогії або розповсюдження нейтронів у ядерному реакторі та інших ланцюгових реакцій.
Центральним питанням у теорії процесів з розгалуженням є ймовірність остаточного вимирання, коли після певної кількості поколінь не залишається жодної особини. Використовуючи рівняння Вальда, можна показати, що починаючи з однієї особини в нульовому поколінні, очікувана кількість особин у поколінні дорівнює , де — це математичне сподівання кількості нащадків кожної особини. Якщо , то очікувана кількість особин швидко зменшується до нуля, що означає остаточне вимирання з ймовірністю 1 (майже напевне) згідно з нерівністю Маркова. Якщо ж , то ймовірність остаточного вимирання менша за 1 (але не обов’язково нульова; наприклад, процес, де кожна особина має або 0, або 100 нащадків з однаковою ймовірністю. У цьому випадку , але ймовірність остаточного вимирання перевищує , оскільки це ймовірність того, що перша особина не матиме нащадків). Якщо , то остаточне вимирання відбувається з ймовірністю , якщо кожна особина не має точно одного нащадка.
У параметр процесу з розгалуженням називається базовим репродуктивним показником.
Математична формалізація Найпоширенішою формалізацією процесу з розгалуженням є . Нехай позначає стан у періоді (часто інтерпретується як кількість особин в поколінні ), а — випадкова змінна, що позначає кількість прямих нащадків особини у періоді , де — незалежні та однаково розподілені випадкові величини для всіх та . Тоді рекурсивне рівняння еволюції такого процесу має вигляд:
де 0 = 1.
Альтернативно, процес з розгалуженням можна сформулювати як випадкове блукання. Нехай позначає стан у періоді , а — випадкова змінні, які є незалежними та однаково розподіленими для всіх . Тоді рівняння рекурсії має вигляд:
де = 1. Щоб краще зрозуміти цю формалізацію, варто уявити випадкове блукання, таке яке за визначенням має відвідати кожну вершину, але кожного разу, коли відвідується нова вершина, йому відкриваються додаткові вершини, які також необхідно відвідати. Нехай позначає кількість відкритих, але ще не відвіданих вершин у періоді , а — кількість нових вершин, що відкриваються при відвідуванні вершини . Тоді в кожному періоді кількість відкритих, але не відвіданих вершин дорівнює кількості таких вершин у попередньому періоді, плюс нові вершини, що відкриваються, мінус одна вершина, яка вже відвідана. Процес завершується, коли всі відкриті вершини буде відвідано.
Процеси з розгалуженням у неперервному часі Для процесів з розгалуженням у дискретному часі «час галуження» фіксований і дорівнює для всіх особин. У процесах з неперервним часом кожна особина очікує протягом випадкового проміжку часу (який є неперервною випадковою змінною), а потім розмножується згідно з заданим розподілом. Час очікування для різних особин є незалежним і не залежить від кількості нащадків. Загалом, час очікування є експоненціальною змінною з параметром для всіх особин, що робить процес марковським.
Проблема вимирання у процесі з розгалуженням Ймовірність остаточного вимирання задається як
Для будь-яких нетривіальних випадків (тривіальні — це ті, де ймовірність не мати нащадків дорівнює нулю для кожного члена популяції — у таких випадках ймовірність остаточного вимирання дорівнює 0), ймовірність остаточного вимирання дорівнює одиниці, , і строго менша за одиницю, якщо .
Процес можна аналізувати за допомогою методу генерувальної функції ймовірностей. Нехай , — ймовірності того, що кожна особина породжує нащадків у кожному поколінні. Нехай — ймовірність вимирання до -го покоління, починаючи з однієї особини (тобто ). Очевидно, що = 0 і . Оскільки потрібно врахувати всі шляхи, що ведуть до нуля до m-го покоління, ймовірність вимирання не зменшується з поколіннями:
Отже, збігається до межі , і — це остаточна ймовірність вимирання. Якщо в першому поколінні є нащадків, то для вимирання до -го покоління кожна з цих ліній має досягти вимирання за поколінь. Оскільки вони розвиваються незалежно, ймовірність дорівнює . Таким чином:
Права частина рівняння — це генерувальна функція ймовірностей. Нехай — звичайна генерувальна функція для :
Тоді попереднє рівняння набуває вигляду:
Оскільки , значення можна знайти, розв’язавши рівняння:
Це також еквівалентно знаходженню точок перетину ліній та для , де — це пряма. — зростаюча (оскільки ) і опукла (оскільки ) функція. Існує не більше двох точок перетину. Оскільки (1,1) завжди є точкою перетину, існує лише три випадки:
Випадок 1: є ще одна точка перетину при (червона крива).
Випадок 2: єдина точка перетину при (зелена крива).
Випадок 3: ще одна точка перетину при (чорна крива).
У випадку 1 ймовірність остаточного вимирання строго менша за одиницю. У випадках 2 і 3 — дорівнює одиниці.
Оскільки μ — це мат сподівання кількості нащадків, яких може породити одна особина, то можна зробити висновок: якщо середня кількість нащадків , то ймовірність остаточного вимирання дорівнює ; якщо — то строго менша за .
Процеси з розгалуженням, залежні від розміру популяції Окрім розгляду більш загальної моделі процесів з розгалуженням, відомої як віко- (або часо-) залежні процеси з розгалуженням (Grimmett),G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, 2nd ed., Clarendon Press, Oxford, 1992. у яких особини живуть більше одного покоління, Крішна Атрея виокремив ще три типи процесів з розгалуженням, залежних від поточного розміру популяції, що мають загальне застосування. Атрея класифікує їх як субкритичні, стабільні та надкритичні. Центральні параметри є ключовими для контролю поведінки процесу, щоб уникнути нестабільного субкритичного або надкритичного розгалуження.Krishna Athreya and Peter Jagers. Branching Processes. Springer. 1973. Процеси з розгалуженням, залежні від розміру популяції, також розглядаються в контексті тематики F. Thomas Bruss and M. Duerinckx (2015) "Resource dependent branching processes and the envelope of societies", Annals of Applied Probability. 25: 324–372.
Приклад проблеми вимирання Розглянемо випадок, коли особина може породити не більше двох нащадків. Ймовірність вимирання в кожному поколінні задається як:
де . Щоб знайти остаточну ймовірність вимирання, потрібно розв’язати рівняння:
Візьмемо приклад, де ймовірності народження нащадків такі: , , . Ймовірність вимирання для перших 20 поколінь наведена нижче: Покоління (1–10)Ймовірність вимиранняПокоління (11–20)Ймовірність вимирання10,1110,315620,163120,319230,2058130,322140,2362140,324450,2584150,326260,2751160,327670,2878170,328880,2975180,329790,3051190,3304100.3109200,331 У цьому прикладі можна алгебраїчно розв’язати рівняння і отримати , що є значенням, до якого збігається ймовірність вимирання з ростом кількості поколінь.
Моделювання галужувальних процесів Процеси із розгалуженням можуть бути змодельовані для широкого спектра задач. Одним із прикладів застосування моделювання таких процесів є еволюційна біологія. Наприклад, філогенетичні дерева можуть бути змодельовані за кількома підходами, що допомагає розробляти та перевіряти методи оцінювання, а також безпосередньо допомагати в перевірці статистичних гіпотез.
Процеси з розгалуженням із кількома типами У процесах з кількома типами особини не є ідентичними, а можуть бути класифіковані на типів. Після кожного кроку часу особина типу породжує особин різних типів, і , випадковий вектор, що представляє кількість нащадків кожного типу, задовольняє розподіл ймовірностей на .
Наприклад, розглянемо популяцію ракових стовбурових клітин (CSC) і неракових стовбурових клітин (NSCC). Після кожного інтервалу часу кожна CSC має ймовірність породити дві CSC (симетричний поділ), ймовірність породити одну CSC і одну NSCC (асиметричний поділ), ймовірність породити одну CSC (стагнація) і ймовірність не породити нічого (смерть); кожна NSCC має ймовірність породити дві NSCC (симетричний поділ), ймовірність породити одну NSCC (стагнація) і ймовірність не породити нічого (смерть).
Закон великих чисел для процесів з розгалуженням із кількома типами Для процесів з розгалуженням із кількома типами, у яких популяції різних типів зростають експоненціально, частки різних типів майже напевно збігаються до сталого вектора за деяких слабких умов. Це сильний закон великих чисел для таких процесів з кількома типами.
У випадках з неперервним часом очікувані частки популяції задовольняють систему ЗДР, розв'язок якої має єдину точку рівноваги. Ця точка — це саме той вектор, до якого збігаються частки згідно із законом великих чисел.
Монографія Атреї та Нея узагальнює набір умов, за яких цей закон великих чисел є чинним. Пізніше були запропоновані вдосконалення шляхом відмови від деяких умов.
Інші процеси з розгалуженням Існує багато інших типів процесів подібних до простих процесів з розгалуженням, наприклад, процеси із розгалуженням у випадкових середовищах, де закон розмноження випадково обирається для кожного покоління, або процеси, де зростання популяції контролюється зовнішніми впливами чи іншими взаємодіючими процесами. Процеси з розгалуженням, в яких частинки повинні працювати (вносити ресурси в середовище), щоб мати змогу розмножуватися, і жити в змінній соціальній структурі, що контролює розподіл ресурсів, називаються .
Граничний перехід майже критичних процесів з розгалуженням може бути використаний для отримання .
Примітки
Джерела
C. M. Grinstead and J. L. Snell, Introduction to Probability , 2nd ed. Розділ 10.3 детально розглядає галужувальні процеси та застосування генерувальних функцій для їх дослідження. G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, 2nd ed., Clarendon Press, Oxford, 1992. Розділ 5.4 описує модель галужувальних процесів, наведений вище. Розділ 5.5 розглядає загальнішу модель процесів з розгалуженням, відому як віко- (часо-) залежні процеси з розгалуженням, у яких особини живуть більше одного покоління.