436
правок
Изменения
Medium-sized changes
Будем считать шагом алгоритма поиска открытие новой вершины. После первых <tex>i</tex> шагов алгоритма, любая из вершин, кроме стартовой, может быть неоткрытой с вероятностью <tex>p = (1 - \frac{d}{n})^i</tex>. Пусть <tex>z_i</tex> {{---}} число вершин, открытых за первые <tex>i</tex> шагов алгоритма поиска. <tex>z_i</tex> распределены как <tex>Binomial(n − 1,1 − (1 - \frac{d}{n})^i)</tex>.<br>
== Наверное, лучше придумать другой заголовок (Ветвящийся процесс) Вероятность исчезновения ===== От поиска в ширину к ветвящимся процессам ===
Пользуясь идеями, изложенными в доказательстве [[#lemma1|леммы 1]], перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.<br>
{{Определение
|definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).
}}
Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество потомков у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.<br>
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее потомки. Данный процесс может продолжаться бесконечно. <br>
Пусть <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex>. Пусть <tex>p′</tex> {{---}} вероятность того, что <tex>size(cc(v)) = O(\log n)</tex> в модифицированном поиске в ширину. Пусть <tex>q</tex> {{---}} вероятность окончания процесса. Тогда <tex>q \geq p′</tex>, поскольку поиск в ширину, заканчивающийся с <tex> \le c_1\log n</tex> вершинами, приводит к окончанию построения дерева.<br>
<br>
Пусть <tex>p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}</tex> {{---}} вероятность, что <tex>y</tex> производит <tex>i</tex> потомков. Тогда:<br>
<tex>\sum_{i = 0..s}p_i = 1</tex> и <tex>\sum_{i = 0..s}ip_i = E(y) = \frac{ds}{n} > 1</tex>.<br>
<br>Глубина дерева не меньше количества вершин. Пусть <tex>a_i</tex> {{---}} , поэтому вероятность того, что процесс закончится с деревом глубины <tex>t</tex>. Имеем, вычисляется по следующей формуле:<br>
<tex>a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}</tex><br>
=== Вероятность Вычисление вероятности исчезновения ==={{Определение|definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).}}
{{Лемма
|id=lemma2
