Guia de Estudo

Aula de 30/05 - A definição de um processo estocástico

Pontos conceituais importantes da aula

Modelos nada mais são do que caricaturas de sistemas complexos, em que parte da complexidade é jogada fora para tornar o modelo sucetível de análise / simulação eficiente. Quanto mais detalhado o modelo, mais acurada a resposta, porém mais complexa a análise / simulação.
De um ponto de vista rigoroso, um processo estocástico não é nada mais do que uma coleção de variáveis aleatórias. A utilidade dessa ideia surge quando interpretamos essa coleção de variáveis aleatórias como descrevendo o que está acontecendo com um determinado sistema em diferentes instantes.
Processos estocásticos podem ser utilizados para modelar praticamente qualquer sistema em que a evolução do tempo envolva aleatoriedade (tipicamente manifestada por não termos informações suficientes para determinar a evolução com precisão).
Exemplos podem ser encontrados em Economia (Mercado Financeiro), Física (Movimento Browniano e Mecânica Estatística), Biologia (Modelos Ecológicos) e Ciência da Computação (Análise de Algoritmos Randomizados, Previsão de Carga em Servidores).
Um mesmo processo estocástico pode ser descrito usando estados diferentes. Um tipo extremamente conveniente de estados são os estados Markovianos, em que o estado em um determinado tempo tem toda a informação necessária para determinar o que pode acontecer com o futuro do sistema.

Leitura Recomendada:

Cap 2.9
Exemplo 3.13 no cap 3.4 (problema do labirinto repaginado), além dos exemplos 3.12 e 3.18

Exercícios:

Do capítulo 3: 40, 41

Vídeo-Aulas:

Os vídeos 1.1 e 1.2 da aula 1 (o vídeo da aula 1.3 requer o conteúdo da aula 0, mas ainda é o assunto coberto em aula)

Aula de 01/06 - Cadeias de Markov e conceitos básicos

Pontos conceituais importantes da aula

A memória de um processo estocástico é basicamente a quantidade de estados passados que eu preciso para descrever os estados futuros. Se eu descrevo um processo estocástico usando estados Markovianos, então ele não tem memória. Se o meu processo tem memória finita eu sempre consigo encontrar um conjunto de estados Markovianos para ele.
A noção de ausência de memória pode ser feita mais precisa pela Propriedade de Markov. Processos estocásticos que obedecem à Propriedade de Markov são chamados de cadeias de Markov e serão o foco principal do curso.
Assim como distribuições simples (como as vistas em IPE) carregam toda a informação estatística de uma variável aleatória, podemos criar descrições parecidas para quando temos mais do que um variável aleatória.
É muitas vezes útil extrair o comportamento de apenas algumas das variáveis descritas em uma distribuição conjunta. A operação que faz isso é a marginalização, que é obtida grosso modo somando/integrando sobre todos os valores das variáveis sendo removidas da descrição.
Uma outra operação importante é o condicionamento de uma variável com respeito à outra (como vocês podem ver lendo o Ross, é possível condicionar uma distribuição com respeito a eventos, mas essa ideia não é tão útil nesse curso).

Leitura Recomendada:

Caps 2.5.1, 3.2, 4.1

Exercícios:

Do capítulo 2: 20, 21
Do capítulo 3: 1, 2, 9

Vídeo-Aulas:

Vídeos 2.1 e 2.2 da aula 2, para a parte de memória e cadeias de Markov
Vídeos 0.1 e 0.2 da aula 0, para a parte de distribuições conjuntas

Aula de 06/06 - Evolução temporal e comportamentos estacionários

Pontos conceituais importantes da aula

A evolução temporal de uma cadeia de Markov pode ser descrita em termos de matrizes em que as distribuições em um dado tempo são representadas por vetores coluna e as probabilidades de transição são representadas em uma matriz (chamada de matriz de transição).
Outra forma de representar as transições possíveis é o grafo de transições que será útil daqui a algumas aulas.
É importante notar que essa evolução é uma evolução temporal da estatística e logo é distinta da evolução que vemos nas realizações do processo.
A estrutura da equação mestra me diz que as informações necessárias para descrever a evolução de um processo estocástico se resumem a calcular potências de matrizes. Uma consequência é a equação de Chapmann-Kolmogorov que relaciona as matrizes que me dão n passos de tempo da minha cadeia de Markov.
Outro conceito importante vão ser as distribuições em que a evolução temporal para (chamadas de estacionárias). É possível mostrar que elas sempre existem e além disso dadas algumas propriedades do grafo de transições, podemos usar um teorema (Perron-Frobenius) para determinar se elas são únicas.

Leitura Recomendada:

Caps 4.1, 4.2

Exercícios:

Do capítulo 4: 1, 2, 3, 6, 7, 8

Vídeo-Aulas:

Vídeo 2.3 da aula 2
Vídeos 3.1 e 3.3 da aula 3
O vídeo 3.2 é um complemento interessante, especialmente para acompanhar vídeo-aulas seguintes, mas é um conceito que eu vou meio que contornar em aula

Aula de 15/06 - Séries Temporais (prática 1)

Pontos conceituais importantes da aula

Vou mostrar alguns casos práticos de modelagem e como analisar os dados que são obtidos a partir das simulações deles.
Pelo lado da teoria, um ponto importante vai ser como extrair as estatísticas e garantir que as flutuações tenham sido levadas em conta ao fazer a análise.

Códigos

Aula de 20/06 - Estados transientes e recorrentes

Pontos conceituais importantes da aula

Alguns estados em um processo estocástico só acontecem durante uma situação transiente. Ou seja, depois de um tempo, paramos de observar esses estados.
A forma rigorosa de caracterizá-los é pela chamada probabilidade de retorno. A probabilidade de retorno de um estado i é a probabilidade de eventualmente voltar a i, partindo de i. Se a probabilidade de retorno de um estado for 1, ele é dito recorrente, senão ele é dito transiente.
Para fazer a conexão com o que está acontecendo no grafo de transições precisamos primeiro do conceito de acessibilidade. Um estado i acessa j, se a probabilidade de partir de i e eventualmente chegar em j for não-nula. Isso acontece sss existe um caminho indo de i a j no grafo de transições.
As relaçõs de acessibilidade entre diferentes estados me dão um algoritmo que permite identificar quais são os estados transientes e recorrentes só olhando o grafo de transições.

Leitura Recomendada:

Cap. 4.3

Exercícios:

Do cap 4: 14, 15, 16

Vídeo-Aulas:

Vídeos 4.1 a 4.3 da aula 4

Aula de 22/06 - O teorema de Perron-Frobenius

Pontos conceituais importantes da aula

Podemos usar os conceitos de classes e recorrência vistos na aula 4 para falar da versão forte do teorema de Perron-Frobenius, que se aplica a qualquer cadeia de Markov com um número finito de estados.
Os comportamentos novos que surgem para essas cadeias mais gerais dependem de algumas probabilidades de transição serem 0. Dependendo do modelo que tratamos, essa pode ser ou não uma boa aproximação. Um ponto interessante é ver o que acontece quando eu "perturbo" a minha matriz de transição de maneira que voltamos a ter uma cadeia ergódica.
Finalmente, vamos olhar a noção de tempo de correlação, que está intrísecamente ligada com a forma como os transientes desaparecem (e logo com os detalhes que ficam de fora da análise para tempos longos). Vamos ver esse conceito aparecer em dois contextos, em médias de medidas que são tomadas ao longo do tempo e em funções de autocorrelação (também de medidas).

Leitura Recomendada:

Cap 4.4

Exercícios:

Do cap 4: 20 a 25

Vídeo-Aulas:

Vídeos 5.1 a 5.3 da aula 5
Apesar do assunto ser o mesmo, estou focando nesse vídeos em autovalores e autovetores como a explicação das previsões de Perron-Frobenius

Aula de 27/06 - A caminhada aleatória em ℤ

Pontos conceituais importantes da aula

A caminhada aleatória em Z é um processo estocástico extremamente importante por ser um ingrediente/inspiração para processos mais complicados. Basicamente temos um espaço 1D, discretizado em que uma partícula dá pulos ou à esquerda ou à direita, podendo haver ou não um viés para uma das direções.
Vou mostrar como fica a evolução da distribuição, dos valores esperados e das variâncias.
O problema da primeira passagem é derivado da caminhada em Z. A modificação é que um dos estados (a origem 0) agora aprisiona a partícula. A pergunta que vamos estudar é quanto tempo a partícula leva até ficar aprisionada.
Nós usamos a lei da esperança total para obter o valor esperado para esse tempo e obtemos a distribuição do tempo para o caso sem viés.

Leitura Recomendada:

A caminhada aleatória infelizmente está espalhada por várias seções do Ross. Essas são as mais relevantes:
- Na seção 3.6.6 ele faz uma análise de um caso um pouco mais geral tanto da caminhada quando da primeira passagem.
- O exemplo 4.18 que começa na pág. 208.

Exercícios:

Considere uma caminhada em Z² em que eu tenho probabilidades distintas de ir um passo acima, abaixo, à esquerda e à direita. O estado desse processo será (X(t), Y(t)). Estude os valores esperados e variâncias de X e Y a medida que o tempo cresce. Como você espera que a distribuição conjunta de X e Y evolua no tempo se eu começar na origem (0,0)?

Vídeo-Aulas:

Vídeos 6.1 e 6.2 da aula 6

Aula de 29/06 - Usando a caminhada aleatória como ingrediente básico (prática 2)

Pontos conceituais importantes da aula

Nessa aula eu mostro diferentes aplicações de caminhadas aleatórias como ingredientes de outros modelos.

Códigos:

Aula de 04/07 - O problema da ruína

Pontos conceituais importantes da aula

Adicionando um segundo estado absorvente à caminhada nos inteiros nos leva ao modelo da ruína.
Podemos usar as leis da probabilidade e da esperança totais para determinar a probabilidade de terminar em um dado estado absorvente, dada a condição inicial e quanto tempo em média eu necessito até atingir um estado absorvente (esse segundo só vou fazer a conta no caso sem viés, para manter as coisas simples)
Uma das aplicações do modelo da ruína é em testes sequênciais de hipótese, que são uma classe interessante de testes de hipótese em estatística. A grande diferença desses testes para testes mais usuais é que ao contrário de fixar um número de repetições para tirar as conclusões, os dados sendo obtidos é que nos dizem quando parar as repetições. Isso agiliza testes em que uma das hipóteses é esmagadoramente mais provável que a outra e evita subestimar o número de repetições no caso de hipóteses com probabilidades parecidas.
Uma pergunta mais sofisiticada e que é útil na modelagem de mercados financeiros é como que um apostador deveria jogar o modelo da ruína sem saber de antemão quais são os viéses. Para tanto vamos ter que estimar o parâmetro a partir do que está acontecendo. Isso pode ser feito com uma abordagem Bayesiana e podemos usar como condição de parada o valor esperado (do caixa do jogador ao fim da partida) estar abaixo de um limite prestabelecido.

Leitura Recomendada:

Ross cap 4.5.1

Exercícios:

Cap 4: 56, 58, 59, 60, (+ 61 como desafio)

Vídeo-Aulas:

Vídeos 7.1 a 7.3 da aula 7

Aula de 06/07 - O teorema ergódico

Pontos conceituais importantes da aula

Em muitas vezes quando usamos um processo estocástico, nosso objetivo é calcular um determinado valor esperado para a distribuição limite. em um primeiro momento isso parece indicar que precisariamos para cada ponto de estatística que obtivermos, fazer a simulação um tempo longo o suficiente para atravessar o transiente e depois começar tudo de novo para o ponto seguinte.
O teorema ergódico que vou provar nessa aula, nos mostra que na verdade basta tomar uma média na série temporal para um tempo longo o suficiente (desde que algumas condições sejam satisfeitas pelo modelo).
Em preparação para a prova do teorema, eu calculo qual é o tempo médio de retorno de um estado (tempo entre partir de um estado e voltar nele pela primeira vez) e introduzo a noção de recorrência positiva, como um refinamento da nossa classificação de estados.

Leitura Recomendada:

Infelizmente o Ross não menciona mais do que uma nota de rodapé.

Exercícios:

Exercício 7 da lista 2
Do cap 4: 67

Vídeo-Aulas:

Vídeo 8.1 da aula 8

11/07 - P1

Aula de 13/07 - Métodos de Monte Carlo (prática 3)

Pontos conceituais importantes da aula

Métodos de Monte Carlo são uma forma de obter valores esperados (amparados pelo teorema ergódico) que interessantemente podem ser usados para obter estimativas para problemas determinísticos também (em situações em que algoritmos deterministas não seriam viáveis).
O tipo de método em que vamos nos focar são os Métodos de Monte Carlo via cadeias de Markov (Markov Chain Monte Carlo, MCMC). Nesses métodos eu crio uma cadeia que tem uma única classe recorrente positiva e cuja distribuição estacionária é exatamente a que eu quero analisar.
Um ansatz muito útil é considerar uma cadeia que possua balanço detalhado (ou ainda, seja reversível no tempo), pois essa propriedade deixa bem claro como deve ser a estrutura da cadeia e também permites soluções esquemáticas para se encontrar as probabilidades de transição.
O método para criar essas cadeias em que eu vou focar é a solução de Metrópolis-Hastings.
Vou mostrar diferentes aplicações dessas ideias, focando na simulação de distribuições, problemas de física e problemas de inferência.

Leitura Recomendada:

Caps 4.8 e 4.9

Exercícios:

Do cap 4: 69, 71, 72, 73, 74

Vídeo-Aulas:

Vídeos 8.2, 8.3 da aula 8. Os vídeos da aula 9 dão um certo aprofundamento mas não é tão essencial

Códigos:

Aula de 18/07 - Cadeias de Markov contínuas no tempo

Pontos conceituais importantes da aula

Vamos começar a considerar processos estocásticos em que o tempo é contínuo, ao invés de termos passos de tempo pré-determinados.
Uma coisa interessante é que a forma como o tempo entre transições é distribuído, afeta a Markovianidade do processo. Olhando o que a propriedade de Markov significaria para o tempo entre as transições, chegamos a conclusão que esse tempo tem que ser uma variável exponencial.
Um processo de Markov desse tipo que vocês já conhecem é o processo de Poisson. Esse é o processo em que é feita ao longo do tempo a contagem que leva a uma variável de Poisson. Em um certo sentido, esse é um dos processos contínuos mais simples e ele vai ser a base para a descrição desse tipo de processo.
Veremos também como podemos adaptar a representação gráfica usada para processos discretos para o caso contínuo no tempo, como simular esses processos e a forma da equação mestra para eles.

Leitura Recomendada:

Caps 5 (principalmente o 5.3), 6.1 e 6.2 do Ross

Exercícios:

Vídeo-Aulas:

Vídeos da aula 10

Aula de 20/07 - Evolução temporal no caso contínuo

Pontos conceituais importantes da aula

Usando a equação mestra que montamos na aula passada, podemos escrever sistemas de EDOs que vão me dar a evolução no tempo do sistema. Também podemos encontrar a equação que leva às distribuições estacionárias para esse caso.
Assim como no caso discreto no tempo, também é possível encontrar uma solução formal para a distribuição em função do tempo. Invocando álgebra linear podemos usar essa solução para dizer em linhas extremamente gerais como o transiente da cadeia se comporta.
Outro ângulo pelo qual a evolução pode ser analisada é considerando evoluções estroboscópicas (ou seja medindo o sistema em intervalos de tempo igualmente espaçados). Isso nos permite perceber que a estrutura de classes é essencialmente a mesma que no caso discreto no tempo. Também nos permite usar o teorema de Perron-Frobenius para tornar um pouco mais precisa a cara do transiente e dos estados estacionários.
Um outro ponto que vou abordar é como devemos combinar processos diferentes e independentes que causem a mesma transição, que será um ponto recorrente na modelagem desse tipo de sistema.

Leitura Recomendada:

Caps. 6.4, 6.5 (o Ross foca mais na evolução no tempo da probabilidade dada uma condição inicial, mas é essencialmente a mesma coisa)

Exercícios:

Do cap 6: Escreva as equações mestras dos processos descritos nos exercícios 4, 7 e 10 (o resto do exercício são coisas que veremos na semana que vem)

Vídeo-Aulas:

Vídeos da aula 12

Aula de 25/07 - Processos de morte e nascimento

Pontos conceituais importantes da aula

Os processos de morte e nascimento são processos estocásticos a tempo contínuo em que as únicas transições possíveis são do tipo n → n-1 e n → n+1. Um exemplo desse tipo com que já nos deparamos é o processo de Poisson e outro exemplo importante que veremos nessa aula é a caminhada aleatória.
Veremos algumas técnicas possíveis para investigar a distribuição dos estados, a média e a variância do estado a medida que o tempo passa.
Outro processo importante nessa classe é o processo de Yule. Esse processo modela uma população em que cada indivíduo morre com taxa μ e cria um novo indivíduo com taxa λ. Veremos para esse modelo uma outra maneira de investigar médias e variâncias, a partir de equações diferenciais.
Uma variante um pouco mais elaborada do processo de Yule é introduzir imigração. Isso é modelado como um aumento constante da taxa da transição n→n+1 por θ. A mesma técnica ainda funciona, porém com um pouco mais de trabalho, então não vou olhar a variância.

Leitura Recomendada:

Cap 6.3 do Ross

Exercícios:

Do cap 6: exs. 3 a 7

Vídeo-Aulas:

Vídeos da aula 13

Aula de 27/07 - Experimentos com cadeias contínuas e processos relacionados (prática 4)

Pontos conceituais importantes da aula

Leitura Recomendada:

Exercícios:

Vídeo-Aulas:

Aula de 01/08 - Fila M/M/1, processo de Galton-Watson e problemas de hierarquia

Pontos conceituais importantes da aula

A análise da evolução no tempo dos valores esperados e variâncias que fizemos na aula passada depende crucialmente da derivada de um determinado valor esperado só depender do valor esperado em questão e potencialmente de valores esperados que já calculamos. Ou seja se dE(X)/dt só depende de E(x) e dE(X²)/dt só depende de E(x) e E(X²), então eu tenho como encontrar E(X) e E(X²) resolvendo equações diferenciais.
Isso infelizmente não é o caso típico. Um exemplo importante é quando eu tenho um processo de morte e nascimento em que as taxas de morte e nascimento para o estado com n indivíduos não são funções afins de n (ou seja, da forma an+b). Veremos nessa aula a fila M/M/1 que é um exemplo onde essa hipótese falha.
Ainda assim, remetendo aos resultados que já conhecemos sobre caminhadas aleatórias discretas no tempo, podemos obter uma ideia qualitativa de como devem ser os resultados de simulação para a fila M/M/1. Entre outras coisas, podemos determinar a distribuição estacionária na situação em que a taxa de entrada de pessoas na fila é menor do que a taxa de saída (as outras situações não possuem uma distribuição estacionária).
Finalmente, eu retorno para um processo discreto no tempo que eu deixei pra agora por causa das similaridades dele com o Yule (tanto do ponto de vista do que está sendo modelado quanto do ponto de vista dos resultados). Esse processo é conhecido como Galton-Watson (ou processo de ramificação) e ele modela a quantidade de descendentes de uma pessoa ao longo de diferentes gerações. Uma coisa interessante vai ser a diferença de técnicas que são utilizadas. Aqui a análise é feita inteiramente utilizando as leis da esperança e variância totais, ao invés de utilizar equações diferenciais (que exigiriam um tempo contínuo).

Leitura Recomendada:

Cap 8.3.1 (para a fila M/M/1) e cap. 4.7 (para o Galton-Watson) do Ross

Exercícios:

Do cap 4: ex. 64 (μ representa a média de descendentes E(ξ))
Do cap 8: exs. 1 e 3

Vídeo-Aulas:

Víedos da aula 14

Aula de 03/08 - Os processos de Wiener e de Ornstein-Uhlenbeck

Pontos conceituais importantes da aula

Finalmente, chegamos no último assunto do curso que são os processos contínuos no tempo e no espaço. Ao contrário dos outros processos contínuos no tempo, não podemos caracterizá-los por taxas de transição por exemplo. Ao invés disso, podemos especificá-los, ou fornecendo a distribuição de estados em função do tempo, dada uma condição inicial, ou então (o que dá um insight melhor sobre o significado do modelo) por uma equação diferencial estocástica (uma EDO em que partes dela são dadas por variáveis aleatórias).
Vou começar com o processo de Wiener, que é o análogo CTCE de uma caminhada aleatória 1D e depois vou olhar o processo de Ornstein-Uhlenbeck, que pode ser interpretado como um movimento aleatório de uma partícula confinada a um potencial harmônico.
Finalmente, eu vou mostrar algumas situações limite em que esses dois processos aparecem. A saber, o Wiener pode ser obtido como um limite da caminhada aleatória em Z e o Ornstein-Uhlenbeck pode ser obtido como um llimite da urna de Ehrenfest.
Olhando o que acontece com as equações mestras desses processos DTDE a medida que o limite vai ser feito vai me levar às equações que dão a evolução dos processos DTDE, as chamadas equações de Fokker-Planck que vão ser EDPs.

Leitura Recomendada:

Cap 10.1 para o processo de Wiener, 10.3 para variantes interessantes do movimento Browniano. O Ornstein-Uhlenbeck é só mencionado por cima no exemplo 10.6. O artigo da Wikipedia em inglês por outro lado tem mais informações úteis.

Exercícios:

Do cap 10: 1, 2, 3, 9 e 10

Vídeo-Aulas:

Vídeos da aula 15

Aula de 08/08 - Método de Euler-Maruyama e equações de Fokker-Planck

Pontos conceituais importantes da aula

A forma mais flexível de especificar um processo estocástico é através de uma equação diferencial estocástica (EDE). Veremos as equações que me dão os processos de Wiener e Ornstein-Uhlenbeck e como elas me dão uma ideia melhor do significado desses processos.
Um ponto extremamente útil em aplicações é que se eu tenho a EDE, isso me dá a equação de Fokker-Planck do modelo (ou seja, a EDP que a distribuição de estados obedece ao longo do tempo) e temos como entender a evolução temporal da distribuição, além de obter uma EDO para a distribuição estacionária.
A EDE também pode ser integrada numericamente, assim como qualquer outra EDO. A diferença é que o resultado da integração não é uma solução fixa e sim uma realização do modelo. O método mais simples que me permite fazer isso (e também o mais fácil de interpretar) é o chamado método de Euler-Maruyama.
Uma outra coisa útil desse método é que se eu tenho uma EDE linear (como é o caso para os modelos de Wiener e Ornstein-Uhlenbeck) então eu consigo usar ela para deduzir EDOs para os valores esperados e variâncias do modelo, o que me dá uma forma bem mais simples de abordar essa parte da análise, comparada com resolver a equação de Fokker-Planck inteira.