\documentclass[10pt,xcolor=table]{beamer}
%\usepackage[brazil]{babel}
\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{graphicx, color}
\usepackage{verbatim}
\usepackage{tikz}
\usepackage{tkz-graph}
\usetikzlibrary{calc}


\usepackage{graphicx}
%\usepackage{enumitem}
\usepackage{booktabs}

\usepackage{latexsym,enumerate}
\usepackage{fancybox}
\usepackage[T1]{fontenc}
\usepackage{scalefnt}
%\usepackage[table,xcdraw]{xcolor}


\def\And{\wedge}
\def\Or{\vee}
\def\AND{\bigwedge}
\def\OR{\bigvee}
\def\iff{\Leftrightarrow}
\def\tto{\Rightarrow}
\def\Iff{\Longleftrightarrow}
\def\Tto{\Longrightarrow}
\newcommand{\esp}[1]{\hspace{#1 mm}}

\def\I{{\rm I}}



\def\sW{\textcolor{blue}{$\leftarrow$}}
\def\sN{\textbf{\textcolor{green}{$\uparrow$}}}
\def\sNW{\alert{$\nwarrow$}}
\def\COR{\cellcolor{yellow}}


\definecolor{red}{rgb}{1,0,0}
\definecolor{redy}{rgb}{0.9,0,0}
\definecolor{greeny}{rgb}{0,0.8,0}
\definecolor{bluey}{rgb}{0.3,0.3,0.6}
\definecolor{blue}{rgb}{0,0,1}
\definecolor{orange}{rgb}{0.8,0.2,0}
\definecolor{whitey}{rgb}{1,1,1}
\definecolor{purple}{rgb}{0.4,0,0.4}
\definecolor{pink}{rgb}{0.7,0,0.6}%{0.8,0.1,0.5}{1,1,0.9-light}
\definecolor{brown}{rgb}{0.5,0.3,0.2}
\definecolor{dkblue}{rgb}{0,0.4,0.3}
\definecolor{lblue}{rgb}{0.2,0.2,0.7}

\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}

\begin{document}

\setbeamercovered{highly dynamic}
\def\pix{p}
\def\x{\mathbf{x}}
\def\y{\mathbf{y}}
\def\z{\mathbf{z}}
\def\p{\mathbf{p}}
\def\u{\mathbf{u}}
\def\e{\mathbf{e}}
\def\w{\mathbf{w}}
\def\eps{\epsilon}
\def\S{\mathfrak{S}}
\def\PP{\mathbb{P}}
\def\EE{\mathbb{E}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\NN{\mathbb{N}}
\def\Var{\mathbb{V}ar}
\def\Cov{\mathbb{C}ov}

\def\cor{\textcolor{blue}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos}

\begin{itemize}
\item Algoritmos Probabilísticos, Algoritmos Aleatórios, Algoritmos Randômicos, \textit{Randomized Algorithms}
\item São algoritmos que usam probabilidade em sua lógica, ou seja, que fazem escolhas aleatórias.
\end{itemize}

\begin{block}{Bibliografia}
\begin{itemize}
\item Motwani, Raghavan, Randomized Algorithms, Cambridge, 1995
\item Mitzenmacher, Upfal, Probability and Computing, Cambridge, 2006
\item Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005
\item Sheldon Ross, Probability Models for Computer Science, Academic Press, 2002
\item Dubhashi, Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge, 2009
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Bibliografia}

\begin{figure}\centering
\includegraphics[scale=0.39]{livros.png}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Tipos}

\begin{itemize}
\item {\bf Algoritmo Las Vegas:} Sempre faz o esperado. O tempo do algoritmo depende das escolhas aleatórias (Quick Sort, Seleção).
\item {\bf Algoritmo Monte Carlo:} Pode não fazer o esperado, com baixa probabilidade. O tempo do algoritmo pode ou não depender das escolhas aleatórias.
\end{itemize}

\begin{block}{Exemplo: Problema do Popular-busca}
\begin{itemize}
\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Busca:} Dado vetor com popular, encontrar um deles.}
\item {\bf Algoritmo Las Vegas:} Repita até encontrar: escolhe um elemento aleatório e conta quantas vezes aparece. Se for mais de $n/5$ vezes, retorne esse elemento.
\item {\bf Algoritmo Monte Carlo:} Semelhante ao Las Vegas, mas repete no máximo 9 vezes. Retorne um elemento aleatório se não encontrou um popular nas iterações anteriores.
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Problema Popular-busca}

\begin{block}{Algoritmo Determinístico p/ Problema Popular-busca}
\begin{itemize}
\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Busca:} Dado vetor com popular, encontrar um deles.}
\item {\bf Algoritmo Determinístico:} Usa o algoritmo SELEÇÃO do k-ésimo mínimo para $k=n/5$, $2n/5$, $3n/5$ e $4n/5$. Pelo menos um desses 4 elementos será popular, basta contar para descobrir qual.
\item $[0,1,\alert{1},2,2,\alert{3},4,5,\alert{5},5,5,\alert{6},7,8,9]$: O elemento 5 é popular.
\item {\bf Tempo de pior caso:} $4\cdot(n+\mbox{TempoSeleção}(n))=O(n)$
\item \alert{constantes não muito pequenas escondidas na notação: $O(44\cdot n)$}
\item \cor{Observação:} SELEÇÃO tem algoritmo Las-Vegas bem mais rápido.
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Las Vegas - Popular-busca}

\begin{block}{Algoritmo Las-Vegas p/ Problema Popular-busca}
\begin{itemize}
\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Busca:} Dado vetor com popular, encontrar um deles.}
\item {\bf Algoritmo Las Vegas:} Repita até encontrar: escolhe um elemento aleatório e conta quantas vezes aparece. Se for mais de $n/5$ vezes, retorne esse elemento.
\item Las Vegas sempre retorna um popular, mas pode demorar.
\item Distribuição Geométrica: 5 buscas são suficientes em média
\item Tempo Esperado: \cor{$O(5n)$}
\item Mas pode dar tempo bem mais alto: Variância grande
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Monte Carlo - Popular-busca}

\begin{block}{Algoritmo Monte-Carlo p/ Problema Popular-busca}
\begin{itemize}
\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Busca:} Dado vetor com popular, encontrar um deles.}
\item {\bf Algoritmo Monte Carlo:} Semelhante ao Las Vegas, mas repete no máximo 9 vezes. Retorne um elemento aleatório se não encontrou um popular nas iterações anteriores.
\item Monte Carlo pode errar e o tempo pode variar: $O(9n)$ pior caso
\item Distribuição Geométrica: Probabilidade de errar em 10 tentativas: $(4/5)^{10}<11\%$
\item {\bf Conclusão:} Tempo esperado: $O(3.2\cdot n)$ com probab acerto 89\%
\item Tempo não passa de $O(9\cdot n)$
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Monte Carlo - Popular-busca}

\begin{block}{Algoritmo Monte-Carlo-2 p/ Problema Popular-busca}
\begin{itemize}
\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Busca:} Dado vetor com popular, encontrar um deles.}
\item {\bf Algoritmo Monte-Carlo-2:} Selecione 1000 elementos aleatoriamente e retorne o que aparece mais vezes.
\item Monte Carlo pode errar, mas sempre tem mesmo tempo $O(1000)$ constante no pior caso
\item Distribuição ????. Probabilidade de errar pequena ????
\item {\bf Conclusão:} Tempo pior caso constante e probab acerto grande ????
\item {\bf Exercício:} pesquise quanto seria esta probabilidade
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmos Probabilísticos - Popular-decisão}

\begin{block}{Exemplo: Problema do Popular-decisão}
\begin{itemize}
%\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
%\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Decisão:} Dado vetor, decidir se ele tem popular.}
\item {\bf Algoritmo Las Vegas:} ???? (que use realmente probabilidade)
\item {\bf Algoritmo Monte Carlo:} Repita no máximo 9 vezes: escolhe um elemento aleatório e conta quantas vezes aparece. Se for mais de $n/5$ vezes, retorne SIM. Se nenhum encontrado, retorne NÃO.
\item Monte Carlo pode errar e o tempo pode variar: $O(3.2\cdot n)$ esperado
\item \alert{Se NÃO (tem popular), o algoritmo sempre acerta e retorna NÃO.}
\item \cor{Se SIM (tem popular), o algoritmo pode errar.}
\item Distribuição Geométrica: Probab errar 9 vezes: $(4/5)^{9}<14\%$
\item {\bf Conclusão:} Tempo esperado $O(3.2\cdot n)$ com probab acerto 86\%
\item Algoritmo {\it one-sided error true-biased (OK p/ SIM)}: sempre acerta quando diz SIM. Pode errar quando diz NÃO.
\item Popular-dec $\in$ classe RP (Randomized Poly) p/ Problemas Decisão
\item Outras classes: ZPP (zero error), RP, co-RP, BPP (two sided error)
\end{itemize}
\end{block}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Próximas aulas}

\begin{itemize}
\item \cor{Resumo} das Noções básicas de probabilidade: Independência, Variável aleatória, Esperança, Variância
\item Desigualdades clássicas: Markov e Chebyschev
\item \cor{Aplicação} em Algoritmos Probabilísticos interessantes
\item Distribuições Discretas: Binomial, Geométrica, HiperGeométrica, Poisson, Binomial Negativa,...
\item \cor{Aplicações:} Problemas do Colecionador de Figurinhas
\item Mais Algoritmos Probabilísticos: Quick Sort Aleatório, Mediana Aleatória, MaxSAT
\item \cor{Desaleatorização:} obter algoritmo determinístico (não probabilístico)
\item \cor{Classificação p/ Problemas de Decisão:} ZPP, RP, co-RP, BPP.
\item \alert{E mais:} Amplificação, Cadeias de Markov, outras Desigualdades, outros Algoritmos Probabilísticos,...
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Noções básicas de Probabilidade Discreta}

Um \alert{\bf espaço de probabilidade discreto} $(\Omega,\PP)$ é dado por um conjunto $\Omega$ (chamado \cor{espaço amostral}, finito ou infinito enumerável) e uma \cor{função de probabilidade} $\PP:\Omega\to[0,1]$ tal que $\sum_{\omega\in\Omega}\PP(\omega)=1$.\\
Subconjuntos do espaço amostral são chamados de \alert{\bf eventos}.
\vspace{0.5cm}

\cor{\bf Exemplo:} Lançamento de 1 moeda. Espaço amostral $\{$C,K$\}$ com $\PP(C)=1/2$ e $\PP(K)=1/2$. 
\vspace{0.2cm}

\cor{\bf Exemplo:} 2 moedas. Espaço amostral $\{$CC,CK, KC, KK$\}$ com probabilidade 1/4 para cada. 
\vspace{0.2cm}

\cor{\bf Exemplo:} Lançamento de 1 dado. Espaço amostral $\{$1,2,3,4,5,6$\}$ com probabilidade 1/6 para cada. 
\vspace{0.2cm}

\cor{\bf Exemplo:} Duplas em sala com 4 alunos A,B,C,D. Espaço amostral $\{$AB,AC,AD,BC,BD,CD$\}$ com probabilidade 1/6 para cada. 
\vspace{0.2cm}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Noções básicas de Probabilidade Discreta}

Um \alert{\bf espaço de probabilidade discreto} $(\Omega,\PP)$ é dado por um conjunto $\Omega$ (chamado \cor{espaço amostral}, finito ou infinito enumerável) e uma \cor{função de probabilidade} $\PP:\Omega\to[0,1]$ tal que $\sum_{\omega\in\Omega}\PP(\omega)=1$.\\
Subconjuntos do espaço amostral são chamados de \alert{\bf eventos}.
\vspace{0.5cm}

\cor{\bf Exemplo:} Moeda não-viciada até obter uma coroa. Espaço amostral $\{1,2,\ldots\}$ do número de lançamentos. Determine função de probab. 
\vspace{0.2cm}

{\bf Solução:} $\PP(n)\ =\ (\frac{1}{2})^{n-1}\cdot(\frac{1}{2})\ =\ (\frac{1}{2})^n$\ \ \ \ \ \ \ \ \ \cor{(Distribuição Geométrica)}\\
Note que $\sum_{n=1}^\infty\PP(n)\ =\ \sum_{n=1}^{\infty}(\frac{1}{2})^n\ =\ \frac{1/2}{1-1/2}\ =\ 1$ ({soma de PG}).
\vspace{0.5cm}

\cor{\bf Exemplo:} Moeda viciada é lançada até se obter uma coroa, que tem probab. 1/9. Espaço amostral $\{1,2,\ldots\}$ do número de lançamentos. Determine a função de probabilidade. 

\vspace{0.2cm}

{\bf Solução:} $\PP(n)\ =\ (\frac{8}{9})^{n-1}\cdot(\frac{1}{9})\ =\ \frac{1}{8}(\frac{8}{9})^n$\ \ \ \ \ \ \ \ \ \cor{(Distribuição Geométrica)}\\
Note que $\sum_{n=1}^\infty\PP(n)\ =\ \sum_{n=1}^{\infty}\frac{1}{8}(\frac{8}{9})^n\ =\ \frac{1/9}{1-8/9}\ =\ 1$ ({soma de PG}).
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Noções básicas de Probabilidade Discreta}

\cor{\bf Exemplo:} Moeda viciada até obter 4 coroas. Espaço amostral $\{4,5,\ldots\}$ do número de lançamentos. Determine função de probab. 
\vspace{0.2cm}

{\bf Solução:} $\PP(n)\ =\ \binom{n-1}{3}(\frac{1}{9})^4\cdot(\frac{8}{9})^{n-4}$\ \ \ \ \ \ \ \ \ \ \ \ \cor{(Distr Binomial Negativa)}\\
%Note que $\sum_{n=1}^\infty\PP(n)\ =\ \sum_{n=1}^{\infty}(\frac{1}{2})^n\ =\ \frac{1/2}{1-1/2}\ =\ 1$ ({\bf soma de PG}).
\vspace{0.5cm}

\cor{\bf Exemplo:} Uma moeda não-viciada é lançada 5 vezes. Qual é a probabilidade de aparecer apenas uma cara? E 2, 3, 4 ou 5 caras?
\vspace{0.2cm}

{\bf Solução:} Seja C (cara) e K (coroa).\\
As possibilidades de lançamentos com 1 cara são:\\ CKKKK, KCKKK, KKCKK, KKKCK, KKKKC:\\
\vspace{0.2cm}

$\PP(\mbox{número de caras} = 0)\ =\ \binom{5}{0}/2^5\ =\ 1/32$.\\
$\PP(\mbox{número de caras} = 1)\ =\ \binom{5}{1}/2^5\ =\ 5/32$.\\
$\PP(\mbox{número de caras} = 2)\ =\ \binom{5}{2}/2^5\ =\ 10/32$.\ \ \ \ \ \cor{(Distribuição Binomial)}\\
$\PP(\mbox{número de caras} = 3)\ =\ \binom{5}{3}/2^5\ =\ 10/32$\\
$\PP(\mbox{número de caras} = 4)\ =\ \binom{5}{4}/2^5\ =\ 5/32$.\\
$\PP(\mbox{número de caras} = 5)\ =\ \binom{5}{5}/2^5\ =\ 1/32$.
\vspace{0.5cm}

}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Probabilidade Condicional}

\cor{\bf Probabilidade de um evento A dado que ocorreu um evento B:}
\[
  \PP(A\ |\ B)\ =\ \frac{\PP(A\ \cap\ B)}{\PP(B)},\ \ \mbox{se}\ \ \PP(B)>0
\]
\vspace{0.2cm}

\cor{\bf Exemplo:} Qual a probabilidade de se obter 3 caras em 5 lançamentos, considerando que nos dois primeiros só teve 1 cara?\\
As possibilidades são:\\ CKCCK, CKCKC, CKKCC, KCCCK, KCCKC, KCKCC:\\
\[
  \frac{6}{2\cdot 8}=\frac{3}{8}\ \ \ \ =\ \ \ \ \frac{2/4\cdot 3/8}{16/32}
\]
\vspace{0.2cm}

Eventos A e B são \cor{\bf independentes} se $\PP(A | B)= \PP(A)$.\\
Conclusão: $\PP(A\cap B)\ =\ \PP(A)\cdot\PP(B)$\ \ \ e\ \ \ $\PP(B | A)=\PP(B)$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Probabilidade Condicional}

\cor{\bf Probabilidade de um evento A dado que ocorreu um evento B:}
\[
  \PP(A\ |\ B)\ =\ \frac{\PP(A\ \cap\ B)}{\PP(B)},\ \ \mbox{se}\ \ \PP(B)>0
\]
\vspace{0.2cm}

\cor{\bf Caso geral:} $\PP(A \cap B)\ =\ \PP(A)\cdot\PP(B|A)$.\\
\cor{\bf Caso geral:} $\PP(A \cap B\cap C)\ =\ \PP(A)\cdot\PP(B|A)\cdot\PP(C|A,B)$.\\
\alert{\bf Caso mais geral:}
\[
\PP(A_1\cap A_2\cap\ldots\cap A_k)\ =\ \PP(A_1)\cdot\PP(A_2|A_1)\cdot\PP(A_3|A_1,A_2)\cdot\ldots\cdot\PP(A_k|A_1,\ldots,A_{k-1})
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Amplificação Probabilística da probabilidade de acerto}

\begin{itemize}
\item Seja $\mathcal{A}$ um algoritmo probabilístico \cor{SIM}/\alert{NÃO} {\it one-sided-error} de tempo polinomial que sempre acerta quando retorna \cor{SIM}, mas acerta quando retorna \alert{NÃO} com probabilidade baixa de \alert{1\%}.
\item Repetindo $k$ vezes o algoritmo $\mathcal{A}$ e retornando \alert{NÃO} só se todas as execuções retornaram \alert{NÃO}, quanto será a probab de erro? \alert{$0.99^k$}
\item Tomando $k=500$, temos probab de erro $\leq 1\%$.
\item O algoritmo probabilístico \cor{SIM}/\alert{NÃO} {\it one-sided-error} obtido desse procedimento é  polinomial, sempre acerta quando retorna \cor{SIM} e acerta quando retorna \alert{NÃO} com probabilidade alta de \alert{99\%}.
\end{itemize}
\vspace{0.8cm}

\begin{itemize}
\item Analogamente também vale se $\mathcal{A}$ sempre acerta ao retornar \alert{NÃO}, mas acerta quando retorna \cor{SIM} com probabilidade baixa de \alert{1\%}.
\item É mais complicado se o algoritmo probabilístico $\mathcal{A}$ é {\it two-sided-error}: pode errar o SIM e o NÃO. {\bf Aulas futuras.}
\end{itemize}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Amplificação Probabilística da probabilidade de acerto}

\begin{itemize}
\item Seja $\mathcal{A}$ um algoritmo probabilístico \cor{SIM}/\alert{NÃO} de tempo polinomial que sempre acerta quando retorna \cor{SIM}, mas acerta quando retorna \alert{NÃO} com probabilidade baixa de \alert{$\varepsilon>0$}.
\item Repetindo $k$ vezes o algoritmo $\mathcal{A}$ e retornando \alert{NÃO} só se todas as execuções retornaram \alert{NÃO}, quanto será a probab de erro? \alert{$(1-\varepsilon)^k$}
\item Para $k=\log_{1-\varepsilon}0.01=\log_{\frac{1}{1-\varepsilon}}100$, temos probab erro $\leq 1\%$.
\item Exemplo: Para $\varepsilon=0.01\%$, $k=50000$ repetições são suficientes.
\item O algoritmo probabilístico \cor{SIM}/\alert{NÃO} obtido desse procedimento é  {\bf polinomial}, sempre acerta quando retorna \cor{SIM} e acerta quando retorna \alert{NÃO} com probabilidade alta de \alert{99\%}.
\item Isso porque, quando $\varepsilon$ é constante (não depende do tam da instância de $\mathcal{A}$), mesmo que seja muito pequeno, $k$ também é constante.
\end{itemize}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Classes probabilísticas de Problemas de Decisão}

Dados $0\leq s<c\leq 1$, seja $PCP_{c,s}$ o conjunto dos problemas de decisão que possuem algoritmos probabilísticos de tempo polinomial tais que:
\begin{itemize}
\item \cor{Se instância SIM, $\PP(\mbox{algoritmo retorna SIM})\geq c$ (\textit{completeness})}
\item \alert{Se instância NÃO, $\PP(\mbox{algoritmo retorna SIM})\leq s$ (\textit{soundness})}
\end{itemize}

\vspace{0.2cm}
\begin{block}{Classes conhecidas}
\begin{itemize}
\item \cor{ZPP\ \ \ = PCP$_{1,0}$}\ \ \ \ \ \ (Zero erro: possui algoritmo Las Vegas)
\item \cor{RP\ \ \ \ \ = PCP$_{1/2,0}$}\ \ \ (Pode errar dizendo NÃO p/ instância SIM)
\item \cor{coRP\ \ = PCP$_{1,1/2}$}\ \ \ (Pode errar dizendo SIM p/ instância NÃO)
\item \cor{BPP\ \ \ = PCP$_{2/3,1/3}$}\ (Pode errar quando retorna SIM ou NÃO)
\end{itemize}
\end{block}

%\begin{figure}\centering
%\includegraphics[scale=0.3]{classes.png}
%\end{figure}

\begin{table}[h!]
     \begin{center}
     \begin{tabular}{ c  p{3.9cm} }
     \raisebox{-\totalheight}{\includegraphics[width=0.55\textwidth]{classes.png}}
      &
      \begin{itemize}
      \item\cor{P $\subseteq$ ZPP}
      \item\cor{ZPP\ =\ RP $\cap$ coRP}
      \item\cor{BPP $\supseteq$ RP $\cup$ coRP}
      \item \alert{P = ZPP ?}
      \item \alert{P = BPP ?}
      \item \alert{BPP = RP $\cup$ coRP ?}
      \end{itemize}
      \end{tabular}
      \end{center}
      \end{table}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Aplicação: Verificar se tem Popular}

\begin{itemize}
\item Elem. \cor{popular} de vetor de tam. $n$: aparece mais de $n/5$ vezes 
\item $[1,2,3,4,5,6,7,8,9,0,1,2,5,5,5]$: O elemento 5 é popular.
\item \alert{{\bf Problema de Decisão:} Dado vetor, decidir se ele tem popular.}
\item {\bf Algoritmo Monte Carlo:} Escolhe um elemento aleatório e conta quantas vezes aparece. Se for mais de $n/5$ vezes, retorne SIM. Se nenhum encontrado, retorne NÃO.
\item \alert{Se NÃO (tem popular), o algoritmo sempre acerta e retorna NÃO.}
\item \cor{Se SIM (tem popular), o algoritmo pode errar com probab $\leq 4/5$.}
\item {\bf Amplificação:} Repete 21 vezes: erro $(4/5)^{21}<1\%$
\item \cor{\textit{One-sided error true biased} (acerta ao dizer SIM)}: \alert{Classe RP}.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Aplicação: Verificar Igualdade de Polinômios}

\alert{\bf Problema:} Dados dois polinômios $F(x)$ e $G(x)$ de grau $n$, decidir se são iguais ou não, considerando $F(x)$ como produto de monômios.\\
{\bf Exemplo:} $(x+1)(x-2)(x+3)(x-4)\ =\ x^4+7x^2-24$\ ?\ \ \ ($n=4$)
\vspace{0.6cm}

\cor{\bf Algoritmo-1:} Transformar $F(x)$ p/ forma canônica e comparar com coeficientes de $G(x)$.
{\bf Tempo} $\Theta(4+6+8+10+\ldots+2(n-1)) = \Theta(n^2)$\\
%Divisão-conquista: Tempo $T(n)=2\cdot T(n/2)+n \Rightarrow T(n)=\Theta(n \log n)$\\
\vspace{0.6cm}

\cor{\bf Algoritmo-2:} Escolher inteiro $r$ em $\{1,\ldots,100n\}$ aleatório uniforme. Calcular $F(r)$ e $G(r)$ e comparar. Se igual, retornar SIM.\\
Caso contrário, retornar NÃO.
{\bf Tempo} $\Theta(n)$.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{Monte Carlo}\\
\vspace{0.2cm}

{\bf Análise Algoritmo-2:} Se \cor{SIM} ($F(x)=G(x)$), o algoritmo acerta.\\
Se \alert{NÃO} ($F(x)\ne G(x)$) e $F(r)\ne G(r)$, o algoritmo acerta.\\
O algoritmo só erra se for \alert{NÃO} ($F(x)\ne G(x)$), mas $F(r)=G(r)$.\\
\cor{\textit{One-sided error false biased} (acerta ao dizer NÃO)}: \alert{Classe co-RP}.
\vspace{0.2cm}

{\bf Probabilidade de errar:} $r$ deve ser raiz de $F(x)-G(x)$, que tem grau $\leq n$ e no máximo $n$ raizes. Probabilidade de erro $\leq 1/100$
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Aplicação: Verificar Igualdade de Polinômios}

\alert{\bf Problema:} Dados dois polinômios $F(x)$ e $G(x)$ de grau $n$, decidir se são iguais ou não, considerando $F(x)$ como produto de monômios.\\
{\bf Exemplo:} $(x+1)(x-2)(x+3)(x-4)\ =\ x^4+7x^2-24$\ ?\ \ \ ($n=4$)
\vspace{0.3cm}

\cor{\bf Algoritmo-2:} Escolher inteiro $r$ em $\{1,\ldots,100n\}$ aleatório uniforme. Calcular $F(r)$ e $G(r)$ e comparar. Se igual, retornar SIM.\\
Caso contrário, retornar NÃO.
{\bf Tempo} $\Theta(n)$.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{Monte Carlo}\\
\vspace{0.2cm}

{\bf Análise Algoritmo-2:} Se \cor{SIM} ($F(x)=G(x)$), o algoritmo acerta.\\
Se \alert{NÃO} ($F(x)\ne G(x)$) e $F(r)\ne G(r)$, o algoritmo acerta.\\
O algoritmo só erra se for \alert{NÃO} ($F(x)\ne G(x)$), mas $F(r)=G(r)$.\\
\cor{\textit{One-sided error false biased} (acerta ao dizer NÃO)}: \alert{Classe co-RP}.
\vspace{0.2cm}

{\bf Probabilidade de errar:} $r$ deve ser raiz de $F(x)-G(x)$, que tem grau $\leq n$ e no máximo $n$ raizes. Probabilidade de erro $\leq 1/100$
\vspace{0.2cm}

{\bf Amplificação:} Repetindo $k$ vezes com reposição: $\PP($erro$)\leq (1/100)^k$\\
}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Aplicação: Verificar produto de matrizes}

\alert{\bf Problema:} Dadas três matrizes $n\times n$ $A$, $B$ e $C$, decidir se $A\times B=C$.\\
\vspace{0.6cm}

\cor{\bf Algoritmo-1:} Multiplicar $A\times B$ e comparar com $C$.\\
{\bf Tempo} $\Theta(n^3)$ (simples) ou $\Theta(n^{2.37})$ (sofisticado)\\
\vspace{0.7cm}

\cor{\bf Algoritmo-2:} Escolher vetor $r=(r_1,\ldots,r_n)$ em $\{0,1\}^n$ aleatório uniforme. Calcular $A\cdot(B\cdot r)$ e $C\cdot r$ e comparar. Se igual, retornar SIM.\\
Caso contrário, retornar NÃO.
{\bf Tempo} $\Theta(n^2)$.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{Monte Carlo}\\
\vspace{0.2cm}

{\bf Análise Algoritmo-2:} Se \cor{SIM} ($AB=C$), o algoritmo acerta.\\
Se \alert{NÃO} ($AB\ne C$) e $A\cdot(B\cdot r)\ne C\cdot r$, o algoritmo acerta.\\
O algoritmo só erra se for \alert{NÃO} ($AB\ne C$), mas $A\cdot(B\cdot r)=C\cdot r$.\\
\cor{\textit{One-sided error false biased} (acerta ao dizer NÃO)}: \alert{Classe co-RP}.
\vspace{0.2cm}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Aplicação: Verificar produto de matrizes}

\alert{\bf Problema:} Dadas três matrizes $n\times n$ $A$, $B$ e $C$, decidir se $A\times B=C$.\\
\vspace{0.3cm}

\cor{\bf Algoritmo-2:} Escolher vetor $r=(r_1,\ldots,r_n)$ em $\{0,1\}^n$ aleatório uniforme. Calcular $A\cdot(B\cdot r)$ e $C\cdot r$ e comparar. Se igual, retornar SIM.\\
Caso contrário, retornar NÃO.
{\bf Tempo} $\Theta(n^2)$.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{Monte Carlo}\\
\vspace{0.2cm}

{\bf Análise Algoritmo-2:} Se \cor{SIM} ($AB=C$), o algoritmo acerta.\\
Se \alert{NÃO} ($AB\ne C$) e $A\cdot(B\cdot r)\ne C\cdot r$, o algoritmo acerta.\\
O algoritmo só erra se for \alert{NÃO} ($AB\ne C$), mas $A\cdot(B\cdot r)=C\cdot r$.\\
\cor{\textit{One-sided error false biased} (acerta ao dizer
 NÃO)}: \alert{Classe co-RP}.
\vspace{0.4cm}

{\bf Probabilidade de errar:} Seja $D=AB-C\ne 0$. Logo $D$ tem valor $\ne 0$ (para simplificar, suponha que $d_{1,1}\ne 0$).
\[
A\cdot (B\cdot r)=C\cdot r\ \cor{\Rightarrow}\ D\cdot r=0\ \cor{\Rightarrow}\ \sum_{k=1}^n d_{1,k}\cdot r_k=0\ \cor{\Rightarrow}\ r_1=-\sum_{k=2}^n \frac{d_{1,k}\cdot r_k}{d_{1,1}}
\]
$\PP(r_1$ ser este valor $|\ r_2,\ldots,r_n)\leq 1/2$. Logo $\PP$(erro)$\leq 1/2$. 
\vspace{0.2cm}

{\bf Amplificação:} Repetindo $k$ vezes com reposição: $\PP($erro$)\leq (1/2)^k$\\
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo de Karger'93 para Corte Mínimo}

\alert{\bf Min-Cut (otimização):} Dado um grafo simples $G$, obter o menor número de arestas cuja remoção desconecta o grafo.\\
\vspace{0.3cm}

\begin{figure}\centering
\includegraphics[scale=0.3]{karger1.png}
\end{figure}

\cor{\bf Algoritmo de Fluxo Máximo:} Aplicar Ford-Fulkerson (ou outro) p/ cada par $(s,t)$ de vértices, pondo capacidade 1 e direção nos dois sentidos para cada aresta. Ok pelo Teorema max-flow min-cut. Tempo $O(n^5)$. 
\vspace{0.2cm}

\cor{\bf Algoritmo de Gabow'95:} matroides, mais complicado. Tempo $O(n^3)$. 
\vspace{0.2cm}

\cor{\bf Algoritmo de Karger'93:} Probabilístico, mais simples e mais rápido. Tempo $O(n^2\log^3 n)$. 
\vspace{0.2cm}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo de Karger'93 para Corte Mínimo}

\alert{\bf Min-Cut (otimização):} Dado um grafo simples $G$, obter o menor número de arestas cuja remoção desconecta o grafo.\\
\vspace{0.3cm}

\cor{\bf Algoritmo de Karger'93:} Escolhe uma aresta aleatoriamente de modo uniforme e a contrai. Repete até sobrar apenas 2 vértices. 
\vspace{0.2cm}

\begin{figure}\centering
\includegraphics[scale=0.65]{karger2.png}
\end{figure}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo de Karger'93 para Corte Mínimo}

\cor{\bf Algoritmo de Karger'93:} Escolhe uma aresta aleatoriamente de modo uniforme e a contrai. Repete até sobrar apenas 2 vértices. 
\vspace{0.2cm}

\cor{\bf Teorema:} Algoritmo encontra Corte Mínimo com prob. $\geq\frac{2}{n(n-1)}$. 
\vspace{0.2cm}

{\bf Prova:} Seja $C$ um corte mínimo com $k$ arestas. Vamos calcular a probabilidade de encontrar $C$. O algoritmo não pode contrair nenhuma aresta de $C$. Como $C$ é mínimo, todo vértices tem grau $\geq k$. Logo $m\geq nk/2$ (número arestas).
\[
\PP(1^o \mbox{ iteração OK})\ \geq\ 1-\frac{k}{nk/2}\ =\ 1-\frac{2}{n}\ =\ \frac{n-2}{n}
\]
Vértices restantes mantém grau $\geq k\ \ \Rightarrow\ \ (n-1)k/2$ arestas.
\[
\PP(2^o \mbox{ iteração OK})\ \geq\ 1-\frac{k}{(n-1)k/2}\ =\ 1-\frac{2}{n-1}\ =\ \frac{n-3}{n-1}
\]
Vértices restantes mantém grau $\geq k\ \ \Rightarrow\ \ (n-2)k/2$ arestas.
\[
\PP(3^o \mbox{ iteração OK})\ \geq\ 1-\frac{k}{(n-2)k/2}\ =\ 1-\frac{2}{n-2}\ =\ \frac{n-4}{n-2}
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo de Karger'93 para Corte Mínimo}

\cor{\bf Algoritmo de Karger'93:} Escolhe uma aresta aleatoriamente de modo uniforme e a contrai. Repete até sobrar apenas 2 vértices. 
\vspace{0.2cm}

\cor{\bf Teorema:} Algoritmo encontra Corte Mínimo com prob. $\geq\frac{2}{n(n-1)}$. 
\vspace{0.2cm}

{\bf Prova:} Seja $C$ um corte mínimo com $k$ arestas. Vamos calcular a probabilidade de encontrar $C$. O algoritmo não pode contrair nenhuma aresta de $C$. Como $C$ é mínimo, todo vértices tem grau $\geq k$. Logo $m\geq nk/2$ (número arestas).
\[
\PP(\mbox{tudo OK})\ \geq\ \prod_{i=1}^{n-2}\frac{n-i-1}{n-i+1}\ =\ \frac{2\cdot 1}{n(n-1)}\ \ \ \ \ \ \ \ \ \ \ \ \ \square
\]
\alert{Repetindo $3n(n-1)$ vezes e retornando o menor corte obtido, qual a probabilidade de um corte mínimo $C$ não ser encontrado?}
\[
\left(1-\frac{2}{n(n-1)}\right)^{3n(n-1)}\ \leq\ e^{-6}\ <\ 1\%,
\]
pois $1-x \leq e^{-x}$ para todo $x$ (especialmente $x$ próximo de zero).
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo de Karger'93 para Corte Mínimo}

\begin{figure}\centering
\includegraphics[scale=0.3]{karger3.png}
\end{figure}

\alert{Repetindo $n(n-1)\ln n$ vezes e retornando o menor corte obtido, qual a probabilidade de um corte mínimo $C$ não ser encontrado?}
\[
\left(1-\frac{2}{n(n-1)}\right)^{n(n-1)\ln n}\ \leq\ e^{-2\ln n}\ =\ \frac{1}{n^2}.
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo de Karger'93 para Corte Mínimo}

{\bf Tempo do algoritmo:} \cor{$O(n^2)$} \alert{vezes} \cor{o tempo do processo de contração}, que é similar à execução do Algoritmo de Kruskal (para árvore geradora mínima com pesos aleatórios) até sobrarem 2 componentes conexas.\\
\alert{\bf Tempo total: $O(n^4)$.} \cor{Pode ser melhorado para tempo $O(n^2\log^3 n)$.}

\begin{figure}\centering
\includegraphics[scale=0.15]{karger4.png}
\end{figure}


\vspace{0.5cm}
\tiny
{\bf Observação final:} Os algoritmos probabilísticos vistos nesta disciplina obtém tempos melhores que os algoritmos determinísticos tanto para problemas de busca (popular) e de decisão (igualdade de polinômios, produto de matrizes) como otimização (corte mínimo). Porém, não se conhece algoritmo probabilístico polinomial eficiente que resolva um problema NP-Difícil. Isso está relacionado às questões P=ZPP? e P=BPP? já mencionadas. Ou seja, não se espera com o uso de probabilidade obter algoritmos polinomiais para problemas NP-Difíceis, mas sim obter algoritmos mais rápidos do que os existentes com ajuda da processos aleatórios. 
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Variável Aleatória Discreta}

Uma \cor{\bf variável aleatória (v.a.)} de um espaço de probabilidade discreto $(\Omega,\PP)$ é uma função $X:\Omega\to\RR$ que associa um valor real a cada elemento do espaço amostral $\Omega$.
\vspace{0.2cm}

{\bf Exemplo:} 3 moedas; \cor{v.a. $X$} conta o número de caras.\\
$X(KKC)=1$, $X(CCK)=2$.
\vspace{0.2cm}

{\bf Probabilidade de uma v.a.:} Escrevemos $\PP(X\in S)$ para $S\subseteq\RR$:
\[
\PP(X\in S)\ =\ \PP(X^{-1}(S))\ =\ \sum_{\omega\in X^{-1}(S)} \PP(\omega).
\]
\vspace{0.0cm}

{\bf Exemplo:} 3 moedas; \cor{v.a. $X$} conta o número de caras.\\
$\PP(X\geq 2)=\PP(\{CCK,CKC,KCC,CCC\})=4\cdot\frac{1}{8}=\frac{1}{2}$.
\vspace{0.6cm}

\small
{\bf Observação:} A maioria das variáveis aleatórias usadas aqui serão do tipo $X:\Omega\to\NN$. Nesse caso, $\sum_{x=0}^\infty\PP(X=x)=1$
\vspace{0.2cm}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuição de Probabilidade Conjunta}

Dadas duas v.a. $X$ e $Y$ de um espaço de probabilidade discreto $(\Omega,\PP)$, escrevemos $\PP(X\in A, Y\in B)$ como a probabilidade de $X\in A$ e $Y\in B$.
\vspace{0.2cm}

$X$ e $Y$ são \cor{\bf independentes} se, para quaisquer conjuntos $A$ e $B$: $\PP(X\in A, Y\in B)=\PP(X\in A)\cdot\PP(Y\in B)$.
\vspace{0.2cm}

{\bf Exemplo:} 3 moedas. v.a.'s $X$ (num caras), $Y$ (num coroas), $Z$ (num caras nos 2 primeiros lançamentos) e $W$ (num caras no último).

\[
\PP(X=2,Y=0)\ =\ 0\ \alert{\ne}\ \frac{3}{8}\cdot\frac{1}{8}\ \ \ \ \ \ \ \alert{\mbox{$X$ e $Y$ não são independentes}}
\]
\[
\PP(X=3,Z=1)\ =\ 0\ \alert{\ne}\ \frac{1}{8}\cdot\frac{2}{4}\ \ \ \ \ \ \ \alert{\mbox{$X$ e $Z$ não são independentes}}
\]
\[
\PP(Z=0,W=w)\ =\ \frac{1}{8}\ =\ \frac{1}{4}\cdot\frac{1}{2}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{\mbox{Analogamente para $Z=2$}}
\]
\[
\PP(Z=1,W=w)\ =\ \frac{1}{4}\ =\ \frac{1}{2}\cdot\frac{1}{2}\ \ \ \ \ \ \ \cor{\mbox{Logo $Z$ e $W$ são independentes}}
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Valor esperado, Esperança ou Média $\EE(X)$}

\[
\cor{\mbox{v.a. discreta $X$:}}\ \ \ \ \ \ \ \ \ \ \EE(X)\ =\ \sum_{x} x\cdot\PP(X=x)
\]
Média dos valores de $X$, ponderada pela probabilidade de cada valor.
\vspace{0.7cm}

{\bf Ex:} \cor{valor $X$ de 1 dado:} $\EE(X)=1\cdot\frac{1}{6}+2\cdot\frac{1}{6}+3\cdot\frac{1}{6}+\ldots+6\cdot\frac{1}{6}=3.5$
\vspace{0.2cm}

{\bf Ex:} \cor{num caras em 3 moedas:} $\EE(X)=0\cdot\frac{1}{8}+1\cdot\frac{3}{8}+2\cdot\frac{3}{8}+3\cdot\frac{1}{8}=1.5$
\vspace{0.2cm}

\[
\cor{\mbox{v.a.'s discretas $X$ e $Y$:}}\ \ \ \ \ \ \ \ \ \ \EE(XY)\ =\ \sum_{x,y} x\cdot y\cdot\PP(X=x,Y=y)
\]
{\bf Se $X$ e $Y$ são independentes, então:}\esp{30}\alert{\tiny (a volta nem sempre vale)}
\[
  \EE(XY)\ =\ \sum_x  x\sum_y y\cdot\PP(X=x)\cdot\PP(Y=y)\ =\ \EE(X)\cdot\EE(Y)
\]
{\bf Ex:} $\EE(XY)=0\cdot\frac{1}{8}+2\cdot\frac{3}{8}+2\cdot\frac{3}{8}+0\cdot\frac{1}{8}=1.5\alert{\ne} 1.5^2=\EE(X)\cdot\EE(Y)$
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Linearidade da Esperança $\EE(X)$}

\[
\cor{\mbox{v.a. discreta $X$, função $g:\RR\to\RR$:}}\ \ \ \ \ \ \ \ \ \ \EE(g(X))\ =\ \sum_{x} g(x)\cdot\PP(X=x)
\]
\[
%\EE(aX+b)\ =\ \sum_{x} (ax+b)\cdot\PP(X=x)\ =\ a\sum_{x} x\cdot\PP(X=x)+b\sum_{x}\PP(X=x)\ =\ a\cdot\EE(X)+b
\EE(aX+b)\ =\ \sum_{x} (ax+b)\cdot\PP(X=x)\ =\ a\cdot\EE(X)+b
\]
\vspace{0.7cm}

\alert{\bf Linearidade da Esperança: $\EE(X+Y)=\EE(X)+\EE(Y)$}\\
{\bf Prova:}
\[
\cor{\EE(X+Y)}\ =\ \sum_x\sum_y(x+y)\cdot\PP(X=x,Y=y)=
\]
\[
=\sum_x x\cdot\sum_y \PP(X=x,Y=y)\ +\ \sum_y y\cdot\sum_x\PP(X=x,Y=y)
\]
\[
=\sum_x x\cdot\PP(X=x)\ +\ \sum_y y\cdot\PP(Y=y)\ =\ \cor{\EE(X)\ +\ \EE(Y)}\ \ \ \square
\]

\vspace{0.4cm}
\tiny
\alert{{\bf Observação:} Para variáveis contínuas, vale o mesmo (trocando somatórios por integrais).}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Método Probabilístico: subgrafo bipartido grande}

Método para provar resultados combinatórios teóricos usando probabilidade. Ideias aplicáveis a algoritmos probabilísticos (\cor{Paul Erd{\H o}s}).
\vspace{0.4cm}

\cor{\bf Teorema:} Todo grafo $G=(V,E)$ possui um subgrafo bipartido com pelo menos $m/2$ (metade) das arestas, onde $m=|E|$ e $n=|V|$.\\
{\bf Prova:}\\

\begin{itemize}
\item Seja $A$ um subconjunto aleatório de vértices: $\PP(v\in A)=p=1/2$.
\item Seja $B=V-A$ e seja $X$ a v.a. do num arestas entre $A$ e $B$.
\item $X=\sum_{uv\in E}X_{uv}$, onde $X_{uv}=1$, se $uv$ está entre $A$ e $B$, e 0 c.c.
\item $\EE(X_{uv})=1\cdot(p\cdot(1-p)+(1-p)\cdot p)=\frac{1}{2}$
\item $\EE(X)=m/2$. Logo existe subgrafo bipartido com $m/2$ arestas.\ \ \ \ \ $\square$
\end{itemize}
\vspace{0.4cm}

\alert{\bf Algoritmo Probabilístico:} Seja $A$ inicialmente vazio. Para cada vértice de $G$, coloque-o em $A$ com probabilidade 1/2. Seja $B=V-A$. Remova todas as arestas entre vértices de $A$ e remova todas as arestas entre vértices de $B$. O subgrafo resultante é bipartido com número esperado de arestas igual a $m/2$.
\vspace{0.2cm}

\tiny
\alert{Ainda não fizemos conta da probabilidade desse algoritmo errar, produzindo um subgrafo bipartido com menos da metade do número de arestas. Próximas aulas.}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Método Probabilístico: subgrafo bipartido grande c/ pesos}

Método para provar resultados combinatórios teóricos usando probabilidade. Ideias aplicáveis a algoritmos probabilísticos (\cor{Paul Erd{\H o}s}).
\vspace{0.4cm}

\cor{\bf Teorema:} Todo grafo $G=(V,E)$ com pesos nas arestas tem subgrafo bipartido com pelo menos metade do peso total $W=\sum_{uv\in E}w_{uv}$.\\
{\bf Prova:}\\

\begin{itemize}
\item Seja $A$ um subconjunto aleatório de vértices: $\PP(v\in A)=p=1/2$.
\item Seja $B=V-A$ e $X$ a v.a. do peso total das arestas entre $A$ e $B$.
\item $X=\sum_{uv\in E}X_{uv}$, onde $X_{uv}=w_{uv}$, se $uv$ está entre $A$ e $B$, e 0 c.c.
\item $\EE(X_{uv})=w_{uv}\cdot(p\cdot(1-p)+(1-p)\cdot p)=w_{uv}/2$
\item $\EE(X)=W/2$. Logo há subgrafo bipartido com peso total $W/2$.\ $\square$
\end{itemize}
\vspace{0.4cm}

\alert{\bf Algoritmo Probabilístico:} Seja $A$ inicialmente vazio. P/ cada vértice de $G$, coloque-o em $A$ com probabilidade 1/2. Seja $B=V-A$. Remova todas as arestas entre vértices de $A$ e remova todas as arestas entre vértices de $B$. O subgrafo gerado é bipartido com peso esperado $W/2$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Método Probabilístico: conjunto independente grande}

{\footnotesize Método para provar existência de estruturas combinatórias usando probabilidade. Ideias aplicáveis a algoritmos probabilísticos (\cor{Paul Erd{\H o}s}).
\vspace{0.2cm}

\cor{\bf Teorema:} Todo grafo $G=(V,E)$ com $n$ vértices e \alert{$m\leq nd/2$ arestas} (para algum $d\geq 1$, por exemplo grau máximo) possui \alert{$\alpha(G)\geq n/2d$}, onde $\alpha(G)$ é o tamanho do conjunto independente máximo de $G$ (subconjunto de vértices sem arestas entre si).\\
{\bf Prova:}\\

\begin{itemize}
\item Seja $A$ um subconjunto aleatório de vértices: $\PP(v\in A)=p$ a ser definido.
\item Seja v.a. $X=|A|$ ($\EE(X)=np$) e $Y$ o num arestas em $G[A]$.
\item Logo $Y=\sum_{uv\in E}Y_{uv}$, onde $Y_{uv}=1$, se $u,v\in A$, e 0 c.c.
\item $\EE(Y)=\sum_{uv\in E}\EE(Y_{uv})=m\cdot p^2\leq (nd/2)p^2$.
\item $\EE(X-Y)\geq np-(nd/2)p^2$\esp{15}\cor{(removendo um vértice para cada aresta).}
\item  Tomando $p=1/d$ para maximização: $\EE(X-Y)\geq n/2d$\esp{25}$\square$
\end{itemize}
\vspace{0.4cm}}

\alert{\bf Algoritmo Probabilístico:} Seja $A$ inicialmente vazio. Para cada vértice de $G$, coloque-o em $A$ com probabilidade $1/d$. Remova todos os vértices fora de $A$. Iterativamente, remova o vértice com maior grau até o subgrafo resultante não ter arestas. Tamanho esperado $n/2d$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Variância $\Var(X)$, Desvio padrão $\sigma(X)$ e Covariância}

Medidas para avaliar o quanto uma v.a. $X$ desvia de sua média.
\[
Var(X) = \EE\Big((X-\EE(X))^2\Big) = \EE(X^2)-\EE^2(X).\ \ \ \ \ \ \ \ \cor{\sigma(X)=\sqrt{\Var(X)}}
\]
$\Var(a\cdot X+b)\ =\ a^2\cdot \Var(X)$\ \ \ e\ \ \ $\sigma(a\cdot X+b)=a\cdot \sigma(X)$
\vspace{0.3cm}

{\bf Ex:} \cor{valor $X$ de 1 dado:} $\EE(X^2)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{6}+3^2\cdot\frac{1}{6}+\ldots+6^2\cdot\frac{1}{6}=\frac{91}{6}=15.2$. $\Var(X)=15.2-3.5^2=2.92$. \ \ \ \ \ \ \ \ $\sigma(X)=\sqrt{\Var(X)}=1.71$.
\vspace{0.6cm}


\cor{Covariância de v.a. $X$ e $Y$:} \cor{$\Cov(X,Y)=\EE(XY)-\EE(X)\cdot\EE(Y)$.}\\
Logo, se $X$ e $Y$ são independentes, então $\Cov(X,Y)=0$. {\tiny(a volta não vale)}
\vspace{0.2cm}

\begin{block}{Propriedades da Covariância: {\small $\Cov(X,Y)=\EE(XY)-\EE(X)\cdot\EE(Y)$}}
\begin{itemize}
\item $\Cov(X,X)=Var(X)$
\item $\Cov(X,Y)=Cov(Y,X)$
\item $\Cov(a\cdot X,Y)=a\cdot \Cov(X,Y)$
\item $\Cov(X,Y+Z)=Cov(X,Y)+Cov(X,Z)$
\end{itemize}
\end{block}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Variância $\Var(X)$\ \ e\ \ Covariância $\Cov(X,Y)$}

\begin{block}{Propriedades da Covariância: {\small $\Cov(X,Y)=\EE(XY)-\EE(X)\cdot\EE(Y)$}}
\begin{itemize}
\item $\Cov(X,X)=Var(X)$
\item $\Cov(X,Y)=Cov(Y,X)$
\item $\Cov(a\cdot X,Y)=a\cdot \Cov(X,Y)$
\item $\Cov(X,Y+Z)=Cov(X,Y)+Cov(X,Z)$
\end{itemize}
\end{block}
\[
\Cov\left(\sum_{i=1}^{n}X_i\ ,\ \sum_{j=1}^{m}Y_j\right)\ \ =\ \ \sum_{i=1}^n\sum_{j=1}^m \Cov(X_i,Y_j)
\]
\[
\Var\left(\sum_{i=1}^{n}X_i\right)\ =\ \Cov\left(\sum_{i=1}^{n}X_i\ ,\ \sum_{j=1}^{n}X_j\right)\ =\ \sum_{i=1}^n\sum_{j=1}^n \Cov(X_i,X_j)\ =
\]
{\small
\[
=\sum_{i=1}^{n} \Cov(X_i,X_i)+2\sum_{i=1}^{n-1}\sum_{j=i+1}^n \Cov(X_i,X_j)
\ =\ \sum_{i=1}^{n} \Var(X_i)+2\sum_{i=1}^{n-1}\sum_{j=i+1}^n \Cov(X_i,X_j)
\]}
\cor{Se $X_1,\ldots,X_n$ são independentes, então: $\Var(\sum_{i=1}^n X_i)=\sum_{i=1}^n \Var(X_i)$.}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Variância, Desvio Padrão e Covariância}

\begin{block}{Propriedades da Covariância: {\small $\Cov(X,Y)=\EE(XY)-\EE(X)\cdot\EE(Y)$}}
\begin{itemize}
\item $\Cov(X,X)=Var(X)$
\item $\Cov(X,Y)=Cov(Y,X)$
\item $\Cov(a\cdot X,Y)=a\cdot \Cov(X,Y)$
\item $\Cov(X,Y+Z)=Cov(X,Y)+Cov(X,Z)$
\end{itemize}
\end{block}
\[
\Cov\left(\sum_{i=1}^{n}X_i\ ,\ \sum_{j=1}^{m}Y_j\right)\ \ =\ \ \sum_{i=1}^n\sum_{j=1}^m \Cov(X_i,Y_j)
\]
{\small
\[
\Var\left(\sum_{i=1}^{n}X_i\right)\ =\ \sum_{i=1}^{n} \Var(X_i)+2\sum_{i=1}^{n-1}\sum_{j=i+1}^n \Cov(X_i,X_j)
\]}
\vspace{0.2cm}

\cor{Se $X_1,\ldots,X_n$ são independentes, então: $\Var(\sum_{i=1}^n X_i)=\sum_{i=1}^n \Var(X_i)$.}
\vspace{0.2cm}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdades de Markov e Chebyshev}

\cor{{\bf Markov:} v.a. $X\geq 0$, $a>0$, $\alpha>1$:
\[
\PP(X\geq a)\ \leq\ \frac{\EE(X)}{a}\esp{10}ou\esp{10}\PP(X\geq\alpha\cdot\EE(X))\leq \frac{1}{\alpha}
\]}
{\bf Prova:}
\begin{itemize}
\item $\EE(X)\ =\ \sum_{k=0}^\infty k\cdot\PP(X=k)\ \geq\ \sum_{k=a}^\infty k\cdot\PP(X=k)\ \geq$
\item $\EE(X)\ \geq\ a\cdot\sum_{k=a}^\infty\PP(X=k)\ =\ a\cdot\PP(X\geq a)\esp{20}\square$
\end{itemize}
\vspace{0.7cm}

\alert{{\bf Chebyshev:} v.a. $X$, $b>0$, $\beta>1$:
\[
\PP\left(\big|X-\EE(X)\big|\geq b\right)\ \leq\ \frac{\Var(X)}{b^2}\esp{6}ou\esp{6}
\PP\left(\big|X-\EE(X)\big|\geq \beta\cdot\sigma(X)\right)\ \leq\ \frac{1}{\beta^2}
\]}
{\bf Prova:}
\[
\PP\left(\big|X-\EE(X)\big|\geq b\right)=\PP\big((X-\EE(X))^2\geq b^2\big)\leq\frac{\EE((X-\EE(X))^2)}{b^2}=\frac{\Var(X)}{b^2}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: Bernoulli$(p)$ e Binomial$(n,p)$}

\alert{$X\sim Bernoulli(p)$:} {\bf 1 (sucesso) com prob $p$, e 0 com prob $1-p$.}\\
\vspace{0.1cm}
$\cor{\PP(X=1)=p}$ e $\cor{\PP(X=0)=1-p}$.\esp{10}$\cor{\EE(X)}=1\cdot p+0\cdot(1-p)\ =\ \cor{p}$.\\
\vspace{0.1cm}
$\cor{\Var(X)}=\EE(X^2)-\EE^2(X)=\EE(X)-p^2=p-p^2=\cor{p(1-p)}$.
\vspace{0.9cm}

\alert{$X\sim Binomial(n,p)=\sum_{i=1}^n Bernoulli(p)$:} {\bf número de sucessos (de probabilidade $p$) em $n$ experimentos independentes.}
$$\cor{\PP(X=k)=\binom{n}{k}p^k(1-p)^{n-k}}\esp{4}\Rightarrow\esp{4}\sum_{k=0}^n\PP(X=k)=(p+1-p)^n=1.$$
$$\cor{\EE(X)}=\sum_{k=0}^n k\cdot\PP(X=k)=\sum_{k=0}^n k\binom{n}{k}p^k(1-p)^{n-k}\ =\ \cor{n\cdot p},$$
pois $X=\sum_{i=1}^n Bernoulli(p)$ e portanto $\cor{\EE(X)=\sum_{i=1}^n \EE(X_i)=n\cdot p}$ e\\ 
\vspace{0.1cm}
$\cor{\Var(X)=\sum_{i=1}^n \Var(X_i)\ =\ n\cdot p\cdot(1-p)}$\esp{12}{\tiny(pois os $X_i$'s são independentes entre si)}.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: Bernoulli$(p)$ e Binomial$(n,p)$}

\cor{{\bf Aplicação:} $n$ moedas não-viciadas lançadas. Seja $X$ o número de caras.}\\
$X\sim Binomial(n,\frac{1}{2})$,\ \ \cor{$\EE(X)=n/2$}\ \ e\ \ $\Var(X)=n\cdot\frac{1}{2}(1-\frac{1}{2})=n/4$.\\
\vspace{0.5cm}

Markov: \esp{4.5}$\PP(X\geq 3n/4)\leq\frac{\EE(X)}{3n/4}=\frac{n/2}{3n/4}=\frac{2}{3}$ \alert{\bf(ruim)}\\
\vspace{0.2cm}
Chebyshev: $\PP(X\geq 1.5\frac{n}{2})\leq\PP(|X-\EE(X)|\geq 0.5\frac{n}{2})\leq\frac{\Var(X)}{(n/4)^2}=\frac{4}{n}$. \cor{\bf(bom)}\\
\vspace{0.1cm}
Chebyshev: $\PP(X\geq 1.1\frac{n}{2})\leq\PP(|X-\EE(X)|\geq 0.1\frac{n}{2})\leq\frac{\Var(X)}{(0.1\cdot n/2)^2}=\frac{100}{n}$.
\vspace{0.2cm}
{\small
Chebyshev:\esp{3}$\PP(X\geq 1.01\frac{n}{2})\leq\PP(|X-\EE(X)|\geq 0.01\frac{n}{2})\leq\frac{\Var(X)}{(0.01\cdot n/2)^2}=\frac{10000}{n}$.}
\vspace{0.2cm}
%{\scriptsize
%{\footnotesize
{\small
Chebyshev:\esp{3}$\PP(X\geq\frac{n+\sqrt{n}}{2})\leq\PP(|X-\EE(X)|\geq \frac{\sqrt{n}}{2})\leq\frac{\Var(X)}{(\sqrt{n}/2)^2}=1$. \alert{\bf(ruim)}}

\vspace{0.9cm}
\alert{\tiny
Nas próximas aulas, veremos outras distribuições clássicas e desigualdades mais fortes, como a de Chernoff.}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Método Probabilístico: subgrafo bipartido grande}

{\footnotesize
\cor{\bf Teorema:} Todo grafo $G=(V,E)$ possui um subgrafo bipartido com pelo menos $m/2$ (metade) das arestas, onde $m=|E|$ e $n=|V|$.\\
{\bf Prova:}\\

\begin{itemize}
\item Seja $A$ um subconjunto aleatório de vértices: $\PP(v\in A)=p=1/2$.
\item Seja $B=V-A$ e seja $X$ a v.a. do num arestas entre $A$ e $B$.
\item $X=\sum_{uv\in E}X_{uv}$, onde $X_{uv}=1$, se $uv$ está entre $A$ e $B$, e 0 c.c.
\item $\EE(X_{uv})=1\cdot(p\cdot(1-p)+(1-p)\cdot p)=\frac{1}{2}$
\item $\EE(X)=m/2$. Logo existe subgrafo bipartido com $m/2$ arestas.\ \ \ \ \ $\square$
\end{itemize}
\vspace{0.4cm}

\alert{\bf Algoritmo Probabilístico:} Seja $A$ inicialmente vazio. Para cada vértice de $G$, coloque-o em $A$ com probabilidade 1/2. Seja $B=V-A$. Remova todas as arestas entre vértices de $A$ e remova todas as arestas entre vértices de $B$. O subgrafo resultante é bipartido com número esperado de arestas igual a $m/2$.}
\vspace{0.4cm}

\cor{$X_{uv}$ são v.a.'s $Bernoulli(\frac{1}{2})$. Vamos mostrar que são independentes.}\\
$X_{uv}$ e $X_{wz}$ são independentes, pois\\
$\PP(X_{u,v}=1,X_{w,z}=1)=(\frac{1}{2})\cdot(\frac{1}{2})=\frac{1}{4}=\PP(X_{u,v}=1)\cdot\PP(X_{w,z}=1)$.\\
\vspace{0.1cm}
$X_{uv}$ e $X_{uz}$ são independentes, pois\esp{25}\alert{\tiny(para $p\ne 1/2$, não são independentes)}\\
$\PP(X_{u,v}=1,X_{u,z}=1)=(\frac{1}{2})\cdot(\frac{1}{2})=\frac{1}{4}=\PP(X_{u,v}=1)\cdot\PP(X_{u,z}=1)$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Método Probabilístico: subgrafo bipartido grande}

{\footnotesize
\cor{\bf Teorema:} Todo grafo $G=(V,E)$ possui um subgrafo bipartido com pelo menos $m/2$ (metade) das arestas, onde $m=|E|$ e $n=|V|$.\\
{\bf Prova:}\\

\begin{itemize}
\item Seja $A$ um subconjunto aleatório de vértices: $\PP(v\in A)=p=1/2$.
\item Seja $B=V-A$ e seja $X$ a v.a. do num arestas entre $A$ e $B$.
\item $X=\sum_{uv\in E}X_{uv}$, onde $X_{uv}=1$, se $uv$ está entre $A$ e $B$, e 0 c.c.
\item $\EE(X_{uv})=1\cdot(p\cdot(1-p)+(1-p)\cdot p)=\frac{1}{2}$
\item $\EE(X)=m/2$. Logo existe subgrafo bipartido com $m/2$ arestas.\ \ \ \ \ $\square$
\end{itemize}
\vspace{0.4cm}

\alert{\bf Algoritmo Probabilístico:} Seja $A$ inicialmente vazio. Para cada vértice de $G$, coloque-o em $A$ com probabilidade 1/2. Seja $B=V-A$. Remova todas as arestas entre vértices de $A$ e remova todas as arestas entre vértices de $B$. O subgrafo resultante é bipartido com número esperado de arestas igual a $m/2$.}
\vspace{0.4cm}

\cor{$X=\sum_{uv\in E}X_{uv}$ é v.a. $X\sim Binomial(m,\frac{1}{2})\ \ \ \ \Rightarrow\ \ \ \ \Var(X)=\frac{m}{4}$}\\
\vspace{0.1cm}
{\bf Chebyshev:} $\PP(X\leq 0.9\frac{m}{2})\leq\PP(|X-\EE(X)|\geq 0.1\frac{m}{2})\leq\frac{\Var(X)}{(0.1\cdot m/2)^2}=\frac{100}{m}$.

\alert{\tiny
Nas próximas aulas, veremos outras distribuições clássicas e desigualdades mais fortes, como a de Chernoff.}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: Geométrica$(p)$}

\alert{$X\sim Geom(p)$:} {\bf Num experimentos indep até 1 sucesso (de prob $p$).}\\
\vspace{0.1cm}
$\cor{\PP(X=n)=p(1-p)^{n-1}}$.\esp{15}$\sum_{n=1}^\infty\PP(X=n)=\frac{p}{1-(1-p)}=1$.
\[
\sum_{n=1}^\infty n\cdot x^{n-1}=\frac{d}{dx}\left(\sum_{n=1}^\infty x^n\right)=\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{1}{(1-x)^2}\esp{10}\mbox{para}\ 0<x<1
\]
\[
\sum_{n=1}^\infty n(n-1)\cdot x^{n-2}=\frac{d}{dx}\left(\sum_{n=1}^\infty n\cdot x^{n-1}\right)=\frac{d}{dx}\left(\frac{1}{(1-x)^2}\right)=\frac{2}{(1-x)^3}
\]
\[
\cor{\EE(X)=\sum_{n=1}^\infty n\cdot\PP(X=n)=\sum_{n=1}^\infty n\cdot p(1-p)^{n-1}\ =\ p\cdot\frac{1}{(1-(1-p))^2}\ =\ \frac{1}{p}}
\]
\[
\EE(X^2)=\sum_{n=1}^\infty n^2\cdot\PP(X=n)=\frac{2p(1-p)}{p^3}+\frac{p(1-p)}{(1-p)p^2}=\frac{2-p}{p^2}
\]
\[
\cor{\Var(X)=\EE(X^2)-\EE^2(X)=\frac{2-p}{p^2}-\frac{1}{p^2}\ =\ \frac{1-p}{p^2}}
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: Binomial Negativa$(k,p)$}

\alert{$X\sim BN(k,p)$:} {\bf Num experimentos indep até k sucessos (de prob $p$).}\\
\vspace{0.1cm}
$\cor{\PP(X=n)=\binom{n-1}{k-1}p^k(1-p)^{n-k}}$.\\
\vspace{0.2cm}
v.a. $X\sim BN(k,p)$ pode ser vista como $X=\sum_{i=1}^k X_i$: a soma de $k$ v.a. $X_i\sim Geom(p)$. Ou seja, \cor{$BN(k,p)=\sum_{i=1}^k Geom(p)$.}
\[
\cor{\EE(X)=\sum_{i=1}^k \EE(X_i)\ =\ k\cdot\frac{1}{p}}
\]
\[
\cor{\Var(X)=\sum_{i=1}^k\Var(X_i)\ =\ k\cdot\frac{1-p}{p^2}
}
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Problema do Colecionador de Cupons/Figurinhas}

\alert{Álbum com $n$ diferentes tipos de figurinhas. Cada figurinha comprada tem probabilidade igual para ser de qualquer tipo. Determinar esperança e variância do número de figurinhas compradas para encher o álbum.}\\
\vspace{0.1cm}
Seja v.a. $X$ esse número. Seja $X_i$ o número a comprar até obter uma nova figurinha, dado que já possui $i$ figurinhas.\\
\vspace{0.2cm}
\cor{$X=\sum_{i=0}^{n-1}X_i$}, onde \cor{$X_i\sim Geom(\frac{n-i}{n})$.} {\footnotesize $X$ é semelhante à Binomial Negativa.}
\[
\cor{\EE(X)=\sum_{i=0}^{n-1} \EE(X_i)\ =\ \sum_{i=0}^{n-1}\frac{n}{n-i}=n\cdot\sum_{k=1}^{n}\frac{1}{k}\approx n\ln n+0.5772\cdot n+\frac{1}{2},}
\]
{\footnotesize pois $\sum_{k=1}^n\frac{1}{k}=\ln n+0,5772+\frac{1}{2n}+O(\frac{1}{n^2})$. \esp{6}Ademais, $0\leq \sum_{k=1}^n\frac{1}{k}-\ln n\leq 1$.}
{\scriptsize
\[
\cor{\Var(X)=\sum_{i=0}^{n-1}\Var(X_i)\ =\ n\sum_{i=0}^{n-1}\frac{i}{(n-i)^2}=n\sum_{k=1}^n \frac{n-k}{k^2}=n^2\sum_{k=1}^{n}\frac{1}{k^2}-n\sum_{k=1}^{n}\frac{1}{k}}
\]}
\[
\cor{\Var(X)=n^2\sum_{k=1}^{n}\frac{1}{k^2}-n\sum_{k=1}^{n}\frac{1}{k}\approx n^2\frac{\pi^2}{6}-n\ln n-0,5772\cdot n-\frac{1}{2},}
\]
pois $\lim_{n\to\infty}\sum_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}$.

}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Problema do Colecionador de Cupons/Figurinhas}

\alert{Álbum com $n$ diferentes tipos de figurinhas. Cada figurinha comprada tem probabilidade igual para ser de qualquer tipo. Determinar esperança e variância do número $X$ de figurinhas compradas para encher o álbum.}\\
\vspace{0.1cm}
{\footnotesize
\[
\cor{\EE(X)=\sum_{i=0}^{n-1} \EE(X_i)\ =\ \sum_{i=0}^{n-1}\frac{n}{n-i}=n\cdot\sum_{k=1}^{n}\frac{1}{k}\ \ \approx\ \ n\ln n\ +\ 0,5772\cdot n\ +\ \frac{1}{2}.}
\]
\[
\cor{\Var(X)=n^2\sum_{k=1}^{n}\frac{1}{k^2}-n\sum_{k=1}^{n}\frac{1}{k}\ \ \approx\ \ n^2\cdot\frac{\pi^2}{6}-n\cdot\ln n-0,5772\cdot n-\frac{1}{2}.}
\]}
{\bf Exemplo:} Álbum da copa: $n=680$ figurinhas.\\
\alert{$\EE(X)=4828.03\approx 4828.02$,\esp{10}$\sigma(X)=\sqrt{\Var(X)}=869.0\approx 869.4$.}
\vspace{0.7cm}

{\scriptsize{\bf Exercício:} \cor{(a)} Implementar simulação do problema do colecionador de figurinhas para $n=680$, repetir 5000 vezes obtendo o número de figurinhas compradas até preencher o álbum, calcular média e desvio padrão. \cor{(b)} Fazer o mesmo considerando a venda em pacotes de 5 figurinhas diferentes entre si. \cor{(c)} Fazer gráficos das distribuições dos itens (a) e (b) obtidas nas simulações.}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Problema do Colecionador de Cupons/Figurinhas - 2}

\alert{\footnotesize Álbum com $n$ diferentes tipos de figurinhas. Comprando $k$ figurinhas com álbum vazio, determinar esperança e variância do número de figurinhas no álbum.}\\
\vspace{0.1cm}
Seja v.a. $X=\sum_{i=1}^n X_i$ esse número, onde $X_i=1$, se a figurinha $i$ foi comprada, e 0 c.c.\\
\vspace{0.2cm}

\cor{$\PP(X_i=0)=\left(1-\frac{1}{n}\right)^k$\esp{10}e\esp{10}$\PP(X_i=1)=1-\left(\frac{n-1}{n}\right)^k$}\\
\vspace{0.2cm}

$X_i\sim Bernoulli\left(1-\left(\frac{n-1}{n}\right)^k\right)$\esp{20}\alert{\scriptsize(não independentes entre si)}\\

\cor{$\EE(X_i)=1-\left(\frac{n-1}{n}\right)^k$\esp{10}e\esp{10}$\Var(X_i)=\left(\frac{n-1}{n}\right)^k\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)$}\\
\vspace{0.2cm}

\cor{$\EE(X)=n\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)$}.\esp{10}Exemplo: $n=k=680\ \Rightarrow\ \EE(X)=430$\\
\vspace{0.5cm}

\alert{Para $k=c\cdot n$, temos:} \cor{$\EE(X)=n\cdot\left(1-\left(1-\frac{1}{n}\right)^{n\cdot c}\right)\approx n\cdot\left(1-\frac{1}{e^c}\right)$},\\
pois $lim_{n\to\infty}(1+\frac{\alpha}{n})^n=e^\alpha$.\esp{8.5}Exemplo: $n=k=680\ \Rightarrow\ \EE(X)=430$\\
\vspace{0.5cm}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Problema do Colecionador de Cupons/Figurinhas - 2}

\alert{\footnotesize Álbum com $n$ diferentes tipos de figurinhas. Comprando $k$ figurinhas com álbum vazio, determinar esperança e variância do número de figurinhas no álbum.}\\
\vspace{0.1cm}
{\footnotesize v.a. $X=\sum_{i=1}^n X_i$ esse número, onde $X_i=1$, se a figurinha $i$ foi comprada, e 0 c.c.}\\
\vspace{0.2cm}

\cor{$\PP(X_i=0)=\left(1-\frac{1}{n}\right)^k$\esp{10}$X_i\sim Bernoulli\left(1-\left(\frac{n-1}{n}\right)^k\right)$}\\
\vspace{0.2cm}
\cor{$\EE(X)=n\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)$}.\esp{10}Exemplo: $n=k=680\ \Rightarrow\ \EE(X)=430$\\
\vspace{0.5cm}

{%\small
\[
\Var(X)\ =\ \Var\left(\sum_{i=1}^{n}X_i\right)\ =\ \sum_{i=1}^{n} \Var(X_i)+2\sum_{i=1}^{n-1}\sum_{j=i+1}^n \Cov(X_i,X_j)
\]}

{\footnotesize
$\Cov(X_i,X_j)=\EE(X_iX_j)-\EE(X_i)\EE(X_j)$.\esp{10}$\EE(X_iX_j)=\PP(X_iX_j=1)=\PP(A_i\cap A_j)$\\
$\PP(A_i\cap A_j)=1-\PP(\overline{A_i\cap A_j})=1-\PP(\overline{A_i}\cup\overline{A_j})=1-\PP(\overline{A_i})-\PP(\overline{A_j})+\PP(\overline{A_i}\cap\overline{A_j})$}\\
\cor{$\EE(X_iX_j)=1-2\left(\frac{n-1}{n}\right)^k+\left(\frac{n-2}{n}\right)^k$}\\
\[
\Cov(X_i,X_j)=\left(\frac{n-2}{n}\right)^k-\left(\frac{n-1}{n}\right)^{2k}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Problema do Colecionador de Cupons/Figurinhas - 2}

{\footnotesize
\alert{Álbum com $n$ diferentes tipos de figurinhas. Comprando $k$ figurinhas com álbum vazio, determinar esperança e variância do número de figurinhas no álbum.}\\
\vspace{0.1cm}
Seja v.a. $X=\sum_{i=1}^n X_i$ o número, onde $X_i=1$, se a figurinha $i$ foi comprada, e 0 c.c.\\
\vspace{0.0cm}

\cor{$\PP(X_i=0)=\left(1-\frac{1}{n}\right)^k$\esp{10}e\esp{10}$\PP(X_i=1)=1-\left(\frac{n-1}{n}\right)^k$}\\
\vspace{0.0cm}

$X_i\sim Bernoulli\left(1-\left(\frac{n-1}{n}\right)^k\right)$\esp{20}\alert{\scriptsize(não independentes entre si)}}\\

\cor{$\EE(X_i)=1-\left(\frac{n-1}{n}\right)^k$\esp{10}e\esp{10}$\Var(X_i)=\left(\frac{n-1}{n}\right)^k\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)$}\\
\vspace{0.0cm}

\cor{$\EE(X)=n\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)$}.\esp{10}Exemplo: $n=k=680\ \Rightarrow\ \EE(X)=430$\\
\vspace{0.2cm}

{\small
\[
\Var(X)\ =\ \Var\left(\sum_{i=1}^{n}X_i\right)\ =\ \sum_{i=1}^{n} \Var(X_i)+2\sum_{i=1}^{n-1}\sum_{j=i+1}^n \Cov(X_i,X_j)
\]}

{\footnotesize
\[
\Cov(X_i,X_j)=\left(\frac{n-2}{n}\right)^k-\left(\frac{n-1}{n}\right)^{2k}
\]
\[
\Var(X)=n\left(\frac{n-1}{n}\right)^k\left(1-\left(\frac{n-1}{n}\right)^k\right)+n(n-1)\left(\left(\frac{n-2}{n}\right)^k-\left(\frac{n-1}{n}\right)^{2k}\right)
\]
\[
\cor{\Var(X)\ =\ n\left(\frac{n-1}{n}\right)^k\ +\ n(n-1)\left(\frac{n-2}
{n}\right)^k\ -\ n^2\left(\frac{n-1}{n}\right)^{2k}}
\]
}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Problema do Colecionador de Cupons/Figurinhas - 2}

{\footnotesize
\alert{Álbum com $n$ diferentes tipos de figurinhas. Comprando $k$ figurinhas com álbum vazio, determinar esperança e variância do número de figurinhas no álbum.}\\
\vspace{0.1cm}
Seja v.a. $X=\sum_{i=1}^n X_i$ o número, onde $X_i=1$, se a figurinha $i$ foi comprada, e 0 c.c.\\
\vspace{0.0cm}

\cor{$\PP(X_i=0)=\left(1-\frac{1}{n}\right)^k$\esp{10}e\esp{10}$\PP(X_i=1)=1-\left(\frac{n-1}{n}\right)^k$}\\
\vspace{0.0cm}

$X_i\sim Bernoulli\left(1-\left(\frac{n-1}{n}\right)^k\right)$\esp{20}\alert{\scriptsize(não independentes entre si)}}\\

\cor{$\EE(X_i)=1-\left(\frac{n-1}{n}\right)^k$\esp{10}e\esp{10}$\Var(X_i)=\left(\frac{n-1}{n}\right)^k\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)$}
\[
\cor{\EE(X)=n\cdot\left(1-\left(\frac{n-1}{n}\right)^k\right)\ \approx\ n\cdot\left(1-\frac{1}{e}\right)}\esp{7}{\footnotesize\mbox{(para $k=n$ grande)}}.
\]
{\small
\[
\cor{\Var(X) = n\left(\frac{n-1}{n}\right)^k + n(n-1)\left(\frac{n-2}
{n}\right)^k - n^2\left(\frac{n-1}{n}\right)^{2k}\ \approx\ n\cdot\left(\frac{1}{e}-\frac{2}{e^2}\right)}
\]
Exemplo: $n=k=680:\ \EE(X)=430,\ \Var(X)=66.1,\ \sigma(X)=\sqrt{66.1}=8.13$
}\vspace{0.6cm}

{\scriptsize{\bf Exercício:} \cor{(a)} Implementar simulação do problema do colecionador de figurinhas-2 para $n=k=680$, repetir 5000 vezes obtendo o número de figurinhas novas no álbum, calcular média e desvio padrão. \cor{(b)} Fazer o mesmo considerando a venda em pacotes de 5 figurinhas diferentes entre si. \cor{(c)} Fazer gráficos das distribuições dos itens (a) e (b) obtidas nas simulações.}
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: HiperGeométrica$(N,K,n)$}

\alert{$X\sim HiperGeom(N,K,n)$:} {\bf Número de sucessos em $n$ retiradas\\(sem reposição) de uma população de tamanho $N$ com $K$ sucessos.}\\
\vspace{0.1cm}
{\footnotesize
\[
\cor{\PP(X=k)\ =\ \frac{\binom{K}{k}\cdot\binom{N-K}{n-k}}{\binom{N}{n}}.}\esp{10}\sum_{k=0}^K\PP(X=k)=\sum_{k=0}^K \frac{\binom{K}{k}\cdot\binom{N-K}{n-k}}{\binom{N}{n}}=1\ \ \mbox{(Vandermonde)}
\]
\[
\cor{\EE(X)=\sum_{k=0}^K k\cdot\PP(X=k)}=\frac{n K}{N}\sum_{k=1}^K \frac{\binom{K-1}{k-1}\binom{N-K}{n-k}}{\binom{N-1}{n-1}}=\frac{n K}{N}\sum_{\ell=0}^{K-1} \frac{\binom{K-1}{\ell}\binom{N-1-(K-1)}{n-1-\ell}}{\binom{N-1}{n-1}}\cor{=\frac{n K}{N}}
\]
\vspace{0.5cm}
\[
\EE(X^2)=\sum_{k=0}^K k^2\cdot\PP(X=k)=\mbox{... contas ...}=\frac{nK(n-1)(K-1)}{N(N-1)}+\frac{nK}{N}
\]
\[
\alert{\Var(X)=\EE(X^2)-\EE^2(X)}=\frac{nK(n-1)(K-1)}{N(N-1)}+\frac{nK}{N}-\left(\frac{nK}{N}\right)^2\ \alert{=\ \frac{nK(N-K)}{N^2}\cdot\left(\frac{N-n}{N-1}\right)}
\]}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: Poisson$(\lambda)$}

\alert{$X\sim Poisson(\lambda)$:} {\bf Aproximação útil p/ $Binomial(n,p)$ quando $\lambda=np$ tende a uma constante para $n$ muito grande (e $p$ muito pequeno).}\\
Também mede número de sucessos. Exemplo: Número de meteoritos com mais de 1m de diâmetro que atingem a Terra por ano.

\vspace{0.1cm}
{\footnotesize
\[
\cor{\PP(X=k)\ =\ \frac{e^{-\lambda}\cdot\lambda^k}{k!}.}\esp{10}\sum_{k=0}^\infty\PP(X=k)=\sum_{k=0}^K \frac{e^{-\lambda}\lambda^k}{k!}=1\ \ \mbox{(Taylor p/ exp)}
\]
\[
\cor{\EE(X)=\sum_{k=0}^\infty k\cdot\PP(X=k)}=\lambda\cdot\sum_{k=1}^\infty \frac{e^{-\lambda}\cdot\lambda^{k-1}}{(k-1)!}=\lambda\cdot\sum_{\ell=0}^\infty \frac{e^{-\lambda}\cdot\lambda^{\ell}}{\ell!}\ \cor{=\ \lambda}
\]
\vspace{0.4cm}
\[
\EE(X^2)=\sum_{k=0}^\infty k^2\cdot\PP(X=k)=\lambda\cdot\sum_{k=1}^\infty k\frac{e^{-\lambda}\cdot\lambda^{k-1}}{(k-1)!}=\mbox{...contas...}=\lambda^2+\lambda
\]
\[
\alert{\Var(X)=\EE(X^2)-\EE^2(X)}=(\lambda^2+\lambda)-\lambda^2\ \alert{=\ \lambda}
\]}

\vspace{0.2cm}
{\bf Aproximação:} Considere $n\to\infty$, $p\to 0$ e $np\to\lambda$ constante.
{\footnotesize
\[
\PP(Bin(n,p)=k)\ =\ \binom{n}{k}p^k(1-p)^{n-k}\ =\ \frac{n!}{k!(n-k)!}p^k(1-p)^{n-k}\ \to\ \frac{n^k}{k!}\cdot p^k(1-p)^n
\]
\[
\cor{\PP(Bin(n,p)=k)\ \to\ \frac{\lambda^k}{k!}\left(1-\frac{\lambda}{n}\right)^n}\ \to\ \alert{\frac{e^{-\lambda}\cdot\lambda^k}{k!}\ =\ \PP(Poisson(\lambda)=k)}
\]}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
%\frametitle{Aproximação: Binomial$(n,p)$ p/ Poisson$(\lambda)$}
\frametitle{Paradigma de Poisson}

\cor{\small Poisson é aproximação útil para Binomial mesmo se experimentos de Bernoulli têm probabilidades diferentes $p_i$ (mas pequenas) e são fracamente dependentes.\\
Nesse caso, $\lambda=\sum_{i=1}^n p_i$.}
\vspace{0.4cm}

\alert{\bf Exemplo:} Menor $n$ para que seja mais provável encontrar 2 pessoas com mesmo aniversário do que o contrário.
\vspace{0.4cm}

{\bf Solução 1:} Probabilidade de todos diferentes: $\prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right)\leq\frac{1}{2}\ \Rightarrow\ n\geq 23$.
\vspace{0.4cm}

{\bf Solução 2:} Poisson: v.a. $X_{i,j}=1$ se pessoas $i$ e $j$ tem mesmo aniversário. $X_{i,j}$ são fracamente dependentes. São $\binom{n}{2}$ experimentos de Bernoulli com probabilidade $\frac{1}{365}$. {\bf Assim:} \cor{$\lambda=\binom{n}{2}\cdot\frac{1}{365}$.}
\vspace{0.4cm}
{\small
\[
  \PP\left(\sum X_{i,j}=0\right) \approx \PP(Poisson(\lambda)=0) = \frac{e^{-\lambda}\cdot\lambda^0}{0!} \leq \frac{1}{2} \Rightarrow n(n-1)\geq 730\ln 2=506
\]}
Portanto $n\geq 23$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
%\frametitle{Aproximação: Binomial$(n,p)$ p/ Poisson$(\lambda)$}
\frametitle{Paradigma de Poisson}
{\tiny
\cor{Poisson é aproximação útil para Binomial mesmo se experimentos de Bernoulli têm probabilidades diferentes $p_i$ (mas pequenas) e são fracamente dependentes.
Nesse caso, $\lambda=\sum_{i=1}^n p_i$.}
\vspace{0.4cm}

\alert{\bf Exemplo:} Menor $n$ para que seja mais provável encontrar 2 pessoas com mesmo aniversário do que o contrário.
\vspace{0.4cm}

{\bf Solução 1:} Probabilidade de todos diferentes: $\prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right)\leq\frac{1}{2}\ \Rightarrow\ n\geq 23$.
\vspace{0.4cm}

{\bf Solução 2:} Poisson: v.a. $X_{i,j}=1$ se pessoas $i$ e $j$ tem mesmo aniversário. $X_{i,j}$ são fracamente dependentes. São $\binom{n}{2}$ experimentos de Bernoulli com probabilidade $\frac{1}{365}$. {\bf Assim:} \cor{$\lambda=\binom{n}{2}\cdot\frac{1}{365}$.}
{
\[
  \PP\left(\sum X_{i,j}=0\right) \approx \PP(Poisson(\lambda)=0) = \frac{e^{-\lambda}\cdot\lambda^0}{0!} \leq \frac{1}{2} \Rightarrow n(n-1)\geq 730\ln 2=506
\]}
Portanto $n\geq 23$.}

\begin{figure}\centering
\includegraphics[scale=0.39]{poisson1.png}
\end{figure}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Discretas: Uniforme$\{a,b\}$}

\alert{$X\sim Unif\{a,b\}$ p/ $a,b\in\ZZ$:} {\bf $X$ é número inteiro entre $a$ e $b$, inclusive, todos com a mesma probabilidade $\PP(X=k)=\frac{1}{b-a+1}$.}\\
\vspace{0.1cm}
\[
\cor{\EE(X)} = \sum_{k=a}^b k\cdot\PP(X=k)\ =\ \frac{(b+a)(b-a+1)}{2(b-a+1)}\ =\ \frac{b+a}{2}
\]
\vspace{0.1cm}
\[
\cor{\EE(X^2)} = \sum_{k=a}^b k^2\cdot\PP(X=k)\ =\ \frac{b(b+1)(2b+1)}{6(b-a+1)}-\frac{(a-1)a(2a-1)}{6(b-a+1)}
\]
\vspace{0.1cm}
\[
\cor{\Var(X)} = \EE(X^2)-\EE^2(X)\ =\ \ldots\ =\ \frac{(b-a)(b-a+2)}{12}
\]
\vspace{0.1cm}
\[
\cor{\sigma(X)} = \sqrt{\Var(X)}\ \approx\ \frac{(b-a)}{2\sqrt{3}},\esp{10}\mbox{para $b-a$ muito grande.}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Contínuas: Uniforme$[a,b]$}

\alert{$X\sim Unif[a,b]$ p/ $a,b\in\RR$:} {\bf $X$ é número real entre $a$ e $b$, inclusive, todos com a mesma probabilidade.}\\
\vspace{0.1cm}
Função densidade de prob $f(x)=\frac{1}{b-a}$ se $a\leq x\leq b$; $f(x)=0$, cc.\\
\vspace{0.1cm}
\[
\cor{\EE(X)} = \int_{a}^b f(x)\cdot x dx\ =\ \frac{x^2}{2(b-a)}\Big\vert_a^b\ =\ \frac{b^2-a^2}{2(b-a)}\ =\ \frac{b+a}{2}
\]
\vspace{0.1cm}
\[
\cor{\EE(X^2)} = \int_{a}^b f(x)\cdot x^2 dx\ =\ \frac{x^3}{3(b-a)}\Big\vert_a^b\ =\ \frac{b^3-a^3}{3(b-a)}\ =\ \frac{b^2+ab+a^2}{3}
\]
\vspace{0.1cm}
\[
\cor{\Var(X)} = \EE(X^2)-\EE^2(X)\ =\ \frac{b^2+ab+a^2}{3}-\left(\frac{b+a}{2}\right)^2\ =\ \frac{(b-a)^2}{12}
\]
\vspace{0.1cm}
\[
\cor{\sigma(X)} = \sqrt{\Var(X)}\ =\ \frac{(b-a)}{2\sqrt{3}}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuições Contínuas: Normal$(\mu,\sigma^2)$}

\alert{$X\sim Normal(\mu,\sigma^2)$:} {\bf $X$ é v.a. real com média $\mu$ e variância $\sigma^2$}\\
\vspace{0.1cm}
Função densidade de prob $f(x)=\frac{1}{\sigma\sqrt{2\pi}}\cdot\exp\left\{-\frac{(x-\mu)^2}{2\sigma^2}\right\}$.\\
\vspace{0.1cm}
\[
\cor{\EE(X)} = \int_{a}^b f(x)\cdot x dx\ =\ \ldots\ =\ \mu
\]
\vspace{0.1cm}
\[
\cor{\EE(X^2)} = \int_{a}^b f(x)\cdot x^2 dx\ =\ \ldots\ =\ \sigma^2+\mu^2
\]
\vspace{0.1cm}
\[
\cor{\Var(X)} = \EE(X^2)-\EE^2(X)\ =\ \sigma^2.\esp{20}\cor{\sigma(X)} = \sqrt{\Var(X)}\ =\ \sigma
\]
\begin{figure}\centering
\includegraphics[scale=0.25]{gauss1.png}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Distribuição Binomial tende a Normal para $n\to\infty$}
Seja \alert{$X\sim Binomial(n,p)$}. Por Stirling: $n!\approx n^n\cdot e^{-n}\cdot\sqrt{2\pi n}$:
\[
\alert{\PP(X=k)} = \binom{n}{k}p^k(1-p)^{n-k} \approx \frac{n^n e^{-n}\sqrt{2\pi n}\cdot p^k(1-p)^{n-k}}{k^k e^{-k}\sqrt{2\pi k}\cdot (n-k)^{n-k} e^{-(n-k)}\sqrt{2\pi(n-k)}}
\]
\[
=\left(\frac{np}{k}\right)^k\left(\frac{n(1-p)}{n-k}\right)^{n-k}\sqrt{\frac{n}{2\pi k(n-k)}}\ =\ \ldots\ =
\]
\[
=\frac{1}{\sqrt{2\pi np(1-p)}}\cdot\exp\left\{-\frac{(k-np)^2}{2np(1-p)}\right\}\ =\ \cor{\PP\Big(Normal(np,np(1-p))\ =\ k\Big)}
\]
\begin{figure}\centering
\includegraphics[scale=0.2]{gauss2.png}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Geração de v.a. Uniforme$(0,1)$ no computador}

\alert{Alerta 1:} computador não gera números reais. Aproximação razoável usando 64 bits: divide o intervalo $[0,1]$ em $2^{64}$ subintervalos.

\vspace{0.3cm}
\alert{Alerta 2:} computador é determinístico. Aproximação razoável: simular comportamento probabilístico com gerador pseudo-aleatório. Os melhores geradores passam em testes estatísticos para medir a independência das amostras geradas e sua aleatoriedade.

\vspace{0.3cm}
\alert{\bf Suposição:} Temos algoritmo $\cor{randUni}$ que gera uma v.a. \cor{Uniforme$(0,1)$}.

\vspace{0.5cm}
$X\sim Bernoulli(p)$: Se ($\cor{randUni}<p$), $X=1$; caso contrário, $X=0$.

\vspace{0.5cm}
$X\sim Uniforme\{a,b\}$: $X=a+\lfloor\cor{randUni}\cdot(b-a+1)\rfloor$.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Geração de v.a. $X\sim Geometrica(p)$ no computador}

\cor{\bf Algoritmo 1:} Gera v.a.'s $Bernoulli(p)$ até obter um sucesso (1).

\vspace{0.2cm}
\cor{\bf Algoritmo 2:} Gera $Uniforme(0,1)$ e aplica a inversa da função de probabilidade acumulada.

\begin{figure}\centering
\includegraphics[scale=0.6]{geometric1.png}
\end{figure}
\[
F(k)=\PP(X\leq k)=1-(1-p)^k\ =\ u\ \Rightarrow\ F^{-1}(u)=k=\left\lceil\frac{\log(1-u)}{\log(1-p)}\right\rceil.
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Geração de v.a. $X\sim Binomial(n,p)$ no computador}

\alert{Geração de v.a. $X\sim Binomial(n,p)$:}

\vspace{0.3cm}
\cor{\bf Algoritmo 1:} Gera $n$ v.a.'s $Bernoulli(p)$ e conta o número de sucessos.

\vspace{0.4cm}
\cor{\bf Algoritmo 2:} Gera v.a.'s $Geometrica(p)$ até sua soma ultrapassar $n$ e retorna o número de v.a.'s menos 1. Número esperado de geométricas geradas: $n\cdot p$.

\vspace{0.2cm}
{\bf Exemplo:} $n=10$, $p=0.5$. $Geometrica(p)$ geradas: \cor{2,3,1,2},4. $Binomial(n,p)$ gerada = 4.

\vspace{1.2cm}
\alert{Geração de v.a. $X\sim BinomialNegativa(k,p)$:}

\vspace{0.3cm}
\cor{\bf Algoritmo 1:} Gera $k$ v.a.'s $Geometrica(p)$ e soma seus valores.

}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Geração de Permutação aleatória no computador}

\cor{\bf Algoritmo 1:} Gera $n$ v.a.'s $Uniforme(0,1)$, ordena seus valores e substitui os valores pela sua posição no vetor ordenado. Tempo $O(n \log n)$.

\vspace{0.3cm}
{\bf Exemplo:} $[0.6, 0.2, 0.7, 0.4, 0.3]$. Permutação = (4,1,5,3,2).

\vspace{1.0cm}
\cor{\bf Algoritmo 2:} Fisher-Yates Shuffle. Tempo $O(n)$

\vspace{0.4cm}
\cor{Algoritmo Fisher-Yates-Shuffle (inteiro $n$)}
\begin{itemize}
\item[1]\ Cria vetor $perm[1,\ldots,n]$
\item[2]\ \textbf{para} $k\leftarrow 1$ \textbf{até} $n$ \textbf{faça}
\item[3]\ \esp{8}$perm[k]\ \leftarrow\ k$
\item[4]\ \textbf{para} $k\leftarrow 1$ \textbf{até} $n$ \textbf{faça}
\item[5]\ \esp{8}$\ell\ \leftarrow\ Uniforme\{k,n\}$
\item[6]\ \esp{8}Trocar $perm[k]\ \leftrightarrow\ perm[\ell]$
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de Chernoff (p/ v.a. Binomiais)}

\cor{{\bf Chernoff:} $n$ v.a.'s {\bf independentes} $X_1,\ldots,X_n\sim Bernouli(p)$\\
Seja\ \ \ $X=\sum_{i=1}^n X_i\sim Binomial(n,p)$\ \ \ e\ \ \ $\EE(X)=\sum_{i=1}^n \EE(X_i)=np$:}
\[
\PP\left(X>\EE(X)+t\cdot n\right)\ \leq\ \exp\left\{-2t^2\cdot n\right\}
\]
\[
\PP\left(X<\EE(X)-t\cdot n\right)\ \leq\ \exp\left\{-2t^2\cdot n\right\}
\]

\vspace{0.5cm}
\alert{Juntando os dois bounds em um só:}
\vspace{0.2cm}

{\normalsize
\[
\cor{\PP\left(|X-\EE(X)|\geq t\cdot n\right)\leq\ 2\cdot\exp\left\{-2t^2\cdot n\right\}}
\]
\[
\cor{\PP\left(|X-\EE(X)|\geq\alpha\right)\leq\ 2\cdot\exp\left\{\frac{-2\alpha^2}{n}\right\}}
\]
\[
\cor{\PP\left(|X-\EE(X)|\geq t\cdot\sqrt{n}\right)\ \leq\ 2\cdot\exp\left\{-2t^2\right\}}.\esp{3}
\]}
\esp{70}$\alert{t=3\Rightarrow prob\approx 3\cdot 10^{-8}}$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de Chernoff-Hoeffding (generalização)}

\cor{{\bf Chernoff:} $n$ v.a.'s {\bf independentes} $X_i\in[0,1]$ com média $\mu_i$\\
As v.a.'s não precisam ser Bernoulli, nem ter a mesma distribuição.\\
Seja\ \ \ $X=\sum_{i=1}^n X_i$\ \ \ e\ \ \ $\EE(X)=\sum_{i=1}^n \EE(X_i)=n\cdot\mu$,
onde $\mu=(\mu_1+\ldots+\mu_n)/n$}
\[
\PP\left(X>\EE(X)+t\cdot n\right)\ \leq\ \exp\left\{-2t^2\cdot n\right\}
\]
\[
\PP\left(X<\EE(X)-t\cdot n\right)\ \leq\ \exp\left\{-2t^2\cdot n\right\}
\]

\vspace{0.5cm}
\alert{Juntando os dois bounds em um só:}
\vspace{0.2cm}

{\normalsize
\[
\cor{\PP\left(|X-\EE(X)|\geq t\cdot n\right)\leq\ 2\cdot\exp\left\{-2t^2\cdot n\right\}}
\]
\[
\cor{\PP\left(|X-\EE(X)|\geq\alpha\right)\leq\ 2\cdot\exp\left\{\frac{-2\alpha^2}{n}\right\}}
\]
\[
\cor{\PP\left(|X-\EE(X)|\geq t\cdot\sqrt{n}\right)\ \leq\ 2\cdot\exp\left\{-2t^2\right\}}.\esp{3}
\]}
\esp{70}$\alert{t=3\Rightarrow prob\approx 3\cdot 10^{-8}}$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de Chernoff-Hoeffding (generalização)}

\cor{{\bf Chernoff:} $n$ v.a.'s {\bf independentes} $X_i\in[a_i,b_i]$ com média $\mu_i$\\
As v.a.'s não precisam ser Bernoulli, nem ter a mesma distribuição.\\
Seja\ \ \ $X=\sum_{i=1}^n X_i$\ \ \ e\ \ \ $\EE(X)=\sum_{i=1}^n \EE(X_i)=n\cdot\mu$,
onde $\mu=(\mu_1+\ldots+\mu_n)/n$}
\[
\PP\left(X>\EE(X)+t\cdot n\right)\ \leq\ \exp\left\{\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \cdot n^2\right\}
\]
\[
\PP\left(X<\EE(X)-t\cdot n\right)\ \leq\ \exp\left\{\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \cdot n^2\right\}
\]

\vspace{0.1cm}
\alert{Juntando os dois bounds em um só:}
\vspace{0.1cm}

{\footnotesize
\[
\cor{\PP\left(|X-\EE(X)|\geq t\cdot n\right)\leq\ 2\cdot\exp\left\{\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \cdot n^2\right\}}
\]
\[
\cor{\PP\left(|X-\EE(X)|\geq\alpha\right)\leq\ 2\cdot\exp\left\{\frac{-2\alpha^2}{\sum_{i=1}^n(b_i-a_i)^2}\right\}}
\]
\[
\cor{\PP\left(|X-\EE(X)|\geq t\cdot\sqrt{n}\right)\ \leq\ 2\cdot\exp\left\{\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \cdot n\right\}}
\]}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de Chernoff-Hoeffding (comparação)}

\cor{{\bf Aplicação:} $n$ moedas não-viciadas lançadas. Seja $X$ o número de caras.}\\
$X\sim Binomial(n,\frac{1}{2})$,\ \ \cor{$\EE(X)=n/2$}\ \ e\ \ $\Var(X)=n\cdot\frac{1}{2}(1-\frac{1}{2})=n/4$.\\

\vspace{0.5cm}
Markov: \esp{4.5}$\PP(X\geq 3n/4)\leq\frac{\EE(X)}{3n/4}=\frac{n/2}{3n/4}=\frac{2}{3}$ \alert{\bf(ruim)}\\

\vspace{0.2cm}
Chebyshev: $\PP(X\geq 1.5\frac{n}{2})\leq\PP(|X-\EE(X)|\geq 0.5\frac{n}{2})\leq\frac{\Var(X)}{(n/4)^2}=\frac{4}{n}$. \cor{\bf(bom)}\\

\vspace{0.2cm}
{\small
Chebyshev:\esp{3}$\PP(X\geq 1.01\frac{n}{2})\leq\PP(|X-\EE(X)|\geq 0.01\frac{n}{2})\leq\frac{\Var(X)}{(0.01\cdot n/2)^2}=\frac{10000}{n}$.}

\vspace{0.2cm}
{\small
Chebyshev:\\\esp{3}$\PP(|X-\EE(X)|\geq t\sqrt{n})\leq\frac{\Var(X)}{(t\sqrt{n})^2}=\frac{1}{4\ t^2}$. \alert{\bf(razoável)}}

\vspace{0.4cm}
{\small
\cor{\bf Chernoff:}\\\esp{3}$\PP(|X-\EE(X)|\geq \frac{1}{4}\cdot n)\leq 2e^{-2\cdot(1/4)^2\cdot n}\ =\ 2e^{-n/8}$. \cor{\bf(excelente)}}

\vspace{0.2cm}
{\small
\cor{\bf Chernoff:}\\\esp{3}$\PP(|X-\EE(X)|\geq \frac{0.01}{2}\cdot n)\leq 2e^{-2 (0.01/2)^2\cdot n}\ =\ 2e^{-n/20000}$. \cor{\bf(excelente)}}

\vspace{0.2cm}
{\small
\cor{\bf Chernoff:}\\\esp{3}$\PP(|X-\EE(X)|\geq t\sqrt{n})\leq 2e^{-2 t^2}$. \cor{\bf(excelente)}}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de Chernoff-Hoeffding (comparação)}

\begin{figure}\centering
\includegraphics[scale=0.5]{chernoff01.png}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Chernoff: subgrafo bipartido grande}

\cor{{\bf Problema:} Dado um grafo com $n$ vértices e $m$ arestas, obter subgrafo bipartido com muitas arestas, próximo da metade $m/2$.}
\vspace{0.5cm}

{\footnotesize
\alert{\bf Algoritmo Probabilístico:} Seja $A$ inicialmente vazio. Para cada vértice de $G$, coloque-o em $A$ com probabilidade 1/2. Seja $B=V-A$. Remova todas as arestas entre vértices de $A$ e remova todas as arestas entre vértices de $B$. O subgrafo resultante é bipartido com número esperado de arestas igual a $m/2$.}
\vspace{0.4cm}

\cor{$X=\sum_{uv\in E}X_{uv}$ é v.a. $X\sim Binomial(m,\frac{1}{2})\ \ \ \ \Rightarrow\ \ \ \ \Var(X)=\frac{m}{4}$}\\

\vspace{0.3cm}
{\bf Chebyshev:} $\PP(X\leq 0.9\frac{m}{2})\leq\PP(|X-\EE(X)|\geq 0.1\frac{m}{2})\leq\frac{\Var(X)}{(0.1\cdot m/2)^2}=\frac{100}{m}$.

\vspace{0.3cm}
{\bf Chernoff:} $\PP(X\leq 0.9\frac{m}{2})\leq\PP(X\leq \EE(X)-0.1\frac{m}{2})\leq e^{-2\cdot (0.1/2)^2m}=e^{-m/200}$.

\vspace{0.7cm}
Exemplo: $m=1000$: Chebyshev 10\%. Chernoff $< 0.7\%$\\
Exemplo: $m=10000$: Chebyshev 1\%. Chernoff $< 10^{-20}$
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Chernoff: Amplificação para Classe BPP}

{\footnotesize
\alert{\bf Teorema:} As seguintes afirmações são equivalentes, onde $n$ é tam. da instância de $\Pi$:
\begin{itemize}
\item[(1)] O Problema $\Pi$ está em BPP (erro $\leq\frac{1}{3}$ \cor{\emph{two sided error}})
\item[(2)] Existe um polinômio $q(n)$ tal que $\Pi$ possui um algoritmo probabilístico polinomial com erro no máximo $\frac{1}{2}-\frac{1}{q(n)}$ (\cor{\emph{two sided error}})
\item[(3)] Para todo polinômio $p(n)>1$, $\Pi$ possui um algoritmo probabilístico polinomial com erro no máximo $2^{-p(n)}$ (\cor{\emph{two sided error}})
\end{itemize}

\vspace{0.4cm}
\alert{Proof:} Claramente (3)$\Rightarrow$(1)$\Rightarrow$(2). Vamos provar que (2)$\Rightarrow$(3).

\vspace{0.2cm}
Seja $M$ um algoritmo com erro $\leq\frac{1}{2}-\frac{1}{q(n)}$ que retorna SIM/NÃO. Seja $M'$ um algoritmo que repete $t(n)$ vezes o algoritmo $M$ sobre a mesma instância e retorna o valor SIM/NÃO que mais ocorre (majoritário), onde $t(n)$ será definido depois.

\vspace{0.3cm}
Seja $X_i$ a v.a. indicadora que retorna 1 se a $i$-ésima execução de $M$ retornou a resposta correta. Seja $X=\sum X_i$. Logo $\EE(X)\geq t(\frac{1}{2}+\frac{1}{q})$. Usando Chernoff:
\[
\PP(X\leq t/2)\ \leq\ \PP(X\leq\EE(X)-t/q)\ \leq\ \exp\left\{-\frac{2(t/q)^2}{t}\right\}\ \leq\ \exp\left\{-\frac{2t}{q^2}\right\} \leq e^{-p(n)} \leq 2^{-p(n)},
\]
para \cor{$t(n)=p(n)\cdot q^2(n)/2$}, pois $\EE(X)\leq t$.
}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de McDiarmid (Bounded Differences)}

\cor{\bf Função $c$-Lipschitz:} Função $f(x_1,\ldots,x_n)$ tal que $|f(x)-f(x')|\leq c$ se $x$ e $x'$ diferem em só uma das $n$ coordenadas.

\vspace{0.2cm}
\alert{\bf Método das Diferenças Limitadas:} \textit{generaliza Chernoff-Hoeffding.}\\
v.a. {\bf independentes} $X_1,\ldots,X_n$ e função $f(x_1,\ldots,x_n)$ $c$-Lipschitz.
\[
\PP\Big(\Big|\cor{f(X_1,\ldots,X_n)}-\EE(\cor{f(X_1,\ldots,X_n)})\Big|\ >\ t\cdot n\Big)\ \leq\ 2\cdot\exp\left\{\frac{-2t^2}{c^2}\cdot n\right\}
\]

\vspace{0.2cm}
{\bf Exemplo: Binomial.} v.a. $X_1,X_2,\ldots,X_n\sim Bernoulli(p)$ e função $f(X_1,\ldots,X_n)=\sum_{i=1}^n X_i\ \cor{=\ X}$.
\[
\PP\Big(\Big|\cor{X}-\EE(\cor{X})\Big|\ >\ t\cdot n\Big)\ \leq\ 2\cdot\exp\left\{-2t^2\cdot n\right\} \esp{5}\mbox{\alert{(McDiarmid\ $\equiv$\ Chernoff)}}
\]

\vspace{0.2cm}
{\bf Exemplo: Soma dos senos.} v.a. $X_1,X_2,\ldots,X_n$ uniformes em $[0,2\pi]$ e função $f(X_1,\ldots,X_n)=\sum_{i=1}^n sen(X_i)\ \cor{=\ X}$. Nesse caso, $c=2$.
\[
\PP\Big(\Big|\cor{X}-\EE(\cor{X})\Big|\ >\ t\cdot n\Big)\ \leq\ 2\cdot\exp\left\{-(t^2/2)\cdot n\right\} \esp{5}\mbox{\alert{(McDiarmid\ $\equiv$\ Chernoff)}}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de McDiarmid (Bounded Differences)}

\alert{\bf Método das Diferenças Limitadas:} \textit{generaliza Chernoff-Hoeffding.}\\
v.a. {\bf independentes} $X_1,\ldots,X_n$ e função $f(x_1,\ldots,x_n)$ $c$-Lipschitz.
\[
\PP\Big(\Big|\cor{f(X_1,\ldots,X_n)}-\EE(\cor{f(X_1,\ldots,X_n)})\Big|\ >\ t\cdot n\Big)\ \leq\ 2\cdot\exp\left\{\frac{-2t^2}{c^2}\cdot n\right\}
\]

\vspace{0.2cm}
{\bf Exemplo: Grafo aleatório $G\sim G(n,p)$ de Erd{\H o}s-Rényi:}\\
$n$ vértices $\{1,2,\ldots,n\}$ e
uma v.a. $X_{i,j}\sim Bernoulli(p)$ para cada par $(i,j)$ de vértices distintos.

\vspace{0.2cm}
Considerar outra sequência de v.a.: $Y_2,Y_3,\ldots,Y_n$, onde $Y_i$ representa as v.a.'s $X_{1,i},\ldots,X_{i-1,i}$. Seja $Y$ o tamanho da maior clique $\omega(G)$ (ou o número mínimo de cores $\chi(G)$).
\[
\PP\Big(\Big|\cor{Y}-\EE(\cor{Y})\Big|\ >\ t\cdot n\Big)\ \leq\ 2\cdot\exp\left\{-2t^2\cdot n\right\} \esp{5}\mbox{\alert{(McDiarmid)}}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Desigualdade de McDiarmid (generalização)}

\cor{\bf Função $(c_1,\ldots,c_n)$-Lipschitz:} Função $f(x_1,\ldots,x_n)$ tal que $|f(x)-f(x')|\leq c_i$ se $x$ e $x'$ diferem apenas na coordenada $i$.

\vspace{0.2cm}
\alert{\bf Método das Diferenças Limitadas:} \textit{generaliza Chernoff-Hoeffding.}\\
v.a. {\bf independentes} $X_1,\ldots,X_n$ e\\
função $f(x_1,\ldots,x_n)$ $(c_1,\ldots,c_n)$-Lipschitz.
\[
\PP\Big(\Big|\cor{f(X_1,\ldots,X_n)}-\EE(\cor{f(X_1,\ldots,X_n)})\Big|\ >\ t\cdot n\Big)\ \leq\ 2\cdot\exp\left\{\frac{-2t^2}{\sum_{i=1}^n c_i^2}\cdot n^2\right\}
\]

\vspace{0.7cm}
\cor{\bf Chernoff-Hoeffding (generalização):} só serve p/ somatório de v.a.'s\\
v.a.'s {\bf independentes} $X_i\in[a_i,b_i]$. 
Seja $X=\sum_{i=1}^n X_i$.
\[
\PP\left(|X-\EE(X)|>t\cdot n\right)\ \leq\ 2\cdot\exp\left\{\frac{-2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \cdot n^2\right\}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Convergência em probabilidade (w.h.p)}

Seja $A(n)$ um evento em um espaço de probabilidade, onde $n$ é um parâmetro.
Dizemos que $A(n)$ ocorre ``\emph{com alta probabilidade}'' (w.h.p) se:
$$\lim_{n\to\infty}\PP(A_n)\ =\ 1\ \ \ \ \ \ \mbox{\cor{(convergência em probabilidade)}}.$$
Por exemplo,
\[
  \PP(A(n))\ \geq\ 1-\frac{1}{n^\beta}\ \ \ \ \ \mbox{para algum $\beta>0$ constante}
\] 

\vspace{0.0cm}
\alert{\bf Exemplo:} v.a. $X$, que é a soma de $n$ variáveis 0/1 $X_i$ com prob. $1/2$ de ser 1. $\EE(X)=n/2$. Onde está concentrada a distribuição de $X$? Determinar quando $\PP(|X-\EE(X)|\geq\alpha)<1/n$ (w.h.p: probabilidade da ``cauda'' tende a 0).
\[
\PP(|X-\EE(X)|\geq\alpha)\leq 2\cdot\exp\left\{\frac{-\alpha^2}{3\EE(X)}\right\}=2\cdot\exp\left\{\frac{-2\alpha^2}{3n}\right\}<1/n
\]
Tomando \alert{$\alpha\geq 2\sqrt{n\cdot\ln n}$}\ \ e\ \ $n$ suficientemente grande, temos o desejado.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Leis dos Grandes Números}

Seja $X_1,X_2,X_3,\ldots$ uma sequência de v.a. iid (independentes e identicamente distribuídas) com média $\mu$ e variância $\sigma^2$ finitos.

A \cor{\bf Média Amostral} $M_n$ é definida como $M_n\ =\ \frac{1}{n}\cdot\sum_{i=1}^n X_i$ 
\[
\EE(M_n)\ =\ \EE\left(\frac{1}{n}\sum_{i=1}^n X_i\right)\ =\ \frac{1}{n}\sum_{i=1}^n \EE(X_i)\ =\ \frac{1}{n}\cdot n\mu\ =\ \mu
\]
\[
\Var(M_n)\ =\ \Var\left(\frac{1}{n}\sum_{i=1}^n X_i\right)\ =\ \frac{1}{n^2}\sum_{i=1}^n \Var(X_i)\ =\ \frac{1}{n^2}\cdot n\sigma^2\ =\ \frac{\sigma^2}{n}
\]
\vspace{0.0cm}
\cor{Conclusão:} A Média Amostral $M_n$ tem mesma média $\mu$ e variância que tende a 0 quanto maior for o número $n$ de ``amostras''.

\vspace{0.4cm}
\alert{Teorema Central do Limite:} $M_n$ \cor{converge em distribuição} para uma v.a. de distribuição Normal com média $\mu$ e variância $\sigma^2/n$.

\vspace{0.2cm}
\alert{Lei Fraca dos Grandes Números:} Para todo $\varepsilon>0$, $|M_n-\mu|<\varepsilon$ w.h.p. Assim, $\lim_{n\to\infty}\PP(|M_n-\mu|<\varepsilon)=1$ (\cor{convergência em probabilidade}).

\vspace{0.2cm}
\alert{Lei Forte dos Grandes Números:} $\PP(\lim_{n\to\infty}M_n\ =\ \mu)\ =\ 1$ (\cor{convergência quase certa}). $M_n$ realmente converge p/ valor esperado $\mu$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Leis dos Grandes Números}

\begin{figure}\centering
\includegraphics[scale=0.45]{binomial1.png}
\end{figure}

\vspace{0.2cm}
\cor{Conclusão:} A Média Amostral $M_n$ tem mesma média $\mu$ e variância que tende a 0 quanto maior for o número $n$ de ``amostras''.

\vspace{0.4cm}
\alert{Teorema Central do Limite:} $M_n$ \cor{converge em distribuição} para uma v.a. de distribuição Normal com média $\mu$ e variância $\sigma^2/n$.

\vspace{0.2cm}
\alert{Lei Fraca dos Grandes Números:} Para todo $\varepsilon>0$, $|M_n-\mu|<\varepsilon$ w.h.p. Assim, $\lim_{n\to\infty}\PP(|M_n-\mu|<\varepsilon)=1$ (\cor{convergência em probabilidade}).

\vspace{0.2cm}
\alert{Lei Forte dos Grandes Números:} $\PP(\lim_{n\to\infty}M_n\ =\ \mu)\ =\ 1$ (\cor{convergência quase certa}). $M_n$ realmente converge p/ valor esperado $\mu$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Margem de Erro e Confiança}

Dizemos que um experimento tem \alert{Margem de Erro $\varepsilon$} e \cor{Confiança $\beta$} se a Média Amostral $M_n$ (com valor esperado $\mu$) satisfaz:
\[
  \PP\left(M_n=\mu\pm\varepsilon\right)\ =\ \PP\left(|M_n-\mu|\leq\varepsilon\right)\ \geq\ \beta
\]

\vspace{0.3cm}
Lembrando que $\Var(M_n)=\sigma^2/n$, temos por Chebyshev que
\[
\PP(M_n=\mu\pm\varepsilon)\ \geq\ 1-\frac{\sigma^2}{\varepsilon^2 n}\ =\ \beta,
\]
tomando $$n\ =\ \frac{\sigma^2}{\varepsilon^2(1-\beta)}.$$
Diminuir a Margem de Erro (ou aumentar a precisão) tem mais impacto do que aumentar a Confiança.

\vspace{0.3cm}
\alert{Exemplo:} Testar com margem de erro 1\% e confiança 99\% se uma moeda é viciada. Seja $M_n$ a média amostral de caras.
\[
\PP(M_n\ =\ 0.5\pm 0.01)\ \geq\ 1-\frac{0.25}{0.01^2n}\ =\ 0.99;
\]
tomando $n=250.000$
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Margem de Erro e Confiança}

\alert{Exemplo:} Pesquisa com 2000 eleitores indica que certo candidato vence no 2o turno com 55\% de votos. Calcule a margem de erro para 95\% de confiança.

\vspace{0.3cm}
Considerando cada pessoa como uma v.a. $X_i\sim Bernoulli(0.55)$, temos: $\mu=0.55$ e $\sigma^2=0.55\cdot 0.45$
\[
\PP(M_n=\mu\pm\varepsilon)\ \geq\ 1-\frac{\sigma^2}{\varepsilon^2 n}\ =\ \beta,
\]
\[
\PP(M_n\ =\ 0.55\pm \varepsilon)\ \geq\ 1-\frac{0.55\cdot 0.45}{\varepsilon^2\cdot 2000}\ =\ 0.95;
\]
tomando $\varepsilon=0,0498=4,98\%$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Margem de Erro e Confiança}

\alert{Exemplo:} Calcular o valor de $\pi$ experimentalmente.

\vspace{0.3cm}
Sortear $n$ pontos unif aleatórios no quadrado $[0,1]^2$ e ver quantos caem no círculo de diâmetro 1 (com área $\pi/4$) dentro do quadrado.\\
Acertar a 4o casa decimal (margem de erro $10^{-5}$) com confiança 70\%.\\
 $\mu=\pi/4$ e $\sigma^2=\frac{\pi}{4}(1-\frac{\pi}{4})$.
\[
\PP(M_n=\mu\pm\varepsilon)\ \geq\ 1-\frac{\sigma^2}{\varepsilon^2 n}\ =\ \beta,
\]
\[
\PP\left(4\cdot M_n = \pi\pm 4\cdot 10^{-5}\right) = \PP\left(M_n = \frac{\pi}{4}\pm 10^{-5}\right)\ \geq\ 1-\frac{\pi\cdot(4-\pi)}{4^2\cdot 10^{-10}\cdot n}\ =\ 0.7;
\]
tomando $n=6\cdot 10^9$ (seis bilhões de experimentos).


%\begin{figure}\centering
%\includegraphics[scale=0.2]{pi1.png}
%\end{figure}


\begin{table}[h!]
  \centering
  \begin{tabular}{ c m{7cm}}
    \begin{minipage}{.3\textwidth}
      \includegraphics[scale=0.2]{pi1.png}
    \end{minipage}
    &
    %\begin{minipage}[t]{5cm}
      \alert{MCM (Monte Carlo Method)}
      {\footnotesize
      \begin{itemize}
        \item Algoritmos que realizam muitas amostragens aleatórias para obter soluções razoáveis de problemas difíceis.
        \item Pelas Leis dos Grandes Números, uma grande quantidade de amostras levam à solução do problema (no limite tendendo ao infinito).
      \end{itemize}}
    %\end{minipage}
  \end{tabular}
\end{table}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo para Elemento Máximo de um vetor}

\cor{Máximo (vetor $A$, inteiro $n$)}
\begin{itemize}
\item[1]\ $max\ \leftarrow\ 0$
\item[2]\ \textbf{para} $i\leftarrow 1$ \textbf{até} $n$ \textbf{faça}:
\item[3]\ \esp{8}\textbf{se} $A[i] > max$ \textbf{então}
\item[4]\ \esp{16}$max\ \leftarrow\ A[i]$
\item[5]\ \textbf{retorne} max
\end{itemize}


\vspace{0.3cm}
\alert{Pergunta:} Quantas vezes a linha 4 é executada no caso médio?

\vspace{0.3cm}
Suponha que o vetor $A$ é uma permutação aleatória uniforme de 1 a $n$. Cada permutação tem probabilidade $1/n!$

\vspace{0.3cm}
Seja $X_i=1$ se a linha 4 foi executada na iteração $i$; e 0, cc.\\
Seja $X$ o número total de execuções da linha 4: $X=\sum_{i=1}^n X_i$.

\vspace{0.2cm}
Qual a esperança $\EE(X_i)$? É a prob da linha 4 ser executada na iteração $i$.\\

\vspace{0.2cm}
\cor{Resposta: $\EE(X_i)=1/i$,} pois o elemento $A[i]$ deveria ser o maior entre os primeiros $i$ elementos $A[1\ldots i]$.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Algoritmo para Elemento Máximo de um vetor}

\cor{Máximo (vetor $A$, inteiro $n$)}
\begin{itemize}
\item[1]\ $max\ \leftarrow\ 0$
\item[2]\ \textbf{para} $i\leftarrow 1$ \textbf{até} $n$ \textbf{faça}:
\item[3]\ \esp{8}\textbf{se} $A[i] > max$ \textbf{então}
\item[4]\ \esp{16}$max\ \leftarrow\ A[i]$
\item[5]\ \textbf{retorne} max
\end{itemize}


\vspace{0.3cm}
\alert{Pergunta:} Quantas vezes a linha 4 é executada no caso médio?

\vspace{0.3cm}
Seja $X_i=1$ se a linha 4 foi executada na iteração $i$; \cor{$\EE(X_i)=1/i$}\\
Seja $X$ o número total de execuções da linha 4: $X=\sum_{i=1}^n X_i$.

\[
  \EE(X)\ =\ \EE\left(\sum_{i=1}^n X_i\right)\ =\ \sum_{i=1}^n\EE(X_i)\ =\ \sum_{i=1}^n\frac{1}{i}\ \approx\ \ln n\ +\ 0.5772\ +\ \frac{1}{2n}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio do Insertion Sort}

\begin{table}[h!]
  \centering
  \begin{tabular}{ m{7cm} c }
\cor{Insertion-Sort (vetor $A$, inteiro $n$)}
\begin{itemize}
\item[1]\ \textbf{para} $k\leftarrow 2$ \textbf{até} $n$ \textbf{faça}:
\item[2]\ \esp{8}$carta\ \leftarrow\ A[j]$;\esp{15}$i\leftarrow k-1$
\item[3]\ \esp{8}\textbf{enquanto} $i\geq 1$\ \textbf{e} $A[i]>carta$ \textbf{faça}:
\item[4]\ \esp{16}$A[i+1]\leftarrow A[i]$;\esp{5}$i\leftarrow i-1$
\item[5]\ \esp{8}$A[i+1]\leftarrow carta$
\end{itemize}
    &
    \begin{minipage}{.3\textwidth}
      \includegraphics[scale=0.15]{insertion-sort.jpg}
    \end{minipage}
  \end{tabular}
\end{table}

\vspace{0.3cm}
\alert{Tempo do Caso Médio:} Considere o vetor de entrada do algoritmo como uma permutação de 1 a $n$ escolhida aleatoriamente com prob uniforme.\\
Qual é o número esperado de execuções da linha 4?

\vspace{0.3cm}
Para cada valor de $k$, a linha 4 é executada um num de vezes entre 1 e $k$.\\
Para um certo $t$ entre 1 e $k$, qual a probab de ser executada $t$ vezes?\\

\vspace{0.2cm}
\cor{Resposta: $1/k$,} pois a nova carta (a $k$-ésima) deveria ser a $t$-ésima maior entre as primeiras $k$ cartas $A[1\ldots k]$.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio do Insertion Sort}

\alert{Tempo do Caso Médio:} Considere o vetor de entrada do algoritmo como uma permutação de 1 a $n$ escolhida aleatoriamente com probabilidade uniforme. Qual é o número esperado de execuções da linha 4?

\vspace{0.3cm}
Para cada valor de $k$, a linha 4 é executada um num de vezes entre 1 e $k$.\\
Para um certo $t$ entre 1 e $k$, qual a probab de ser executada $t$ vezes?\\

\vspace{0.2cm}
\cor{Resposta: $1/k$,} pois a nova carta (a $k$-ésima) deveria ser a $t$-ésima maior entre as primeiras $k$ cartas $A[1\ldots k]$.

\vspace{0.4cm}
Seja $X_k$ o número de execuções da linha 4 para um certo $k$ fixo. Portanto:
\[
  \EE(X_k)\ =\ \sum_{t=1}^k t\cdot\PP(X_k=t)\ =\ \sum_{t=1}^k t\cdot\frac{1}{k}\ =\ \frac{1}{k}\sum_{t=1}^k t\ =\ \frac{1}{k}\cdot\frac{k(k+1)}{2}\ =\ \frac{k+1}{2}
\]

\vspace{0.4cm}
Seja $X$ o número total de execuções da linha 4: $X=\sum_{k=2}^n X_k$. Portanto:
\[
  \EE(X)\ =\ \EE\left(\sum_{k=2}^n X_k\right)\ =\ \sum_{k=2}^n \EE(X_k)\ =\ \sum_{k=2}^n \frac{k+1}{2}\ =\ \frac{(n+4)(n-1)}{4}\ =\ \Theta(n^2)
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Insertion Sort Probabilístico}

\begin{table}[h!]
  \centering
  \begin{tabular}{ m{7cm} c }
\cor{Insertion-Sort-Prob (vetor $A$, inteiro $n$)}
\begin{itemize}
\item[1]\ \textbf{rearranja} o vetor $A$ de modo aleatório e uniforme
\item[2]\ Insertion-Sort($A$,$n$)
\end{itemize}
    &
    \begin{minipage}{.3\textwidth}
      \includegraphics[scale=0.15]{insertion-sort.jpg}
    \end{minipage}
  \end{tabular}
\end{table}

\vspace{0.3cm}
Algoritmo \cor{Las Vegas} de ordenação (sempre produz a resposta esperada)

\vspace{0.3cm}
\alert{Tempo Esperado do Insertion Sort Probabilístico} supondo todos os elementos diferentes entre si no vetor $A$: análise praticamente idêntica à do Tempo do Caso Médio do Insertion Sort Determinístico.

\vspace{0.4cm}
\cor{Tempo Esperado $\Theta(n^2)$}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio do Quick Sort}

\begin{table}[h!]
  \centering
  \begin{tabular}{ m{5cm} | m{7cm} }
\cor{Quick-Sort (vetor $A$, inteiros $p$, $r$)}
\begin{itemize}
\item[1]\ \textbf{se} $p<r$ \textbf{então}:
\item[2]\ \esp{4}$q\ \leftarrow\ Particione(A,p,r)$
\item[3]\ \esp{4}Quick-Sort($A$,$p$,$q-1$)
\item[4]\ \esp{4}Quick-Sort($A$,$q+1$,$r$)
\end{itemize}
    &
\cor{Particione (vetor $A$, inteiros $p$, $r$)}
\begin{itemize}
\item[1]\ $pivo\ \leftarrow\ A[r]$;\esp{5}$i\ \leftarrow\ p-1$
\item[2]\ \textbf{para} $k\ \leftarrow\ p$\ \textbf{até}\ $r$\ \textbf{faça}:
\item[3]\ \esp{4}\textbf{se} $A[k]\ \leq\ pivo$ \textbf{então}
\item[4]\ \esp{8}$i\leftarrow i+1$; Trocar $A[i] \leftrightarrow A[j]$
\item[5]\ \textbf{retorne} $i$
\end{itemize}
  \end{tabular}
\end{table}



\vspace{0.2cm}
\alert{Tempo do Caso Médio:} Considere o vetor de entrada do algoritmo como uma permutação de 1 a $n$ escolhida aleatoriamente com prob uniforme.\\
Qual é o número esperado de execuções da linha 3 do Particione?\\
Boa estimativa para o tempo total do Quick Sort.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio do Quick Sort}

{\footnotesize
\begin{table}[h!]
  \centering
  \begin{tabular}{ m{5cm} | m{7cm} }
\cor{Quick-Sort (vetor $A$, inteiros $p$, $r$)}
\begin{itemize}
\item[1]\ \textbf{se} $p<r$ \textbf{então}:
\item[2]\ \esp{4}$q\ \leftarrow\ Particione(A,p,r)$
\item[3]\ \esp{4}Quick-Sort($A$,$p$,$q-1$)
\item[4]\ \esp{4}Quick-Sort($A$,$q+1$,$r$)
\end{itemize}
    &
\cor{Particione (vetor $A$, inteiros $p$, $r$)}
\begin{itemize}
\item[1]\ $pivo\ \leftarrow\ A[r]$;\esp{5}$i\ \leftarrow\ p-1$
\item[2]\ \textbf{para} $k\ \leftarrow\ p$\ \textbf{até}\ $r$\ \textbf{faça}:
\item[3]\ \esp{4}\textbf{se} $A[k]\ \leq\ pivo$ \textbf{então}
\item[4]\ \esp{8}$i\leftarrow i+1$; Trocar $A[i] \leftrightarrow A[j]$
\item[5]\ \textbf{retorne} $i$
\end{itemize}
  \end{tabular}
\end{table}}

\vspace{0.0cm}
\alert{Tempo do Caso Médio:} 
Na linha 3 do Particione, os elementos são comparados com o pivô, que depois nunca mais será analisado.\\
Para $a,b\in\{1\ldots,n\}$, seja $X_{a,b}=1$ se os elementos com valor $a$ e $b$ no vetor são comparados na linha 3 do Particione.\\
Seja $X$ o número total de execuções da linha 3: $X=\sum_{a=1}^{n-1}\sum_{b=a+1}^n X_{a,b}$.
\[
\EE(X_{a,b})\ =\ \PP(\mbox{$a$ ou $b$ ser o 1o pivô em $[a,b]$})\ =\ \frac{2}{b-a+1}
\]
\[
\EE(X)\ =\ \sum_{a=1}^{n-1}\sum_{b=a+1}^n \EE(X_{a,b})\ =\ \sum_{a=1}^{n-1}\sum_{b=a+1}^n \frac{2}{b-a+1}\leq\sum_{a=1}^{n-1}\sum_{\ell=1}^n \frac{2}{\ell}\leq 2n(\ln n + 1)
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Quick Sort Probabilístico}

{\normalsize
\begin{table}[h!]
  \centering
  \begin{tabular}{ m{6cm} | m{6cm} }
\cor{Quick-Sort-Prob ($A$, $p$, $r$)}
\begin{itemize}
\item[1]\ \textbf{se} $p<r$ \textbf{então}:
\item[2]\ \esp{4}$q\ \leftarrow$\ Particione-Aleat$(A,p,r)$
\item[3]\ \esp{4}Quick-Sort-Prob($A$,$p$,$q-1$)
\item[4]\ \esp{4}Quick-Sort-Prob($A$,$q+1$,$r$)
\end{itemize}
    &
\cor{Particione-Aleat ($A$, $p$, $r$)}
\begin{itemize}
\item[1]\ $i\ \leftarrow\ random(p,r)$
\item[2]\ Trocar $A[i]\ \leftrightarrow\ A[r]$
\item[3]\ Particione($A$,$p$,$r$)
\end{itemize}
  \end{tabular}
\end{table}}


\vspace{0.3cm}
Algoritmo \cor{Las Vegas} de ordenação (sempre produz a resposta esperada)

\vspace{0.3cm}
\alert{Tempo Esperado do Quick Sort Probabilístico} supondo todos os elementos diferentes entre si no vetor $A$: análise praticamente idêntica à do Tempo do Caso Médio do Quick Sort Determinístico.

\vspace{0.4cm}
\cor{Tempo Esperado $\Theta(n\cdot \log n)$}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio da Seleção do $k$-ésimo mínimo}

{\footnotesize
\begin{table}[h!]
  \centering
  \begin{tabular}{ m{5cm} | m{7cm} }
\cor{Seleção (vetor $A$, inteiros $p$, $r$, $k$)}
\begin{itemize}
\item[1]\ \textbf{se} $p=r$ \textbf{retorne} $A[p]$
\item[2]\ $q\ \leftarrow\ Particione(A,p,r)$
\item[3]\ \textbf{se} $k=q-p+1$ \textbf{então}
\item[4]\ \esp{4}\textbf{retorne} $A[q]$
\item[5]\ \textbf{senão se} $k<q-p+1$ \textbf{então}
\item[6]\ \esp{4}\textbf{retorne} Seleção ($A$,$p$,$q-1$,$k$)
\item[7]\ \textbf{senão} \textbf{retorne}\\ Seleção ($A$,$q+1$,$r$,$k-(q-p+1)$)
\end{itemize}
    &
\cor{Particione (vetor $A$, inteiros $p$, $r$)}
\begin{itemize}
\item[1]\ $pivo\ \leftarrow\ A[r]$;\esp{5}$i\ \leftarrow\ p-1$
\item[2]\ \textbf{para} $k\ \leftarrow\ p$\ \textbf{até}\ $r$\ \textbf{faça}:
\item[3]\ \esp{4}\textbf{se} $A[k]\ \leq\ pivo$ \textbf{então}
\item[4]\ \esp{8}$i\leftarrow i+1$; Trocar $A[i] \leftrightarrow A[j]$
\item[5]\ \textbf{retorne} $i$
\end{itemize}
  \end{tabular}
\end{table}}



\vspace{0.2cm}
\alert{Tempo do Caso Médio:} Considere o vetor de entrada do algoritmo como uma permutação de 1 a $n$ escolhida aleatoriamente com prob uniforme.\\
Qual é o número esperado de execuções da linha 3 do Particione?\\
Boa estimativa para o tempo total da Seleção do $k$-ésimo mínimo.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio da Seleção do $k$-ésimo mínimo}

{\footnotesize
\begin{table}[h!]
  \centering
  \begin{tabular}{ m{5cm} | m{7cm} }
\cor{Seleção (vetor $A$, inteiros $p$, $r$, $k$)}
\begin{itemize}
\item[1]\ \textbf{se} $p=r$ \textbf{retorne} $A[p]$
\item[2]\ $q\ \leftarrow\ Particione(A,p,r)$
\item[3]\ \textbf{se} $k=q-p+1$ \textbf{então}
\item[4]\ \esp{4}\textbf{retorne} $A[q]$
\item[5]\ \textbf{senão se} $k<q-p+1$ \textbf{então}
\item[6]\ \esp{4}\textbf{retorne} Seleção ($A$,$p$,$q-1$,$k$)
\item[7]\ \textbf{senão} \textbf{retorne}\\ Seleção ($A$,$q+1$,$r$,$k-(q-p+1)$)
\end{itemize}
    &
\cor{Particione (vetor $A$, inteiros $p$, $r$)}
\begin{itemize}
\item[1]\ $pivo\ \leftarrow\ A[r]$;\esp{5}$i\ \leftarrow\ p-1$
\item[2]\ \textbf{para} $k\ \leftarrow\ p$\ \textbf{até}\ $r$\ \textbf{faça}:
\item[3]\ \esp{4}\textbf{se} $A[k]\ \leq\ pivo$ \textbf{então}
\item[4]\ \esp{8}$i\leftarrow i+1$; Trocar $A[i] \leftrightarrow A[j]$
\item[5]\ \textbf{retorne} $i$
\end{itemize}
  \end{tabular}
\end{table}

\vspace{0.0cm}
\alert{Tempo do Caso Médio:} 
Na linha 3 do Particione, os elementos são comparados com o pivô, que depois nunca mais será analisado.
Para $a,b\in\{1\ldots,n\}$, seja $X_{a,b}=1$ se os elementos com valor $a$ e $b$ no vetor são comparados na linha 3 do Particione.}\\
\esp{15}\cor{$\EE(X_{a,b})\ =\ \PP(\mbox{$a$ ou $b$ ser o 1o pivô em $[a,b,k]$})$.}\\
{\footnotesize Por exemplo, se $k<a$ e o 1o pivô em $[k,b]$ não for $a$ ou $b$, nunca serão comparados pois ficarão em lados opostos entre si ou em lados opostos com relação ao $k$.}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio da Seleção do $k$-ésimo mínimo}

\alert{Tempo do Caso Médio:} 
\esp{15}\cor{$\EE(X_{a,b})\ =\ \PP(\mbox{$a$ ou $b$ ser o 1o pivô em $[a,b,k]$})$.}\\
{\footnotesize Por exemplo, se $k<a$ e o 1o pivô em $[k,b]$ não for $a$ ou $b$, nunca serão comparados pois ficarão em lados opostos entre si ou em lados opostos com relação ao $k$.}

\vspace{0.3cm}
$\EE(X_{a,b})=\frac{2}{b-k+1}$, se $a\geq k$\\
$\EE(X_{a,b})=\frac{2}{k-a+1}$, se $b\leq k$\\
$\EE(X_{a,b})=\frac{2}{b-a+1}$, se $a<k<b$

\vspace{0.3cm}
Seja $X$ o número total de execuções da linha 3: $X=\sum_{a=1}^{n-1}\sum_{b=a+1}^n X_{a,b}$.\\
Para facilitar as contas, vamos assumir que $k=1$
\[
\EE(X)\ =\ \sum_{a=1}^{n-1}\sum_{b=a+1}^n \EE(X_{a,b})\ =\ \sum_{b=2}^{n}\sum_{a=1}^{b-1} \frac{2}{b}=\sum_{b=2}^{n}\frac{2(b-1)}{b}\leq 2n
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Análise do Caso Médio da Seleção do $k$-ésimo mínimo}

\alert{Tempo do Caso Médio:} \cor{$\EE(X_{a,b})\ =\ \PP(\mbox{$a$ ou $b$ ser o 1o pivô em $[a,b,k]$})$.}\\
{\footnotesize Por exemplo, se $k<a$ e o 1o pivô em $[k,b]$ não for $a$ ou $b$, nunca serão comparados pois ficarão em lados opostos entre si ou em lados opostos com relação ao $k$.}

\vspace{0.3cm}
$\EE(X_{a,b})=\frac{2}{b-k+1}$, se $a\geq k$\\
$\EE(X_{a,b})=\frac{2}{k-a+1}$, se $b\leq k$\\
$\EE(X_{a,b})=\frac{2}{b-a+1}$, se $a<k<b$

\vspace{0.3cm}
Seja $X$ o número total de execuções da linha 3: $X=\sum_{a=1}^{n-1}\sum_{b=a+1}^n X_{a,b}$.\[
\sum_{a=k}^{n-1}\sum_{b=a+1}^n \EE(X_{a,b})\ =\ \sum_{b=k+1}^{n}\sum_{a=k}^{b-1} \frac{2}{b-k+1}=\sum_{b=k+1}^{n}\frac{2(b-k)}{b-k+1}\leq 2(n-k)
\]
\[
\sum_{a=1}^{k-1}\sum_{b=a+1}^k \EE(X_{a,b})\ =\ \sum_{a=1}^{k-1}\sum_{b=a+1}^k\frac{2}{k-a+1}=\sum_{a=1}^{k-1}\frac{2(k-a)}{k-a+1}\leq 2(k-1)
\]
\[
\sum_{a=1}^{k-1}\sum_{b=k+1}^n \EE(X_{a,b})\ =\ \sum_{a=1}^{k-1}\sum_{b=k+1}^n\frac{2}{b-a+1}\leq\sum_{\ell=3}^{n}\sum_{a=k-\ell+2}^{k-1}\frac{2}{\ell}\leq\sum_{\ell=3}^n\ell\cdot\frac{2}{\ell}\leq 2n
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Seleção Probabilística do $k$-ésimo mínimo}

{\footnotesize
\begin{table}[h!]
  \centering
  \begin{tabular}{ m{7cm} | m{5cm} }
\cor{Seleção-Prob (vetor $A$, inteiros $p$, $r$, $k$)}
\begin{itemize}
\item[1]\ \textbf{se} $p=r$ \textbf{retorne} $A[p]$
\item[2]\ $q\ \leftarrow$\ Particione-Aleat$(A,p,r)$
\item[3]\ \textbf{se} $k=q-p+1$ \textbf{então}
\item[4]\ \esp{4}\textbf{retorne} $A[q]$
\item[5]\ \textbf{senão se} $k<q-p+1$ \textbf{então}
\item[6]\ \esp{4}\textbf{retorne} Seleção-Prob ($A$,$p$,$q-1$,$k$)
\item[7]\ \textbf{senão} \textbf{retorne}\\\esp{10}Seleção-Prob ($A$,$q+1$,$r$,$k-(q-p+1)$)
\end{itemize}
    &
\cor{Particione-Aleat ($A$, $p$, $r$)}
\begin{itemize}
\item[1]\ $i\ \leftarrow\ random(p,r)$
\item[2]\ Trocar $A[i]\ \leftrightarrow\ A[r]$
\item[3]\ Particione($A$,$p$,$r$)
\end{itemize}
  \end{tabular}
\end{table}}

\vspace{0.3cm}
Algoritmo \cor{Las Vegas} de seleção (sempre produz a resposta esperada)

\vspace{0.3cm}
\alert{Tempo Esperado da Seleção Probabilística} supondo todos os elementos diferentes entre si no vetor $A$: análise praticamente idêntica à do Tempo do Caso Médio da Seleção Determinística.

\vspace{0.4cm}
\cor{Tempo Esperado $\Theta(n)$}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Cadeias de Markov (\emph{Markov Chains})}

Um \cor{\bf processo estocástico discreto} é uma sequência $X_0,X_1,X_2,\ldots$ de v.a. que assumem valores em um conjunto finito (ou infinito enumerável). Se $X_t=i$, dizemos que o processo está no estado $i$ no tempo $t$.

\vspace{0.4cm}
Uma \cor{\bf cadeia de Markov} é um processo estocástico discreto tal que\\
$\PP(X_t=a_t\ |\ X_{t-1}=a_{t-1},\ldots,X_0=a_0)\ =\ \PP(X_t=a_t\ |\ X_{t-1}=a_{t-1})$,\\
cujo valor não depende de $t$ (\emph{Memoryless/Markov property}).

\vspace{0.4cm}
Seja $P_{i,j}=\PP(X_{t+1}=j\ |\ X_t=i)$.

\vspace{0.2cm}
\[
\cor{\mbox{Matriz de transição (1 passo):}\esp{10} P\ =\ 
\begin{bmatrix}
P_{0,0} & P_{0,1} & \ldots & P_{0,j} & \ldots\\
P_{1,0} & P_{1,1} & \ldots & P_{1,j} & \ldots\\
\vdots  & \vdots  & \ddots & \vdots  & \ddots\\
P_{i,0} & P_{i,1} & \ldots & P_{i,j} & \ldots\\
\vdots  & \vdots  & \ddots & \vdots  & \ddots\\
\end{bmatrix}}
\]

\vspace{0.4cm}
\alert{Lei da Probabilidade total:\esp{5}$\sum_{j=0}^\infty P_{i,j}\ =\ 1$}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - transição em $m$ passos}

\alert{Matriz de transição ($m$ passos):} Seja $P_{i,j}^{(m)}=\PP(X_{t+m}=j\ |\ X_t=i)$.

\[
P_{i,j}^{(m)}=\sum_{k=0}^\infty\PP(X_{t+m}=j,X_{t+1}=k\ |\ X_t=i)\ =\ \sum_{k=0}^{\infty}\PP(X_{t+m}=j\ |\ X_{t+1}=k,X_t=i)\cdot\PP(X_{t+1}=k\ |\ X_t=i)
\]
\[
P_{i,j}^{(m)}=\sum_{k=0}^{\infty}P_{i,k}\cdot P_{k,j}^{(m-1)}
\]

\vspace{0.2cm}
\alert{Seja $P^{(m)}$ a matriz com valores $[\ P_{i,j}^{(m)}\ ]$.\esp{3}
Logo $P^{(m)}=P\cdot P^{(m-1)}$.\\
Por indução, temos que $P^{(m)}=P^m$.}

\vspace{0.2cm}
\[
\cor{\mbox{Matriz transição ($m$ passos):}\esp{1} P^{(m)} = 
\begin{bmatrix}
P_{0,0}^{(m)} & P_{0,1}^{(m)} & \ldots & P_{0,j}^{(m)} & \ldots\\
P_{1,0}^{(m)} & P_{1,1}^{(m)} & \ldots & P_{1,j}^{(m)} & \ldots\\
\vdots        & \vdots        & \ddots & \vdots        & \ddots\\
P_{i,0}^{(m)} & P_{i,1}^{(m)} & \ldots & P_{i,j}^{(m)} & \ldots\\
\vdots        & \vdots        & \ddots & \vdots        & \ddots\\
\end{bmatrix}
 = P^m}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - transição em $m$ passos - exemplo}

\begin{figure}[hbtp]\centering
\scalebox{0.60}{
\begin{tikzpicture}[scale=1.0]
\tikzstyle{uvertex}=[draw,circle,fill=white!25,minimum size=20pt,inner sep=1pt]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,4) {0};
\node[cvertex] (v1) at (4,4) {1};
\node[cvertex] (v2) at (8,4) {2};
\node[cvertex] (v3) at (4,0) {3};
\path[->,thick]
   (v0) edge[bend left] node[above] {1/4} (v1) edge node[left] {3/4} (v3)
   (v1) edge[bend left] node[below] {1/2} (v0) edge[bend left] node[left] {1/6} (v3) edge node[above] {1/3} (v2)
   (v2) edge[out=120,in=60,looseness=8] node[above] {1} (v2)
   (v3) edge[bend left] node[left] {1/2} (v1) edge node[right] {1/4} (v2) edge[out=150,in=210,looseness=8] node[left] {1/4} (v3);
\end{tikzpicture}}
\end{figure}

\cor{\footnotesize
\[
P=
\begin{bmatrix}
0 & 1/4 & 0 & 3/4\\
1/2 & 0 & 1/3 & 1/6\\
0 & 0 & 1 & 0\\
0 & 1/2 & 1/4 & 1/4
\end{bmatrix}
\esp{4}\Rightarrow\esp{4}
P^3=
\begin{bmatrix}
3/16 & 7/48 & 29/64 & \alert{41/192}\\
5/48 & 5/24 & 79/144 & 5/36\\
0 & 0 & 1 & 0\\
1/16 & 13/96 & 107/192 & 47/192
\end{bmatrix}
\]}

\vspace{0.3cm}
\alert{$P_{0,3}^{(3)}=41/192$:} prob de ir de 0 a 3 em 3 passos.\\
\cor{Outro modo:} caminhos possíveis 0103, 0133, 0313, 0333.
\[
\frac{1}{4}\cdot\frac{1}{2}\cdot\frac{3}{4}+\frac{1}{4}\cdot\frac{1}{6}\cdot\frac{1}{4}+\frac{3}{4}\cdot\frac{1}{2}\cdot\frac{1}{6}+\frac{3}{4}\cdot\frac{1}{4}\cdot\frac{1}{4}\ =\ \frac{3}{32}+\frac{1}{96}+\frac{1}{16}+\frac{3}{64}\ =\ \alert{\frac{41}{192}}
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - transição em $m$ passos - exemplo}

\begin{figure}[hbtp]\centering
\scalebox{0.80}{
\begin{tikzpicture}[scale=1.0]
\tikzstyle{uvertex}=[draw,circle,fill=white!25,minimum size=20pt,inner sep=1pt]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {$H-O$};
\node[cvertex] (v1) at (4,0) {$\overline{H}-O$};
\node[cvertex] (v2) at (8,0) {$H-\overline{O}$};
\node[cvertex] (v3) at (12,0) {$\overline{H}-\overline{O}$};
\path[->,thick]
   (v0) edge node[above]{0.3} (v1) edge[out=120,in=60,looseness=8] node[above] {0.7} (v0)
   (v1) edge node[above]{0.4} (v2) edge[bend right] node[below]{0.6} (v3)
   (v2) edge[bend left] node[below]{0.5} (v0) edge[bend right] node[above]{0.5} (v1)
   (v3) edge node[above]{0.2} (v2) edge[out=120,in=60,looseness=8] node[above]{0.8} (v3);
\node[] at (0,-1.3) {Choveu hoje}; \node[] at (0,-1.6) {e ontem};
\node[] at (4,1.3) {Choveu ontem}; \node[] at (4,1) {mas não hoje};
\node[] at (8,1.3) {Choveu hoje,}; \node[] at (8,1) {mas não ontem};
\node[] at (12,-1.3) {Não choveu hoje,}; \node[] at (12,-1.6) {nem ontem};
\node[] at (0,-0.8) {\cor{Estado 0}};
\node[] at (4,-0.8) {\cor{Estado 1}};
\node[] at (8,-0.8) {\cor{Estado 2}};
\node[] at (12,-0.8){\cor{Estado 3}};
\end{tikzpicture}}
\end{figure}

\cor{\footnotesize
\[
P=
\begin{bmatrix}
0.7 & 0.3 & 0 & 0\\
0 & 0 & 0.4 & 0.6\\
0.5 & 0.5 & 0 & 0\\
0 & 0 & 0.2 & 0.8
\end{bmatrix}
\esp{4}\Rightarrow\esp{4}
P^2=
\begin{bmatrix}
\alert{0.49} & 0.21 & \alert{0.12} & 0.18\\
0.20 & 0.20 & 0.12 & 0.48\\
0.35 & 0.15 & 0.20 & 0.30\\
0.10 & 0.10 & 0.16 & 0.64
\end{bmatrix}
\]}

\vspace{0.3cm}
Choveu na segunda e na terça. Qual a probabilidade de chover na quinta?\\
$\alert{P_{0,0}^{(2)}+P_{0,2}^{(2)}}\ =\ 0.49+0.12\ =\ 0.61$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Classificação dos estados}

Dizemos que o Estado $j$ é \cor{\bf acessível} a partir do Estado $i$ se:\\ \esp{10}$P_{i,j}^{(n)}>0$ para algum $n\geq 0$.

\vspace{0.2cm}
Dizemos que os Estados $i$ e $j$ \cor{\bf se comunicam ($i\leftrightarrow j$)} se\\\esp{10}$i$ é acessível de $j$ e $j$ é acessível de $i$.

\vspace{0.3cm}
\alert{Propriedades: (Relação de Equivalência)}
\begin{itemize}
\item {\bf Reflexiva:} $i\leftrightarrow i$.
\item {\bf Simétrica:} se $i\leftrightarrow j$, então $j\leftrightarrow i$.
\item {\bf Transitiva:} se $i\leftrightarrow j$ e $j\leftrightarrow k$, então $i\leftrightarrow k$.
\end{itemize}

\vspace{0.2cm}
\alert{Partição} dos Estados da Cadeia de Markov em \alert{Classes de Equivalência} com relação à comunicabilidade. Mostrar 2 exemplos slides anteriores.

\vspace{0.2cm}
Uma cadeia é \cor{\bf irredutível} se possui apenas 1 classe.

\vspace{0.3cm}
\cor{Outro exemplo:} 3 classes: $\{0,1\},\ \ \{2\},\ \ \{3\}$

\begin{figure}[hbtp]\centering
\scalebox{0.75}{
\begin{tikzpicture}[scale=0.8]
\tikzstyle{uvertex}=[draw,circle,fill=white!25,minimum size=20pt,inner sep=1pt]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (4,0) {1};
\node[cvertex] (v2) at (8,0) {2};
\node[cvertex] (v3) at (12,0) {3};
\path[->,thick]
   (v0) edge node[above]{1/2} (v1) edge[out=120,in=60,looseness=8] node[above] {1/2} (v0)
   (v1) edge node[above]{1/2} (v0) edge[out=120,in=60,looseness=8] node[above] {1/2} (v1)
   (v2) edge[bend left] node[above]{1/4} (v0) edge node[above]{1/4} (v1) edge[out=120,in=60,looseness=8] node[above] {1/4} (v2) edge node[above]{1/4} (v3)
   (v3) edge[out=120,in=60,looseness=8] node[above] {1} (v3);
\end{tikzpicture}}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Estados Recorrentes $\times$ Estados Transientes}

Seja $f_{ij}$ a prob de, começando no Estado $i$, o processo visitar $j$ em algum momento futuro. Ou seja, $1-f_{ii}$ é a prob de nunca mais voltar.

\vspace{0.4cm}
Dizemos que o Estado $i$ é \cor{\bf recorrente} se $f_{ii}=1$. Caso contrário, $f_{ii}<1$ e o estado é \alert{\bf transiente} (existe a prob $1-f_{ii}$ de nunca mais voltar).

\vspace{0.4cm}
Se um estado $i$ é \alert{transiente}, o número $X$ de vezes que o processo esteve em $i$, começando em $i$, é uma v.a. com distribuição geométrica:\\ $\PP(X=n)=f_{ii}^n\cdot(1-f_{ii})$.

\vspace{0.4cm}
\cor{\bf Proposição 4.3.1 (Ross):}\\
\[
\mbox{Um Estado $i$ é \alert{transiente}\esp{5} {\bf se e só se}}\esp{5} \sum_{n=0}^\infty P_{i,i}^{(n)}<\infty.
\]

\vspace{0.0cm}
\cor{\bf Corolário 4.3.1 (Ross):}\\
Se o Estado $i$ é \cor{recorrente} e $i\leftrightarrow j$, então o Estado $j$ é recorrente.

\vspace{0.4cm}
\cor{\bf Observação:} Toda cadeia de Markov finita tem um estado \cor{recorrente}.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Ruína do Jogador (\emph{Gambler's Ruin})}

Probabilidade $p$ de ganhar 1 real e prob $q=1-p$ de perder 1 real. Jogadas independentes. Qual a probabilidade de conseguir $n$ reais começando com 1 real?

\vspace{0.4cm}
\cor{Modelar o problema como uma Cadeia de Markov:}\\
$P_{0,0}=P_{n,n}=1$;\esp{5}$P_{i,i+1}=p$;\esp{5}$P_{i,i-1}=q$ \esp{5}para $i=1,\ldots,n-1$.

\begin{figure}[hbtp]\centering
\scalebox{0.75}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node[cvertex] (v3) at (9,0) {3};
\node at (12,0.5) {$\ldots$};
\node at (12,-.5) {$\ldots$};
\node[cvertex] (v5) at (15,0) {$n-1$};
\node[cvertex] (v6) at (18,0) {$n$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {1} (v0)
   (v6) edge[out=120,in=60,looseness=8] node[above] {1} (v6)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$q$} (v1) edge[bend left] node[above]{$p$} (v3)
   (v3) edge[bend left] node[below]{$q$} (v2) edge[bend left] node[above]{$p$} (11,.5)
   (11,-.5) edge[bend left] node[below]{$q$} (v3) (13,.5) edge[bend left] node[above]{$p$} (v5)
   (v5) edge[bend left] node[below]{$q$} (13,-.5) edge[bend left] node[above]{$p$} (v6);
\end{tikzpicture}}
\end{figure}

\cor{\bf 3 classes:} $\{0\}$ recorrente, $\{n\}$ recorrente, $\{1,\ldots,n-1\}$ transiente.

\vspace{0.4cm}
Seja $R_i$ a prob de, começando com $i$ reais, atingir $n$ reais antes de 0:\\ \alert{$R_0=0$;}\esp{4}$R_n=1$;\esp{4}\cor{$R_i\ =\ p\cdot R_{i+1}+q\cdot R_{i-1}$ para $i=1,\ldots,n-1$}.

\vspace{0.4cm}
{\bf Objetivo:} Calcular $R_1$. Generalizar para $R_i$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Ruína do Jogador (\emph{Gambler's Ruin})}

Seja $R_i$ a prob de, começando com $i$ reais, atingir $n$ reais antes de 0:\\ \alert{$R_0=0$;}\esp{4}$R_n=1$;\esp{4}\cor{$R_i\ =\ p\cdot R_{i+1}+q\cdot R_{i-1}$ para $i=1,\ldots,n-1$}.

\vspace{0.2cm}
{\bf Objetivo:} Calcular $R_1$. Generalizar para $R_i$.
{\small\[
R_{i+1}-R_i = \left(\frac{q}{p}\right)\cdot(R_i-R_{i-1}) = \left(\frac{q}{p}\right)^2\cdot(R_{i-1}-R_{i-2}) = 
\left(\frac{q}{p}\right)^i\cdot(R_1-R_0) = \left(\frac{q}{p}\right)^i\cdot R_1
\]}
\[
\cor{\Rightarrow} R_{i+1}=R_i+\left(\frac{q}{p}\right)^i R_1\ \cor{\Rightarrow}\ R_i=R_1\cdot\left[1+\frac{q}{p}+\left(\frac{q}{p}\right)^2+\ldots+\left(\frac{q}{p}\right)^{i-1}\right]
\]
Se $p=1/2$:\ \ $R_i=i\cdot R_1$.\esp{5}Se $p\ne 1/2$:\ \  $R_i=\frac{1-(q/p)^i}{1-(q/p)}\cdot R_1$.

\vspace{0.2cm}
\cor{Como $R_n=1$, então:}\\

\vspace{0.2cm}
Se $p=1/2$:\ \ $R_n=n\cdot R_1$.\esp{5}Se $p\ne 1/2$:\ \  $R_n=\frac{1-(q/p)^n}{1-(q/p)}\cdot R_1$. {\bf Portanto:}\\

\vspace{0.2cm}
Se $p=1/2$:\ \ $R_1=1/n$.\esp{8}Se $p\ne 1/2$:\ \  $R_1=\frac{1-(q/p)}{1-(q/p)^n}$. \esp{2}{\bf Finalmente:}\\

\vspace{0.2cm}
Se $p=1/2$:\ \ \cor{$R_i=i/n$}.\esp{9}Se $p\ne 1/2$:\ \  \cor{$R_i=\frac{1-(q/p)^i}{1-(q/p)^n}$}.\\
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Passeio Aleatório (\emph{Random Walk})}

$P_{i,i+1}=p$;\esp{3}$P_{i,i-1}=q=1-p$; \esp{3}onde $i\in\ZZ$.

\begin{figure}[hbtp]\centering
\scalebox{0.75}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0){-2};
\node[cvertex] (v1) at (3,0){-1};
\node[cvertex] (v2) at (6,0) {0};
\node[cvertex] (v3) at (9,0) {1};
\node[cvertex] (v4) at (12,0){2};
\node at (-2,0.5) {$\ldots$};
\node at (-2,-.5) {$\ldots$};
\node at (14,0.5) {$\ldots$};
\node at (14,-.5) {$\ldots$};
\path[->,thick]
   (-1.5,0.5) edge[bend left] node[above]{$p$} (v0)
   (13.5,-.5) edge[bend left] node[below]{$q$} (v4)
   (v0) edge[bend left] node[below]{$q$} (-1.5,-.5) edge[bend left] node[above]{$p$} (v1)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$q$} (v1) edge[bend left] node[above]{$p$} (v3)
   (v3) edge[bend left] node[below]{$q$} (v2) edge[bend left] node[above]{$p$} (v4)
   (v4) edge[bend left] node[below]{$q$} (v3) edge[bend left] node[above]{$p$} (13.5,0.5);
\end{tikzpicture}}
\end{figure}

Todos os estados {\bf se comunicam}. Logo, todos são \cor{recorrentes} ou todos são \alert{transientes}. O estado 0 é recorrente {\bf se e só se} $\sum_{n=0}^\infty P_{0,0}^{(n)}=\infty$.
\[
P_{0,0}^{(2n+1)}=0,\ \forall n.\esp{5} P_{0,0}^{(2n)}=\binom{2n}{n}p^n(1-p)^n=\frac{(2n)!}{n!n!}[p(1-p)]^n\approx\frac{[4p(1-p)]^n}{\sqrt{\pi\cdot n}},
\]
usando Stirling: $n!\approx n^ne^{-n}\sqrt{2\pi n}$.
Note que $4p(1-p)\leq 1$, $\forall p\in[0,1]$.

\vspace{0.3cm}
Igualdade $4p(1-p)=1$ \cor{se e só se $p=1/2$.}

\vspace{0.3cm}
Logo, $\sum_{n=0}^{\infty}P_{0,0}^{(2n)}=\sum_{n=0}^{\infty}\frac{[4p(1-p)]^n}{\sqrt{\pi\cdot n}}=\infty$ \textbf{se e só se} $p=1/2$.

\vspace{0.3cm}
\textbf{Conclusão:} Se $p=1/2$, todos os estados são \cor{recorrentes}.\\
\esp{19}Se $p\ne 1/2$, todos os estados são \alert{transientes}.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - \emph{Random Walk} em 2 dimensões}

\begin{figure}[hbtp]\centering
\scalebox{0.5}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]
\node[cvertex] (v0) at (3,3){$(1,1)$};
\node[cvertex] (N)  at (3,6){$(1,2)$};
\node[cvertex] (S)  at (3,0){$(1,0)$};
\node[cvertex] (L)  at (6,3){$(2,1)$};
\node[cvertex] (O)  at (0,3){$(0,1)$};
\path[->,thick]
   (v0) edge node[below]{$1/4$} (L) edge node[above]{$1/4$} (O) edge node[right]{$1/4$} (N) edge node[left]{$1/4$} (S);
\end{tikzpicture}}
\end{figure}
\[
P_{1,1}^{(2n)} = \sum_{i=0}^n \frac{(2n)!\cdot (1/4)^{2n}}{i!\cdot i!\cdot (n-i)!\cdot (n-i)!} = \left(\frac{1}{4}\right)^{2n}\binom{2n}{n}\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}
\]
\tiny{alert{Identidade de Vandermonde.}}
\[
P_{1,1}^{(2n)} = \left(\frac{1}{4}\right)^{2n}\binom{2n}{n}\binom{2n}{n}\approx\frac{((2n)^{2n}e^{-2n}\sqrt{2\pi 2n})^2}{4^{2n}(n^n e^{-n}\sqrt{2\pi n})^4} \cor{\ =\ \frac{1}{n\cdot \pi}}
\]
Portanto:
\[
\sum_{n=0}^\infty P_{1,1}^{(2n)}\ =\ \infty\esp{5}\Rightarrow\esp{5}\cor{\mbox{Todos os estados são Recorrentes}}
\]
\alert{Symmetric Random Walk:} 1|2 dimensões (todos estados são \cor{recorrentes})\\
\esp{38} $\geq 3$ dimensões (todos estados são \alert{transientes})
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Distribuição Estacionária e Periodicidade}

\cor{\bf Vetor de probabilidade $\pi^{(t)}=[\pi^{(t)}_1,\ldots,\pi^{(t)}_n]$}: Matriz linha $1 \times n$ tal que $\pi^{(t)}_i$ é a probabilidade do processo estar no estado $i$ no tempo $t$.

\vspace{0.2cm}
\cor{$\bullet$} $\pi^{(t)}=\pi^{(t-1)}\cdot P$. Ou seja, $\pi_i^{(t)}=\sum_{k=1}^n \pi_k^{(t-1)}\cdot P_{k,i}$\\
\cor{$\bullet$} $\Rightarrow\ \ \pi^{(t)}=\pi^{(0)}\cdot P^t$, onde $P$ é matriz de transição da Cadeia de Markov.

\vspace{0.3cm}
\cor{\bf Distribuição limite (ou estacionária):} Qualquer vetor $\pi$ tq \alert{$\pi=\pi\cdot P$}.\\
\cor{$\bullet$} {\bf Intuição:} Se o vetor de prob for igual a $\pi$ em algum momento, o vetor de prob do processo será sempre $\pi$.\esp{35}\alert{$\sum_{i=0}^n \pi_i=1$}

\vspace{0.3cm}
\cor{\bf Tempo de travessia (\emph{hitting time}) $T_{ij}$:} Tempo (número de passos) esperado para alcançar o estado $j$ iniciando no estado $i$. \cor{$T_{ij}>0$.}

\vspace{0.3cm}
\cor{\bf Periodicidade do estado $i$:} $\max\{d:\ P_{i,i}^n=0, \forall n \mbox{ não divisível por } d\}$.\\
Estados de uma mesma classe tem a mesma periodicidade.

\vspace{0.3cm}
Uma cadeia é \cor{\bf aperiódica} se todo estado é aperiódico (periodicidade=1).

\vspace{0.3cm}
{\bf Exemplo:} Random Walk tem período 2 em cada estado. Triângulo direcionado com probabilidades 1 tem periódo 3 em cada estado.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Teorema Fundamental}

\alert{\bf Teorema Fundamental das Cadeias de Markov:}\\
Toda Cadeia de Markov finita, irredutível e aperiódica satisfaz:
\begin{itemize}
\item[(a)] Todos os estados são recorrentes e aperiódicos
\item[(b)] Existe uma única distribuição estacionária $\pi$ tq $\pi_i>0,\ \forall i$
\item[(c)] \cor{$f_{ii}=1$}\ \ e\ \ \cor{$T_{ii}=1/\pi_i$} para todo estado $i$
\item[(d)] Para qualquer vetor $\pi^{(0)}$ de prob inicial, \cor{$$\lim_{t\to\infty} \pi^{(t)}\ =\ \pi \ \ \ \ \mbox{\footnotesize(Convergência exponencialmente rápida)}$$}

\item[(e)] Seja $N(i,t)$ o número de vezes que $i$ é visitado em $t$ passos.\\ \cor{$$\lim_{t\to\infty} \frac{N(i,t)}{t}\ =\ \pi_i$$}
\end{itemize}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

Probabilidade $p$ de ganhar 1 real e prob $q=1-p$ de perder 1 real.\\
Mas, se perder tudo, consegue 1 real com um padrinho rico e recomeça.\\
Se ganhar $n$ reais, dá $n-1$ ao padrinho e recomeça.\\
Qual o tempo esperado para conseguir $n$ reais começando com 1 real?

\begin{figure}[hbtp]\centering
\scalebox{0.7}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node[cvertex] (v3) at (9,0) {3};
\node at (12,0.5) {$\ldots$};
\node at (12,-.5) {$\ldots$};
\node[cvertex] (v5) at (15,0) {$n-1$};
\node[cvertex] (v6) at (18,0) {$n$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$q$} (v0)
   (v0) edge[bend left] node[above]{p} (v1)
   (v6) edge[in=300,out=240,looseness=0.4] node[above] {1} (v1)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$q$} (v1) edge[bend left] node[above]{$p$} (v3)
   (v3) edge[bend left] node[below]{$q$} (v2) edge[bend left] node[above]{$p$} (11,.5)
   (11,-.5) edge[bend left] node[below]{$q$} (v3) (13,.5) edge[bend left] node[above]{$p$} (v5)
   (v5) edge[bend left] node[below]{$q$} (13,-.5) edge[bend left] node[above]{$p$} (v6);
\end{tikzpicture}}
\end{figure}

\alert{\bf 1 classe:} todos os estados são recorrentes e aperiódicos.

\vspace{0.2cm}
{\bf Objetivo:} Calcular o tempo esperado $T_{1,n}$ p/ ir de 1 até $n$.
{\footnotesize
\begin{itemize}
\item \cor{Método 1:} Calcular $\pi_n\ \Rightarrow\ \frac{1}{\pi_n}=T_{n,n}=1+T_{1,n}$
\item \cor{Método 2:} Calcular $T_{1,n}$ diretamente em função de outros $T_{i,n}$.
\item \cor{Método 3:} Fazer a conta na marra: analisar cada caminho possível de 1 até $n$ e calcular sua probabilidade.
\item \cor{Método 4:} Experimental p/ $T_{1,n}$. MCMC (Monte Carlo Markov Chain).
\item \cor{Método 5:} Experimental p/ $\pi_n$. Convergência rápida ao limite.
\end{itemize}}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

\cor{Método 1:} Calcular $\pi_n\ \Rightarrow\ \frac{1}{\pi_n}=T_{n,n}=1+T_{1,n}$

\vspace{0.3cm}
\alert{{\bf Info:} $\pi=\pi\cdot P$\ \ e\ \ $\sum_{i=0}^n\pi_i=1$}. Portanto:\\
$\pi_n=p\cdot \pi_{n-1}\esp{20.5} \Rightarrow\ \pi_{n-1}=\frac{1}{p}\cdot\pi_n$\\
$\pi_{n-1}=p\cdot\pi_{n-2}\esp{17} \Rightarrow\ \pi_{n-2}=\frac{1}{p^2}\cdot\pi_n$\\
$\pi_{n-2}=p\cdot\pi_{n-3}+q\cdot\pi_{n-1}\ \Rightarrow\ \pi_{n-3}=\frac{1}{p^3}(1-pq)\cdot\pi_n$\\

\vspace{0.2cm}
\alert{{\bf Simplificação:} $p=1/2$.\esp{15} {\bf Exercício 1:} terminar p/ $p$ qualquer.}
{\small
\begin{align*}
\pi_n=(1/2)\cdot \pi_{n-1}&\ \Rightarrow\ \pi_{n-1}=2\cdot\pi_n\\
\pi_{n-1}=(1/2)\cdot\pi_{n-2}&\ \Rightarrow\ \pi_{n-2}=4\cdot\pi_n\\
\pi_{n-2}=(1/2)\cdot\pi_{n-3}+(1/2)\cdot\pi_{n-1}&\ \Rightarrow\ \pi_{n-3}=6\cdot\pi_n\\
\pi_{n-3}=(1/2)\cdot\pi_{n-4}+(1/2)\cdot\pi_{n-2}&\ \Rightarrow\ \pi_{n-4}=8\cdot\pi_n\\
\pi_{n-4}=(1/2)\cdot\pi_{n-5}+(1/2)\cdot\pi_{n-3}&\ \Rightarrow\ \pi_{n-5}=10\cdot\pi_n\\
\ldots\\
\pi_{i+1}=(1/2)\cdot\pi_{i}+(1/2)\cdot\pi_{i+2}&\ \Rightarrow\ \pi_{i}=2(n-i)\cdot\pi_n\\
\ldots\\
\pi_{2}=(1/2)\cdot\pi_{1}+(1/2)\cdot\pi_{3}&\ \Rightarrow\ \pi_{1}=2(n-1)\cdot\pi_n\\
\pi_0=(1/2)\pi_0+(1/2)\pi_1&\ \Rightarrow\ \pi_0=\pi_1=2(n-1)\cdot\pi_n
\end{align*}}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

\cor{Método 1:} Calcular $\pi_n\ \Rightarrow\ \frac{1}{\pi_n}=T_{n,n}=1+T_{1,n}$

\vspace{0.2cm}
\alert{{\bf Simplificação:} $p=1/2$.\esp{15} {\bf Exercício 1:} terminar p/ $p$ qualquer.}
{\small
\[
1=\sum_{i=0}^n \pi_i=\pi_n-2\pi_n+\sum_{i=1}^{n} 2i\cdot\pi_n=\pi_n\left(-1+n(n+1)\right)\ \Rightarrow\ \pi_n=\frac{1}{n^2+n-1}
\]}
\begin{figure}[hbtp]\centering
\scalebox{0.7}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node[cvertex] (v3) at (9,0) {3};
\node at (12,0.5) {$\ldots$};
\node at (12,-.5) {$\ldots$};
\node[cvertex] (v5) at (15,0) {$n-1$};
\node[cvertex] (v6) at (18,0) {$n$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$q$} (v0)
   (v0) edge[bend left] node[above]{p} (v1)
   (v6) edge[in=300,out=240,looseness=0.4] node[above] {1} (v1)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$q$} (v1) edge[bend left] node[above]{$p$} (v3)
   (v3) edge[bend left] node[below]{$q$} (v2) edge[bend left] node[above]{$p$} (11,.5)
   (11,-.5) edge[bend left] node[below]{$q$} (v3) (13,.5) edge[bend left] node[above]{$p$} (v5)
   (v5) edge[bend left] node[below]{$q$} (13,-.5) edge[bend left] node[above]{$p$} (v6);
\end{tikzpicture}}
\end{figure}

Portanto, do Teorema Fundamental das Cadeias de Markov:
\[
T_{n,n}\ =\ \frac{1}{\pi_n}\ =\ n^2+n-1\esp{3}\Rightarrow\esp{3} \cor{T_{1,n}=}T_{n,n}-1\cor{=n^2+n-2=(n+2)(n-1)}
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

\cor{Método 2:} Calcular $T_{1,n}$ diretamente em função de outros $T_{i,n}$.

\vspace{0.3cm}
\alert{{\bf Info:} Esperança condicional: $\EE(X)=\sum_i \EE(X|Y=i)\cdot\PP(Y=i)$}.

\vspace{0.3cm}
Seja $T_i$ o tempo esperado para chegar em $n$ a partir de $i$, inclusive.\\
Formalmente, $T_i=T_{i,n}$ se $i\ne n$ e \cor{$T_{n}=0$}, cc.;\\
\alert{$T_i\ =\ 1\ +\ p\cdot T_{i+1}+q\cdot T_{i-1}$}\\
\cor{$T_0=1+p\cdot T_1+q\cdot T_0\ \ \Rightarrow\ T_1-T_0=-1/p$}

\vspace{0.2cm}
{\bf Objetivo:} Calcular $T_1$. Generalizar para $T_i$.
{\small
\[
(T_{i+1}-T_{i}) = \left(\frac{q}{p}\right)\cdot(T_{i}-T_{i-1})\ -\ \frac{1}{p}
\]}
\alert{{\bf Simplificação:} $p=1/2$.\esp{14} {\bf Exercício 2:} terminar p/ $p$ qualquer.}
\[
(T_{i+1}-T_{i}) = (T_1-T_0)-2i\ \Rightarrow\ \cor{T_{i+1} = T_{i} - 2(i+1)}\ \Rightarrow\ \cor{T_{n} = T_i - 2\sum_{k=i+1}^n k}
\]
\[
\cor{T_i\ =\ (n+i+1)(n-i)}\esp{5} \Rightarrow\esp{5} \alert{T_1\ =\ (n+2)(n-1)}
\]
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

\cor{Método 3:} Fazer a conta na marra: analisar cada caminho possível de 1 a $n$ e calcular prob. \alert{Dificuldade: num caminhos é exponencial !!}

\begin{figure}[hbtp]\centering
\scalebox{0.5}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node at (13,0) {$n=2\ \Rightarrow\ T_{1,n}=(2+2)(2-1)\ =\ 4$};
\node at (-5,0) {\Large\cor{Exemplo:}};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$q$} (v0)
   (v0) edge[bend left] node[above]{p} (v1)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$1$} (v1);
\end{tikzpicture}}
\end{figure}
{\tiny
1 tam 1 (12)\\
0 tam 2\\
1 tam 3 (1012)\\
1 tam 4 (10012)\\
2 tam 5 (100012,\ 101012)\\
3 tam 6 (1000012,\ 1001012,\ 1010012)\\
5 tam 7 (10000012,\ 10001012,\ 10010012,\ 10100012,\ 10101012)\\
8 tam 8 (100000012,\ 100001012,\ 100010012,\ 100100012,\ 101000012,\ 100101012,\ 101001012,\ 101010012)}

\vspace{0.3cm}
Fibonacci $F(k-2)$ caminhos de tam. $k\geq 2$.\esp{20}\alert{\bf Exercício 3 !!}
\[
\cor{T_{1,2}\ =\ 1\cdot\frac{1}{2} + \sum_{k=2}^{\infty}k\cdot F(k-2)\cdot\left(\frac{1}{2}\right)^k\ =\ 4} \esp{18}\mbox{\alert{\bf Exercício 4 !!}}
\]
\begin{figure}\centering
\includegraphics[scale=0.45]{desmos01.png}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

\cor{Método 4:} Experimental p/ $T_{1,n}$. MCMC (Monte Carlo Markov Chain)

\begin{figure}[hbtp]\centering
\scalebox{0.5}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node at (15,0) {$n=2\ \Rightarrow\ T_{1,n}=(2+2)(2-1)\ =\ 4$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$q$} (v0)
   (v0) edge[bend left] node[above]{p} (v1)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$1$} (v1);
\end{tikzpicture}}
\end{figure}

\begin{figure}\centering
\includegraphics[scale=0.4]{mcmc01.png}
\end{figure}

\alert{{\bf Exercício 5:} Fazer p/ $n=3,\ldots,100$, listar tempos médios e comparar.}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Glória do Jogador (\emph{Gambler's Glory})}

\cor{Método 5:} Experimental p/ $\pi_n$. Convergência rápida ao limite.\\
$\frac{1}{\pi_n}=T_{n,n}=1+\cor{T_{1,n}}$.

\begin{figure}[hbtp]\centering
\scalebox{0.5}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node at (15,0) {$n=2\ \Rightarrow\ T_{1,n}=(2+2)(2-1)\ =\ 4$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$q$} (v0)
   (v0) edge[bend left] node[above]{p} (v1)
   (v1) edge[bend left] node[below]{$q$} (v0) edge[bend left] node[above]{$p$} (v2)
   (v2) edge[bend left] node[below]{$1$} (v1);
\end{tikzpicture}}
\end{figure}

\begin{figure}\centering
\includegraphics[scale=0.55]{mcmc02.png}
\end{figure}

\alert{{\bf Exercício 6:} Fazer p/ $n=3,\ldots n=100$, listar tempos médios. Comparar com os valores dos slides anteriores.}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - 2-SAT - algoritmo probabilístico polinomial}

{\footnotesize{\bf Problema $k$-SAT de decisão:} Dada uma fórmula lógica na FNC onde cada cláusula tem no máximo $k$ literais, existe uma atribuição às variáveis que satisfaça a fórmula?}

\vspace{0.3cm}
Exemplo 2-SAT: \cor{$(x_1\vee x_2)\ \wedge\ (x_1\vee\overline{x_2})\ \wedge\ (\overline{x_1}\vee x_2)$}\\
Exemplo 2-SAT: \alert{$(x_1\vee x_2)\ \wedge\ (x_1\vee\overline{x_2})\ \wedge\ (\overline{x_1}\vee x_2)\ \wedge\ (\overline{x_1}\vee\overline{x_2})$}

{\bf Literatura:} $k$-SAT é poli $O(n^3)$ p/ $k\leq 2$, mas NP-Completo p/ $k\geq 3$. Existem algoritmos mais rápidos p/ $k\leq 2$, mas são mais complicados.

\vspace{0.4cm}
\alert{Algoritmo probabilístico poli $O(n^2)$ p/ 2-SAT usando Cadeia de Markov.}\\
\cor{\footnotesize A partir de uma atribuição qualquer às variáveis, repita $\leq 2\cdot n(n+1)$ vezes:\\
\cor{$\bullet$} Se há cláusula insatisfeita, tome um literal uniform aleatório dela, mudando valor na atribuição. Caso contrário, retorne a atribuição.} \alert{One sided error.}

\vspace{0.4cm}
{\footnotesize{\bf Análise por Cadeia de Markov:} Suponha que a fórmula seja satisfatível e considere uma atribuição fixa que a satisfaz como sendo os valores ``corretos'' das variáveis.\\
{\bf Objetivo:} obter $n$ valores ``corretos'' ou alcançar outra atribuição que satisfaz fórmula.}

\begin{figure}[hbtp]\centering
\scalebox{0.6}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node[cvertex] (v3) at (9,0) {3};
\node at (12,0.5) {$\ldots$};
\node at (12,-.5) {$\ldots$};
\node[cvertex] (v5) at (15,0) {$n-1$};
\node[cvertex] (v6) at (18,0) {$n$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$1/2$} (v0)
   (v0) edge[bend left] node[above]{$1/2$} (v1)
   (v6) edge[in=300,out=240,looseness=0.4] node[above] {1} (v1)
   (v1) edge[bend left] node[below]{$1/2$} (v0) edge[bend left] node[above]{$1/2$} (v2)
   (v2) edge[bend left] node[below]{$1/2$} (v1) edge[bend left] node[above]{$1/2$} (v3)
   (v3) edge[bend left] node[below]{$1/2$} (v2) edge[bend left] node[above]{$1/2$} (11,.5)
   (11,-.5) edge[bend left] node[below]{$1/2$} (v3) (13,.5) edge[bend left] node[above]{$1/2$} (v5)
   (v5) edge[bend left] node[below]{$1/2$} (13,-.5) edge[bend left] node[above]{$1/2$} (v6);
\end{tikzpicture}}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - 2-SAT - algoritmo probabilístico polinomial}

\alert{Algoritmo probabilístico poli $O(n^2)$ p/ 2-SAT usando Cadeia de Markov.}\\
\cor{\footnotesize A partir de uma atribuição qualquer às variáveis, repita $\leq 2\cdot n(n+1)$ vezes:\\
\cor{$\bullet$} Se há cláusula insatisfeita, tome um literal uniform aleatório dela, mudando valor na atribuição. Caso contrário, retorne a atribuição.} \alert{One sided error.}

\vspace{0.3cm}
{\footnotesize{\bf Análise por Cadeia de Markov:} Suponha que a fórmual seja satisfatível e considere uma atribuição fixa que a satisfaz como sendo os valores ``corretos'' das variáveis.\\
{\bf Objetivo:} obter $n$ valores ``corretos'' ou alcançar outra atribuição que satisfaz fórmula.}

\begin{figure}[hbtp]\centering
\scalebox{0.6}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node[cvertex] (v3) at (9,0) {3};
\node at (12,0.5) {$\ldots$};
\node at (12,-.5) {$\ldots$};
\node[cvertex] (v5) at (15,0) {$n-1$};
\node[cvertex] (v6) at (18,0) {$n$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$1/2$} (v0)
   (v0) edge[bend left] node[above]{$1/2$} (v1)
   (v6) edge[in=300,out=240,looseness=0.4] node[above] {1} (v1)
   (v1) edge[bend left] node[below]{$1/2$} (v0) edge[bend left] node[above]{$1/2$} (v2)
   (v2) edge[bend left] node[below]{$1/2$} (v1) edge[bend left] node[above]{$1/2$} (v3)
   (v3) edge[bend left] node[below]{$1/2$} (v2) edge[bend left] node[above]{$1/2$} (11,.5)
   (11,-.5) edge[bend left] node[below]{$1/2$} (v3) (13,.5) edge[bend left] node[above]{$1/2$} (v5)
   (v5) edge[bend left] node[below]{$1/2$} (13,-.5) edge[bend left] node[above]{$1/2$} (v6);
\end{tikzpicture}}
\end{figure}

{\footnotesize Em cláusula insatisfeita, pelo menos 1 literal não está c/ valor correto. Prob $\geq 1/2$ de obter mais um valor correto e prob $\leq 1/2$ de diminuir o número de valores corretos.}

\vspace{0.3cm}
{\footnotesize
Número esperado de passos: $\EE(X)=n^2+n-2$. Repetindo $2n(n+1)$ vezes, temos pela Desigualdade de Markov que a probabilidade de não obter $n$ valores corretos se a fórmula for satisfatível é $\PP(X\geq 2\cdot\EE(X))\leq 1/2$.}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - 3SAT - algoritmo probab exponencial}

\alert{Algoritmo probabilístico expo $O(??)$ p/ 3-SAT usando Cadeia de Markov.}\\
\cor{\footnotesize A partir de uma atribuição qualquer às variáveis, repita no máximo \alert{???} vezes:\\
$\bullet$ Se há cláusula insatisfeita, tome um literal uniform aleatório dela, mudando valor na atribuição. Caso contrário, retorne a atribuição.} \alert{One sided error.}

\vspace{0.4cm}
{\footnotesize{\bf Análise por Cadeia de Markov:} Suponha que a fórmual seja satisfatível e considere uma atribuição fixa que a satisfaz como sendo os valores ``corretos'' das variáveis.\\
{\bf Objetivo:} obter $n$ valores ``corretos'' ou alcançar outra atribuição que satisfaz fórmula.}

\begin{figure}[hbtp]\centering
\scalebox{0.6}{
\begin{tikzpicture}[scale=0.75]
\tikzstyle{cvertex}=[draw,circle,fill=black!10,minimum size=20pt,inner sep=1pt]

\node[cvertex] (v0) at (0,0) {0};
\node[cvertex] (v1) at (3,0) {1};
\node[cvertex] (v2) at (6,0) {2};
\node[cvertex] (v3) at (9,0) {3};
\node at (12,0.5) {$\ldots$};
\node at (12,-.5) {$\ldots$};
\node[cvertex] (v5) at (15,0) {$n-1$};
\node[cvertex] (v6) at (18,0) {$n$};
\path[->,thick]
   (v0) edge[out=120,in=60,looseness=8] node[above] {$2/3$} (v0)
   (v0) edge[bend left] node[above]{$1/3$} (v1)
   (v6) edge[in=300,out=240,looseness=0.4] node[above] {1} (v1)
   (v1) edge[bend left] node[below]{$2/3$} (v0) edge[bend left] node[above]{$1/3$} (v2)
   (v2) edge[bend left] node[below]{$2/3$} (v1) edge[bend left] node[above]{$1/3$} (v3)
   (v3) edge[bend left] node[below]{$2/3$} (v2) edge[bend left] node[above]{$1/3$} (11,.5)
   (11,-.5) edge[bend left] node[below]{$2/3$} (v3) (13,.5) edge[bend left] node[above]{$1/3$} (v5)
   (v5) edge[bend left] node[below]{$2/3$} (13,-.5) edge[bend left] node[above]{$1/3$} (v6);
\end{tikzpicture}}
\end{figure}

{\footnotesize Em cláusula insatisfeita, pelo menos 1 literal não está c/ valor correto. Prob $\geq 1/3$ de obter mais um valor correto e prob $\leq 2/3$ de diminuir o número de valores corretos.}

\vspace{0.3cm}
{\footnotesize
Número esperado de passos: $\EE(X)=\alert{??}$. Repetindo $2\cdot \EE(X)$ vezes, temos pela Desigualdade de Markov que a probabilidade de não obter $n$ valores corretos se a fórmula for satisfatível é $\PP(X\geq 2\cdot\EE(X))\leq 1/2$.}\esp{15}\alert{\bf Exercício !!}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Cadeias de Markov em Grafos}

{\footnotesize
\cor{\bf Periodicidade do estado $i$:} $\max\{d:\ P_{i,i}^n=0, \forall n \mbox{ não divisível por } d\}$.\\
Estados de uma mesma classe tem a mesma periodicidade.

\vspace{0.2cm}
Estado $i$ é aperiódico se \alert{\bf(a)} $P_{i,i}>0$ (laço) ou \alert{\bf(b)} $P_{i,i}^{(k)}>0$ e $P_{i,i}^{(\ell)}>0$ para $k$ e $\ell$ primos entre si ($mdc(k,\ell)=1$).

\vspace{0.2cm}
Seja $G$ um grafo finito não-direcionado conexo.
Seja $M_G$ a \cor {cadeia de Markov induzida por $G$} com matriz de transição com valores $P_{u,v}=1/d(u)$ se $v$ é vizinho de $u$, e 0 caso contrário, onde $d(u)$ é o grau de $u$ em $G$.

\vspace{0.2cm}
$\sum_{v=1}^n P_{u,v}\ =\ d(u)/d(u) = 1$, onde $n$ é o número de vértices de $G$.}

\vspace{0.5cm}
\cor{\bf Lema 6.3/4 (Motwani):} $T_{v,v}\ =\ \frac{2m}{d(v)}=\frac{1}{\pi_v}$, se $G$ é não-bipartido.

\vspace{0.2cm}
{\footnotesize
{\bf Prova:} \alert{$G$ é conexo não-bipartido.} Logo $M_G$ tem ciclos ímpares (e pares) p/ cada vértice. Logo, cada estado (vértice) tem periodicidade 1 e $M_G$ é aperiódica.

\vspace{0.2cm}
$\pi_v\ =\ d(v)/2m$ é solução de $\pi=\pi\cdot P$ e $\sum_{v}\pi_v=1$. Como $M_G$ é finita, recorrente e aperiódica, a solução é única pelo Teorema Fundamental.

\[
(\pi\cdot P)_{v} = \sum_{u}\pi_u\cdot P_{u,v} = \sum_{u\in Adj(v)}\left(\frac{d(u)}{2m}\right)\cdot\left(\frac{1}{d(u)}\right)\ = \sum_{u\in Adj(v)}\frac{1}{2m} = \frac{d(v)}{2m} = \pi_v
\]

$$\sum_{v\in V(G)}\pi_v\ =\ \sum_{v\in V(G)}\frac{d(v)}{2m}\ =\ \frac{1}{2m}\sum_{v\in V(G)} d(v)\ =\ \frac{1}{2m}\cdot 2m\ =\ 1$$}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Cadeias de Markov em Grafos}

{\small Seja $G$ um grafo finito não-direcionado conexo.
Seja $M_G$ a \cor {cadeia de Markov induzida por $G$} com matriz de transição com valores $P_{u,v}=1/d(u)$ se $v$ é vizinho de $u$, e 0 caso contrário, onde $d(u)$ é o grau de $u$ em $G$.}

\vspace{0.3cm}
\cor{\bf Lema 6.3/4 (Motwani):} $T_{v,v}\ =\ \frac{2m}{d(v)}=\frac{1}{\pi_v}$ se $G$ é não-bipartido.

\vspace{0.7cm}
\cor{\bf Lema 6.6 (Motwani):} \cor{$T_{u,v}+T_{v,u}\ =\ 2m\cdot R(u,v)\ \leq\ 2m\cdot d(u,v)$}, onde $u\ne v$, $R(u,v)$ é a resistência efetiva entre $u$ e $v$, e $d(u,v)$ é a distância entre $u$ e $v$ (num arestas em um menor caminho).

\vspace{0.3cm}
Para calcular a \cor{Resistência efetiva} $R(u,v)$, considera-se que cada aresta do grafo representa 1 $\Omega$ (ohm) de resistência e que 1A (ampère) de corrente é introduzido em $u$ e removido de $v$ (ou vice-versa).

\vspace{0.3cm}
\cor{$R(u,v)\leq \ell/k$} se existem $k$ caminhos entre $u$ e $v$ (disjuntos nas arestas) com tamanho no máximo $\ell$ (num arestas).
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{\emph{Markov Chain} - Conectividade em Log-Space}

\cor{Problema USTCON (``\emph{Undirected $s$-$t$ Connectivity}''):} Dado um grafo $G$ não-direcionado e vértices $s$ e $t$, decidir se existe um caminho entre $s$ e $t$.

\vspace{0.3cm}
\cor{Classe RLP (Randomized Log-space Polynomial time):} Problemas de decisão que possuem algoritmo probabilístico de tempo polinomial \cor{e espaço logarítmico} que sempre acerta quando retorna SIM, mas pode errar com probabilidade 1/2 quando retorna NÃO.\esp{13}\alert{RLP $\subseteq$ RP}

\vspace{0.3cm}
\cor{Algoritmo RLP para USTCON:} O espaço não conta a memória da entrada, que é dada numa ``read-only tape''.

\vspace{0.3cm}
\alert{Simular passeio aleatório de tam $2n^3$ sobre (a cadeia de Markov de) $G$ começando em $s$. Se encontrou $t$, retorne SIM. Senão, retorne NÃO.}

\vspace{0.3cm}
$T_{s,t}\leq T_{s,t}+T_{t,s}\leq 2m\cdot d(s,t)\leq 2m\cdot(n-1)\leq n^3$.\\
Pela Desigualdade de Markov, a probabilidade de errar é $\leq\frac{n^3}{2n^3}=1/2$.

\vspace{0.3cm}
{\bf Espaço utilizado:} contador inteiro até $2n^3$ (espaço $\log_2 2n^3$), vértice atual e próximo vértice.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Técnicas Algébricas - \emph{Fingerprint}}

%http://www.cs.cmu.edu/~avrim/451/lectures/lect0923.pdf
%https://www.probabilitycourse.com/chapter11/11_2_4_classification_of_states.php
%https://machinelearningmastery.com/markov-chain-monte-carlo-for-probability/
%https://towardsdatascience.com/basics-of-markov-chain-monte-carlo-algorithms-a53a6b3a763d
%https://cp-algorithms.com/algebra/primality_tests.html

Técnica 1 já vista em 2 problemas:\\
Verificar Igualdade de polinômios\ \ e\ \ Verificar produto de matrizes.

\vspace{0.5cm}
\cor{\it Fingerprint 1:} Para decidir se 2 objetos são iguais, ao invés de comparar os objetos por completo, tratar os objetos como funções, gerar \alert{parâmetro aleatório} e comparar os valores das funções com esse parâmetro.

\vspace{0.5cm}
\cor{\it Fingerprint 2:} Para decidir se 2 objetos são iguais, ao invés de comparar os objetos por completo, tratar os objetos como números inteiros, gerar um \alert{número primo aleatório} e comparar os números nos \alert{inteiros módulo $p$}.

\vspace{0.5cm}
\small
Como gerar números primos aleatórios entre 2 e $n$: gera inteiro aleatório uniforme e testa se é primo.\\
{\bf Chebyshev \esp{20.5}(1848):}\ \ \cor{$NPrimos(\leq n)\ \ \geq\ \ (1/3)(n/\ln n)$.}\\
{\bf Prime Number Theorem (1896):}\ \ \cor{$NPrimos(\leq n)\ \ \approx\ \ n/\ln n$.}\\
Número esperado de buscas por um número primo: $\leq 3\ln n$.\\
Tempo de checar se um inteiro é primo:  $\tilde{O}((\log n)^3)$ ou $\tilde{O}((\log n)^6)$.\\
Tempo esperado total: $\tilde{O}((\log n)^7)=O((\log n)^{7+\varepsilon})$.\alert{\tiny\esp{10}Primality test (Wikipedia)}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Fingerprint 1: Verificar Igualdade de Polinômios}

\alert{\bf Problema:} Alice e Bob tem polinômios $A(x)$ e $B(x)$ de grau $n$, resp. Decidir se $A(x)=B(x)$ ``\emph{transmitindo poucos dados}''.\\
Considere que um deles não tem acesso aos coeficientes do seu polinômio.\\
{\bf Exemplo:} $(x+1)(x-2)(x+3)(x-4)\ =\ x^4+7x^2-24$\ ?\ \ \ ($n=4$)
\vspace{0.6cm}

\cor{\bf Algoritmo:} Escolher inteiro $r$ em $\{1,\ldots,100n\}$ aleatório uniforme. Transmitir $r$ e $A(r)$ para Bob, que deve comparar com $B(r)$.\\
Se iguais, retornar SIM. Caso contrário, retornar NÃO.\\
\cor{Bits transmitidos: $O(\log((100n)^n\cdot n)) = O(n\log n)$}.
\vspace{0.2cm}

{\bf Análise:} Se \cor{SIM ($A(x)=B(x)$)}, o algoritmo acerta.\\
Se \alert{NÃO ($A(x)\ne B(x)$)} e $A(r)\ne B(r)$, o algoritmo acerta.\\
O algoritmo só erra se for \alert{NÃO ($A(x)\ne B(x)$)}, mas $A(r)=B(r)$.\\
\cor{\textit{One-sided error false biased} (acerta ao dizer NÃO)}: \alert{Classe co-RP}.
\vspace{0.2cm}

{\bf Probabilidade de errar:} $r$ deve ser raiz de $A(x)-B(x)$, que tem grau $\leq n$ e no máximo $n$ raizes. Probabilidade de erro $\leq 1/100$

\vspace{0.2cm}
{\bf Amplificação:} Repetindo $k$ vezes com reposição: $\PP($erro$)\leq (1/100)^k$\\
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Fingerprint 1: Verificar igualdade de matrizes}

\alert{\bf Problema:} Alice e Bob tem matrizes $n\times n$ $A$ e $B$, respectivamente. Decidir se $A=B$\ \ ``\emph{transmitindo poucos dados}''.

\vspace{0.3cm}
\cor{\bf Algoritmo:} Escolher vetor $r=(r_1,\ldots,r_n)$ em $\{0,1\}^n$ aleatório uniforme. Transmitir $r$ e $A\cdot r$ para Bob, que deve comparar com $B\cdot r$.\\
Se igual, SIM. C.C, NÃO.\ \ \cor{Bits transmitidos: $O(n)$}.

\vspace{0.3cm}
{\bf Análise:} Se \cor{SIM ($A=B$)}, o algoritmo acerta.\\
Se \alert{NÃO ($A\ne B$)} e $A\cdot r\ne B\cdot r$, o algoritmo acerta.\\
O algoritmo só erra se for \alert{NÃO ($A\ne B$)}, mas $A\cdot r=B\cdot r$.\\
\cor{\textit{One-sided error false biased} (acerta ao dizer NÃO)}: \alert{Classe co-RP}.

{\footnotesize
\vspace{0.3cm}
{\bf Probabilidade de errar:} Seja $D=A-B\ne 0$. Logo $D$ tem valor $\ne 0$ (para simplificar, suponha que $d_{1,1}\ne 0$).
\[
A\cdot r=B\cdot r\ \cor{\Rightarrow}\ D\cdot r=0\ \cor{\Rightarrow}\ \sum_{k=1}^n d_{1,k}\cdot r_k=0\ \cor{\Rightarrow}\ r_1=-\sum_{k=2}^n \frac{d_{1,k}\cdot r_k}{d_{1,1}}
\]
$\PP(r_1$ ser este valor $|\ r_2,\ldots,r_n)\leq 1/2$. Logo $\PP$(erro)$\leq 1/2$. 
\vspace{0.2cm}

{\bf Amplificação:} Repetindo $k$ vezes com reposição: $\PP($erro$)\leq (1/2)^k$}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Fingerprint 2: Verificar igualdade de palavras (\emph{strings})}

\alert{\bf Problema:} Alice/Bob tem sequências de bits $(a_1,\ldots,a_n)$ e  $(b_1,\ldots,b_n)$. Verificar se são iguais com ``\emph{transmissão de poucos dados}''.

\vspace{0.5cm}
\cor{\bf Algoritmo:} Seja $a=\sum_{i=1}^n a_i\cdot 2^{i-1}$ e $b=\sum_{i=1}^n b_i\cdot 2^{i-1}$.\\
Seja $F_p(x)=(x \mod p)$, onde $p$ é um primo aleat entre 2 e $ m=tn\ln tn$ para um $t=O(n)$. Alice transmite $p$ e $F_p(a)$ para Bob, que deve comparar com $F_p(b)$.  \alert{Número de bits transmitidos: $O(\log p)=O(\log n)$.}

\vspace{0.3cm}
\cor{
$F_p(a)\ne F_p(b)\ \Rightarrow\ a\ne b$\\
$F_p(a)  = F_p(b)\ \Rightarrow\ (a=b)\ $ ou $\ p$ é divisor de $|a-b|\leq 2^n$}\\

\vspace{0.3cm}
$|a-b|$ tem $\leq n$ divisores primos. Logo \alert{\footnotesize(Chebyshev: $NPrimos_{\leq  m}\geq m/3\ln m$)}
{\small
\[
\cor{\PP(F_p(a)=F_p(b)\ |\ a\ne b)}\leq \frac{n}{NPrimos_{\leq m}}\leq\frac{n}{ m/3\ln m}\leq\frac{3}{t}\cdot\left(1+\frac{\ln\ln tn}{\ln tn}\right)\cor{\leq\frac{5}{t}}
\]}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Fingerprint 2: Pattern Matching}
{\small
\alert{\bf Problema:} Dadas palavras \cor{$X=x_1\ldots x_n$} e  \alert{$Y=y_1\ldots y_{k\leq n}$} num mesmo alfabeto fixo $\Sigma$, checar se o padrão \alert{$Y$} ocorre contiguamente em \cor{$X$}.

\vspace{0.2cm}
\cor{{\bf Força bruta:} Tempo $O(n\cdot k)$}.\esp{2}
\cor{{\bf Knuth-Morris-Pratt:} Tempo $O(n$+$k)=O(n)$}

\vspace{0.2cm}
Seja \cor{$X(j)=x_{j}x_{j+1}\ldots x_{j+k-1}$} para $j\in\{1,\ldots,n-k+1\}$.
Para simplificar a explicação, seja $\Sigma=\{0,1\}$.
Considere \cor{$X(j)$} e \alert{$Y$} como inteiros com $k$ bits.
{\bf Objetivo:} checar se existe $j$ tal que $\cor{X(j)}=\alert{Y}$.

\vspace{0.2cm}
{\bf Fato:} $X_{j+1}=2\cdot(X(j)-2^{k-1}x_j)\ +\ x_{j+k}$.
Dado $p$, seja $F_p(x)=(x \mod p)$. {\bf Logo:}
$F_p(X_{j+1})=2\cdot(F_p(X(j))-2^{k-1}x_j)\ +\ x_{j+k}\ \ \mod\ p$.

\vspace{0.2cm}
\cor{\bf Alg. Monte Carlo $O(n+k)$:}
Sorteie $p$ primo aleat entre 2 e $m=n^2k\ln n^2k$.
Calcule todos os valores $F_p(\cor{X(j)})$ para $j\in\{1,\ldots,n-k+1\}$.\\
Se algum for igual $F_p(\alert{Y})$, retorne SIM. Caso contrário, retorne NÃO.

\vspace{0.2cm}
Para um certo $j$ fixo:
\cor{
$F_p(Y)\ne F_p(X(j))\ \Rightarrow\ $ sem padrão $Y$ começando em $j$\\
$F_p(Y)  = F_p(X(j))\ \Rightarrow\ (\mbox{com padrão})\ $ ou\ ($p$ é divisor de $|Y-X(j)|\leq 2^k$)}\\

\vspace{0.2cm}
$|Y-X(j)|$ tem $\leq k$ divisores primos. Logo \alert{\footnotesize(Chebyshev: $NPrimos_{\leq  m}\geq m/3\ln m$)}
{\small
\[
\cor{\PP(\ F_p(Y)=F_p(X(j))\ \ |\ \ Y\ne X(j)\ )}\leq \frac{k}{NPrimos_{\leq m}}\leq\frac{k}{m/3\ln m}\leq\frac{5}{n^2}
\]}
Prob $\leq\frac{5}{n}$ de $\exists j$ com $F_p(Y)=F_p(X(j))$ apesar de $Y$ não ser padrão.
}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Fingerprint 2: Pattern Matching}

{\small
\cor{\bf Alg. Monte Carlo $O(n+k)$:}
Sorteie $p$ primo aleat entre 2 e $m=n^2k\ln n^2k$.
Calcule todos os valores $F_p(\cor{X(j)})$ para $j\in\{1,\ldots,n-k+1\}$.\\
Se algum for igual $F_p(\alert{Y})$, retorne SIM. Caso contrário, retorne NÃO.\\
Probabilidade de erro $\leq 5/n$.

\vspace{0.7cm}
\cor{\bf Alg. Las Vegas $O(n+k)$:}
Roda o algoritmo Monte Carlo e, se apontar um padrão $F_p(\cor{X(j)})=F_p(\alert{Y})$, comparar as strings $\cor{X(j)}$ e $\alert{Y}$ em tempo $O(k)$.\\
Se igual, retorna SIM. Caso contrário, reinicia tudo com Força Bruta.\\
Probabilidade de erro $=0$.

\vspace{0.5cm}
\alert{Tempo esperado do Algoritmo Las Vegas:}
\[
\leq \left(1-\frac{5}{n}\right)\cdot O(n+k)\ +\ \left(\frac{5}{n}\right)\cdot O(n\cdot k)\ =\ O(n+k)
\]
}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Teste de Primalidade de Fermat}

\alert{\bf Problema:} Dado um número inteiro $n$, verificar se é primo.

\vspace{0.05cm}
\cor{{\bf Força bruta:} Testar divisibilidade de $n$ com todo inteiro $k$ de 2 até $\sqrt{n}$.}

\vspace{0.15cm}
\cor{{\bf Teste de Primalidade de Fermat:}\ \ Tempo $\tilde{O}((\log n)^2)$}\ \ \ \ \alert{\footnotesize soft-O notation}\\
$\ZZ_n=\{0,1,\ldots,n-1\}$. \esp{5} $\ZZ_n^{cp}\ \subseteq\ \ZZ_n:$ coprimos de $n$;\ \ $mdc(x,n)=1$.

\vspace{0.1cm}
{\bf Fermat's Little Theorem:}\esp{2}\cor{$n$ primo $\Rightarrow \forall a\in\ZZ_n^{cp}:\ a^{n-1}\equiv 1 \mod n$.}\\
\esp{36}\cor{$n$ composto $\Leftarrow \exists a\in\ZZ_n^*:\ a^{n-1}\not\equiv 1 \mod n$.}\\

\vspace{0.1cm}
{\bf Lema 14.28 (Motwani):}\esp{2}\cor{Se $n$ é composto não-\alert{Carmichael}, então\\
pelo menos metade dos elementos $a\in\ZZ_n^{cp}$ satisfazem $a^{n-1}\not\equiv 1 \mod n$}\\

\vspace{0.1cm}
{\bf Definição:} $n$ é \alert{Carmichael} se é composto e $a^{n-1}\equiv 1 \mod n,\ \forall a\in\ZZ_n^{cp}$.\\
Números de \alert{Carmichael} são raros: só 646 entre 1 e $10^9$.\\
$\alert{561} \esp{3}(3\cdot 11\cdot 17)$,\ \ 
$\alert{1105}\esp{1}(5\cdot 13\cdot 17)$,\ \ 
$\alert{1729}\esp{1}(7\cdot 13\cdot 19)$,\ \ 
$\alert{2465}\esp{1}(5\cdot 17\cdot 29)$,\ \ 
$\alert{2821}\esp{1}(7\cdot 13\cdot 31)$,\ \ 
$\alert{6601}\esp{1}(7\cdot 23\cdot 41)$,\ \ 
$\alert{8911}\esp{1}(7\cdot 19\cdot 67)$.

\vspace{0.1cm}
\cor{\bf Alg. Fermat:} Sorteia $2\leq a\leq n-2$. Se $mdc(a,n)\ne 1$, retorne \alert{NÃO}.\\
Testa se $a^{n-1}\equiv 1 \mod n$.\esp{2.5}Se SIM, retorne \cor{SIM}.\esp{3}C.C., retorne \alert{NÃO}.

{\small\vspace{0.1cm}
$n$ primo\esp{27.5} $\Rightarrow$\ Fermat acerta 100\%.\\
$n$ composto não-Carmichael\ $\Rightarrow$\ Fermat acerta com prob $\geq 1/2$.\\
$n$ composto \esp{6}Carmichael\ $\Rightarrow$\ Fermat acerta se $mdc(a,n)\geq 2$.}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Teste de Primalidade de Fermat}

\alert{\bf Problema:} Dado um número inteiro $n$, verificar se é primo.

\vspace{0.2cm}
\cor{{\bf Teste de Primalidade de Fermat:}\ \ Tempo $\tilde{O}((\log n)^2)$}\ \ \ \ \alert{\footnotesize soft-O notation}\\
$\ZZ_n=\{0,1,\ldots,n-1\}$. \esp{5} $\ZZ_n^{cp}\ \subseteq\ \ZZ_n:$ coprimos de $n$;\ \ $mdc(x,n)=1$.

\vspace{0.2cm}
{\bf Alg. Fermat:} Sorteia $2\leq a\leq n-2$. Se $mdc(a,n)\ne 1$, retorne \alert{NÃO}.\\
Testa se $a^{n-1}\equiv 1 \mod n$.\esp{2.5}Se SIM, retorne \cor{SIM}.\esp{3}C.C., retorne \alert{NÃO}.

\vspace{0.4cm}
\cor{\bf Algoritmo de Euclides} para calcular $mdc(a,n)$. Tempo $O(\log n)$.

\vspace{0.4cm}
\cor{\bf Algoritmo ExponenciaçãoBinária (inteiros $base,\ exp,\ n)$}\\
\esp{08}$result = 1$;\esp{5}$base\ \leftarrow\ base\ \%\ n$\\
\esp{08}\textbf{enquanto} ($exp\ >\ 0$)\\
\esp{16}\textbf{se} ($exp\ \&\ 1$):\ \ \ $result\ \leftarrow\ (result \cdot base)\ \%\ n$\\
\esp{16}$base\ \leftarrow\ (base \cdot base)\ \%\ n$\\
\esp{16}$exp\ \ \leftarrow\ exp >> 1$\\
\esp{08}\textbf{retorne} $result$\esp{30}\alert{\tiny Binary Exponentiation (Wikipedia)}\\
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Teste de Primalidade de Miller-Rabin}

\alert{\bf Problema:} Dado um número inteiro $n$, verificar se é primo.

\vspace{0.3cm}
\alert{$n$ ímpar} $\Rightarrow$ \alert{$n-1=2^s\cdot d$} para $s\geq 1$ e $d$ ímpar.
\cor{\small
$\begin{array}{rl}
a^{n-1} \equiv 1 \bmod n &\Longleftrightarrow a^{2^s d} - 1 \equiv 0 \bmod n \\
&\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-1} d} - 1) \equiv 0 \bmod n \\
&\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) (a^{2^{s-2} d} - 1) \equiv 0 \bmod n \\
&\quad\vdots \\
&\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) \cdots (a^{d} + 1) (a^{d} - 1) \equiv 0 \bmod n \\
\end{array}$}

\vspace{0.1cm}
Se $n$ é ímpar, um desses fatores é múltiplo de $n$.

\vspace{0.3cm}
\cor{\bf Alg. Miller-Rabin:} Sorteia $2\leq a\leq n-2$. Calcular $d$ e $s$.\\
Testa se $a^d\equiv 1 \mod n$ ou $a^{2^rd}\equiv -1 \mod n$ para algum $0\leq r<s$.\\
Se SIM, retorne \cor{SIM}. C.C., retorne \alert{NÃO}.

{\small\vspace{0.2cm}
$n$ primo\esp{3} $\Rightarrow$\ Miller-Rabin acerta 100\%.\\
$n$ composto\ $\Rightarrow$\ Miller-Rabin acerta com prob. $\geq 3/4$.\\
{\bf Primality é co-RP e Compositeness é RP, ambos c/ tempo $\tilde{O}((\log n)^3)$.}}

\vspace{0.3cm}
\alert{\bf Obs:} Teste de Primalidade AKS: determinístico tempo poli $\tilde{O}((\log n)^6)$.\\
Artigo famoso ``PRIMES is in P'', 2002. Prêmio G\"odel-2006.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Teste de Primalidade de Miller-Rabin}

\alert{$n$ ímpar} $\Rightarrow$ \alert{$n-1=2^s\cdot d$} para $s\geq 1$ e $d$ ímpar.
\cor{\footnotesize
$\begin{array}{rl}
a^{n-1} \equiv 1 \bmod n &\Longleftrightarrow a^{2^s d} - 1 \equiv 0 \bmod n \\
&\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-1} d} - 1) \equiv 0 \bmod n \\
&\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) (a^{2^{s-2} d} - 1) \equiv 0 \bmod n \\
&\quad\vdots \\
&\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) \cdots (a^{d} + 1) (a^{d} - 1) \equiv 0 \bmod n \\
\end{array}$}

\vspace{0.4cm}
\cor{\bf Algoritmo Cálculo-s-d\ (inteiro $n$)}\\
\esp{8}  $s = 0$;\ \ \ \ $d = n - 1$\\
\esp{8}  \textbf{enquanto} $((d \& 1) = 0)$\\
\esp{16} $d \leftarrow d>>1$;\ \ \ \ $s\ \leftarrow\ s+1$

\vspace{0.4cm}
\cor{\bf Algoritmo Composto\ (inteiros $n$, $a$, $d$, $s$)}\\
\esp{8} $R\ \leftarrow$\ ExponenciaçãoBinária$(a, d, n)$\\
\esp{8} \textbf{se} ($R=1$) \textbf{ou} ($R=n-1$):\ \ \ \textbf{retorne} \alert{falso}\\
\esp{8} \textbf{para} $t=1$ \textbf{até} $s-1$\\
\esp{16}$R\ \leftarrow\ (R \cdot R)\ \%\ n$\\
\esp{16}\textbf{se} ($R=n-1$):\ \ \ \textbf{retorne} \alert{falso}\\
\esp{8} \textbf{retorne} \cor{verdadeiro}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Teste de Primalidade de Miller-Rabin (Determístico)}

\alert{\bf Problema:} Dado um número inteiro $n$, verificar se é primo.

\vspace{0.3cm}
\cor{\bf Alg. Miller-Rabin:} Sorteia $2\leq a\leq n-2$. Calcular $d$ e $s$.\\
Testa se $a^d\equiv 1 \mod n$ ou $a^{2^rd}\equiv -1 \mod n$ para algum $0\leq r<s$.\\
Se SIM, retorne \cor{SIM}. C.C., retorne \alert{NÃO}.

{\small\vspace{0.2cm}
$n$ primo\esp{3} $\Rightarrow$\ Miller-Rabin acerta 100\%.\\
$n$ composto\ $\Rightarrow$\ Miller-Rabin acerta com prob. $\geq 3/4$.\\
{\bf Primality é co-RP e Compositeness é RP, ambos c/ tempo $\tilde{O}((\log n)^3)$.}}

\vspace{0.3cm}
\alert{\bf Versão Determinística (32 bits):} $a=2,3,5,7,11$ (5 primeiros primos).\\
\alert{\bf Versão Determinística (64 bits):} $a=2,\ldots,37$\ \ (12 primeiros primos).\\

\vspace{0.3cm}
\alert{\bf Obs:} Teste de Primalidade AKS: determinístico tempo poli $\tilde{O}((\log n)^6)$.\\
Artigo famoso ``PRIMES is in P'', 2002. Prêmio G\"odel-2006.

\vspace{0.5cm}
\alert{\footnotesize{\bf Exercício:} Implementar algoritmos de teste de primalidade de Fermat e Miller-Rabin e calcular experimentalmente (com pelo menos 100000 execuções para $n$ {\bf composto} aleatório uniforme entre 100 e 100000) as probabilidades de erro para um sorteio apenas do inteiro $2\leq a\leq n-2$. e comparar com $1/2$ e $1/4$, respectivamente.}
}


\end{document}