\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{Probabilidade e Processos Estocásticos}

\begin{block}{Ementa}
Conceitos básicos de Probabilidade, Esperança e Variância, Leis Fraca e Forte dos Grandes Números, Convergência de Distribuições de Probabilidade e o Teorema Central do Limite, Processos Estocásticos Estacionários e seus Teoremas Ergódicos, Movimento Browniano, Cadeias de Markov, Campos Aleatórios de Markov em Grafos.
\end{block}


\begin{block}{Bibliografia}
\begin{itemize}
\item Sheldon Ross. {\bf Introduction to Probability Models}, AP, 2010.
\item S. Ross. {\bf Probability Models for Computer Science}, AP, 2002.
\item P. Fernandez. {\bf Introdução a Processos Estocásticos}, IMPA, 2014.
\item M. Alencar. {\bf Probabilidade e Processos Estocásticos}, Érica, 2008.
\item  J. Albuquerque, J. Fortes, W. Finamore. {\bf Probabilidade, Variáveis Aleatórias e Processos Estocásticos}, Editora Interciência, 2018.
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{
\frametitle{Probabilidade e Processos Estocásticos - Bibliografia}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 Probabilidade e Processos Estocásticos interessantes
\item Distribuições Discretas: Binomial, Geométrica, HiperGeométrica, Poisson, Binomial Negativa,...
\item \cor{Aplicações:} Problemas do Colecionador de Figurinhas
\item \alert{E mais:} Cadeias de Markov, outros Processos Estocá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{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{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{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{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{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.\\
\cor{É na linha 3 onde são feitas comparações entre elementos do vetor.}\\
\textbf{Qual é o número esperado de execuções da linha 3?}

\vspace{0.3cm}
Para cada valor de $k$, a linha 3 é 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 3?

\vspace{0.3cm}
Para cada valor de $k$, a linha 3 é 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 3 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 3: $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{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$:} $\min\{p: n \mbox{ é múltiplo de } p \Rightarrow  P_{i,i}^n>0,\ \forall n\}$.\\
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 Ergódico}

\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).
}




\end{document}