\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\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$:} $=mdc\{n:\ P_{i,i}^n>0\}=$\\ $=\min\{p: \forall n, P_{i,i}^n>0 \Rightarrow n \mbox{ é múltiplo de } p\}$\\ 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. Existência de ciclo par e ciclo ímpar contendo o vértice implica aperiodicidade. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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 limite $\pi=\pi\cdot P$ com $\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. Então a proporção de longa duração de tempo converge:\\ \cor{$$\lim_{t\to\infty} \frac{N(i,t)}{t}\ =\ \pi_i$$} \end{itemize} \vspace{0.1cm} Se a cadeia é periódica, há solução única para $\pi=\pi\cdot P$ com $\pi_i>0\ (\forall i)$ satisfazendo (c) e (e): proporção longa duração de tempo converge p/ $\pi$. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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 Direcionados} {\footnotesize Seja $G$ um grafo direcionado com $n$ vértices e $m$ arestas direcionadas.\\ Sejam $d^-(v)$ e $d^+(v)$ são os graus de entrada e saída de $v$ em $G$. \vspace{0.2cm} Seja $M_G$ a \cor{cadeia de Markov induzida por $G$} com matriz de transição $P_{u,v}=1/d^+(u)$ se $v$ é vizinho de $u$, e 0 caso contrário. \vspace{0.0cm} \[ \sum_{v=1}^n P_{u,v}\ =\ \sum_{v\in Adj^+(u)}\frac{1}{d^+(u)}\ =\ \frac{d^+(u)}{d^+(u)}\ =\ 1. \]} \vspace{0.0cm} \cor{\bf Teorema:} Seja $G$ um grafo direcionado finito fortemente conexo com ciclos pares e ímpares tal que $d^+(v)=d^-(v)$ para todo vértice $v$. Então $\pi_v\ =\ \frac{d^+(v)}{m}$ e $T_{v,v}\ =\ \frac{m}{d^+(v)}$. \vspace{0.2cm} {\footnotesize {\bf Prova:} $M_G$ é finita, aperiódica (pois tem ciclos pares e ímpares) e irredutível (pois é fortemente conexa). Logo pelo Teorema Ergódico: \vspace{0.2cm} $\pi_v\ =\ d^+(v)/m$ é a solução única de $\pi=\pi\cdot P$ e $\sum_{v}\pi_v=1$, pois: \[ (\pi\cdot P)_{v} = \sum_{u}\pi_u\cdot P_{u,v} = \sum_{u\in Adj^-(v)}\frac{d^+(u)}{m}\cdot\frac{1}{d^+(u)}\ = \sum_{u\in Adj^-(v)}\frac{1}{m} = \frac{d^-(v)}{m} = \frac{d^+(v)}{m} = \pi_v \] $$\sum_{v\in V(G)}\pi_v\ =\ \sum_{v\in V(G)}\frac{d^+(v)}{m}\ =\ \frac{1}{m}\sum_{v\in V(G)} d^+(v)\ =\ \frac{1}{m}\cdot m\ =\ 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}