Algoritmos de Monte Carlo e Cadeias de Markov PESC/COPPE/UFRJ CPS767 - 2020/1

The Epic 20,000 Roll Dice Randomness Test

• Daniel R. Figueiredo
• Horário de atendimento: sob demanda (enviar email)

• Victor Garritano Noronha - vgarritano@cos.ufrj.br
• Horário de atendimento: sob demanda
• Encontros na sala virtual: procurar por "monitoria_mcmc_2020" na página inicial do Google Meet, ou ver grupo no telegram

• Sala H-324B - CT, Bloco H, terceiro andar
• Dia/horário: terças e quintas, das 15h às 17h
• Primeira aula: 10/3 (terça)

• Retomada das aulas remotas: 2/6 (terça)
• Sala virtual: https://meet.google.com/cww-nswv-kqg

Desde da sua concepção na década de 40 algoritmos de Monte Carlo vem sendo utilizados para resolver diversos tipos de problemas, tais como problemas de amostragem e estimação, encontrando aplicações na Física, Biologia e Engenharia. Dentre suas muitas variações, algoritmos de Monte Carlo acoplados a cadeias de Markov (MCMC) estão entre os mais poderosos, tais como Metropolis-Hastings e simulated annealing. Com a crescente quantidade de dados e demanda por eficiência computacional, tais algoritmos vem sendo usados como base de técnicas emergentes em Ciências dos Dados e Inteligência Artificial. Nesta disciplina iremos explorar algoritmos de Monte Carlo com um enfoque teórico e fundamental, cobrindo probabilidade e teoria de cadeias de Markov, e também algumas aplicações práticas.

Algoritmo de Metropolis para Monte Carlo foi nomeado pela revista IEEE Computing in Science & Engineering como sendo um dos 10 algoritmos que mais influenciaram o desenvolvimento e a prática da ciência e engenharia no século 20!

Revisão de probabilidade, lei dos grandes números, algoritmos de amostragem, integração de Monte Carlo, cadeias de Markov, estado estacionário, tempo de mistura, passeios aleatórios, Metropolis-Hastings, amostragem de Gibbs, simulated annealing.

Pré-requisito: Probabilidade e estatística

Todos devem se inscrever no Moodle da discilina. Iremos utilizar esta plataforma para troca de mensagens e avisos, e entrega de tarefas (listas). O código de acesso para inscrição na disciplina no Moodle é mcmc2020.

Usaremos o Google Meet como ambiente de sala virtual. Você deve fazer o "sign in" utilizando seu email do PESC (@cos). A sala da disciplina fica em https://meet.google.com/cww-nswv-kqg

Aula	Data	Comentário	Slides/Vídeo	Tarefa
1	10/3	Logística, programação e regras do jogo. Três problemas, Monte Carlo to the rescue, História das origens, Monte Carlo na Computação	aula_0.pdf aula_1.pdf	Saiu lista 1
2	12/3	Revisão de probabilidade: espaço amostral, probabilidade, eventos, independência, exclusão mútua, probabilidade total, regra de Bayes, variável aleatória, função de distribuição, Bernoulli, sequência iid, binomial	aula_2.pdf	Fazer lista 1
3	17/3	Revisão de probabilidade: Geométrica, zeta, valor esperado, variância, função de v.a., distribuição conjunta, independência de v.a., valor esperado conditional, espaço amostral contínuo, função densidade	aula_3.pdf Vídeo	Fazer lista 1
4	19/3	Limitantes para cauda e cabeça, desigualdade de Markov, desigualdade de Chebyshev, desigualdade de Chernoff, with high probability, exemplos, limitante da união	aula_4.pdf Vídeo	Fazer lista 1
5	24/3	Método do primeiro momento, exemplo, Lei dos grandes números (fraca e forte), erro e confiança, exemplo	aula_5.pdf Vídeo	Rever lista 1
E1	26/3	Discussão sobre aulas remotas e presenciais, MOOCs, Marcelo Viana, IMPA, e o problema da porta da esperança (Monty Hall Problem)!	Não gravei o encontro!
E2	31/3	Discussão e solução do Monty Hall Problem. Vídeo com explicação lógica (intuitiva), vídeo com explicação matemática	Não gravei o encontro!
E3	7/4	Discussão e solução do problema das três filhas, das quatro bolas (ver abaixo), e o Pardoxo do Aniversário.	Vídeo	Ver abaixo
E4	14/4	Discussão e solução do Problema do Colecionador de Figurinhas (Coupon Collector Problem), e do Base Rate Fallacy (assista ao vídeo e responda perguntas abaixo)	Vídeo	Ver abaixo
E5	21/4	Analisando e projetando tabelas hash (ver problema). O andarilho aleatório pelos números naturais.	Vídeo	Ver abaixo
E6	28/4	Discussão e solução do andarilho aleatório pelos naturais (recursão)!	Vídeo	Ver abaixo
E7	5/5	Generalização do andarilho em grafos conexos, cálculo da evolução do vetor de probabilidade, relação com graus	Vídeo	Ver abaixo
E8	12/5	Distribuição estacionária do andarilho no grafo conexo, relação com os graus.	Vídeo
E9	19/5	Andarilho no grafo com pesos. Distribuição estacionária e relação com os pesos das arestas.	Vídeo
E10	26/5	Andarilho em grafos direcionados, Modelo do Surfista Aleatório, e Pagerank.	Vídeo
6	2/6	Retomada das aulas: Método de Monte Carlo, estimando somatórios, calculando erro, estimando pi	aula_6.pdf Vídeo	Terminar Lista 1
7	4/6	Estimando pi, Calculando o erro de pi, integração de Monte Carlo, Monte Carlo Ray Tracing	aula_6.pdf Vídeo	Saiu Lista 2
8	9/6	Gerando amostras de v.a. discretas, gerando Geométrica, método da transformada inversa, gerando Binomial	aula_7.pdf Vídeo	Entregar Lista 1
-	11/6	Não teremos aula. Feriado Nacional: Dia de Corpus Christi Monitoria com o Victor no mesmo horário e mesma sala virtual!	Vídeo	Terminar lista 2
9	16/6	Gerando permutações (slides aula_7.pdf), método da rejeição (rejection sampling), exemplos, importance sampling, generalização	aula_8.pdf Vídeo	Entregar lista 2, saiu lista 3
10	18/6	Importance sampling, generalização (slides aula_8.pdf), gerando amostras complicadas, variância amostral, simulação	aula_9.pdf Vídeo	Fazer lista 3
11	23/6	Cadeias de Markov, definição e exemplos, modelo On-Off, sem memória, distribuição no tempo, irredutibilidade, aperiodicidade	aula_11.pdf Vídeo	Fazer lista 3
12	25/6	Distribuição estacionária, tempo de chegada, distância de variação total, convergência, calculando distribuição estacionária, reversibilidade, passeios aleatórios	aula_12.pdf Vídeo	Terminar lista 3
-	26/6	Monitoria com o Victor às 15h na seguinte sala virtual: https://meet.google.com/mmm-ehtg-nxz (ou procurar por "monitoria_mcmc_2020" na página inicial do Google Meet)	Vídeo	Terminar lista 3
13	30/6	Autovalores, autovetores, e decomposição, convergência para estacionaridade, tempo de mistura, spectral gap, tempo de mistura de passeios aleatórios	aula_13.pdf Vídeo	Entregar lista 3, saiu lista 4
14	2/7	Caminho amostral, teorema Ergódico, estimando pi, simulação de CM, gerando amostras, Markov Chain Monte Carlo (caso simétrico), exemplo	aula_14.pdf Vídeo	Fazer lista 4
15	7/7	Revisando MCMC, Metropolis-Hasting, amostrando vértices em redes	aula_15.pdf Vídeo	Fazer lista 4
-	8/7	Monitoria com o Victor às 10h na seguinte sala virtual (discussão da Lista 4)	Vídeo
16	9/7	Otimização, caixeiro viajante, Hill Climbing, distribuição de Boltzman, simulated Annealing, de volta ao caixeiro	aula_16.pdf Vídeo	Fazer lista 4
-	13/7	Monitoria com o Victor às 10h na sala virtual (discussão da Lista 4)	Vídeo
17	14/7	Problemas iniciais, Monte Carlo na moda, caminho trilhado, dúvidas, avaliação	aula_17.pdf Vídeo	Terminar lista 4
-	15/7	Monitoria de véspera de prova com o Victor às 17:30h na sala virtual (revisão final)	Vídeo
18	16/7	Prova única (início às 15h, 2h de duração). Rever todas as listas em preparação para a prova.	Vídeo Presença	Entregar lista 4

Encontro 3

• 1) Um casal teve 3 filhos(as). Alguém te disse que ao menos dois são meninas. Qual é a probabilidade dos três serem meninas?
• 2) Um saco tem 1 bola azul, 1 bola vermelha, e 2 bolas brancas. Seu colega tira duas bolas do saco e diz para você que uma delas é branca. Qual é a chance da outra também ser branca?
• 3) [Paradoxo do Aniversário] Quantas pessoas temos que colocar em uma sala para que a chance de que pelo menos duas façam aniversário no mesmo dia seja maior do que meio?

Encontro 4

• [Colecionador de Figurinhas] Um álbum de figurinhas tem 30 figurinhas diferentes e os pacotinhos vendidos na banca sempre trazem uma única figurinha. Quantos pacotinhos, em média, você precisa comprar para completar o álbum?
• Considerando o vídeo do Base Rate Fallacy:
  1) Calcule a probabilidade da pedra ter o minério (os 9% que o vídeo comenta).
  2) Calcule o valor esperado da receita (quanto receberia), caso você faça o negócio.

Encontro 5

• Uma tabela hash (também conhecido por dicionário) é uma estrutura de dados fundamental que mapeia elementos de dados em chaves (números naturais) através de uma função de hash. Ou seja, f : D --> [1, k], onde D é o universo dos elementos de dados e [1, k] é um intervalo dos números naturais, com k sendo o tamanho da tabela hash.

  Um aspecto fundamental das tabelas hash são as colisões, que ocorrem quando dois ou mais elementos são mapeados no mesmo valor, ou seja, f(d_1) = f(d_2). Em particular, o tempo de acesso a um elemento armazenado na tabela hash depende das colisões. Além disso, a chance de colisão depende, intuitivamente, do número de elementos de dados armazenados e do tamanho da tabela.

  Assuma que a função f é "perfeita", o que significa que f mapeia D para [1,k] de forma uniforme. Ou seja, a chance de um elemento d_1 escolhido ao acaso ser mapeado para um valor específico é 1/k, ou seja, P[f(d_1) = i] = 1/k, para qualquer i em [1,k].

  Responda às perguntas abaixo:

  • 1) Seu colega quer construir uma tabela hash de forma que a chance de colisão seja no máximo 1%. Ele pretende armazenar 10^6 elementos de dados. Qual deve ser o tamanho da tabela hash?
  • 2) Seu colega quer construiu uma tabela hash de tamanho 10^9. Quantos elementos de dados ele pode armazenar de forma que a chance de colisão seja no máximo 2%?
  • 3) Considere que o tempo de acesso a tabela hash seja t_a quando não há colisão, e 10 vezes este valor quando há colisão. Seu colega deseja manter o tempo médio de acesso em 2*t_a para uma tabela hash de tamanho 10^9. Até quantos elementos de dados ele pode armazenar na tabela?
  • 4) Seja k o tamanho da tabela hash, e n o número de elementos de dados a serem armazenados. Trace um gráfico da probabilidade de colisão (eixo y) em função de n (eixo x), para diferentes valores de k (diferentes curvas). Faça k={10^4, 10^6, 10^8, 10^10}.

Encontro 6

• Considere um andarilho que se movimenta sobre a faixa [1,N] dos números naturais. A cada instante de tempo, o andarilho dá um passo e se movimenta para um número adjacente ao atual. Entretanto, esta escolha é aleatória, e com probabilidade p ele se movimenta para a direita e com probabilidade (1-p) ele se movimenta para a esquerda. Queremos entender o local do andarilho após dar t passos.

  Seja X_t a posição do andarilho no tempo t, e seja X_0 a posição inicial do andarilho. Assuma que X_0 = 1.

  • 1) Determine P[X_t = i] para i = 1,...,N, e para qualquer t.
  • 2) Determine lim t-->oo P[X_t = i].
  • 3) Discuta o resultado obtido.

Encontro 7

• Considere um andarilho que se movimenta pelos vértices de um grafo conexo. A cada instante de tempo, o andarilho dá um passo e se movimenta para um vértice vizinho ao atual, escolhido de maneira uniforme. Queremos entender onde estará nosso andarilho depois de dar t passos.

  Seja X_t o vértice onde o andarilho se encontra no tempo t, e seja X_0 a posição inicial do andarilho.

  • 1) Determine P[X_t = i] para i = 1,...,N, e para qualquer t. Dica: use a idéia de recursão apresentada como solução para o problema acima.
  • 2) Determine numericamente lim t-->oo P[X_t = i].
  • 3) Discuta o resultado obtido. Em particular, encontre uma relação entre os vértices do grafo e a probabilidade limite.
  • Use o Wolfram Alpha para calcular os valores numéricos. A matriz de transição para o grafo da aula é {{0,1/2,1/2,0,0,0,0},{1/2,0,1/2,0,0,0,0},{1/4,1/4,0,1/4,0,1/4,0},{0,0,1/3,0,1/3,1/3,0},{0,0,0,1/3,0,1/3,1/3},{0,0,1/3,1/3,1/3,0,0},{0,0,0,0,1,0,0}} e para calcular o produto vetor com matriz elevada a uma potência, use {0,0,0,0,0,0,1}.{{0,1/2,1/2,0,0,0,0},{1/2,0,1/2,0,0,0,0},{1/4,1/4,0,1/4,0,1/4,0},{0,0,1/3,0,1/3,1/3,0},{0,0,0,1/3,0,1/3,1/3},{0,0,1/3,1/3,1/3,0,0},{0,0,0,0,1,0,0}}^4. Boa diversão!

Encontro 8

• Considere um andarilho que se movimenta pelos vértices de um grafo conexo. A cada instante de tempo, o andarilho dá um passo e se movimenta para um vértice vizinho ao atual, escolhido de maneira uniforme. Queremos entender onde estará nosso andarilho depois de dar t passos.

  Seja X_t o vértice onde o andarilho se encontra no tempo t, e seja X_0 a posição inicial do andarilho.

  • 1) Determine analiticamente a distribuição estacionária de P[X_t = i], ou seja, para t muito grande. Dica: use a ideia de ponto fixo de função: x* é ponto fixo da função f se f(x*) = x*.
  • 2) Determine analiticamente a relação com os graus do grafo. Dica: mostrar que é solução!

Encontro 9

• Considere um andarilho enviesado que se movimenta pelos vértices de um grafo conexo com peso nas arestas. A cada instante de tempo, o andarilho dá um passo e se movimenta para um vértice vizinho escolhido aleatoriamente com probabilidade proporcional ao peso da aresta. Ou seja, a chance do andarilho ir para o vértice j dado que ele está no vértice i, é dada por w_ij / sum_k w_ik. Queremos entender onde estará nosso andarilho depois de dar t passos.

  Seja X_t o vértice onde o andarilho se encontra no tempo t, e seja X_0 a posição inicial do andarilho.

  • 1) Determine analiticamente a distribuição P[X_t = i].
  • 2) Determine numericamente a distribuição para alguns grafos pequenos e determine uma relação dos pesos das arestas com as probabilidades.
  • 3) Determine analiticamente a distribuição estacionária, e a relação da mesma com os pesos nas arestas. Dica: use o conhecimento do resultado para o grafo sem pesos.

Encontro 10

• Considere um andarilho que se movimenta em grafo direcionado, fortemente conexo, respeitando a direção da arestas. Ou seja, a cada instante de tempo, o andarilho dá um passo e se movimenta para um vértice vizinho escolhido aleatoriamente entre as arestas de saída do vértice presente. Queremos entender onde estará nosso andarilho depois de dar t passos.

  Seja X_t o vértice onde o andarilho se encontra no tempo t, e seja X_0 a posição inicial do andarilho.

  • 1) Construa a matriz de transição condicional, para determinar analiticamente a distribuição P[X_t = i].
  • 2) Determine numericamente a distribuição para alguns grafos pequenos, e buque uma relação dos pesos das arestas com as probabilidades para t grande o suficiente.

• Considere agora que o andarilho pode teleportar. A cada passo, o andarilho joga uma moeda, e com probabilidade alpha ele escolhe um vértice vizinho de forma uniforme, dentre as arestas de saída (caminha no grafo). Entretanto, com probabilidae 1-alpha ele teleporta para um vértice qualquer do grafo, escolhido de forma aleatória. Seja q o vetor do teleporte de forma que ao teleportar, o andarilho vai para o vértice i com probabilidade q_i. Vamos assumir que q_i = 1/n, de forma que teleportar seja uniforme. Queremos entender onde estará nosso andarilho depois de dar t passos.
  • 1) Construa a matriz de transição condicional deste modelo. Assuma que o grafo está representado por um matriz de adjacência.
  • 2) Determine numericamente a distribuição para alguns grafos pequenos, para valores de t grande o suficinte. Quais vértices tem o maior valor de probabilidade?
  • 3) Explore diferentes valores de alpha, em particular muito pequenos (0.01) e muito grandes (0.99). O que você pode concluir?
  • 4) Construa um grafo onde o vértice de maior probabilidade não é o vértice de maior grau.

As listas devem ser submetidas no Moodle da disciplina, até o final do dia de entrega.

• Primeira Lista de Exercícios - Entrega: 24/03 - adiada para 9/6
• Segunda Lista de Exercícios - Entrega: 16/6 - adiada para 18/6
• Terceira Lista de Exercícios - Entrega: 30/6 - adiada para 2/7
• Quarta Lista de Exercícios - Entrega: 14/7 - adiada para 16/7

• Prova única: 16/7 (quinta) (início às 15h pontualmente, com 2h de duração)

• Matemática dos cassinos resolve muitos problemas práticos, por Marcelo Viana, Folha de São Paulo (dez 2017).

As notas de aulas serão tiradas principalmente dos seguintes livros:

• Finite Markov Chains and Algorithmic Applications, by Olle Haggstrom, 2001.
• Non-Uniform Random Random Variate Generation, by Luc Devroye, 1986.
• Simulation, by Sheldon Ross (5th edition), 2012.
• A First Course in Probability, by Sheldon Ross (10th edition), 2019.