Изменения

Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.

|definition='''Простейший ветвящийся процесс.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины <ref>https://ru.wikipedia.org/wiki/Распределение_Пуассона</ref> с одним и тем же средним [[Математическое ожидание случайной величины | математическим ожиданием]] <tex>\lambda</tex>. Положим

Представлять себе описанный только что процесс можно так. В : в начальный момент времени есть одна активная частица. Затем она приносит создает <tex>Z_1\geq 0</tex> потомков и умирает. Заметим, что она (может умереть, даже не принеся потомствабыть достигнуто, так как величина <tex>Z_1</tex> равна нулю с положительной вероятностью) активных потомков и перестает быть активной. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает <tex>Z_2</tex> новых частиц, а сама гибнет. И перестает быть активной, и так далее. Популяция Данный процесс может выродитьсякак завершиться (частицы перестанут быть активными), так и продолжаться бесконечно.<br>Говоря в терминах данного выше определения, а может <tex>Y_i</tex> и <tex>Z_i</tex> {{---}} количество активных и жить вечнопорожденных частиц в момент времени <tex>t</tex>, соответственно.

|about=1|statement=Пусть <tex>\lambda \leq 1</tex>. Тогда с вероятностью 1 процесс <tex>Y_t</tex> вырождается, т.е. <tex>P(\exists t: Y_t \leq = 0) = 1</tex>.

|definition='''Ветвящийся процесс на случайном графе.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины с одним и тем же средним [[Математическое ожидание случайной величины | математическим ожиданием]] <tex>\lambda</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>) и нейтральные вершины.<br>Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], этим свойством мы воспользуемся позднее.<br>

Обозначим число «живых» активных вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число потомков очередной «живой» соседей вершины, «отправляющейся в последний путь»которую собираемся пометить как неактивную, {{---}} через <tex>Z_t</tex>. Тогда, очевидно, <tex>Y_0 = 1,Y_t = Y_t−1 Y_{t − 1} + Z_t − 1</tex>. Разумеется, все Все введенные величины зависят от графа <tex>G</tex> и от последовательности выбираемых вершин <tex>v_1,\dotsc</tex>.

: Если <tex>c < 1</tex>, то найдется такая константа <tex>\beta = \beta(с)</tex>, зависящая от <tex>c</tex>, что а.п.н. (асимптотически почти наверное) размер каждой связной компоненты случайного графа не превосходит <tex>b\beta \ln n</tex>.: Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma = \gamma(</tex>, зависящая от <tex>c)</tex>, что а.п.н. в случайном графе есть ровно одна компонента размера <tex>\geq\gamma n</tex>. Размер остальных компонент не превосходит <tex>b\beta \ln n</tex>.

Приведем здесь идеи<ref>Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.{{---}} М.: МЦНМО, 2013 {{---}} C.330-339 {{---}} ISBN 978-5-4439-0040-7</ref>, изложенные А.М. Райгородским [1], основанные на доказательстве <ref>Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.</ref> Р. Карпа [2]. Данное доказательство может бытьТакой формат позволит понять основные идеи и логику рассуждений. Строгий вариант приведен в <ref name="trueproof">Алон Н., не настолько строгоеСпенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, как приведенное в [3], однако2007.</ref>. отличается лаконичностью Здесь и наглядностьюдалее: <tex>Binomial</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(\frac{1}{n}\right).</tex><br><br>: <tex>P_{n, p}(Y_{t_0} > 0) = P_{n, p}(\xi_{t_o} \geq t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) \geq t_0) \thickapprox</tex><br>: (с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) </tex><br>: <tex>\thickapprox P_{n, p}(Binomial(n, pt_0) \geq t_0) \thickapprox</tex><br>: (с учетом центральной предельной теоремы) <br>: <tex> \thickapprox \int\limits_{\frac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx</tex>.

Поскольку <tex>P_c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{nt_0}</tex>. Таким образом, pвесь интеграл не превосходит величины<tex>e^{−\delta t_0}(</tex>. Выберем <tex>\exists v_1 : Y_beta</tex> таким, чтобы <tex>e^{−\delta t_0} </tex> 0) оказалось меньше, чем<tex>e^{-2 \rightarrow 0, ln n } = \rightarrow \inftydfrac{1}{n^2}</tex>, и в случае <tex>c < 1</tex> теорема доказана.<br><br>

В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что а.п.н. хотябы в одном запуске возникнет гигантская компонента. Подробности можно найти в <texref name="trueproof" />P_{n, p}(\exists v_1 : Y_{t_0} мы же лишь поясним, откуда в текущей ситуации появляется <tex> 0) \le nP_{n, p}(Y_{t_0} \ge 0)gamma</tex>из формулировки [[#th2|теоремы 2]] и почему она совпадает с одноименной константой из той же теоремы.

достаточно найти такое Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался дажепри <tex>t \betathickapprox \gamma n</tex>, при которомто есть:<br><tex>P_{n, p}(Y_{t} \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_0t} > \le 0) = o\leftthickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>Пределы интегрирования в данном случае: от <tex>-\infty</tex> до <tex>\dfrac{\alpha n - n(1- e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\right).alpha}}}</tex>.

ДалееЕсли <tex>P_\alpha < 1 - e^{n, p}(Y_{t_0-c\alpha} </tex> 0) = P_{n, p}(то мы получим искомое стремление вероятности к нулю. Если <tex>\xi_{t_o} alpha > t_0) \thickapprox P_{n, p}(Binom(n, 1 - (1 - p)e^{t_0-c\alpha}) </tex>, то вероятность, напротив, будет стремиться к единице. Таким образом, критическое значение <tex> t_0) \thickapprox (alpha</tex> с учетом асимптотики , вплоть до которого есть именно стремление к нулю, {{---}} это решение уравнения <tex>\alpha = 1 - (1 - p)e^{t_0} \thicksim pt_0) -c\thickapprox P_{n, palpha}(Binom(n, pt_0) > t_0)</tex>или, что равносильно, <tex>1 - \thickapprox (alpha = e^{-c\alpha}</tex>с учетом . А это и есть уравнение из [[Центральная предельная теорема#th2| центральной предельной теоремы2]]) , если заменить <tex> \thickapprox lambda</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}}\,dxc</tex>.}}

Поскольку == Обход случайного графа ==Приведем ряд утверждений, которые будут использованы в дальнейшем. Их доказательство, а также более детальный рассказ можно найти здесь<ref name="chap4">Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf</ref>.{{Лемма|id=lemma1|about=1|statement=Пусть <tex>d > 1</tex>c . Тогда вероятность < 1tex>p</tex>, нижний предел интегрирования имеет порядок что <tex>size(cc(v)) = O(\sqrt{t_0}log n)</tex>. Таким образом, весь интеграл не превосходит величины(<tex>cc</tex>e^{−\delta t_0{---}}компонента связности, содержащая <tex>v</tex>. Выберем ): <tex>\betap < 1</tex> {{---}} константа.|proof=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма поиска в ширину такимобразом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс.}}{{Теорема|id=th4|about=4|statement=Пусть <tex>e^p = \frac{d}{−\delta t_0n}, d > 1</tex> оказалось меньше, чем. <br><tex>e^\begin{-2 equation*} \ln nbegin{cases} = & \text{1) Найдутся такие $c_1, c_2$, что с $p \leq \dfracfrac{1}{n^}$ $\exists cc: size(cc) \in (c_1\log n; c_2n)$;} \\ & \text{2}</tex>) Число вершин в компонентах размера $O(\ln n)$ а.п.н. $\leq cn, и в случае <tex>c < 1$.} \\ & \quad\:\text{Тогда с $p = 1 - o(1)$ существует компонента связности размера $\Omega (n)$;} \\ \end{cases}\end{equation*}</tex> теорема доказана.}}

'''Случай === Проблема поиска в ширину ===[[Файл:Bfs_problem_on_random_graph.png|300px|thumb|left|Проблема поиска в ширину на случайном графе]]На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине <tex>c 1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>''', во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют.Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.<br><br><br><br><br>

Нам хочется доказать, что есть гигантская компонента=== Неоткрытые вершины ===Будем считать шагом алгоритма поиска открытие новой вершины. Тогда, как следствие, нам нужно, чтобы ветвящийся процесс на графе не вырождался дажепри После первых <tex>t \thickapprox \gamma ni</tex>. Иными словамишагов алгоритма, необходимолюбая из вершин, чтобы:<tex>P_{nкроме стартовой, p}(Y_{t_0} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>У нас может быть неоткрытой с вероятностью <tex>p = (1 - \dfracfrac{ c d}{n})^i</tex>. Значит, при Пусть <tex>t \thicksim \alpha nz_i</tex> выполнено<tex> 1 {{- (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}число вершин, открытых за первые <tex>i</tex>Применим [[Центральная предельная теорема| центральную предельную теорему]] кшагов алгоритма поиска. <tex>P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(Binom(n, 1 - e^{-c\alpha}) \le \alpha n).z_i</tex>Интегрирование пойдет от минус бесконечности дораспределены как <tex>\dfrac{\alpha n - Binomial(n− 1,1 − (1 - e^\frac{-c\alpha})d}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}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>.<br>* <tex>p′</tex> {{---}} вероятность того, что <tex>size(cc(v)) = O(\alpha log n)</tex> в модифицированном поиске в ширину.<br>* <tex>q</tex> {{---}} вероятность окончания процесса.<br>Тогда <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 - e− \frac{d}{n})^{s − i}</tex> {{---c}} вероятность, что <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) = \alphafrac{ds}{n}> 1</tex>.<br><br>Глубина дерева не меньше количества вершин, то мы получим искомое стремление вероятности к нулюпоэтому вероятность того, что процесс закончится с деревом глубины <tex>t</tex>, вычисляется по следующей формуле:<br><tex>a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}</tex><br>

Если === Вычисление вероятности исчезновения ==={{Лемма|id=lemma2|about=2|statement=Пусть <tex>\alpha m > 1 - e^{-c\alpha}</tex>, то вероятность, напротив, будет стрметиться к единице. Таким образом, критическое значение Пусть <tex>\alphaq</tex>, вплоть до которого есть именно стремление к нулю, {{---}} это решение уравнения единственный корень <tex>\alpha f(x) = x</tex> на <tex>[0, 1 - e^)</tex>. Тогда <tex>f_j(x) = \lim_{-cj \to \alphainfty}p(j) = q</tex> или, что равносильно, для <tex>x\in [0,1 - \alpha = e^{-c\alpha})</tex>. А это и есть уравнение из [[th2}}{{Теорема|about=5|id=th5| предыдущей теоремы]]statement=Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть <tex>f(x)</tex> {{---}} производящая функция числа потомков каждой вершины, если заменить а <tex>\lambdak</tex> на {{---}} ожидаемое количество потомков в каждой вершине. Тогда верно следующее:<br><tex>c\begin{equation*} \begin{cases} k \le 1 &\text{—$\;$ вероятность исчезновения равна 1, если вероятность} \\ & \;\;\;\;\;\,\text{появления ровно одного ребенка равна $1$;}\\ k > 1 &\text{—$\;$ вероятность исчезновения является }\\&\;\;\;\;\;\,\text{единственным решением $f(x) = x,\; x \in [0, 1)$;} \end{cases}\end{equation*}</tex>.

== Литература Вывод ==* 1. Введение Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-еширину на случайном графе <tex>G(n, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.\frac{d}{---n}} М)</tex>.Рассчитав <tex>p_0</tex> и <tex>p_1</tex>, можно сделать следующие выводы: МЦНМО, 2013 <br><tex>\begin{equation*} \begin{cases} d < 1\;\vee\; d = 1\;\wedge\; p_1 < 1&\text{---—$\;$ процесс завершится с вероятностью один;}\\ d = 1\;\wedge\; p_1 = 1&\text{—$\;$ процесс будет протекать бесконечно;} C.330-339 \\ d > 1&\text{—$\;$ вероятность исчезновения меньше единицы, но, если $p_0 = 0$, процесс не завершится, так как у каждой вершины}\\&\;\;\;\;\;\,\text{---найдется по крайней мере один потомок;}\\ \end{cases} ISBN 978-5-4439-0040-7\end{equation* 2. Karp R. The transitive closure of a random digraph}<//Random structures and algorithms. 1990. V. 1. P. 73–94.* 3. Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.tex>