\Section{Вероятностные алгоритмы}{27 мая}{Черепанов Валерий}

\Subsection{Фильтр Блюма}

Детерминированная структура данных, похожая на хэш-таблицу. Умеет добавлять элементы и проверять вхождение. Работает за настоящее $\O(1)$. Единственный минус заключается в том, что иногда он говорит ``да'' на запрос о несуществещем элементе.

Алгоритм:
Есть $m$ бит, $n$ элементов, $k$ \textit{универсальных} хэш функции $h$.
\begin{code}
void add(int x) {
  // h is a vector of hash functions, a may be a bitset
  for (int i = 0; i < h.size(); i++)
    a[h[i](x)] = 1;
}

bool get(int x) {
  retval = 1;
  for (int i = 0; i < h.size(); i++)
    retval &= a[h[i](x)];
  return retval;
}
\end{code}
Заполненность не более $\max\big(0, \frac {nk}m\big)$.

\THEE{Как выбрать оптимальное $k$?}
Давайте посчитаем вероятность ошибки:
\begin{align*}
  P[\text{error}] &= \\
  \Big(1-\big(1-\frac 1 m\big)^{nk}\Big)^{k} &= \\
  \big(1-e^{-\frac {nk} m}\big)^k &= \\
  2^{-k}~(\text{if}~k=\ln 2 \cdot \frac m n) &= \\ 0.6185^{m/n}
\end{align*}

\Subsection{Вероятностные алгоритмы}
\begin{description}
  \item[RP] Randomized polinomial. Если ответ нет, тогда говорим нет, если ответ да, то говорим да с вероятностью не менее $\frac 1 2$.
  \item[coRP] Дополнение RP. Если ответ да, тогда говорим да, если ответ нет, то говорим нет с вероятностью не менее $\frac 1 2$.
  \item[ZPP] Zero-error Probablistic Polynomial. Матожидание времени полиномиально, всегда дает верный ответ.
  \item[BPP] Bounded-error Probablistic Polynomial. Полиномиален по времени, вероятность правильного ответа $\ge \frac 2 3$.
\end{description}

\begin{Thm}
  {$ZPP=RP \cap coRP$}
\end{Thm}
\begin{proof} % FIXME what?
  Докажем, что $ZPP \in RP \cap coRP$.
  Запустим алгоритм $C \in ZPP$, дадим ему работать как минимум в два раза дольше матожидания. Тогда мы получим правильный ответ с вероятностью не менее $\frac 1 2$
  (По неравенству Маркова: $Pr(X \geq a) \leq \frac{E[x]}a; a = E[x]\cdot 2$).

  Докажем теперь в обратную сторону, это делается конструктивно:
  \begin{code}
  while true:
    if RP_algo(x) == 1:  return 1;
    if coRP_algo(x) == 0: return 0;
  \end{code}
  $$x\in L; F(Time)=\frac{Time(RP_{algo})}{Pr(RP_{algo})}$$
  $$E = 1+p+p^2+p^3+\dots=\frac{1}{1-Pr[Error]}$$
\end{proof}

\Subsection{Понижение ошибки и прочее}

%\begin{Lm}{О понижении ошибки} ???
  %$p\Rightarrow q = p^{\log_p q}$ \\
  %$1-1/n \Rightarrow \frac {\log 1 2}{\log (1-\frac 1 n)}=n\cdot \text{const}$
%\end{Lm}

\begin{Lm}{О понижении ошибки в BPP}

  Утвержение: можно за $\O(k)$ запусков уменьшить ошибку до обратной экспоненты.
  Нужно всего лишь запустить алгоритм $k$ раз и выбрать более популярный ответ.
\end{Lm}

\begin{proof}
  Закон больших чисел для распределения Бернулли.
  \begin{align}
  \text{Pr} = \sum^k_{a=k/2} C^a_k\cdot \big(\frac 1 3\big)^a \cdot \big(\frac 2 3\big)^{k-a}
  \leq \frac {2^k}2\cdot \big(\frac 2 9\big)^{k/2}=1\frac 1 2 \cdot \big(\frac 2 9\big)^{k/2}
  \end{align}
\end{proof}

\begin{Lm}
  \begin{gather*}
    x \in L \Rightarrow \text{Pr}[1]>\frac 1 2 + \varepsilon \\
    x \notin L \Rightarrow \text{Pr}[0] < \frac 1 2 + \varepsilon
  \end{gather*}
  Тоже по закону больших чисел для распределения Бернулли.
\end{Lm}

Некоторые вероятностные методы:
\begin{description}
  \item[Метод Лас-Вегаса] ткнем в случайный объект, скажем что этот ответ. Работает неожиданно часто.
  \item[Метод Монте-Карло] хотим посчитать площадь объекта. Натыкаем много точек в квадрате, который точно включает объект. Тогда процент точек, попавших в объект, будет равен проценту, который его площадь занимает от площади квадрата.
\end{description}
