436
правок
Изменения
м
В поисках другогоВведем обозначения: <tex>k</tex> {{---}} количество потомков вершины, меньшего корня, рассмотрим а <tex>m = f'(1)</tex>.<br>Тогда: <tex>m = f'(1) = \sum_{i = 1..\infty}ip_i</tex>, другими словами <tex>m = E(k)</tex>количество потомков вершины '''оформи по-другому, введи переменную, нельзя просто обернуть русский текст в тех'''.<tex>)</texbr>Кажется, что при <tex>m > 1</tex> дерево будет расти вечно, так как каждая вершина в момент времени <tex>j</tex> должна иметь потомков, однако при <tex>p_0 > 0</tex> с положительной вероятность вероятностью у корня может вообще не быть потомков. Вспоминая об В исходном <tex>G(n,\frac{d}{n})</tex>б ввиду того, что <tex>dm</tex> {{---}} ожидаемое количество потомков, играет роль <tex>md</tex> играет роль , ввиду того, что <tex>d= E(k)</tex>.<br>
Далее, '''Ещё одно бессмысленное вводное слово, старайся не использовать их там, где не нужно''' пользуясь Пользуясь описанными выше утверждениями, можно доказать, что:<br>
small changes
В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины. <br>
Обозначим:
* <tex>q</tex> {{- --}} вероятность исчезновения;<br>
* <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex> {{---}} количество потомков у очередной исследованной вершины;<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>f(x) = \sum_{i = 0..\infty}p_ix^i,</tex> где <tex>p_i</tex> {{---}} вероятность того, что <tex>y = i</tex><br>
<br>
Так как <tex>q</tex> {{---}} вероятность конечности алгоритма, то, если у корневой вершины <tex>i</tex> потомков, то построение каждого из поддеревьев должно завершиться, и это произойдет с вероятностью <tex>q^i</tex>. Таким образом, : <br>
<tex>q = \sum_{i = 0..\infty}p_iq^i</tex><br>
Таким образом, '''Либо убери вводное слово, либо придумай другое'''<tex>q</tex> является корнем уравнения:<br>
<tex>x = \sum_{i = 0..\infty}p_ix^i \Leftrightarrow f(x) = x</tex><br>
<br>
Рассмотрим решение данного уравнения на <tex>[0; 1]</tex>. <br>
<tex>x = 1</tex> {{---}} всегда решение данного уравнения, так как <tex>\sum_{i = 0..\infty}p_i1^i = \sum_{i = 0..\infty}p_i = 1 = x</tex>.<br>
[[Файл:Extinction_probability_equation_root_random_graph.png|thumb|300px|center|Решение уравнения f(x)=x]]
# <tex>m < 1</tex> <tex>||</tex> <tex>m = 1</tex> <tex>\&</tex> <tex>p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br>
# <tex>m = 1</tex> <tex>\&</tex> <tex>p_1 = 1</tex> {{---}} вероятность исчезновения <tex> = 0</tex>;<br>
