436
правок
Изменения
Разобрана теорема о гигантской компоненте
{{В разработке}}
== Теорема о гигантской компоненте ==
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения
{{Определение
|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</tex> потомков и умирает. Заметим, что она может умереть, даже не принеся потомства, так как величина <tex>Z_1</tex> равна нулю с положительной вероятностью. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает <tex>Z_2</tex> новых частиц, а сама гибнет. И так далее. Популяция может выродиться, а может и жить вечно.{{Теорема|id = th1|statement=Пусть <tex>\lambda \leq 1</tex>. Тогда с вероятностью 1 процесс <tex>Y_t</tex> вырождается, т.е. <tex>P(\exists t: Y_t \leq 0) = 1</tex>.}}{{Теорема|id = th2|statement=Пусть <tex>\lambda \ge 1</tex>. Пусть <tex>\gamma \in (0, 1)</tex> {{---}} единственное решение уравнения <tex>1 - \gamma = e^{-\lambda \gamma}</tex>. Тогда процесс <tex>Y_t</tex> вырождается с вероятностью <tex>1 - \gamma</tex>, т.е. <tex>P(\exists t: Y_t \leq 0) = 1 - \gamma</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>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>c > 1</tex>, то найдется такая константа <tex>\gamma = \gamma(c)</tex>, что а.п.н. в случайном графе есть ровно одна компонента размера <tex>\geq\gamma n</tex>. Размер остальных компонент не превосходит <tex>b\ln n</tex>.
|proof=
Приведем здесь идеи, изложенные А.М. Райгородским [1], основанные на доказательстве Р. Карпа [2]. Данное доказательство может быть, не настолько строгое, как приведенное в [3], однако
отличается лаконичностью и наглядностью.
'''Случай <tex>c < 1</tex>'''.
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta = \beta(c)</tex> {{---}} константа, которую мы подберем позднее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер <tex>\le t_0</tex>.
Но размер компоненты {{---}} это момент вырождения процесса <tex>Y_t</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}(Y_{t_0} > 0) = o\left(\dfrac{1}{n}\right).</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>
<tex>\int\limits_{\dfrac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \dfrac{1}{\sqrt{2\pi}}e^{-\dfrac{x^2}{2}}\,dx</tex>.
Поскольку <tex>c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины
<tex>e^{−\delta t_0}</tex>. Выберем <tex>\beta</tex> таким, чтобы <tex>e^{−\delta t_0}</tex> оказалось меньше, чем
<tex>e^{-2 \ln n} = \dfrac{1}{n^2}</tex>, и в случае <tex>c < 1</tex> теорема доказана.
'''Случай <tex>c > 1</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>p = \dfrac{ c }{n}</tex>. Значит, при <tex>t \thicksim \alpha n</tex> выполнено
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
Применим [[Центральная предельная теорема| центральную предельную теорему]] к
<tex>P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(Binom(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
Интегрирование пойдет от минус бесконечности до
<tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</tex>.
Если <tex>\alpha < 1 - e^{-c\alpha}</tex>, то мы получим искомое стремление вероятности к нулю.
Если <tex>\alpha > 1 - e^{-c\alpha}</tex>, то вероятность, напротив, будет стрметиться к единице.
Таким образом, критическое значение <tex>\alpha</tex>, вплоть до которого есть именно стремление к нулю, {{---}} это решение уравнения <tex>\alpha = 1 - e^{-c\alpha}</tex> или, что равносильно, <tex>1 - \alpha = e^{-c\alpha}</tex>. А это и есть уравнение из [[th2| предыдущей теоремы]], если заменить <tex>\lambda</tex> на <tex>c</tex>.
}}
== Литература ==
* 1. Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.{{---}} М.: МЦНМО, 2013 {{---}} C.330-339 {{---}} ISBN 978-5-4439-0040-7* 2. Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.* 3. Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.
== См. также ==
