|
Сначала найдем эту пороговую функцию. Зафиксируем $n$.
- Заметим, что функция $f(p)=P(G(n,p)\in\mathcal{A})$ непрерывна. На самом деле это многочлен, у которого степень оценивается как количество ребер в полном графе.
- Вероятность получить конкретный граф равна $p^\alpha\cdot(1-p)^\beta$, где $\alpha$ и $\beta$— количество присутствующих и отсутствующих ребер соответственно ($\alpha+\beta=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}$.
Докажем это.
Пусть $\dfrac{p(n)}{p_0(n)}\xrightarrow[n \to \infty]{} \infty$. Докажем, что $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$.
Докажем, что неравенство $P(G(n,p(n))\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(n)$. Неравенство верно с некоторого момента, так как $p\gg p_0$ по предположению.
- $m p_0(n)\geqslant 1-(1-p_0(n))^m$. Это неравенство Бернулли. Оно верно при $(-p_0(n))>-1$ и $m\notin[0,1]$. Первое ограничение соблюдено, далее выберем $m$ с учетом второго ограничения.
Выберем графы $G_1,\ldots,G_m\in G(n,p_0(n))$ и рассмотрим $H=G_1\cup G_2\cup\ldots\cup G_m$.
Оказывается, что $P(G(n,1-(1-p_0(n))^m)\in\mathcal{A})=P(H\in\mathcal{A})$.
- Действительно, посмотрим, с какой вероятностью в $H$ не окажется фиксированного ребра. Это будет тогда, когда во всех графах $G_i$ не будет его, то есть $P(\text{в }H\text{ нет ребра})=(1-p_0(n))^m$. Тогда в $H$ будет ребро с вероятностью $1-(1-p_0(n))^m$. Мы получили даже, что $H\in G(n,1-(1-p_0(n))^m)$.
Оценим вероятность принадлежности $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}$.
По построению $p_0(n)$ правую часть последнего неравенства можно легко посчитать: $1-(1-P(G(n,p_0(n))\in\mathcal{A}))^m=1-(1-1/2)^m=1-1/2^m$
Совершим последнюю оценку: $1-1/2^m>1-\varepsilon$.
- Это равносильно $m\geqslant \log_2{1/\varepsilon}$. Положим $m=\log_2{1/\varepsilon}+2$. Тогда исходное неравенство верно, а также ограничение для неравенства Бернулли выполнено.
За несколько шагов мы показали, что неравенство $P(G(n,p(n))\in\mathcal{A})>1-\varepsilon$ выполняется с некоторого момента. Это и значит $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 1$
Теперь пусть $\dfrac{p(n)}{p_0(n)}\xrightarrow[n \to \infty]{} 0$. Докажем, что $P(G(n,p(n))\in\mathcal{A})\xrightarrow[n \to \infty]{} 0$.
Зафиксируем $\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$.
Выберем $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)$.
$(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).
$1/2>(1-\varepsilon)^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$ верно с некоторого момента, что и означает сходимость. |
