436
правок
Изменения
м
Minor changes
Рассмотрим натуральное случайное число <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> в модифицированном поиске в ширину. <br>Пусть <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>t</tex>, вычисляется по следующей формуле:<br>
<tex>a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}</tex><br>
=== Вычисление вероятности исчезновения ===
{{Лемма
