66
правок
Изменения
м
small fix
{{Определение
|definition =
Свойство $\mathcal{A}$ называется '''монотонным''' (англ. ''monotone property''), если '''forall лучше заменить на "для любого": не стоит сокращать русские слова математическими симолами там, где они не несут математического смысла''' любой пары $\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}$
}}
{{Определение
|definition =
Функция $p_0(n)$ называется '''пороговой''' для монотонного свойства $\mathcal{A}$ (англ. ''threshold''), если '''тут тоже''' для любой функции вероятности $\forall\,p(n)$ выполнено:
* $P(G(n,p)\in\mathcal{A})\xrightarrow[n \to \infty]{} 0$, если $p(n)/p_0(n)\xrightarrow[n \to \infty]{} 0$
* $P(G(n,p)\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$, если $p(n)/p_0(n)\xrightarrow[n \to \infty]{} \infty$
{{Лемма
|about=о монотонности вероятности
|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})$ '''тут, видимо, надо написать, что для какого-то свойства? можешь мне объяснить в тг, что это такое. лучше унифицировать обозначения с первой статьей про случайные графы, если это просто что-то оттуда в другой записи'''
|proof=
Пусть $p=\dfrac{p_2-p_1}{1-p_1}\in[0,1]$. Выберем случайно граф $G_1$ из $G(n,p_1)$, затем $G$ из $G(n,p)$ и рассмотрим $G_1\cup G$.
|proof=
Сначала найдем эту пороговую функцию. Зафиксируем $n$.
* Заметим, что функция $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}$.
* $f(0)=0$, $f(1)=1$, так как свойство нетривиальное и монотонное (то есть пустой граф точно не удовлетворяет ему, тогда как полный должен удовлетворять).
* По теореме Больцано-Коши найдется такое $p_0$, что $P(G(n,p_0)\in\mathcal{A})=1/2$.
* Проделаем Мы по $n$ научились находить такую вероятность $p_0$, что $P(G(n,p_0)\in\mathcal{A})=1/2$. Теперь проделаем это '''тут лучше переформулировать попонятнее''' для каждого $n\in\mathbb{N}$ и получим функцию $p_0(n)$. Она окажется пороговой для свойства $\mathcal{A}$.
Докажем это.
Пусть '''оформи как $\frac'''$dfrac{p(n)/}{p_0(n)}\xrightarrow[n \to \infty]{} \infty$.
'''вот тут идёт стена текста, проструктурируй чуть лучше по строкам и абзацам'''
Выберем $m$ графов из $G(n,p_0)$ $G_1,\ldots,G_m$ и рассмотрим $H=G_1\cup G_2\cup\ldots\cup G_m$.
В нем фиксированного ребра не будет тогда, когда ни в одном из $G_i$ нет ребра, то есть $P(\text{в }H\text{ нет ребра})=1-(1-p_0)^m$, то есть $H\in G(n,1-(1-p_0)^m)$.
* $P(G(n,p)\in\mathcal{A})>P(G(n,1-(1-p_0)^m)\in\mathcal{A})$. Для этого сравним $p$ и $1-(1-p_0)^m$: $p>m p_0\geqslant 1-(1-p_0)^m$. Первое неравенство верно с некоторого момента, так как $p\gg p_0$, второе {{---}} неравенство Бернулли '''лучше избавиться от скобок и написать нормальное предложение'''(нужно . Оно верно при $(-p_0)>-1$, что верно, и $m\notin[0,1]$; запомним это). Первое ограничение соблюдено, потом выберем $m$ с учетом этого ограничения.
* $P(G(n,1-(1-p_0)^m)\in\mathcal{A})=P(H\in\mathcal{A})\geqslant 1-(1-P(G(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-P(H\notin\mathcal{A})$, перенесем, уберем по единице). А это верно в силу монотонности свойства $\mathcal{A}$.
* $1-1/2^m>1-\varepsilon$. Это равносильно $m\geqslant \log_2{1/\varepsilon}$. Так как Положим $m=\log_2{1/\varepsilon}+2$ ограничена только снизу. Тогда исходное неравенство верно, нам не составит труда подобрать такое, '''лучше написать букву явно''' чтобы сработало неравенство а также ограничение для неравенства Бернулливыполнено.
Мы по зафиксировали $\varepsilon$ '''переставь слова''' научились пониматьи доказали, что $P(G(n,p_p)\in\mathcal{A})>1-\varepsilon$ верно с некоторого момента, что . Это и значит $P(G(n,p)\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$
Теперь пусть $\dfrac{p(n)/}{p_0(n)}\xrightarrow[n \to \infty]{} 0$.
Зафиксируем $\varepsilon$. Так как $1-\varepsilon<1$, то найдется такое натуральное $m$, что $(1-\varepsilon)^m<1/2$.
Так как $p\ll p_0$, то с некоторого момента $p m<p_0$, тогда $p_0>m p\geqslant 1-(1-p)^m$.
