Изменения

Свойство $\mathcal{A}$ называется '''монотонным''' (англ. ''monotone property''), если для любой пары $\forall\,G_1,G_2\in G(n,p),\, E(G_1)\subset E(G_2)$ выполнено следствие: $G_1\in \mathcal{A}\Rightarrow G_2\in\mathcal{A}$

Функция $p_0(n)$ называется '''пороговой''' для монотонного свойства $\mathcal{A}$ (англ. ''threshold''), если для любой функции вероятности $\forall\,p(n)$ выполнено:* $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 0$, если $p(n)/p_0(n)\xrightarrow[n \to \infty]{} 0$* $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$, если $p(n)/p_0(n)\xrightarrow[n \to \infty]{} \infty$

|statement=Для любого монотонного свойства $\mathcal{A}$ верно следствие: $p_2\geqslant p_1\Rightarrow P(G(n,p_2)\in \mathcal{A})\geqslant P(G(n,p_1)\in \mathcal{A})$

* Заметим, что функция $f(p)=P(G(n,p)\in\mathcal{A})$ непрерывна. На самом деле это многочлен, у которого степень оценивается как количество ребер в полном графе. :* Вероятность получить конкретный граф равна $p^\alpha\cdot(1-p)^\beta$, где $\alpha$ и $\beta${{---}} количество присутствующих и отсутствующих ребер соответственно ($\alpha+\beta=\frac{n(n-1)}{C_n^2}$).И, чтобы :* Чтобы получить $f(p)$, нужно просуммировать такие многочлены по всем графам из $\mathcal{A}$.

* Проделаем Мы по $n$ научились находить такую вероятность $p_0$, что $P(G(n,p_0)\in\mathcal{A})=1/2$. Теперь проделаем это для каждого $n\in\mathbb{N}$ и получим функцию $p_0(n)$. Она окажется пороговой для свойства $\mathcal{A}$.

Пусть $\dfrac{p(n)/}{p_0(n)}\xrightarrow[n \to \infty]{} \infty$. Докажем, что $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$.

Выберем $m$ графов из $G(n,p_0)$ $G_1,\ldots,G_m$ и рассмотрим $H=G_1\cup G_2\cup\ldots\cup G_m$.<br>В нем фиксированного ребра не будет тогдаДокажем, когда ни в одном из $G_i$ нет ребра, то есть что неравенство $P(\text{в }H\text{ нет ребра})=1-(1-p_0)^m$, то есть $H\in G(n,1-p(1-p_0n)^m)$.* $P(G(n,p)\in\mathcal{A})>P(G(n,1-(1-p_0(n))^m)\in\mathcal{A})$ верно при достаточно больших $n$. * Для этого сравним по лемме о монотонности вероятности достаточно установить: $p$ и $(n)>1-(1-p_0(n))^m$.: * $p(n)>m p_0\geqslant 1-(1-p_0n)^m$. Первое неравенство Неравенство верно с некоторого момента, так как $p\gg p_0$, второе {{---}} неравенство Бернулли (нужно $(-p_0)>-1$, что верно, и $m\notin[0,1]$; запомним это)по предположению.:* $P(Gm p_0(n,1-(1-p_0)^m)\in\mathcal{A})=P(H\in\mathcal{A})\geqslant 1-(1-P(Gp_0(n,p_0)\in\mathcal{A}))^m=1-1/2^m$. Про первое равенство уже поняли, про последнее {{---}} так выбрали $p_0$Это неравенство Бернулли.Для доказательства неравенства достаточно понять, что если Оно верно при $H\notin\mathcal{A}$, то все $G_i\notin\mathcal{A}$ (действительно, ведь $P(H\in\mathcal{A})=1-Pp_0(H\notin\mathcal{A}n)$, перенесем, уберем по единице). А это верно в силу монотонности свойства $\mathcal{A}$.* $1>-1/2^m>1-\varepsilon$. Это равносильно и $m\geqslant \log_2{notin[0,1/\varepsilon}]$. Так как Первое ограничение соблюдено, далее выберем $m$ ограничена только снизу, нам не составит труда подобрать такое, чтобы сработало неравенство Бернуллис учетом второго ограничения.

Мы по <br>Выберем графы $G_1,\varepsilon$ научились пониматьldots, что $P(G_m\in G(n,p_pp_0(n)\in\mathcal{A})>1-\varepsilon$ верно с некоторого момента, что и значит рассмотрим $P(G(n,p)\inH=G_1\mathcal{A})cup G_2\xrightarrow[n cup\to ldots\infty]{} 1cup G_m$.

Теперь пусть Оказывается, что $pP(G(n)/,1-(1-p_0(n))^m)\in\xrightarrow[n mathcal{A})=P(H\to in\infty]mathcal{A} 0)$.Зафиксируем * Действительно, посмотрим, с какой вероятностью в $\varepsilonH$не окажется фиксированного ребра. Так как Это будет тогда, когда во всех графах $1-\varepsilon<1G_i$не будет его, то найдется такое натуральное $m$, что есть $P(\text{в }H\text{ нет ребра})=(1-\varepsilonp_0(n))^m<1/2$.Так как Тогда в $p\ll p_0H$, то будет ребро с некоторого момента вероятностью $p 1-(1-p_0(n))^m<p_0$. Мы получили даже, тогда что $p_0>m pH\geqslant in G(n,1-(1-pp_0(n))^m)$.

<br>Оценим вероятность принадлежности $H$ свойству $\mathcal{A}$: $P(H\in\mathcal{A})\geqslant 1-(1-P(G(n,p_0(n))\in\mathcal{A}))^m$. * Перепишем неравенство с учетом $P(H\in\mathcal{A})=1-P(H\notin\mathcal{A})$: $(1-P(G(n,p_0(n))\in\mathcal{A}))^m\geqslant P(H\notin\mathcal{A})$.* Если мы покажем, что из правого события следует левое, то тогда докажем само неравенство.* Справа {{---}} вероятность того, что граф $H$ не попал в $\mathcal{A}$. Тогда (в силу монотонности свойства) и все его подграфы (в том числе и $G_i$) тоже не попали в $\mathcal{A}$.* А слева как раз и есть вероятность того, что все графы $G_i$ не попали в $\mathcal{A}$. <br>По построению $p_0(n)$ правую часть последнего неравенства можно легко посчитать: $1-(1-P(G(n,p_0(n))\in\mathcal{A}))^m=1-(1-1/2)^m=1-1/2^m$ <br>Совершим последнюю оценку: $1-1/2^m>1-\varepsilon$.* Это равносильно $m\geqslant \log_2{1/\varepsilon}$. Положим $m=\log_2{1/\varepsilon}+2$. Тогда исходное неравенство верно, а также ограничение для неравенства Бернулли выполнено. <br>За несколько шагов мы показали, что неравенство $P(G(n,p(n))\in\mathcal{A})>1-\varepsilon$ выполняется с некоторого момента. Это и значит $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$ <br>Теперь пусть $\dfrac{p(n)}{p_0(n)}\xrightarrow[n \to \infty]{} 0$. Докажем, что $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 0$. <br>Зафиксируем $\varepsilon>0$.* (1) Так как $1-\varepsilon<1$, то найдется такое натуральное $m$, что $(1-\varepsilon)^m<1/2$.* (2) Так как $p\ll p_0$, то с некоторого момента $p(n) m<p_0(n)$, тогда $p_0(n)>m p(n)\geqslant 1-(1-p(n))^m$. <br>Выберем $m$ графов из $G(n,p(n))$ $G_1,\ldots,G_m$ и рассмотрим $H=G_1\cup G_2\cup\ldots\cup G_m$. Как мы уже знаем, $H\in G(n,1-(1-p(n))^m)$. <br>* $(1-P(G(n,p(n))\in\mathcal{A}))^m=P(\forall\,i\colon G_i\notin\mathcal{A})\geqslant P(H\notin\mathcal{A})\geqslant1/2$. * Из нового только последнее неравенство, остальное уже доказано. * Оно следует из $P(H\in\mathcal{A})=P(G(n,1-(1-p(n))^m)\in\mathcal{A})<P(G(n,p_0(n))\in\mathcal{A})=1/2$. В последнем неравенстве мы пользуемся леммой о монотонности вероятности и (2). <br>* $1/2>(1-\varepsilon)^m$. Из-за выбора $m$по (1). Тогда $(1-P(G(n,p(n))\in\mathcal{A}))^m>(1-\varepsilon)^m\Rightarrow P(G(n,p(n))\in\mathcal{A})<\varepsilon$Мы по $\varepsilon$ научились понимать, что $P(G(n,p_0(n))\in\mathcal{A})<\varepsilon$ верно с некоторого момента, что и означает сходимость.