[TOC]

# 1. Неравенство Маркова, Чебышева. Быстрая сортировка, +

## Общие понятия

## Быстрая сортировка

Прокидываем относительно pivot что-то влево, а что-то вправо. Pivot выбираем случайно. Докажем, что работает за O(n log n).

Скорость работы пропорциональна количеству сравнений

Отсортированный массив: $x_1, x_2, ..., x_n$

Найдем вероятность, что $x_i, x_j$ были сравнены за время работы алгоритма

Когда это происходит:

Если $x_i, x_j$ были находились по одну сторону от pivot, то они сравнены не будут, просто перекинуты в какую-то из сторон, если pivot выбран внутри интервала $(x_i, x_j)$, то они просто будут раскидаы в разные сторону и сравниваться друг с другом не будут.

Единственная опция - pivot один из этих двух элементов. Вероятность этого равна $P(x_i or x_j - pivot) = 2 / (j - i +1)$.

$E(algo time) = \sum_{i < j}E(x_i or x_j - pivot) = \sum_{i < j}2/(j-i+1) = $

$i = 1: 2 \cdot (1/1+1/2+1/3+...+1/n) $ ~log n

$i = 2: 2 \cdot (1/1+1/2+1/3+...1/(n-1))$

$i = n-1: 2 \cdot (1)$

Итого на одну итерацию: $log{n} + o(log{n})$

Итого : $O(n \log{n})$

Про квадрат история в том, что его вероятность стремится к нулю, иначе мат. ожидание было бы квадратное

## Неравенство Маркова

**Само неравенство:**

$P(X \ge C) \leq E(X)/ c$
Выполняется для неотрицательных случайных величин.

**Док-во:**

$] x_1 \le x_2 \le ... \le x_n =>$

$EX = \sum_{i}(p_i x_i) \ge \sum_{i=k}^{n}p_i x_i$

Заменим $x_i$ на минимальный из элементов, на которые смотрим сейчас, а потом заменим $x_k = c$, а вероятность тогда как раз есть сумма слева:

$\sum_{i=k}^{n}p_i x_i \ge (p_k + ... + p_n)\cdot x_k = P(X \ge c)\cdot c$

## Неравенство Чебышева

**Само неравенство:**

$P(|X-EX| \ge \sqrt{c}) \le DX / c$

**Док-во:**

Возведем в квадрат:

$P((X-EX)^2 \ge c)$

Пусть $Y = (X-EX)^2=>$

Возьмем неравенство Маркова:

$P(Y \ge C) = E(Y)/ c$

$P((X-EX)^2 \ge C) = E((X-EX)^2)/ c$

$P(|X-EX| \ge \sqrt{c}) = DX / c$

# 2. Поиск медианы за 2n+o(n), +

Тут есть какой-то quick select, работает как quick sort.

Массив длины n.

Случайно с повторением выберем $n^{0.75}$ элементов. Сортируем за: $n^{3/4}\log{n^{3/4}} = o(n)$. Получается, что сортировка такого массива бесплатная.

Найдем медиану в маленьком массиве, найдем $l = 1/2n^{3/4}-\sqrt{n}, r=1/2n^{3/4}+\sqrt{n}$

Сравниваем l, r с исходным массивом; слева то, что меньше l, справа, что больше r, иначе в серединку. Можем сравнивать со случайным из этих двух, тогда в среднем 1.5n вместо 2n.

Мы хотим, чтобы m была между l, r и размер был маленький.

Тогда ситуации:

1. $|X_1+X_2| < n / 2 ->$ медиана справа, выдаем $fail$
2. $|X_1| > n/2->$ медиана левее левой границы, выдаем $fail$
3. $|X_2| > 4n^{3/4}-> fail$
4. $|X_2| \le 4n^{3/4}->$ сортируем, ищем, выдаем ответ

Докажем, что **вероятности первой и второй ситуации** очень малы:

Чтобы элемент l был правее медианы, нам надо, чтобы мы взяли $1/2n^{3/4}+\sqrt{n}$ элементов больше медианы.

$X_i$ - i-ый элемент из маленького массива правее медианы, Бернуллиевая величина, тогда по Чебышеву

$P(\sum_1^{n^{3/4}}{X_i} \ge 1/2n^{3/4}+\sqrt{n}) = P(\sum_1^{n^{3/4}}{X_i} - 1/2n^{3/4}\ge \sqrt{n})$
$= P(Y - EY\ge \sqrt{n}) \le DY/n = \frac{n^{3/4}/4}{n}\sim \frac{1}{4n^{0.25}}$

Докажем, что **вероятность большой длины** очень мала:

Тут хотя бы одна из частей $[l, m], [m, r]$ должна быть больше чем $2n^{3/4}$. Рассмотрим для $[l, m]$.


Кусок в кружочке имеет длину $n/2 - 2n^{3/4}$. В этот кусок попало не меньше чем $1/2 n^{3/4}-\sqrt{n}$ элементов из X’.

Опять по Чебышеву:

$Z_i$ - i-ый элемент из маленького массива попал в конец, Бернуллиевая величина, тогда по Чебышеву

$P(\sum_i^{n^{3/4}}{Z_i} \ge n/2 - 2n^{3/4}) = P(\sum_i^{n^{3/4}}{X_i} - 1/2n^{3/4}\ge \sqrt{n})$
$= P(Y - EY\ge \sqrt{n}) \le DY/n = \frac{n^{3/4}/4}{n}\sim \frac{1}{4n^{0.25}}$

# 3. Неравенство Чернова. Бросание монетки +

## Общая формулировка

Пусть есть у нас функция $f_t(x) = e^{xt}, t > 0$ -- используется в производящей функции ($E[e^{xt}] = g_x(t)$)

Из неравенства Маркова: $P[X\geq a]=P[e^{xt}\geq e^{at}]$ (вследствие монотонности)

Применим к правой части Маркова: $P[X\geq a] = P[e^{xt} \geq e^{at}] \leq \frac{E(e^{xt})}{e^{at}}$

Нам интересно когда тут минимум, а это тогда когда мы будем минимизировать по t

Итого оценка Чернова: $P[X\geq a]\leq \min_{t >0}\frac{E(e^{xt})}{e^{at}}$

## Пуассоновский процесс

Пусть X - биномиальная случайная величина

$P[X=k] = C_n^k\cdot p^k\cdot (1-p)^k$

Тогда Пуассоновским процессом будет называться с.в. такая что:

$Y =Y_1 + Y_2 + ... + Y_n$, где $P[Y_i=1]=p_i$

Найдем мат. ожидание этой штуки: $EY = E(\sum_{i=1}^n Y_i) = \sum_{i=1}^n EY_i = \sum_{i=1}^n p_i$

## Неравенство Чернова

На самом деле, мы хотим оценить вот такую штуку:

$P[Y\geq (1+\delta)E(Y)] \leq ?$

Из определения неравенства Чернова получаем:

$P[e^{Yt}\geq e^{(1+\delta)E(Y)t}] \leq \min_{t > 0}\frac{E(e^{Yt})}{e^{(1+\delta)E(Y)}}$

Оценим мат. ожидание: $E(e^{Yt}) = E(e^{Y_1 t + Y_2t+ ... + Y_nt}) = \prod_{i=1}^n e^{Y_i t}=\prod_{i=1}^n E(e^{Y_i t})$

Заметим, что мы умеем считать м.о. для того что стоит у нас под знаком произведения,поскольку $Y_i$ - величина с распределением Бернулли:

$E(e^{Y_it}) = p_i\cdot e^t + (1-p_i)$

Вернемся к тому, что смотрели раньше:

$\prod_{i=1}^n e^{Y_i t}=\prod_{i=1}^n E(e^{Y_i t}) = \prod_{i=1}^n 1+ p_i(e^t-1)$

Можем использовать что $1+x\leq e^x$ (из того что $e^x = 1 + x + x^2/2 + ...$)

Вернемся опять к тому что было раньше: $\prod_{i=1}^n 1+ p_i(e^t-1) = \prod_{i=1}^n e^{p_i(e^t-1)}=exp(\sum_{i=1}^n p_i(e^t-1))$
$= exp(\sum p_i \cdot (e^t-1)) = exp(\mu\cdot (e_t-1)), \mu=E(Y)=\sum p_i$

Итого: $P[Y\geq (1+\delta)E(Y)]\leq \frac{e^{\mu(e^t - 1)}}{e^{t\mu (1+\delta)}}$

Пусть $t=\ln(1+\delta) => e^t-1=\delta, e^{(1+\delta)t}=(1+\delta)^{1+\delta}$

При такой подстановке получим: $P[Y\geq (1+\delta)\mu]\leq (\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu$

## $\delta \in (0, 1]$

**Утверждение:** при $\delta\in (0, 1]$ выполняется $(\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu \leq e^{-\mu \delta^2 / 3}$

При таких значениях дельта можно сильно упростить исходное неравенство.

Для этого $(\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu \leq e^{-\mu \delta^2 / 3}$

$\frac{e^\delta}{(1+\delta)^{1+\delta}} \leq e^{- \delta^2 / 3}$

Прологарифмируем: $\delta + (1+\delta)\ln{1+\delta} \leq -\frac{1}{3}\delta^2$

$\delta + (1+\delta)\ln{1+\delta} + \frac{1}{3}\delta^2<0, \forall \delta\in(0, 1)$

Ну тут возьмем производные:

$f'(\delta) = \ln{1+\delta}+2/3\delta$

$f''(\delta) = -\frac{1}{1+\delta} + 2/3$

Видим что первая производная и в нуле и в 1 отрицательная. а между ними функция сначала убывала, а потом возрастала. Так что на всем интервале значение отрицательное.

## $1+\delta \geq 6$

**Утверждение:** $P[X\geq R] \leq 2^{-R}$

Исходная штука:

$P[Y\geq (1+\delta)\mu]\leq (\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu \leq (\frac{e^\delta}{(1+\delta)^{1+\delta}})^\mu e^\mu = (\frac{e^{1+\delta}}{(1+\delta)^{1+\delta}})^\mu = (\frac{e}{1+\delta})^{\mu(1+\delta)}$=> $P[Y\geq R] \leq (\frac{e}{1+\delta})^R$

При $1+\delta > 6 => \frac{e}{1+\delta} < 0.5$ =>

$P[Y\geq R] \leq 2^{-R}$

## Двусторонняя оценка

$P[Y\leq (1-\delta)EY]\leq e^{-\frac{\mu\delta^2}{2}}$

$P[|Y-EY|\geq \delta EY]\leq e^{-\mu\delta^2 / 2}+ e^{-\mu\delta^2/3} \leq 2e^{-\mu\delta^2/3}$

## Бросание монетки

Пусть $X=X_1+...+X_n, X_i$- бросание честной монетки

Тогда $P[|X-0.5 n| \geq 0.5\sqrt{6n\ln{n}}]\leq ?$

$\delta = \sqrt{\frac{6\ln{n}}{n}}$

Тогда $P[|X-0.5 n| \geq 0.5\sqrt{6n\ln{n}}]\leq 2e^{-\ln{n}}=2/n$

То есть вероятность отстоять от среднего на такую величину очень мала (меньше 2/n)

При этом Чебышев бы дал: $P[|X-n/2|\geq n/4]\leq \frac{DX}{n^2/16} = 4/n$

Оценка в два раза слабее хотя граница сильно больше

# 4. Set balancing (умножение матрицы на 1 и -1) +

## Чернов для Бернулли

Попробуем для последовательности испытаний Бернулли еще написать. Для этого воспользуемся родственной с.в. Y=2X-1, тогда $Y=\sum_{i=1}^n Y_i$

**Утверждение:** $P[Y\geq a]\leq e^{-\frac{a^2}{2n}}, a>0$

**Док-во:**

Посчитаем мат ожидание для одного испытания: $E(e^{tY_i}) = 0.5e^t+0.5e^{-t}$

$e^t = 1+t/1!+t^2/2!+...$

$e^{-t} = 1-t/1!+t^2/2!+...$

А сумма тогда: $e^t+e^{-t} = 2 \cdot(1 + t^2/2!+t^4/4!+...)$

При этом $e^{t^2/2} = \sum_{i=0}^{\infty}(t^2/2)^i / i!$

Таким образом, то что написано двумя строчками выше меньше чем то что на предыдущей =>

$E(e^{tY_i}) = 0.5e^t+0.5e^{-t} \leq e^{t^2/2}$

Тогда $E(e^{tY}) \leq e ^{nt^2/2}$

$P[Y\geq a] = P[e^{Yt}\geq e^{at}] \leq \frac{Ee^{Yt}}{e^{at}}\leq \frac{e^{nt^2/2}}{e^{at}} = e^{nt^2/2 - at}$

Такая штука достигает минимума при $t=a/n$

Итого получим что: $P[Y\geq a]\leq e^{-\frac{a^2}{2n}}$

Из симметричности: $P[Y\leq -a]\leq e^{-\frac{a^2}{2n}}$

Тут теперь можно перейти обратно к обычному Бернулли:

$P[X \geq EX +a] \leq e^{-\frac{2a^2}{n}}$

$P[X\geq (1+\delta)EX] \leq e^{-\delta^2 n /2}$

## Матрица из -1 и 1

Пусть есть матрица из нулей и 1

$a_{11}... a_{1m}$

$...$

$a_{n1}...a_{nm}$

Хотим ее умножить на вектор $(x_1, x_2, ..., x_m)$ такой чтобы $Ax \sim 0$ ($||Ax||_\infty\leq \sqrt{4mln{n}}$)

$||Ax||_\infty = max_i (a_{i1}x_1+...+a_{im}x_m)$

Вот то что справа написано это как будто мы k раз кинули монетку и k это сколько из ашек получилось единицами

Давайте найдем вероятность, что если мы зафиксируем набор ашек и будем случайно выбирать x, то нам не повезет.

$P[a_{i1}x_1+...+a_{im}x_m]\geq \sqrt{4m\ln{n}}$

Пусть $Y_i = a_{i1}x_1$

давайте используем, что $P[|Y|\geq a]\leq 2e^{-\frac{a^2}{2n}}, a>0$

Только у нас не n, а k слагаемых, так что выходит:

$P[|Y|\geq a]\leq 2e^{-\frac{a^2}{2k}}\leq 2e^{-\frac{a^2}{2m}}\leq 2e^{-4mln{n}/2m}=2e^{-2ln{n}}=2/n^2$

Это мы выяснили вероятность провала для одной строки, а для всех строчек это будет 2/n.

# 5. Routing problem на гиперкубе -



# 6. Wiring problem -

# 7. Congestion problem -
Обощение предыдущей задачи о проводах
Тут вроде понятно написано по модулю деталей и вычислений, хотя бы идея описана

# 8. Balls and bins. Bucket sort, +

## Balls and Bins

Задача: У нас есть n корзин и m шариков. Назовем загрузкой число шариков в корзине. Тогда при n=m средняя загрузка равна 1, а чему равна максимальная загрузка? Очевидно, что совсем максимальная загрузка - 1, но вероятность такого исхода ничтожно мала. Давайте докажем, что $P(MaxLoad > 3\frac{\ln{n}}{ln{ln{n}}}) \leq 1/n, n\to\infty$.

## Bucket Sort

Это сортировка, которая при определенных условиях может работать быстрее чем за $\Omega(n \log{n})$

Условия: берем $n=2^m$ элементов, равномерно распределенных на отрезке $[0, 2^k), k \geq m$ и независимых. Докажем, что ожидаемое время работы алгоритма - O(n). Причем это время зависит только от входных данных.

### Первая часть

Раскладываем элементы по n корзинам. При этом в корзине с номером j будут храниться элементы, у которых первые m битов предcтавляют собой число j. Очевидно, что такое раскладывание делается за O(n), если мы можем запихивать число в корзину за O(1).

Также заметим, что поскольку исходное распределение было равномерным, то количество элементов, которые попали в какую-то конкретную корзину будет распределено как B(n, 1/n).

### Вторая часть

Просто сортим каждую корзину обычной квадратичной сортировкой. Осталось показать, что на вторую часть мы тратим O(n) времени.

#### Док-во

Исходя из того, что элементы распределены равномерно, мы получаем, что работаем с моделью balls and bins.

Заметим, что для того, чтобы отсортировать какую-то одну корзину, мы потратим $c(X_j)^2$ времени, где $X_j$ - количество элементов в j-ой корзине. Тогда математическое ожидание времени, нужной на всю сортировку, будет выглядеть так: $E[\sum_{j=1}^n c(X_j)^2] = c\sum_{j=1}^n X_j^2 = cnEX_1^2$.

Исходя из того, что для биномиального распределение мат. ожидание np, а дисперсия npq получим, что $EX^2 = DX + (EX)^2 = np(1-p) + n^2p^2 = np(1-p+np)$

В нашем случае $p=1/n=> EX^2 = 1-1/n+1 = 2-1/n < 2$

$E[\sum_{j=1}^n c(X_j)^2] =cnEX_1^2 \leq 2cn$, ЧТД

# 9. Гамильтонов цикл на случайном графе

# 10. Граница сверху на количество шаров в самой загруженной корзине, +-

**Лемма:**

Пусть n шариков бросаются независимо из равномерного распределения, тогда $P(MaxLoad > 3\frac{\ln{n}}{ln{ln{n}}}) \leq 1/n, n\to\infty$.

**Док-во:**

Вероятность того, что в первую корзину попадет M шариков: $C_M^n\cdot (\frac{1}{n})^M$

Теперь несколько неравенств: $C_M^n\cdot (1/n)^M = \frac{n!}{M! (n-M)!n^M} \leq \frac{1}{M!(n-M)!} \leq 1/M!$

Несколько замечаний из Маклорена:

$e^k = \sum_{i=0}^{\infty}\frac{k^i}{i!} > \frac{k^k}{k!}$ => $k! > (k/e)^k$ => $1/k! < (e/k)^k$ => $1/M! \leq (e/M)^M$

do not understand what’s going on next

вставила чтобы можно было просто перекатать конец

# 11. Counting Argument. Число Рамсея. +

Для того, чтобы доказать существование какого-либо объекта с каким-то набором свойств, мы можем построить вероятностное пространство и показать, что вероятность достать нужный нам объект в этом пространстве строго больше нуля.

**Пример:** Если $C_2^n 2^{1-C_2^k} < 1$, то можно покрасить ребра полного графа на n вершинах в два цвета так, чтобы в этом графе не было ни одной клики размера k одного цвета.

**Док-во:** Пространство -- все возможные покраски графа в два цвета. Всего их $2^{C_2^n}$. Отсюда вероятность того, что наш граф покрашен каким-то способом - $2^{-C_2^n}$.

Тогда давайте посмотрим на все клики в нашем графе размера k и пронумеруем их. Всего клик такого размера будет $C_k^n$. Тогда пусть $A_i$ - событие, что клика покрашена в один цвет. Найдем вероятность такого события:

$P(A_i) = 2 \cdot 2^{-C^{k}_2} = 2^{1-C^{k}_2}$

Тогда суммарная вероятность того, что произойдет хотя бы одно из этих событий (сразу воспользуемся union bound):

$P(\Cup A_i) \leq \sum P(A_i) = C_n^k\cdot 2^{1-C^{k}_2} < 1$ (по условию теоремы)

$P(\Cap !A_i) = 1 - A(\Cup A_i) > 0$, ЧТД

# 12. Expectation Argument. Derandomization of expectation argument +

## Лемма о мат ожидании

Кроме всего прочего, мы можем смотреть на мат. ожидание какой-то штуки. Например, если м.о. EX, то должен существовать элемент больше и меньше этого мат. ожидания. Можем этим тоже пользоваться.

**Lemma:** Suppose we have a probability space $\mathcal{S}$ and a random variable $X$ defined on $\mathcal{S}$ such that $\mathbf{E}[X]=\mu$. Then $\operatorname{Pr}(X \geq \mu)>0$ and $\operatorname{Pr}(X \leq \mu)>0$.
**Proof:** We have
$$
\mu=\mathbf{E}[X]=\sum_{x} x \operatorname{Pr}(X=x),
$$
where the summation ranges over all values in the range of $X$. If $\operatorname{Pr}(X \geq \mu)=0$, then
$$
\mu=\sum_{x} x \operatorname{Pr}(X=x)=\sum_{x<\mu} x \operatorname{Pr}(X=x)<\sum_{x<\mu} \mu \operatorname{Pr}(X=x)=\mu,
$$
giving a contradiction. Similarly, if $\operatorname{Pr}(X \leq \mu)=0$ then
$$
\mu=\sum_{x} x \operatorname{Pr}(X=x)=\sum_{x>\mu} x \operatorname{Pr}(X=x)>\sum_{x>\mu} \mu \operatorname{Pr}(X=x)=\mu,
$$
again yielding a contradiction.

## Максимальный разрез

**Теорема:** Пусть дан граф с n вершинами и m ребрами, тогда граф можно разбить на 2 непересекающихся подмножества так, чтобы хотя бы m/2 ребер соединяли вершины из разных подмножеств.

**Док-во:** Раскидаем вершины в два множество случайно и пронумеруем все ребра. Тогда пусть с.в. X равна 1 если соединяет вершины из разных частей и ноль иначе. Вероятность соединять вершины из разных частей -- 0.5, отсюда $EX_i = 0.5$. В таком случае математическое ожидание количества ребер, которые соединяют вершины из разных частей $EX=\sum EX_i = m EX_i=m/2$. Исходя из леммы которая была раньше, получаем, что есть такое разбиение.

## Дерандомизация

**Алгоритм:** берем первую вершину в А. Дальше каждую следующую складываем туда, где для нее меньше соседей.

**Док-во:** Индуктивно покажем, что
$$
\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}\right] \leq \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k+1}\right]
$$
Исходя из этого мы можем получить:
$$
\mathbf{E}[C(A, B)] \leq \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{n}\right]
$$
The right-hand side is the value of the cut determined by our placement algorithm, since if $x_{1}, x_{2}, \ldots, x_{n}$ are all determined then we have a cut of the graph. Hence our algorithm returns a cut whose value is at least $\mathbf{E}[C(A, B)] \geq m / 2$.
The base case in the induction is
$$
\mathbf{E}\left[C(A, B) \mid x_{1}\right]=\mathbf{E}[C(A, B)]
$$
which holds by symmetry because it does not matter where we place the first vertex.
We now prove the inductive step, that
$$
\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}\right] \leq \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k+1}\right]
$$
Consider placing $v_{k+1}$ randomly, so that it is placed in $A$ or $B$ with probability $1 / 2$ each, and let $Y_{k+1}$ be a random variable representing the set where it is placed. Then
$$
\begin{aligned}
\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}\right]=& \frac{1}{2} \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=A\right] \\
&+\frac{1}{2} \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=B\right] .
\end{aligned}
$$
It follows that
$$
\begin{aligned}
\max \left(\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=A\right], \mathbf{E}[C(A, B) \mid\right.&\left.\left.\mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=B\right]\right) \\
& \geq \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}\right]
\end{aligned}
$$
Therefore, all we have to do is compute the two quantities $\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots\right.$ $\left.x_{k}, Y_{k+1}=A\right]$ and $\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=B\right]$ and then place the $v_{k+1}$ in the set that yields the larger expectation. Once we do this, we will have a placement satisfying
$$
\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}\right] \leq \mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k+1}\right]
$$
To compute $\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=A\right]$, note that the conditioning gives the placement of the first $k+1$ vertices. We can therefore compute the number of edges among these vertices that contribute to the value of the cut. For all other edges, the probability that it will later contribute to the cut is $1 / 2$, since this is the probability its two endpoints end up on different sides of the cut. By linearity of expectations, $\mathbf{E}[C(A, B) \mid$ $\left.x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=A\right]$ is the number of edges crossing the cut whose endpoints are both among the first $k+1$ vertices, plus half of the remaining edges. This is easy to compute in linear time. The same is true for $\mathbf{E}\left[C(A, B) \mid x_{1}, x_{2}, \ldots, x_{k}, Y_{k+1}=B\right]$.

# 13. 3/4 -приближение для MaxSAT

**Утверждение**: Существует набор значений переменных для k-SAT такой что как минимум $\frac{2^k-1}{2^k}m$ клозов выполнено. m количество дизъюнктов в формуле

**Док-во:** $ECountOfGood = \sum_{i=1}^m E(C_i) = mE(C_i)$

$EC_i = P(C_i=1)=\frac{2^k-1}{2^k}$

$ECountOfGood = m\frac{2^k-1}{2^k}$

Берем фиксируем значение для какой-то вершины, тогда $EF = pE(F_{x_1=0}) + (1-p)E(F_{x_1=1})$

Видно, что такой алгоритм хорошо работает если все клозы достаточно длинные.

А мы хотели бы построить алгоритм, который выполнял бы 3/4 от всех клозов, которые могут выполняться.
Создадим задачу целочисленного линейного программирования, для каждого клоза $z_i$ -- выполнен ли этот клоз. Хотим найти $max(\sum x_i)$
При этом $z_i\leq$ суммы элементов клоза, взятых просто так, если они там без отрицания и 1-х если они в клозе с отрицанием.
$z_p=0$ только если все элементы равны нулю.
Можем решить эту задачу за полиномиальное время. Чще всего на выходе получим не целые числа, а дробные. Тогда будем опринимать это как вероятности, что элемент равен 1. Тогда клоз C будет выполнен с вероятностью 1 - $\prod y_i$
Тут нам сказали поверить что такое произведение будет больше чем $1-(1-\frac{z_p}{k})^k, z_p=\sum_{j} y_{ij}$
В свою очередь это больше чем $(1-(1-1/k)^k)z_p\geq (1-1/e)z_p$
Мат. ожидание количества клозов выдаст тогда $1-1/e$
Оказывается, что это все щее не то что мы хотели, давайте подбрасывать монетку и выбирать один из двух алгоритмов.

# 14. Sample and modify. The second moment method. Two point sampling+

Сначала генерируем объект, а потом уже его меняем.

## Независимое множество

**Теорема:** Пусть есть граф. Тогда в нем есть независимое множество хотя бы на $n^2/4m$ вершин.

**Док-во:** Средняя степень вершины в графе $d=2m/n$. Алгоритм:

1. Удаляем вершины из графа (вместе с инцидентными ребрами) независимо с вероятностью $1-1/d$.
2. Для всех ребер что остались: удаляем ребро и одну из инцидентных ему вершин

Оставшиеся вершины образуют независимое множество.

Давайте докажем, что это так.

Изначально было $n\cdot d/2$ ребер. Мы оставляем вершину на первом шаге с вероятностью $1/d$. Тогда $E[countNodes]=n/d$.

Остается ребер $E[countEdges]=\frac{nd}{2d^2}=\frac{n}{2d}$, так как каждое ребро остается с вероятностью $1/d^2$. На втором шаге мы удаляем максимум столько вершин, сколько было ребер. Остается вершин $$E[countNodes]-E[countEdges] = n/d-n/2d=n/2d=n^2/4m$$, ЧТД

## Метод второго момента

**Теорема:** If $X$ is a nonnegative integer-valued random variable, then
$$
\operatorname{Pr}(X=0) \leq \frac{\operatorname{Var}[X]}{(\mathbf{E}[X])^{2}} .
$$
**Док-во:**
$$
\operatorname{Pr}(X=0) \leq \operatorname{Pr}(|X-\mathbf{E}[X]| \geq \mathbf{E}[X]) \leq \frac{\operatorname{Var}[X]}{(\mathbf{E}[X])^{2}}
$$

## Two point sampling

# 15. Граф с большим обхватом +

Обхват графа -- размер наименьшего цикла.

**Theorem:** For any integer $k \geq 3$ there is a graph with $n$ nodes, at least $\frac{1}{4} n^{1+1 / k}$ edges, and girth at least $k$.

**Proof:** We first sample a random graph $G \in G_{n, p}$ with $p=n^{1 / k-1}$. Let $X$ be the number of edges in the graph. Then
$$
\mathbf{E}[X]=p\left(\begin{array}{l}
n \\
2
\end{array}\right)=\frac{1}{2}\left(1-\frac{1}{n}\right) n^{1 / k+1} .
$$
Let $Y$ be the number of cycles in the graph of length at most $k-1$. Any specific possible cycle of length $i$, where $3 \leq i \leq k-1$, occurs with probability $p^{i}$. Also, there are $\left(\begin{array}{l}n \\ i\end{array}\right) \frac{(i-1) !}{2}$ possible cycles of length $i$; to see this, first consider choosing the $i$ vertices, then consider the possible orders, and finally keep in mind that reversing the order yields the same cycle. Hence,
$$
\mathbf{E}[Y]=\sum_{i=3}^{k-1}\left(\begin{array}{c}
n \\
i
\end{array}\right) \frac{(i-1) !}{2} p^{i} \leq \sum_{i=3}^{k-1} n^{i} p^{i}=\sum_{i=3}^{k-1} n^{i / k}<k n^{(k-1) / k} .
$$
We modify the original randomly chosen graph $G$ by eliminating one edge from each cycle of length up to $k-1$. The modified graph therefore has girth at least $k$. When $n$ is sufficiently large, the expected number of edges in the resulting graph is
$$
\mathbf{E}[X-Y] \geq \frac{1}{2}\left(1-\frac{1}{n}\right) n^{1 / k+1}-k n^{(k-1) / k} \geq \frac{1}{4} n^{1 / k+1} .
$$
Hence there exists a graph with at least $\frac{1}{4} n^{1+1 / k}$ edges and girth at least $k$.
Вставляю потому что на русском))))

# 16. Клика на 4 вершинах +

**Теорема:** Рассмотрим граф G(n, p). Если $p=o(n^{-2/3})$ то в графе с вероятностью близкой к нулю нет клики на 4 вершинах. Если $p=\omega(n^{-2/3})$ то в графе почти точно есть клики на 4 вершинах.

**Док-во**

Докажем первую часть

Чтобы была клика, нужно чтобы были все возможные 6 ребер => вероятность такого $p^6$, а количество таких графов - $C_4^n$

Тогда $E(count-of-cliques) = C_4^np^6 \leq n^4p^6 = n^4 o(n^{-4}) = o(1)$

Это на самом деле значит, что $P[X\geq 1]\leq E(X) = o(1)$

Вторая часть

Пусть X - количество клик, тогда нам хочется узнать $P[X=0]\leq \frac{DX}{(EX)^2}$

Заметим, что сейчас у нас $EX\to\infty$, но это на деле нам не говорит ни о чем. Можем принимать значение ноль почти везде ($p=1-1/n$) и очень большое значение с маленькой ненулевой вероятностью

$(EX)^2 \sim n^8p^{12}$

$DX = D(X_1+X_2+...+X_{C_4^n})=\sum_{i=1}^{c_4^n}D(X_i)+\sum_{i\neq j}cov(X_i, X_j)$

$cov(X_i, X_j) = E(X_i X_j) - EX_i EX_j$

$X_i$ - Бернуллиевская величина с вероятностью успеха $p^6$ (вытащить клику на 4 вершинах)

$\sum_{i=1}^{C_4^n}DX_i=C_4^n p^6(1-p^6)\leq n^4p^6$

$\sum_{i\neq j}cov(X_i, X_j)\leq \sum_{i\neq j}E(X_iX_j)$

Давайте честно посмотрим на то, что у нас может быть в этом произведении. Тут может быть от одной до трех общих вершин

При этом если общая вершина одна -- то общих ребер ноль, а следовательно матожидание общих ребер равно нулю

Общих вершины две: в таком случае у нас всего 6 вершин, 1 общее ребро, всего 11 ребер. Тогда вероятность возникновения такой ситуации $p^{11}$. А сколько таких пар можно сделать? $C_2^n \cdot C_{2}^{n-2}\cdot C_{2}^{n-4}$. Тогда математическое ожидание для количества таких штук будет $\leq p^{11}n^6$ (просто очень грубо обрубаем вверх)

Общих вершин три: 5 вершин, 3 общих ребра, всего 9 ребер. Делаем все те же вычисления и получаем, что м.о. количества таких ситуаций $\leq p^9n^5$.

Тогда $\sum_{i\neq j}E(X_iX_j)\leq 0+n^6p^{11}+n^5p^9$

В таком случае дисперсия оценивается как: $DX\leq n^4p^6 + n^6p^{11}+n^5p^9$

Оценим вероятность того, что X=0: $P[X=0]\leq DX/(EX)^2 = \frac{n^4p^6 + n^6p^{11}+n^5p^9}{n^8p^12}$

Можно видеть, что если к штуке сверху применить ограничение на p из условия, то все получится равным нулю. ЧТД

# 17. Локальная лемма Ловаса +

**Theorem:** Let $E_{1}, \ldots, E_{n}$ be a set of events, and assume that the following hold:

1. for all $i, \operatorname{Pr}\left(E_{i}\right) \leq p$;
2. the degree of the dependency graph given by $E_{1}, \ldots, E_{n}$ is bounded by $d$;
3. $4 d p \leq 1$.
Then $\operatorname{Pr}\left(\bigcap_{i=1}^{n} \bar{E}_{i}\right)>0$

**Доказательство:**

Пусть есть события $E_1, E_2, ..., E_n$ - они все плохие. Если бы они были независимы, то есть вероятность что все будет хорошо ($P[!E_1\cap !E_2 \cap...\cap !E_n]>0$).

Давайте поставим в соответствие этим событиям граф G на n вершинах. Вершина - событие, ребро есть в том случае, если два события не являются независимыми.

Доказывать будем по индукции. Let $S \subset\{1 \ldots . . n\}$. We prove by induction on $s=0, \ldots n-1$ that, if $|S| \leq s$, then for all $k\notin$ $S$ we have
$$
\operatorname{Pr}\left(E_{k} \mid \bigcap_{j\in S} \bar{E}_{j}\right) \leq 2 p .
$$
For this expression to be well-defined when $S$ is not empty. we need $\operatorname{Pr}\left(\bigcap_{j\in S} \bar{E}_{j}\right)>0$.
The base case $s=0$ follows from the assumption that $\operatorname{Pr}\left(E_{k}\right) \leq p$. To perform the inductive step, we first show that $\operatorname{Pr}\left(\bigcap_{j \in S} \bar{E}_{j}\right)>0 .$ This is true when $s=1$. because $\operatorname{Pr}\left(\bar{E}_{j}\right) \geq 1-p>0 .$ For $s>1$, without loss of generality let $S=[1,2 \ldots . .s]$. Then
$$
\begin{aligned}
\operatorname{Pr}\left(\bigcap_{i=1}^{s} \bar{E}_{j}\right) &=\prod_{i=1}^{s} \operatorname{Pr}\left(\bar{E}_{j} \mid \bigcap_{j=1}^{i-1} \bar{E}_{j}\right) \\
&=\prod^{s}\left(1-\operatorname{Pr}\left(E_{i} \mid \prod_{j=1}^{i-1} \bar{E}_{j}\right)\right) \\
& \geq \prod(1-2 p)>0
\end{aligned}
$$
In obtaining the last line we used the induction hypothesis.
For the rest of the induction. let $S_{1}=\left\{j \in S\left|\left(k, j\right) \in E\right\}\right.$ and $S_{2}=S-S_{1}$. If $S_{2}=$ $S$ then $E_{k}$ is mutually independent of the events $\bar{E}_{r}, i \in S$, and
$$
\operatorname{Pr}\left(E_{k} \mid \bigcap_{j\in S} \bar{E}_{j}\right)=\operatorname{Pr}\left(E_{k}\right) \leq p .
$$
We continue with the case $\left|S_{2}\right|<s$. It will be helpful to introdace the following notation. Let $F_{S}$ be defined by
$$
F_{S}=\bigcap_{j \in S} \bar{E}_{j}
$$
and similarly define $F_{S_1}$ and $F_{S_2}$. Notice that $F_{S}=F_{S_1} \cap F_{S_2}$.
Applying the definition of conditional probability yields
$$
\operatorname{Pr}\left(E_{k} \mid F_{s}\right)=\frac{\operatorname{Pr}\left(E_{k} \cap F_{s}\right)}{\operatorname{Pr}\left(F_{s}\right)}
$$
Applying the definition of conditional probability to the numerator of $(6.4)$, we obtain
$$
\begin{aligned}
\operatorname{Pr}\left(E_{k} \cap F_{S}\right) &=\operatorname{Pr}\left(E_{k} \cap F_{S_1} \cap F_{S_2}\right) \\
&=\operatorname{Pr}\left(E_{k} \cap F_{S_1} \mid F_{S_2}\right) \operatorname{Pr}\left(F_{S_2}\right)
\end{aligned}
$$
The denominator can be written as
$$
\begin{aligned}
\operatorname{Pr}\left(F_{S}\right) &=\operatorname{Pr}\left(F_{S_1} \cap F_{S_1}\right) \\
&=\operatorname{Pr}\left(F_{S_1} \mid F_{S_2}\right) \operatorname{Pr}\left(F_{S_{2}}\right)
\end{aligned}
$$
Canceling the common factor, which we have already shown to be nonzero, yields
$$
\operatorname{Pr}\left(E_{k} \mid F_{s}\right)=\frac{\operatorname{Pr}\left(E_{k} \cap F_{S_{1}} \mid F_{S_{2}}\right)}{\operatorname{Pr}\left(F_{S_{1}} \mid F_{S_{2}}\right)} .
$$
Note that $(6.5)$ is valid even when $S_{2}=\emptyset$.
Since the probability of an intersection of events is bounded by the probability of any one of the events and since $E_{k}$ is independent of the events in $S_{2}$, we can bound the numerator of $(6.5)$ by
$$
\operatorname{Pr}\left(E_{k} \cap F_{S_{1}} \mid F_{S_{2}}\right) \leq \operatorname{Pr}\left(E_{k} \mid F_{S_{2}}\right)=\operatorname{Pr}\left(E_{k}\right) \leq p .
$$
Because $\left|S_{2}\right|<|S|=s$, we can apply the induction hypothesis to
$$
\operatorname{Pr}\left(E_{i} \mid F_{S_{2}}\right)=\operatorname{Pr}\left(E_{i} \mid \bigcap_{j\in S_{2}} \bar{E}_{j}\right)
$$
Using also the fact that $\left|S_{1}\right| \leq d$, we establish a lower bound on the denominator of (6.5) as follows:
$$
\begin{aligned}
\operatorname{Pr}\left(F_{S_{1}} \mid F_{S_{2}}\right) &=\operatorname{Pr}\left(\bigcap_{i \in S_{1}} \bar{E}_{j} \mid \bigcap_{j \in S_{2}} \bar{E}_{j}\right) \\
& \geq 1-\sum_{i\in S_{1}} \operatorname{Pr}\left(E_{i} \mid \bigcap_{j \in S_{2}} \bar{E}_{j}\right) \\
& \geq 1-\sum_{i\in S_{1}} 2 p \\
& \geq 1-2 p d \\
& \geq \frac{1}{2}
\end{aligned}
$$
Using the upper bound for the numerator and the lower bound for the denominator, we prove the induction:
$$
\begin{aligned}
\operatorname{Pr}\left(E_{k} \mid F_{S}\right) &=\frac{\operatorname{Pr}\left(E_{k} \cap F_{S_{1}} \mid F_{S_{2}}\right)}{\operatorname{Pr}\left(F_{S_{1}} \mid F_{S_{2}}\right)} \\
& \leq \frac{p}{1 / 2}=2 p
\end{aligned}
$$
The theorem follows from
$$
\begin{aligned}
\operatorname{Pr}\left(\bigcap_{i=1}^{n} \bar{E}_{i}\right) &=\prod_{i=1}^{n} \operatorname{Pr}\left(\bar{E}_{i} \mid \bigcap_{j=1}^{i-1} \bar{E}_{j}\right) \\
&=\prod_{i=1}^{n}\left(1-\operatorname{Pr}\left(E_{i} \mid \bigcap_{j=1}^{i-1} \bar{E}_{j}\right)\right) \\
& \geq \prod_{i=1}^{n}(1-2 p)>0
\end{aligned}
$$

# 18. Применение локальной леммы Ловаса к задаче о путях. Локальная лемма Ловаса и MaxSAT +

## Задача о путях

**Задача:** Есть n пар пользователей, которые хотят общаться друг с другом по непересекающимся путям. Каждая пара может выбирать пусть из коллекции $F_i$ размера m. Если каждая пара $F_i$ шарит не более чем k путей с другой парой $F_j$, при этом $8nk/m \leq 1$, тогда можно выбрать непересекающиеся пути.
(m -- количество возможных путей для каждой пары)

**Док-во:** Пусть для каждой пары рандомно выбираем один путь из m доступных. Тогда пусть $E_{i, j}$- событие что выбранные пути для двух пар имеют хотя бы одно общее ребро. Исходя из того, что мы шарим не более чем k ребер, то $P[E_{i, j}]\leq k/m$.

Заметим, что наше событие независимо ото всех событий, которые не затрагивают вершины i, j. Поэтому степень графа у нас меньше чем 2n.

Посчитаем: $4dp\leq 4*2np = 8nk/m \leq 1$.

Таким образом, все условия для леммы Ловаса выполняются, поэтому существует такое разбиение когда пути нигде не пересекаются.

## MaxSAT

**Теорема:** Если никакая переменная не появляется в k-SAT более чем $T=2^k/4k$ клозах, то у формулы есть решение.

**Док-во:** Рассмотрим для каждого клоза событие $E_i$ - что клоз не выполнен. Поскольку клоз выполняется если есть хотя бы 1 единица, то $P(E_i) = 2^{-k}$.

Заметим, что в графе зависимостей какой-то клоз будет независим ото всех клозов, которые не шарят с ним ни одной переменной. Мы знаем, что одна переменная появляется не более чем в T клозах, поэтому $d\leq kT=2^{k-2}$. (так как $k$ переменных и каждая в не более чем в $T$ клозах)

В таком случае посчитаем: $4dp = 2^k 2^{-k} = 1$ => будет существовать удовлетворяющее решение.

# 19. Поиск выполняющего набора у MaxSAT с помощью леммы Ловаса
Есть k-SAT, к четное, каждая переменная встречается в не более чем $T=2^{\alpha k}$ клозах. хотим найти решение за полиномиальное время.
1. Фиксируем значения у каких-то переменых.
2. Назовем опасными те клозы, у которых более половины переменных зафиксировано, но нет ответа
3. Решаем для оставшихся

Будут две леммы, которые говорят, что:
* частичное решение, полученное на первой фазе может быть преобразовано в полное решение для формулы
* с большой вероятностью поиск решения на второй фазе закончится за полином от m.

Лемма 1. Существует такое установление занчений что формула будет решена.

Let $H^{\prime}=\left(V^{\prime}, E^{\prime}\right)$ be a graph with $V^{\prime} \subseteq V$ and $E^{\prime} \subseteq E$ such that
(a) $i \in V^{\prime}$ if and only if $C_{i}$ is a surviving clause and
(b) $(i, j) \in E^{\prime}$ if and only if $C_{i}$ and $C_{j}$ share a deferred variable. In the following discussion we do not distinguish between node $i$ and clause $i$.
Лемма 2. Все компоненты связности в H' имеют размер $O(log m)$ с вероятностью $1-o(1)$.
Итого получаем:
**Theorem 6.16:** Consider a $k$-SAT formula with $m$ clauses, where $k$ is an even constant and each variable appears in up to $2^{\alpha k}$ clauses for a sufficiently small constant $\alpha>0$. Then there is an algorithm that finds a satisfying assignment for the formula in expected time that is polynomial in $m$.

**Proof:** As we have described, if the first phase partitions the problem into subformulas involving only $O(k \log m)$ variables, then a solution can be found by solving each subformula exhaustively in time that is polynomial in $m$. The probability of the first phase partitioning the problem appropriately is $1-o(1)$, so we need only run phase I a constant number of times on average before obtaining a good partition. The theorem follows.
# 20. Вероятностный алгоритм для k-SAT

# 21. FPRAS. Приближенное вычисление выполняющих наборов у ДНФ
Доказательство по Чернову по идее

# 22. FPAUS. FPAUS влечет за собой FPRAS для множества независимых множеств в графе.

# 23. Минимальный разрез

# 24. Feedback Vertex Set за $O^*(4^k)$

# 25. MST in linear time
что мы умеем
1. за линейное время делать итерации борувки
2. за линейное время чекать что то что мы нашли это мст
3. за линейное время делать сэмплирование отрезая половину ребер

итого мы сначала делаем итерацию борубвки + отбрасываем f-heavy ребра, получаем граф поменьше (не до конца поняла почему количество вершин урезалось в 8 раз) (первое слагаемое)
потом мы делаем эсмплирование с вероятностью оставить ребро 0.5, получаем новый граф, для которого тоже делаем поиск мст рекурсивно (2 слагаемое), а потом уже делаем верификацию для полученного (3 слагамемое)

# 26. All pairs shortest path

# 27. d-кластеризация, субэкспоненциальный алгоритм

# 28. Комбинаторный экспандер. Простое увеличение вероятности успеха с помощью экспандера

# 29. Существование комбинаторного экспандера

# 30. Алгераический экспандер. Задача UPath

# 31. Уменьшение использования случайных бит с помощью экспандера

# 32. Достижимость вершин за логарифмическую память в орграфах

# 33. Универсальное семейство хэш-функций, строго универсальное семейство хэш-функций. Дерандомизация приближения MaxCUT
Пусть H — конечное множество хеш-функций, которые отображают пространство ключей U в диапазон {0,1,2,..,m−1}. Такое множество называется универсальным (англ. universal), если для каждой пары ключей $k,l\in U,(k\neq l)$ количество хеш-функций $h\in H$, для кото
рых h(k)=h(l) не превышает |H|m.
MAX-CUT:

# 34. Perfect hashing. Бросание шаров в корзине при помощи 2 независимых функций


Шары:


# 35. Finding heavy hitters. Count min filter
Это я не понимаю, оставляю записи)