436
правок
Изменения
м
<tex>P_{n, p}(Y_{t_0} > 0) = o\left(\dfrac{1}{n}\right).</tex>Далее:
Далее
Нам хочется Чтобы доказать, что есть гигантская компонента. Тогда, как следствие, нам нужнонеобходимо, чтобы ветвящийся процесс на графе не вырождался даже
У нас Так как по условию <tex>p = \dfrac{ c }{n}</tex>. Значит, то при <tex>t \thicksim \alpha n</tex> выполнено:
→Теорема о гигантской компоненте
== Теорема о гигантской компоненте ==
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
{{Определение
|definition='''Простейший ветвящийся процесс.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины с одним и тем же средним <tex>\lambda</tex>. Положим
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Представлять себе описанный только что процесс можно так. В начальный момент времени есть одна активная частица. Затем она приносит делает <tex>Z_1\geq 0</tex> потомков и умирает. Заметим, что она может умереть, не оставив потомков(можжет ыть достигнуто, так как величина <tex>Z_1</tex> равна нулю с положительной вероятностью) активных потомков и перестает быть активной. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает <tex>Z_2</tex> новых частиц, а сама гибнетперестает быть активной. И так далее. Популяция Данный процесс может выродитьсякак завершиться (частицы перестанут быть активными), а может так и жить вечнопродолжаться бесконечно.
{{Теорема
|id = th1
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Пусть дан граф <tex>G = (V,E)</tex>. Зафиксируем <tex>v_1 \in V</tex>. Назовем Пометим ее «живой»как активную, а все остальные вершины {{---}} «нейтральными»нейтральными. Выберем среди нейтральных вершин всех соседей вершины <tex>v_1</tex>. После этого объявим пометим вершину <tex>v_1</tex> «мертвой»как неактивную , ее соседей а смежных с ней {{---}} «живыми»как активных, а все остальные вершины {{---}} нейтральными.
Снова зафиксируем какую-нибудь «живую» активную вершину <tex>v_2</tex>, и повторим процесс. Выберем всех ее соседей среди нейтральных. Вершину <tex>v_2</tex> объявим вершину «мертвой», а остальные «живые» сохранят свой Не меняем статус, также «оживут» и соседи <tex>v_2</tex>остальных уже активных вершин.
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь «мертвые» неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.
Обозначим число «живых» активных вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число потомков очередной «живой» соседей вершины, объявляющейся «мертвой»которую собираемся пометить как неактивную, {{---}} через <tex>Z_t</tex>. Тогда, очевидно, <tex>Y_0 = 1,Y_t = Y_t−1 + Z_t − 1</tex>. Все введенные величины зависят от графа <tex>G</tex> и от последовательности выбираемых вершин <tex>v_1,\dotsc</tex>.
Если <tex>G</tex> посчитать случайным, то при любом выборе вершин <tex>v_1,\dotsc</tex> получатся случайные величины <tex>Y_t, N_t, Z_t</tex> на пространстве <tex>G(n, p)</tex>.
<tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \rightarrow 0, n \rightarrow \infty</tex>
Поскольку<tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \le nP_{n, p}(Y_{t_0} \ge 0)</tex>, достаточно найти такое <tex>\beta</tex>, при котором
<tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) = o\le nP_left(\dfrac{n, p1}(Y_{t_0n} \ge 0right).</tex> достаточно найти такое <tex>\beta</tex>, при котором
<tex>P_{n, p}(Y_{t_0} > 0) = P_{n, p}(\xi_{t_o} > t_0) \thickapprox P_{n, p}(Binom(n, 1 - (1 - p)^{t_0}) > t_0) \thickapprox (</tex> с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) \thickapprox P_{n, p}(Binom(n, pt_0) > t_0)</tex>
<tex>\thickapprox (</tex>с учетом [[Центральная предельная теорема| центральной предельной теоремы]]) <tex> \thickapprox </tex>
бы в одном запуске возникнет гигантская компонента. Подробности можно найти в [3], мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки [[th2| предыдущей теоремы]] и почему она совпадает с одноименной константой из той же теоремы.
при <tex>t \thickapprox \gamma n</tex>. Иными словами, необходимо, чтобы:
<tex>P_{n, p}(Y_{t_0} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
Применим [[Центральная предельная теорема| центральную предельную теорему]] к
