\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage[brazil,brazilian]{babel}
%\usepackage{abnt-alf}

%\mode{presentation}
\usetheme{Ilmenau}
%\usetheme{Rochester}

%\mode\usepackage{graphicx} %Para incluir graficos EPS, PS
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
 
%\usepackage{setspace} %define o espacamento de linhas

\begin{document}
\title{\textbf{Métodos Computacionalmente Intensivos}}
\author{Stuart Coles,Gareth Roberts e Soren Jarner\\
\small{Orientador: Prof. PhD. Paulo Justiniano Ribeiro Jr. }}
%\sloppy % arruma a separação de silabas do fim da linha

\begin{frame}
% SLIDE 1: Título
	\titlepage
\end{frame}

\section{Capitulo 1}
\begin{frame}{Capitulo1}
%slide 2
\begin{itemize}
\item $1.1$ Introdução
\item Âmbito do curso
\item Uma classificação inicial de métodos intensivos aplicada a estatística é:\\ 
 $1.$Computadores para exploração gráfica de dados \\
 $2.$Computadores para modelagem de dados\\ 
 $3.$Computadores para inferência.\\ 
Há obviamente alguma sobreposição destes três, mas neste curso pretendo focar principalmente na 
terceira das opções acima.  Isto é, que terá por objtivo a compreensão de técnicas de computador que  requerem algoritmos inovadores para aplicar inferências padrão.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Capitulo 1}
%SLIDE 3: Capitulo 1
\begin{itemize}
\item Assim, a compreensão dos princípios subjacentes ao diferentes algoritmos pode  freqüentemente levar a uma melhor compreensão de inferência, probabilidade e estatística em geral. Em suma, as técnicas não são apenas um meio para um fim.  Eles têm o seu próprio valor intrínseco como estatística. 
\item Todos os exemplos serão manipulados usando funções R simples - a maneira mais eficiente de implementar as diversas técnicas.
\item 1.2 Computadores como máquinas de inferência 
\item 1.3 Referências
Stochastic simulation, B. Ripley.  \\
Bootstrap methods and their application, AC Davinson and DV Hinkley \\
Tools for statistical inference, M. Tanner. \\
\item 1.4 Confirmação
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Capitulo 2}
%SLIDE 4:introd
\begin{itemize}
\item \textbf{Simulação} {2.1 Introdução}
\begin{itemize}
\item Neste capítulo, vamos olhar diferentes técnicas de simulação de distribuições e processo estocastico.
\item 2.2 Problemas na simulação
O papel da simulação é gerar dados que temos (para todos os efeitos) das propriedades estatísticas de algum modelo especifico. Este 
gera duas questões:
1. Como fazê-lo, e
2. Como fazê-lo de forma eficiente.
\item Vamos ilustrar a idéia, simplesmente com um bem conhecido exemplo.
\end{itemize}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%
\begin{frame}{Agulha de Buffon }
%\SLIDE 5
\begin{itemize} 
\item Nós vamos começar com uma experiência de simulação que é intrinsecamente nada a ver com computador. Talvez a experiência de simulação mais famosa é a agulha de Buffon,
concebido para calcular (não muito eficaz) uma estimativa de $\pi$. \\
Há também um número de maneiras que a experiência pode ser melhorada para dar melhores estimativas, que irá destacar o princípio geral do projeto,
experimentos simulados para alcançar melhor precisão no sentido de minimizar a variabilidade estatística.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Agulha de Buffon}
%SLIDE 6:
\begin{itemize}
\item A experiência  de Buffon consiste em jogar ao acaso agulhas em um grid de retas paralelas. Sabendo a distância \textit{d} entre elas e o comprimento \textit{l} da agulha , 
calcula-se a probabilidade delas se cruzarem e com o valor obtido, estima-se a constante $\pi$. Repetimos este experimento $n$ vezes, e contagem $R$, o número de vezes que a agulha cruza uma linha. 
\item $l \leq d$
\item $\rho = \textit{l}/ \textit{d}$
\item $\phi=1 / \pi$,  uma estimativa de $\phi$ é 
\item $\hat{\phi_0} = \hat{p}/2 \rho$ onde $\hat{p}=R/n$
\end{itemize}
\end{frame}
%%
\begin{frame}{Agulha de Buffon}
%SLIDE 7:
\begin{itemize}
\item $\hat{\pi_0}=1 / \hat{\phi_0}=2 \rho / \hat{\textit{p}}$ estimativas de $\pi$
\item Ao jogar a agulha aleatoriamente pressupoem que $x\sim U(0,d)$ e $\theta \sim U(0,\pi)$ onde:
\item $p=Pr$ (agulha intercepta o grid)
\item $=1/ \pi \int_{0}^{\pi}$ Pr(agulha intercepta $\mid \theta=\phi)d\phi$
\item $=1/ \pi \int_{0}^{\pi} (2/d*l/2 \sin \theta)d\theta$
\item $2l/ \pi d={2 \rho \phi}$
\end{itemize}
\end{frame}

\begin{frame}{Agulha Buffon}
%SLIDE 8
\begin{itemize}
\item Uma pergunta natural é saber como otimizar o tamanho relativo de $l$ e $d$. 
\item Para resolver isso, precisamos considerar a variabilidade do estimador $\hat{\phi_0}$. 
\item Agora, $R \sin Bin(n,p)$, assim $Var(\hat{p})= p*(1-p)/n $. 
\item Deste modo $Var(\hat{\phi_0}) = 2 \rho \phi(1-2 \rho \phi)/ 4 \rho^{2} n = \phi^{2} (1/2{\rho\phi}-1)/n$ 
\item O que é minimizado (para$\rho \leq 1$) quando $\rho = 1$. 
\item Ou seja, devemos definir $l = d$ para otimizar a eficiência. 
\item Então $(\hat{\phi_0}= p^{2})/2$,  com $Var(\hat{\phi_0})= (\phi/2 -\phi^2)/n$. 
\item R
\end{itemize}
\end{frame}
\begin{frame}{Agulha Buffon}
%SLIDE 9
\begin{itemize}
\item Resulta $Var(\hat{\phi}) \thickapprox\pi^{4} Var(\hat{\phi_0}) \thickapprox 5.63/n$ 
\item A figura $2$ mostra $5000$ simulações cada.
\end{itemize}
\end{frame}

\begin{frame}{Agulha de Buffon }
%\SLIDE 10
\begin{itemize} 
\item 1. Usando uma grid  retângular ou quadrado (o que é melhor?) 
e número baseando a estimativa sobre o cruzamentos com uma ou ambas as linhas horizontais ou verticais. 
\item 2. Usando uma cruz em vez de uma agulha. 
\item 3. Usando uma agulha de tamanho maior do que a separação da rede. 
\item Assim, apenas para re-iteração, o ponto é que a simulação pode ser usada para responder a problemas interessantes, mas cuidado com a forma  pode ser necessário para alcançar até mesmo eficiência.
\end{itemize}
\end{frame}

\begin{frame}{2.4 Ingredientes Bruto}
%SLIDE 11
A matéria-prima para qualquer exercício de simulação é dígitos aleatórios: transformação ou outros tipos de manipulação pode então ser aplicado para criar simulações de distribuições mais complexos ou sistemas. 
Assim, como pode dígitos aleatórios ser gerados? 
Deve ser reconhecido que qualquer tentativa de algoritmos para simular a aleatoriedade é apenas : um imitador. 
\begin{itemize}
\item Dividindo essa seqüência M dá uma seqüência $U_{I}$, que são considerados como realizações distribuição Uniforme$ U[0, 1]$. 
\end{itemize}
\end{frame}

\begin{frame}{2.4 Ingredientes Bruto}
%SLIDE 12
Por definição, se a seqüência gerada é determinista, então não há aleatóriedade.  Assim, o truque 
é a utilização de algoritmos que geram seqüências de números que possam todos os testes de aleatoriedade (a partir da distribuição exigida ou processo), apesar de sua derivação determinista. 
A técnica mais comum é usar um gerador congruente. Isso gera uma seqüência de inteiros, através do algoritmo.
$X_{i}=aX_{i-1}$ (Mod M)
\begin{itemize}
\item Dividindo essa seqüência M dá uma seqüência $U_{I}$, que são considerados como realizações distribuição Uniforme$ U[0, 1]$. 
\end{itemize}
\end{frame}


\begin{frame}{2.5 Simulando distribuições especiais}
%SLIDE 13
Nesta seção, olhar para formas de simular os dados de uma  distribuição F univariada especial , 
com base numa amostra simulada $U_{1}, U_{2},..., U_{n}$ da distribuição $U [0, 1]$.
\textit{2.5.1 Inversão}
Este é o mais simples de todos os procedimentos, e nada mais é do que uma simples aplicação de  
probabilidade de transformada integral: se $X\thicksim F $, então $F(X)\thicksim U [0, 1]$, por
isso, a inversão se $U\thicksim U [0, 1]$, então $F^{-1}(U)\thicksim F$. Assim, definindo 
$x_{i} = F^{-1}(ui)$, gera uma seqüência de realizações independentes de F.\\ 
A figura ilustra como isso funciona. (R)
\end{frame}

\begin{frame}{Inversão}
%SLIDE 14
Onde a distribuicao da funcao inversa $F^{-1}$.Por exemplo, para simular a distribuição exponencial,
temos $F(x) = 1-exp(-\lambda x)$, então $F ^{-1}(u)=-\lambda^{-1} log (1-u)$ 
Assim, e definindo e pode simular a partir da distribuição exponencial (exponencial como unidade padrão).
Figura 2.3 
\begin{itemize}
 \item Este procedimento funciona bem para distribuições discretas, desde que interpretar o inverso função 
de distribuição como $ F^{-1} (u) = min {{x\mid F(x)\geq u}}$               $(2.2)$
\item O procedimento então simplesmente leva-se a busca através de uma tabela da função de distribuição. 
\item R
\end{itemize}
\end{frame}

\begin{frame}{Tabela}
%SLIDE 15
 Por exemplo, a função de distribuição de Poisson (2)
\begin{center}
\begin{tabular}{ll}
x & F(x)\\
0 & 0,1353353\\
1 & 0,4060058\\
2 & 0,6766764\\
3 & 0.8571235\\
4 & 0.9473470\\
5 & 0.9834364\\
6 & 0.9954662\\
7 & 0.9989033\\
8 & 0.9997626\\
9 & 0.9999535\\
10 & 0.9999917
\end{tabular}
\end{center}
\end{frame}

\begin{frame} {Poisson}
%Slide 16
Então, nós geramos uma seqüência de uniformes padrão $u_{1}, u_{2},...,u_{n}$ e para cada $u_{i}$ obter uma Poisson 
variavel x onde $F(x-1)<u_{i}\leq F(x)$.Assim por exemplo, se $u_{1}=0,7352$ entao $x_{1}=3$.Na verdade, existem muitas situações em que a inversão do
método seja (ou ambos) complicado para programar ou excessivamente insuficiente para ser executado. A inversão método só é realmente útil se a função 
de distribuição inversa é fácil de programar e calcular. 
\end{frame}

\begin{frame}{Amostra rejeitadas}
%Slide 17
A idéia de amostragem é simular a rejeição de uma distribuição que seja fácil de simular, mas, em seguida, para apenas aceitar que o valor simulado com alguma probabilidade P. 
Ao escolher P corretamente, podemos assegurar que a seqüência de valores simulados são aceitas a partir do desejada distribuição. A técnica é ilustrada na Figura 2.4. 
\begin{itemize}
 \item R
\item Suponha que desejamos simular uma amostra da Beta (2,2) distribuição. Inversão neste caso exigiria solução (não linear da função de distribuição inversa. 
Em vez disso, vinculados a função de densidade f (x) por um retângulo e simular pontos (xi, yi) uniformemente sobre o retângulo. 
Em seguida, rejeitar os pontos que não se encontram por f (x). A x(coordenadas dos restantes pontos será uma amostra de f (x). Estes são mostrados na Figura 2.5
\item R
\end{itemize}
\end{frame}


\begin{frame}{2.Rejeicao Amostral}
%SLIDE 17
A eficiência do método depende de quantos pontos forem rejeitadas, o que depende, por sua vez sobre a forma como f (x) se assemelha ao retângulo.
Para melhorar a eficiência e do processo e permitir a situações em que f (x) pode ser ilimitada, a técnica pode ser modificada a permitir a 
função delimitadora para tomar qualquer forma kg (x), onde g (x) é a densidade de uma distribuição de que é fácil de simular. Em seguida,
o algoritmo assume a forma: 
\begin{itemize}
\item 1.Simular $x^{*}$ para g(x)
\item 2.Simular $y^{*}$ para $U(0,Kg(x^{*}))$
\item 3.Aceitar $x^{*}$ se $y\leq f(x^{*}$
\item 4.Continuar.
\end{itemize}
\end{frame}

\begin{frame}{2.Algoritmo}
%SLIDE 18
A razão pela qual isso funcione é a seguinte: vamos denotar X uma variável aleatória de uma distribuição g (x), 
tal que $f(x)\leq kg(x)\forall x$ para algum valor K. Deixe h (x) a probabilidade de que x é aceita: $h(x)=f(x)/Kg(x)$.
\begin{itemize}
\item $Pr(X \not\leq x \text{e} X \text{aceito})= \int_{-\infty}^{x} h(y) g(y)dy$ e
\item $Pr(X \text{aceito})= \int_{-\infty}^{\infty} h(y) g(y)dy$ assim
\item $Pr(X \not\leq x\mid X \text{aceito})= \frac{\int_{-\infty}^{x} h(y) g(y)dy}{\int_{-\infty}^{\infty} h(y) g(y)dy}$
\item $=\frac{\int_{-\infty}^{x} f(y)dy}{\int_{-\infty}^{\infty} f(y)dy}$
\item de modo que os valores aceitos realmente tem pdf f. Além disso, $Pr(X \text{aceito})\int gh=1/k$
\end{itemize}
\end{frame}

\begin{frame}{2.1 Algoritimo}
%SLIDE 19
A eficiência  do processo depende da qualidade do acordo entre F e o delimitador kg, desde que se um grande 
valor e de K é necessário, então a probabilidade de aceitação é baixo, de modo que um grande número de simulações 
são necessários para atingir um tamanho de amostra necessário. 
Como exemplo, considere a distribuição com densidade:$f(x)\alpha x^{2}e^{-x}; 0\leq x \leq 1$.
uma distribuição gama truncado. Então, uma vez que f (x) $e^{-x}$ toda a parte, podemos definir   g (x) = exp(-x) 
e assim simular a partir de uma distribuição exponencial, a rejeição de acordo com o algoritmo acima. 
Figura a seguir mostra tanto f (x) e g (x). É evidente que neste caso, o exemplo  é muito pobre para a 
rotina é altamente eficiente (embora estatisticamente correto). 
Aplicando esta ao gerar uma amostra de 100 dados usando o seguinte código:  R
\end{frame}

\begin{frame}{Relação de uniformes}
%SLIDE 20
Uma adaptação do algoritmo de rejeição, que funciona bem para muitas distribuições é dar racoes  entre método uniforme.
Suponha que a  h é uma funcao não negativa $\int h <\infty$ e deixamos $Ch ={{(u, v):0\leq u \leq \sqrt{h(v/u)}}}$.
Então, se (U, V) sao uniformemente distribuídas ao longo Ch então $X = V/U$ tem pdf $h/\int h$
Assim, para simular a partir de uma densidade proporcional h,simulamos uniformemente sobre a região Ch e obtem coordenadas. 
Na prática, Ch pode ser complicado na forma, assim que a prática só que a solução é vinculado com um retângulo (se possível), 
simular dentro do retângulo (por um par de uniformes), e aplicar rejeição: daí, a razão de uniformes.   
\end{frame}

\begin{frame}{Relação de uniformes}
%SLIDE 21
\begin{itemize}
\item Seja $bigtriangleup_{h}$ a área de $C_{h}$. Em seguida, sobre as variáveis em mudança $(u,v) \to (u,x)$ onde$x=v/u$
\item  $\bigtriangleup _{h}= \int \int {Ch} dudv= \int \int_{0}^{\sqrt{h(x)}} u dudx=\int \frac{1}{2} h(x)$ dx.
\item Devido à uniformidade de (U, V) sobre Ch (U, V) tem pdf $1/\bigtriangleup _{h}$ para que a transformação, 
$(U, X)$ tem pdf $u/\bigtriangleup _{h}$, e a integração de U dá a pdf marginal de X com: 
\item $\bigtriangleup _{h}^{-1}\int_{0}^{\sqrt{h(z)}} u du=h(x)/{2\bigtriangleup _{h}}= h(x)/\int h(x)dx$
\item Assim, $V = U$ tem pdf proporcional a h. Novamente, uma propriedade fundamental deste método é que h é só necessárias para
ser especificado  até a proporcionalidade. 
\end{itemize}
\end{frame}

\begin{frame}{2.2.Algoritimo}
%SLIDE 22
Como discutido acima, isto só é útil se podemos gerar uniformemente sobre Ch, que é mais provável 
a ser alcançado por meio da simulação de maneira uniforme dentro de um rectângulo $[0; a]* [b_{-}, b_{+}]$ que contém Ch
(desde que esse rectângulo existe). Caso isso aconteça, temos o seguinte algoritmo.
\begin{itemize}
\item 1.Simular independencia $U \thicksim U[0,a], V\thicksim U[b_{-},b_{+}]$ 
\item 2.Se $(U,V)\in C_{h}$ aceite $X=V/U$ caso contrario repetir.
\item 3.Continuar.
\item Como exemplo, considere a distribuição de Cauchy com densidade $h(x)\alpha* \frac{1}{1+x^{2}}$
\item Entao $C_{h}={(u,v): 0\leq u\leq \sqrt{h(v/u)}}={(u,v):0\leq u, u^{2}+v^{2}\leq 1}$,um semicirculo. 
\item Assim podemos tomar $[0.a]*[b_{-},b_{+}]=[0,1]*[-1,1]$e obter o algoritmo
\end{itemize}
\end{frame}

\begin{frame}{2.3.Algoritimo}
%SLIDE 22
\begin{itemize}
\item 1.Simular independencia $U \thicksim U[0,1], V\thicksim U[-1,1]$ 
\item 2.Se $u^{2}+v^{2}$ aceite $x=v/u$ caso contrario repetir.
\item 3.Continuar.
\item Assim pode ser implementado com codigo
\item Histograma 1000 valores simulados (note a escala incomum porque o peso da cauda de Cauchy faz um ou dois valores 
simulados de ser extremo em relação ao resto dos dados).
\item Um número modificado têm sido proposto para melhorar a eficiência do presente procedimento, 
que ascendem o escalonado  e localizar distribuições antes de aplicar o método. R
\end{itemize}
\end{frame}

\begin{frame} {Algoritmo}
%Slide 24
 Outro método para melhorar a eficiência é por um processo conhecido como pre-teste 
\item Isto se aplica tanto a rejeição e a relação de métodos uniformes. O ponto é que, o método da relação de uniformes, por exemplo, 
a parte mais lenta do algoritmo pode ser a verificação $(u, v)\in C_{h}$ ou não. No entanto, pode haver regiões mais simples
$C_{1} e C_{2}$ que tal $C_{1}\subset C_{h}\subset C_{2}$ de modo que se (u, v) é encontrado para estar dentro $C_{1}$ ou fora $C_{2}$ 
então imediatamente saber se ele está  dentro $C_{h}$ ou não.
\end{frame}

\end{document}
