Теорема о существовании порога для монотонных свойств — различия между версиями

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

Версия 04:11, 19 июня 2020

Рассмотрим биномиальную модель случайного графа $G(n,p)$.


Определение:
Подмножество $\mathcal{A}$ всех графов на $n$ вершинах называется свойством (англ. graph property).


Определение:
Свойство называется нетривиальным (англ. non-trivial property), если существуют графы, как удовлетворяющие ему, так и нет.


Определение:
Свойство $\mathcal{A}$ называется монотонным (англ. monotone property), если для любой пары $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), если для любой функции вероятности $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$

Мы уже знакомы с некоторыми пороговыми функциями.


Лемма (о монотонности вероятности):
Для любого монотонного свойства $\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})$
Доказательство:
[math]\triangleright[/math]

Пусть $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$.

В нем с вероятностью $(1-p)(1-p_1)=(1-p_2)$ не будет фиксированного ребра, как и в графе $G_2$. Мы смогли представить выбор $G_2$ как объединение, один из которых — выбор графа $G(n,p_1)$, значит $P(G(n,p_2))\geqslant P(G(n,p_1))$
[math]\triangleleft[/math]


Теорема (Bollob́as-Thomason):
Любое нетривиальное монотонное свойство имеет пороговую функцию.
Доказательство:
[math]\triangleright[/math]

Сначала найдем эту пороговую функцию. Зафиксируем $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$ верно с некоторого момента, что и означает сходимость.
[math]\triangleleft[/math]