gistfile1.txt

\documentclass[10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\inputencoding{utf8}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}

\newcommand{\Expect}{\mathbb E}
\newcommand{\PRob}{\mathbb P}
\newcommand{\leqs}{\leqslant}
\newcommand{\geqs}{\geqslant}
\newcommand{\eps}{\varepsilon}

\newtheorem{theorem}{Теорема}[section]
\newtheorem{note}[theorem]{Замечание}
\newtheorem{lemma}[theorem]{Лемма}

\begin{document}

\section{Обозначения}
Итак, мы будем иметь дело с двудольным графом, в котором за каждый шаг будет появляться ребро.
Условно назовём $2$ доли так: клиенты и фрагменты информации(далее просто фрагменты).
Обозначим количество клиентов за $n$, а количество фрагментов за $N$. 
На протяжении этой работы я буду считать, что $N$ велико, по сравнению с $n$.

Итак, начинается всё с того, что у нас есть пустой двудольный граф, в котором мы можем провести максимум $nN$ рёбер.
Пусть $G_m$ - это граф, в момент $m$, соответственно $G_0$ -- пустой граф, а в графе $G_m$ будет $m$ рёбер.
Также мы обозначим за $E(G)$ количество ребер в графе $G$.

Нас будет интересовать функция $Q(G_m)$ которая выдаёт нам минимальную степень вершины, из доли фрагментов, 
или другими словами, выбираем фрагмент, который скачало меньше всего клиентов, и выдаём это количество.

Мы постараемся проследить за тем, как ведёт себя случайная величина $Q(G_m)$ при разных моделях роста графа.

Также, сформулируем несколько теорем, которыми воспользуемся в последствии.
\begin{theorem}
Теорема Чернова для Бернулевских случайных величин. Пусть у нас есть $X_1, X_2, X_3, \dots X_n$ -- 
независимые Бернулевские случайные величины(не обязательно одинаково распределенные). Пусть $X = \sum\limits_{i = 1}^n X_i$ и
$\mu = \Expect X$, также пусть $\delta \in (0, 2e-1)$. Тогда выполняются следующие неравенства:

\begin{align*}
\PRob[X < (1-\delta)\mu] &< \exp\left(- \frac{\mu \delta^2}{2} \right)
\\
\PRob[X > (1+\delta)\mu] &< \exp\left(- \frac{\mu \delta^2}{4} \right)
\end{align*}

\end{theorem}

\section{Модель 1. Равномерный выбор рёбер.}
В этой модели граф будет расти следующим образом: для того, чтобы построить граф $G_{m+1}$ мы берём $G_{m}$ и 
проводим произвольное ещё не проведённое ребро, которых, как не сложно посчитать $nN - m$.

К сожалению, в терминах такой модели очень сложно что-то доказывать, поэтому мы сделаем небольшой трюк.
Создадим граф $H_p$, где $p \in [0, 1]$, который будет построен по следующему правилу: 
разыгрываем $nN$ Бернулевских случайных величин $I_{1,1}, I_{1,2}, \dots I_{n,N}$ и проводим ребро от $k$-го клиента к $K$ фрагменту, 
если $I_{k, K} = 1$.

Заметим, что случайный граф $G_m$ устроен следующим образом: все графы, в которых ровно $m$ рёбер, выпадают с одинаковой вероятностью.
А ежели взять граф $H_p$ при условии того, что $E(H_p) = m$, то тогда он устроен так же, как и $G_m$.
Вышесказанное намекает на то, что графы $G_m$ и $H_p$ похожи.

Посчитаем количество рёбер в графе $H_p$. Очевидно, что 
$E(H_p) = \sum\limits_{\substack{1 \leqs i \leqs n\\ 1 \leqs j \leqs N}} I_{i,j}$.
Также заметим, что $\Expect [E(H_p)] = p \cdot nN$.
Напишем для этой суммы $I_{i,j}$ теорему Чернова, которую сформулировали выше.
\begin{align*}
\PRob[\sum I_{i,j} > (1 + \delta) pnN ] &< \exp \left( - \frac{\delta^2}{4} pnN \right)
\\
\PRob[\sum I_{i,j} < (1 - \delta) pnN ] &< \exp \left( - \frac{\delta^2}{2} pnN \right)
\end{align*}
Неравенство выше будет выполняться для любого $\delta \in (0, 1)$.
Комбинируя неравенства выше, мы получаем, что
\begin{align*}
\PRob[E(H_p) \in (pnN(1 - \delta), pnN(1 + \delta)) ] 
	\geqs 
1 - \exp \left( - \frac{\delta^2}{4} pnN \right) - \exp \left( - \frac{\delta^2}{2} pnN \right) \geqs&
\\
\geqs 1 - 2 \cdot \exp \left( - \frac{\delta^2}{4} pnN \right)&
\end{align*}
Запомним это неравенство. Оно нам пригодится, когда мы будем переходить от графа $H_p$ к основной модели $G_m$.

Теперь рассмотрим, как ведёт себя функция $Q(H_p)$. Для начала мы попробуем посчитать $\PRob\big(Q(H_p) \geqs q n\big)$, 
т.е. вероятность того,
что все фрагменты скачены по крайней мере $qn$ клиентами. 
Ясно, что рассматривать $q > p$ немного глупо, т.к. ребер в графе $H_p$ в среднем $pnN$, 
а значит, самое лучшее, на что мы можем рассчитывать, что каждый фрагмент скачан $p$ клиентами.

Итак, $q < p$. Рассмотрим вероятность того, что первый фрагмент скачали хотя бы $qn$ клиентов, 
т.е. $\PRob\left(\sum\limits_{i=1}^n I_{i,1} \geqs qn\right)$. Пусть $\delta = 1 - \frac{q}{p}$, тогда:
\begin{align*}
\PRob\left(\sum_{i=1}^n I_{i,1} \geqs qn\right) = \PRob\left(\sum_{i=1}^n I_{i,1} \geqs (1 - \delta) pn\right) 
= 1 - \PRob\left(\sum_{i=1}^n I_{i,1} < (1 - \delta) pn\right),
\end{align*}
применяя теорему Чернова получаем:
\begin{align*}
&\PRob\left(\sum_{i=1}^n I_{i,1} < (1 - \delta) pn\right) < \exp\left(- \frac{pn \delta^2}{2} \right)
\\
&\PRob\left(\sum_{i=1}^n I_{i,1} \geqs qn\right) > 1 - \exp\left(- \frac{pn \delta^2}{2} \right)
\end{align*}

Теперь посмотрим, что мы знаем, про вероятность того, что все фрагменты скачены хотя бы $qn$ клиентами.
Заметим, что $I_{i,j}$ независимы, а значит и то, что происходит с первым фрагментом не зависит от того, 
что происходит с остальными фрагментами, а значит:
\begin{align*}
&\PRob\big(Q(H_p) \geqs q n\big) = \left( \PRob\left(\sum_{i=1}^n I_{i,1} \leqs qn\right)  \right)^N >
\\
&\left( 1 - \exp\left(- \frac{pn \delta^2}{2} \right) \right)^N > 1 - N \cdot \exp\left(- \frac{pn \delta^2}{2} \right) 
\end{align*}
где $\delta = 1 - \frac{q}{p}$.
Перепишем полученное в другом виде:
\begin{align*}
&\PRob\big(Q(H_p) \geqs (1-\delta_1)p n\big) > 
	1 - N \cdot \exp\left(- \frac{pn \delta_1^2}{2} \right) \text{, где } \delta_1 \in (0,1).
\end{align*}

Теперь мы попробуем перейти от графа $H_p$ обратно к графу$G_p$, для чего докажем следующую лемму:
\begin{lemma}
Пусть $A$ - множество всех графов, который обладают некоторым монотонным свойством(т.е. это свойство не пропадает от добавления рёбер).
Тогда, если $\Prob( H_p \in A) > 1 - \eps$, то
$$
\Prob(G_m \in A) > 1 - \frac{\eps}{1 - \exp\left(-\frac{\sigma^2}{4}pnN\right)}
$$
где $m = \lceil pnN(1+\delta) \rceil$, a $\delta \in (0,1)$.
\end{lemma}

\begin{proof}
Для начала вспомним, что 
$$
\PRob\big( E(H_p) < m) = \PRob\big( E(H_p) < pnN(1+\sigma) \big) > 1 - \exp\left(-\frac{\sigma^2}{4}pnN\right)
$$
откуда получаем, что 
$$
\PRob\big(H_p \in A | E(H_p) < m\big) > 1 - \frac{\eps}{1 - \exp\left(-\frac{\sigma^2}{4}pnN\right)} = 1 - \eta.
$$
%теперь воспользуемся формулой полной вероятности:
%\begin{align*}
%\PRob\big(H_p \in A, E(H_p) < m\big) = \sum_{l=0}^{m-1} \PRob(H_p \in A | E(H_p) = l) \cdot \PRob(E(H_p) = l).
%\end{align*}

Теперь применим немного магии и сделаем из наших непривлекательных графов $H_p$ классные $G_m$.
А именно, мы рассмотрим граф $H_p$ при условии того, что $E(H_p) < m$, и после этого в этот случайный граф, 
в котором меньше $m$ рёбер случайным образом(т.е. на каждом шагу рёбра выбираются равномерно) добавим несколько рёбер, 
пока их не станет ровно $m$. Заметим, что мы получим случайный граф, в котором ровно $m$ ребер, при этом, несложно понять, 
что этот граф по распределению совпадает с $G_m$, т.к. мы нигде не различали рёбра между собой, а значит они перестановочны.
При этом мы знаем, что граф, с которого мы начинали, обладал свойством $A$ с вероятностью большей, чен $1 - \eta$, 
а значит $\PRob(G_m \in A) > 1 - \eta$.
\end{proof}

\end{document}