Cadeias de Markov e Aplicações · Prof. Dr. Adriano de Oliveira Caminha –UFF Orientador Prof. Dr. Alan Prata de Paula –UFRJ ... A probabilidade condicional é uma nova medida

Larissa Miguez da Silva

Cadeias de Markov e Aplicações

Volta Redonda, RJ

2017



Trabalho de Conclusão de Curso submetidoao Curso de Matemática da UniversidadeFederal Fluminense como requisito parcialpara a obtenção do título de Bacharel emMatemática.

Universidade Federal Fluminense

Instituto de Ciências Exatas

Curso de Matemática

Orientador: Adriano de Oliveira CaminhaCoorientador: Alan Prata de Paula

Volta Redonda, RJ2017

Ficha Catalográfica elaborada pela Biblioteca do Aterrado de Volta Redonda da UFF

S586 Miguez, Larissa

Cadeias de Markov e aplicações / Larissa Miguez da Silva. – 2017.

71 f.

Orientador: Adriano de Oliveira Caminha

Coorientador: Alan Prata de Paula

Trabalho de Conclusão de Curso (Graduação em Matemática com

ênfase em Matemática Computacional). – Universidade Federal

Fluminense, Instituto de Ciências Exatas, Departamento de Matemática,

Volta Redonda, 2017.

1. Cadeia de Markov. 2. Método Monte Carlo. 3. Probabilidade. I.

Universidade Federal Fluminense. Instituto de Ciências Exatas.

Departamento de Matemática. II. Caminha, Adriano de Oliveira,

orientador. III. Paula, Alan Prata de coorientador. IV.Título.

CDD 519.233



Trabalho de Conclusão de Curso submetidoao Curso de Matemática da UniversidadeFederal Fluminense como requisito parcialpara a obtenção do título de Bacharel emMatemática.

Trabalho aprovado. Volta Redonda, RJ, 11 de julho de 2017:

Prof. Dr. Adriano de Oliveira Caminha – UFFOrientador

Prof. Dr. Alan Prata de Paula – UFRJCoorientador

Prof. Dr. Carlos Henrique Pereira do Nascimento – UFF

Prof. Dra. Vera Lucia Prudencia dos Santos Caminha –UFF

Volta Redonda, RJ2017

À minha família e todos aqueles que de alguma forma estiveram e estão próximos de mim,fazendo esta vida valer cada vez mais a pena.

Agradecimentos

Agradeço, primeiramente, à Deus, por sempre permanecer ao meu lado, sendo omeu refúgio nos momentos de dificuldade e o meu condutor até o fim da minha caminhadana graduação.

Sou muito grata aos meus grandes orientadores Adriano de Oliveira Caminha e AlanPrata de Paula, pela orientação e envolvimento com este trabalho. Obrigada por abdicaremdos finais de semana, de algumas noites e principalmente obrigada por acreditarem emmim e sempre se preocuparem com o meu futuro. Adriano, obrigada por acreditar em mimdesde o primeiro instante da graduação, por estar me apoiando e incentivando durantetodos estes anos e por ter me apresentado a bela área da computação. E Alan, obrigada porter chegado na hora certa, pela confiança em meu trabalho, pela paciência, pelos valiososensinamentos matemáticos e pelos vários conselhos que levarei comigo para sempre.

À Universidade Federal Fluminense-UFF por ter me dado a oportunidade derealizar este curso e a direção e administração, que realizam seu trabalho incansavelmentepara que nós, alunos, possamos contar com um ensino de extrema qualidade.

Gostaria de agradecer aos meus professores da UFF pelo conhecimento transmitido,por se tornarem família, por ensinarem muito além dos conteúdos programáticos, sepreocupando sempre com o futuro de seus alunos. Em especial à professora Vera Caminha,que mesmo com toda rígidez, "tá fácil?", foi capaz de despertar em mim uma paixão porestruturas de dados com suas aulas. Vera, você é um grande exemplo de mulher, sua paixãopelo que faz é admirável, obrigada por estar comigo desde o início e me mostrar com suasimplicidade e sabedoria, que tudo é possível, só depende de nós. Sou muito grata tambémà professora e coordenadora Rosemary e a professora Marina Ribeiro, lindas por fora e pordentro, sempre de portas abertas para conversas e conselhos, incentivando e acreditandoque eu seria capaz de concluir o curso. Ao professor Honório, esbanjando sempre alegria,contribuindo com o aprendizado dentro e fora das salas de aula.

Agradeço também aos meus familiares, minha avó Estela, minha madrinha Aline,minha querida avó e madrinha Maria Júlia, em memória. Aos meus primos e primas, tiose tias, em especial aos tios Regina, Renato e Lúcia, agradeço todos os dias a Deus pelafamília que tenho. Ludimila, minha irmã de coração, a qual eu me esforço para ser umbom exemplo e retribuir todo carinho e amor. Destaco aqui o agradecimento especial aospais maravilhosos Alexandre e Kátia por serem meus pilares e exemplos. Obrigada pelasmãos entrelaçadas às minhas, doando-me confiança e amor incondicional. Tenho orgulhode ser filha de vocês, sem vocês eu nada seria.

Com muito carinho agradeço a vocês meus amigos, que estiveram comigo durante

toda a caminhada. Aos amigos de infância, que estiveram comigo desde o jardim de infânciaaté o presente momento, e mesmo seguindo caminhos diferentes nunca deixaram de meacompanhar e apoiar. Em especial, gostaria de agradecer ao melhor trio Ádina, Bianca eLarissa, que compartilharam momentos felizes e tristes na graduação, obrigada por meouvirem nos momentos de desespero e angústia, por dividir comigo cada momento, biscoitoe músicas nos intervalos, por serem minhas confidentes e por amarem junto comigo ostrogonoff da tia. Vocês foram essenciais para que eu nunca perdesse o foco e sem vocês eunão teria chegado até aqui. Michel, meu grande amor, amigo e namorado, esteve comigoem todos estes anos, me faltam palavras para agradecer o seu apoio e o carinho, obrigadapor tudo.

Por fim, gostaria de agradecer aos queridos professores participantes da bancaexaminadora, Vera Caminha e Carlos Henrique, que participaram deste momento tãoespecial e ansiado.

"Não é sobre chegar no topo do mundo e saber que venceuÉ sobre escalar e sentir que o caminho te fortaleceu

É sobre ser abrigo e também ter morada em outros coraçõesE assim ter amigos contigo em todas as situações."

(Trem Bala - Ana Vilela)

ResumoEste trabalho tem como principal objetivo resolver alguns problemas científicos via simula-ções, com ênfase aos problemas de decodificar um texto criptografado, escolher um vérticeuniformemente ao acaso em um grafo com estrutura global desconhecida (como o grafoda internet, por exemplo) e o problema de retirar uma amostra de coloração para umgrafo com distribuição uniforme dentre todas as colorações próprias. Com a finalidade defornecer a fundamentação matemática necessária, apresenta-se a teoria clássica de Cadeiasde Markov, suas propriedades básicas e teoria assintótica, destacando-se a convergênciapara a distribuição estacionária. Em sequência, foram realizadas simulações pelo métodode Monte Carlo via Cadeias de Markov. Finalmente, foi discutido o tempo de convergênciado algoritmo de Metropolis, conhecido como tempo de mistura.

Palavras-chave: Cadeias de Markov, Monte Carlo, tempo de mistura, decodificação,coloração.

AbstractThis work has as main goal to solve some scientific problems through simulations. Herewe emphasize the problems of decoding an encrypted text, choose a vertex uniformlyat random in a graph with unknown global structure (such as the internet graph, forexample) and the problem of sample a coloring of a graph uniformly at random. In orderto provide the necessary mathematical foundation, we present the theory of Markov chains,its basic properties and asymptotic theory, highlighting the convergence for the stationarydistribution. Simulations were performed using the Markov Chains Monte Carlo method.Finally, the convergence time of the above algorithm, known as the mixing time, wasdiscussed.

Keywords: Markov Chain, Monte Carlo, mixing time, Decoding, coloring .

Lista de ilustrações

Figura 1 – Grafo com vértices A, B, C e D . . . . . . . . . . . . . . . . . . . . . . 13Figura 2 – Grafo com uma coloração qualquer . . . . . . . . . . . . . . . . . . . . 14Figura 3 – Grafo com uma coloração própria . . . . . . . . . . . . . . . . . . . . 14Figura 4 – Grafo G para o passeio aleatório . . . . . . . . . . . . . . . . . . . . . 15Figura 5 – Grafo para a Cadeia P em 3.6 . . . . . . . . . . . . . . . . . . . . . . 20Figura 6 – Um grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Figura 7 – Configuração possível para uma malha 8x8 . . . . . . . . . . . . . . . . 31Figura 8 – Um algoritmo de hill climb onde pode-se ficar preso no máximo local . 37Figura 9 – Passeios aleatórios em 0, 1, 2, 3, 4. Os passeios ficam juntos após o

encontro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Figura 10 – Duas colorações com apenas o vértice v0 diferente . . . . . . . . . . . 47Figura 11 – Definindo as arestas do grafo a ser colorido . . . . . . . . . . . . . . . . 49Figura 12 – Grafo original antes da coloração . . . . . . . . . . . . . . . . . . . . . 50Figura 13 – Grafo gerado com uma coloração uniforme . . . . . . . . . . . . . . . 51

Sumário

1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 TEORIA BÁSICA DE PROBABILIDADE . . . . . . . . . . . . . . . 32.1 Probabilidade Condicional . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.1 Regra do Produto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.2 Lei da probabilidade total e teorema de Bayes . . . . . . . . . . . . . . . . 52.2 Eventos Independentes . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Variáveis Aleatórias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3.1 Variáveis Aleatórias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3.2 Probabilidade Induzida . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3.3 Variáveis Aleatórias Discretas . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.4 Principais distribuições discretas . . . . . . . . . . . . . . . . . . . . . . . 82.3.5 Variáveis Aleatórias Continuas . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Esperança Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.1 Esperança . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.2 Variância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.3 Desigualdade de Markov e Chebyshev . . . . . . . . . . . . . . . . . . . . 112.4.4 Lei dos Grandes Números . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 CADEIAS DE MARKOV . . . . . . . . . . . . . . . . . . . . . . . . 153.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2 Cadeias de Markov irredutíveis e aperiódicas . . . . . . . . . . . . . . 193.3 Distribuição Estacionária . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Cadeias reversíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 CADEIAS DE MARKOV DE MONTE CARLO . . . . . . . . . . . . 314.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Cadeia de Metropolis . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 DISTÂNCIA DE VARIAÇÃO TOTAL E TEMPO DE MISTURA . . 395.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2 Distância de variação total . . . . . . . . . . . . . . . . . . . . . . . . 395.3 Tempo de mistura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.4 Acomplamento de Cadeias de Markov . . . . . . . . . . . . . . . . . . 425.5 Convergência Rápida . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6 APLICAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.1 Coloração em Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.1.2 Cadeia de Metropolis para Colorações em Grafos e seu Tempo de Mistura . 456.1.3 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.2 Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7 CONSIDERAÇÕES FINAIS . . . . . . . . . . . . . . . . . . . . . . . 53

REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

APÊNDICES 57

APÊNDICE A – DEMONSTRAÇÕES DO CAPÍTULO 3 . . . . . . 59

APÊNDICE B – DEMONSTRAÇÕES DO CAPÍTULO 5 . . . . . . 61

ANEXOS 63

ANEXO A – CÓDIGO FONTE JAVA DA IMPLEMENTAÇÃO DOPROBLEMA DA Q-COLORAÇÃO . . . . . . . . . . . 65

1

1 Introdução

Este trabalho trata sobre um certo tipo de processo aleatório cuja a propriedadecaracterística é que ele não conserva nenhuma lembrança de onde foi no passado. Issosignifica que é necessário saber apenas o presente para definir o futuro. Esse processoé chamado de Cadeia de Markov, sendo ele uma das principais áreas da probabilidademoderna possuindo uma ampla aplicabilidade. Porém, o que o torna importante é quenão apenas modelam muitos fenômenos de interesse, mas também a falta de “memória”possibilita prever como uma Cadeia de Markov pode se comportar e calcular probabilidadese valores esperados que quantificam esse comportamento. Neste trabalho, serão apresen-tados técnicas gerais para a análise desses processos, juntamente com alguns exemplos eaplicações.

Nos últimos anos, houve um progresso considerável na análise das Cadeias de Markovpara, dado um grafo qualquer, gerar uma coloração aleatória uniformemente ao acaso. Essasmelhorias vieram em conjunto com refinamentos da técnica de acoplamento, que é umaferramenta clássica na teoria da probabilidade. Com base nessas ideias, abordaremos aqui oproblema de amostrar uma coloração própria em grafos, preocupando-se não somente como modo que escolhemos cor aos vértices do grafo, mas sim como retiramos uma amostra demodo uniforme. Para isso utiliza-se o algoritmo de Metropolis e a técnica de acoplamentopara calcular o número de etapas necessárias para alcançar a convergência, o chamadotempo de mistura da cadeia.

Além do problema da coloração citado acima, o algoritmo de Metropolis foi utilizadopara o problema de decodificar cifras simples. Esta ideia foi baseada em um artigo publicadopor Persi Diaconis [1] onde é proposto a utilização do uso de simulações computacionaispara a quebra de um código criptografado. O problema apresentado por Diaconis consisteem decifrar mensagens codificadas trocadas por prisioneiros da Califórnia e interceptadaspela polícia.

A organização do trabalho é feita da seguinte forma: o segundo capítulo trazuma revisão dos conceitos básicos de Probabilidade e Estatística, onde são definidosespaço de probabilidade, variáveis aleatórias, esperança, apresentando também a lei dosgrandes números. Além disso, é definido o que é um grafo e como as variáveis aleatórias secomportam neste objeto. No capítulo 3 serão apresentados, detalhadamente, definições eteoremas relacionados às Cadeias de Markov, dentre eles a existência e convergência paraa distribuição estacionária. No quarto capítulo, será exposto o algoritmo de Monte Carlovia Cadeias de Markov, em particular, o algoritmo de Metropolis que será utilizado pararealizar simulações. Dado a relevância do cálculo do tempo de convergência deste algoritmo,

2 Capítulo 1. Introdução

o tempo de mistura, foi dedicado um capítulo especial, capítulo 5, para sua exposição ede resultados precedentes. O capítulo 6 é reservado à apresentação de aplicações, coma primeira sendo colorações em grafos. É importante ressaltar que a implementado foifeita em linguagem JAVA e está disponibilizado no apêndice deste trabalho; a segundaaplicação foi o problema de decodificar um código criptografado. Finalmente, o capítulo 7é dedicado às conclusões e considerações finais, o qual apresenta-se as questões centraistratadas neste trabalho e mostrou possíveis desdobramentos.

3

2 Teoria Básica de Probabilidade

Neste capítulo faremos uma breve revisão de alguns conceitos de probabilidade eestatística de suma importância para o decorrer do trabalho. Os resultados são clássicos eas provas podem ser encontradas nas referências [2], [3] e [4] .

Um modelo probabilístico tem três componentes básicas:

1. Um conjunto não vazio Ω, cujos elementos representam todos os resultadospossíveis de um determinado experimento, é chamado espaço amostral. O experimentoé dado pela escolha de algum dos possíveis ω ∈ Ω, e dizemos que o ω escolhido representaa realização do experimento.

2. Uma classe apropriada F de subconjuntos do espaço amostral Ω, ao qualatribuímos uma probabilidade, é chamada coleção de eventos aleatórios.

3. Seja Ω um espaço amostral e F um evento do espaço amostral Ω. Uma medidade probabilidade P é uma aplicação P : F −→ R satisfazendo as seguintes propriedades:

Propriedade 1. P (A) > 0 para todo A ∈ F ;

Propriedade 2. P (Ω) = 1;

Propriedade 3. Se A1, A2, ... ∈ F , com Ai⋂Aj = ∅, para todo i 6= j, então P (⋃∞i=1Ai) =∑∞

i=1 P (Ai).

Chamamos ao trio (Ω,F , P ) de espaço de probabilidade.

Exemplo 2.1. Se o experimento consiste em lançar uma moeda, então

Ω = 0, 1

onde 1 representa a face “cara” e 0 representa a face “coroa”. Temos que o conjunto doseventos aleatórios é dado por

F = P (Ω) = 0, 1, 0, 1, ∅

e a medida de probabilidade, para uma moeda justa, é

4 Capítulo 2. Teoria Básica de Probabilidade

P : F −→ [0, 1]

0 7−→ 12

1 7−→ 12

0, 1 7−→ 1∅ 7−→ 0

2.1 Probabilidade CondicionalA probabilidade condicional é uma nova medida de probabilidade, de forma a

representar melhor as chances de eventos aleatórios a partir da informação de que umdado evento aconteceu. É definida da seguinte maneira:

Definição 2.2 (Probabilidade Condicional). Dados A,B ∈ F em um espaço (Ω,F , P ),definimos a probabilidade condicional de A dado que ocorreu B, ou simplesmente probabi-lidade de A dado B, por

P (A|B) = P (A ∩B)P (B) . (2.1)

Quando P (B) = 0, definimos P (A|B) = P (A).

Proposição 2.3. A probabilidade condicional é uma medida de probabilidade, isto é, dadoB ∈ F tal que P (B) > 0, a função que leva A em P (A|B) satisfaz as propriedades (1),(2) e (3).

2.1.1 Regra do Produto

A regra do produto permite expressar a probabilidade da ocorrência simultâneade diversos eventos a partir do valor de cada probabilidade condicional dados os eventosanteriores.

Teorema 2.4 (Regra do Produto). Dados A1, A2, ..., An em (Ω,F , P ), vale

P (A1 ∩ ... ∩ An) = P (A1)P (A2|A1)P (A3|A1 ∩ A2)...P (An|A1 ∩ A2 ∩ ... ∩ An−1).

Exemplo 2.5. Se selecionarmos 3 cartas de um baralho de 52 cartas, ao acaso e semreposição. Qual a probabilidade de tirar 3 reis? Seja Ai =“tirar rei na i-ésima retirada” eA =“tirar 3 reis”= A1 ∩ A2 ∩ A3. Temos

P (A) = P (A1)P (A2|A1)P (A3|A1 ∩ A2) = 452

351

250 = 1

5525 .

2.2. Eventos Independentes 5

2.1.2 Lei da probabilidade total e teorema de Bayes

Dizemos que B1, B2, B3, ... ∈ F formam uma partição de Ω se Bi ∩ Bj = ∅, paratodo i 6= j e

⋃∞i=1Bi = Ω.

Teorema 2.6 (Lei da probabilidade total). Sejam A,B1, B2, B3, ... eventos aleatórios em(Ω,F , P ) tais que B1, B2, B3, ... formam uma partição de Ω. Então

P (A) =∞∑i=1

P (Bi)P (A|Bi).

O próximo resultado, a fórmula de Bayes, determina a probabilidade condicionalde eventos que precedem aquele efetivamente observado. Mais precisamente, quandoconhecemos as probabilidades de uma sequência de eventos Bj que particionam Ω e aprobabilidade condicional de um evento posterior A em termos dessa partição, podemoscalcular as probabilidades condicionais de ocorrência de cada Bj sabendo-se da ocorrênciaou não do evento A.

Teorema 2.7 (Fórmula de Bayes). Dado um espaço de probabilidade (Ω,F , P ), umapartição B1, B2, B3, ... , e um evento A, para todo j ∈ N vale a fórmula

P (Bj|A) = P (Bj)P (A|Bj)∑i P (Bi)P (A|Bi)

Exemplo 2.8. Um armário tem duas gavetas, A e B. A gaveta A tem 2 meias azuise 3 meias pretas, e a gaveta B tem 3 meias azuis e 3 meias vermelhas. Abre-se umagaveta ao acaso e retira-se uma meia ao acaso da gaveta escolhida. Qual a probabilidadede escolher-se uma meia azul?

Começamos pelos valores conhecidos: P (A) = P (B) = 12 , P (azul|A) = 2

5 eP (azul|B) = 3

6 . Assim,

P (azul) = P (A)P (azul|A) + P (B)P (azul|B) = 12

25 + 1

236 = 9

20 .

Sabendo-se que uma meia azul foi retirada, qual a probabilidade de ter sido abertaa gaveta A?

Pela Fórmula de Bayes temos

P (A|azul) = P (A)P (azul|A)P (A)P (azul|A) + P (B)P (azul|B) =

15920

= 49 .

2.2 Eventos IndependentesDois eventos aleatórios são independentes quando a ocorrência de um deles não

aumenta nem diminui a chance relativa de que ocorra o outro.


Definição 2.9 (Eventos Independentes). Os eventos aleatórios A e B são ditos indepen-dentes se

P (A) = P (A|B),

quando P (B) > 0.

Proposição 2.10. A e B são eventos independentes se, e somente se, P (A ∩ B) =P (A)P (B).

Definição 2.11 (Eventos Independentes Dois a Dois). Os eventos aleatórios (Ai)i∈I , ondeI é um conjunto qualquer de índices, são ditos independentes dois a dois se Ai e Aj sãoindependentes para todos i, j ∈ I, com i 6= j.

Exemplo 2.12. Vamos considerar um lançamento de um dado de 4 faces. ConsidereA =“par”, B =“menor que 3”, C =“1 ou 4”, i.e., A = 2, 4, B =1, 2, C = 1, 4.Então A, B e C são independentes dois a dois. De fato,

P (A ∩B) = P (2) = 14 = P (A)P (B),

P (A ∩ C) = P (4) = 14 = P (A)P (C),

P (B ∩ C) = P (1) = 14 = P (B)P (C).

2.3 Variáveis AleatóriasNa realização de um fenômeno aleatório, muitas vezes estamos interessados em uma

ou mais quantidades, que são dadas em função do resultado do fenômeno. Por exemplo,sortear 11 cartas do baralho e contar quantas dessas cartas são de espadas, ou sortear doisnúmeros reais entre 0 e 1 e considerar o menor deles. A essas quantidades damos o nomede variáveis aleatórias. Uma variável aleatória é um observável numérico resultante de umexperimento.

2.3.1 Variáveis Aleatórias

Uma variável aleatória é uma função que associa a cada resultado ω do espaçoamostral Ω um número real, ou seja, uma função

X : Ω −→ Rω 7−→ X(ω)

Exemplo 2.13. Joga-se um dado e observa-se a face superior. Nesse caso temos Ω =1, 2, 3, 4, 5, 6 e X(ω) = ω.

2.3. Variáveis Aleatórias 7

Vamos colocar uma restrição sobre a função X com o intuito de poder associar pro-babilidade a eventos como “o valor observado de X é menor que 7”. Para isso, introduzimosuma definição mais formal:

Definição 2.14 (Variável Aleatória). Uma variável aleatória X em um espaço de proba-bilidade (Ω,F , P ) é uma função real definida no espaço Ω tal que o conjunto ω ∈ Ω :X(ω) ≤ x é evento aleatório para todo x ∈ R, isto é,

X : Ω −→ R

é uma variável aleatória se ω ∈ Ω : X(ω) ≤ x ∈ F para todo x ∈ R. Daqui para frentedenotaremos por [X ≤ x]o evento ω ∈ Ω : X(ω) ≤ x.

Exemplo 2.15 (Variável aleatória constante). Se X(ω) = c para todo ω ∈ Ω, então

ω : X(ω) ≤ a =

Ω, se a ≥ c,

∅, a < c.

Portanto, X é variável aleatória.

Exemplo 2.16 (Função indicadora). Dado A ⊆ Ω, definimos

lA(ω) =

1, se ω ∈ A,

0, se ω /∈ A.

Se A ∈ F e X = lA, então

ω : X(ω) ≤ a =

Ω, se a ≥ 1,

Ac, se 0 ≤ a < 1,

0, se a < 0.

Portanto, X é variável aleatória.

Definição 2.17. Um processo estocástico definido sobre o espaço (Ω,F , P ) é uma sequên-cia de variáveis aleatórias (X0, X1, ..., Xn, ...) com cada Xn : Ω −→ R, para cada n.

2.3.2 Probabilidade Induzida

Definição 2.18 (Probabilidade induzida). Dado um espaço de probabilidade (Ω,F , P ),uma variável aleatória X : Ω −→ R, e uma coleção B de eventos aleatórios em R. Definimoso espaço de probabilidade induzido por X como (R,B, PX), onde

PX(B) = P (ω : X(ω) ∈ B), B ∈ B.

Chamamos de lei de distribuição ou distribuição da variável aleatória X, a medidade probabilidade PX em R.


2.3.3 Variáveis Aleatórias Discretas

Definição 2.19 (Variável Aleatória Discreta). Dizemos que uma variável aleatória X, esua lei PX , são discretas se existe um conjunto enumerável A = x1, x2, x3, ... ⊆ R talque,

∞∑n=1

P (X = xn) = 1.

Neste caso definimos a função de probabilidade de uma variável aleatória discreta como

pX = P (X = x), para cada x ∈ A.

A lei de uma variável aleatória discreta é dada por

PX(B) =∑x∈B

pX(x) ∀B ∈ B

O tratamento de variáveis aleatórias discretas é feito em termos de somatórios.

2.3.4 Principais distribuições discretas

Distribuição uniforme discreta: Dado I = x1, x2, ..., xk, dizemos que X temdistribuição uniforme discreta em I, denotado por X ∼ Ud[I], se

pX(xi) = 1k, i = 1, ..., k

Exemplo 2.20. No lançamento de um dado com 6 faces. Temos I = 1, 2, 3, 4, 5, 6 ep(i) = 1

6 , i = 1, 2, . . . , 6.

Distribuição de Bernoulli: Dizemos que X é Bernoulli, X ∼ Bernoulli(p), sepX(1) = p e pX(0) = 1 − p. Indicadores de eventos são Bernoulli e vice-versa. Às vezesassociamos o evento [X = 1] a "sucesso"e [X = 0] a "fracasso".

Distribuição Binomial: Considere n ensaios de Bernoulli independentes e commesmo parâmetro p, e seja X o número de sucessos obtidos. Dizemos que X segue omodelo binomial com parâmetros n e p, X ∼ b(n, p).A função de probabilidade é dada por

PX(x) = n

x

px(1− p)n−x, x = 0, 1, 2, ..., n.

2.3.5 Variáveis Aleatórias Continuas

Definição 2.21. Dizemos que uma variável aleatória X, sua lei PX são contínuas se existefX(·) > 0 tal que

PX(B) = P (X ∈ B) =∫BfX(x)dx, ∀B ∈ B.

2.4. Esperança Matemática 9

Neste caso, dizemos que fX é a função de densidade de probabilidade de X, ou simplesmentedensidade de X.

Exemplo 2.22. Para distribuição uniforme em [0, 1], definimos

fX(x) =

1, se x ∈ [0, 1],

0, caso contrário.

e neste caso temos,

P (x ≤ t) =∫ t

−∞fX(x)dx =

0, t 6 0,

t, 0 6 t < 1,

1, t > 1.

Distribuição normal: Dizemos que a variável aleatória X tem distribuição normalcom parâmetros µ ∈ R e σ2 > 0, denotado por X ∼ N (µ, σ2), se X tem como densidade

fX(x) = 12πσ2 exp

(x− µ)2

2σ2 , x ∈ R

A distribuição N = N (0, 1) é chamada normal padrão.

2.4 Esperança MatemáticaA esperança E[X] de uma variável aleatória X é a média dos valores assumidos

por X, ponderada pela probabilidade de X assumir esses valores. Podemos pensar emE[X] como sendo o “centro de massa” de X. A esperança de X é, em vários sentidos, amelhor aproximação determinística para a variável aleatória X. Uma das justificativasmais importantes, que veremos mais adiante, é a lei dos grandes números: se X1, ..., Xn

são independentes e têm a mesma distribuição de X, então a média amostral 1n

∑ni=1Xi se

aproxima de E[X] quando fazemos n grande.

2.4.1 Esperança

Definição 2.23 (Variáveis Aleatórias Discretas). Dada uma variável aleatória discreta X,definimos a esperança de X, ou média de X, ou ainda o valor esperado de X, denotada porE[X], por

E[X] =∞∑x=1

x · P (X = x),

que é equivalente aE[X] =

∞∑x=1

P (X > x). (2.2)


Definição 2.24 (Variáveis Aleatórias Contínuas). Seja X uma variável aleatória contínua.Então definimos sua esperança por

E[X] =∫Rx · fX(x)dx.

Proposição 2.25 (Propriedades da Esperança). Sejam c constante e X, Y variáveisaleatórias quaisquer e suponha que a esperança, de X e Y existam. Então

1. Se X = c então E[X] = c.

2. E(aX + b) = aE(X) + b.

3. E[X ± Y ] = E[X]± E[Y ].

4. Sejam n variáveis aleatórias X1, X2, ..., Xn, então

E[X1 +X2 + ...+Xn] = E[X1] + E[X2] + ...+ E[Xn].

5. E(X ± c) = E(X)± c.

2.4.2 Variância

Definição 2.26 (Variância). Seja X uma variável aleatória integrável. Define-se a variânciada variável aleatória X, denotada por V [X] ou σ2, como

V [X] = E[(X − E[X])2].

Uma forma alternativa para a variância é dado por:

V [X] = E[X2]− (E[X])2

Proposição 2.27 (Propriedades da Variância). Seja X uma variável aleatória integrável.Então:

1. Se c for uma constante, então V [X + c] = V [X].

2. Se c for uma constante, então V [cX] = c2V [X].

3. Se X e Y forem variáveis aleatórias independentes, então V [X+Y ] = V [X]+V ar[Y ].

4. Sejam X1, ..., Xn variáveis aleatórias independentes. Então,

V [X1 + ...+Xn] = V [X1] + ...+ V [Xn].

Exemplo 2.28. Fixando p ∈ [0, 1], e seja

X =

1, com probabilidade p,

0, com probabilidade 1− p.

2.4. Esperança Matemática 11

Isto é, X é uma variável aleatória de Bernoulli(p).

A esperança de X é dada por

E[X] = 0 · P (X = 0) + 1 · P (X = 1) = p

Além disso, desde que X toma apenas valores 0 e 1, temos que X2 = X, logo E[X2] = E[X]e portanto, a variância será dada por

V [X] = E[X2]− (E[X])2 = p− p2 = p(1− p).

2.4.3 Desigualdade de Markov e Chebyshev

Apresentamos abaixo Desigualdades de Markov e Chebyshev. A desigualdade deChebyshev será de grande importância para a demonstração da Lei dos Grandes Números.

Proposição 2.29 (Desigualdade de Markov). Suponha que X é uma variável aleatóriatal que

P (X ≥ t) ≤ E[X]t

.

Corolário 2.30 (Desigualdade de Chebyshev). Seja X uma variável aleatória tal queV(X) existe. Então, para cada número t > 0

P (|X − E[X]| ≥ t) ≤ V [X]t2

.

Demonstração. Defina outra variável aleatória Y, sendo

Y =

t2, se |X − E[X]| ≥ t

0, caso contrário.

Então nós sempre temos Y ≤ (X − E[X])2 e E[Y ] ≤ E[(X − E[X])2]. Além disso,

E[Y ] = t2P (|X − E[X]| ≥ t),

Logo,P (|X − E[X]| > t) = E[Y ]

t26E[(X − E[X])2]

t2= V [X]

t2.

2.4.4 Lei dos Grandes Números

A desigualdade de Chebyshev pode não ser uma ferramenta prática para determinaro tamanho apropriado da amostra em um problema específico, porque ela pode especificarum tamanho de amostra muito maior do que é realmente necessário para a distribuiçãoem particular, a partir do qual a amostra está sendo tomada. No entanto, a desigualdade


de Chebyshev é uma ferramenta teórica valiosa, e será usada para provar um resultadoimportante conhecido como a lei dos grandes números.

Suponha que Z1, Z2, ... é uma sequência de variáveis aleatórias. A grosso modo, édito que essa sequência converge para Z dado se a distribuição de probabilidade de Zntorna-se cada vez mais concentrada em torno de Z quando n −→∞.

Definição 2.31 (Convergência em Probabilidade). A sequência Z1, Z2, ... de variáveisaleatórias converge para Z em probabilidade se para todo número ε > 0,

limn−→∞

P (|Zn − Z| > ε) = 0

Notação: ZnP−→ Z.

Teorema 2.32 (Lei dos grandes números). Suponha que X1, ..., Xn forma uma amostraaleatória de uma distribuição cuja média é µ e σ2 a variância finita. Denote por Xn amédia amostral, isto é, Xn = X1+X2+...+Xn

n. Então

XnP−→ µ.

Demonstração. Usando os itens (4) e (5) da proposição 2.25 temos

E[Xn] = 1n

(µ+ ...+ µ) = µ

Similarmente, podemos aplicar (2) e (4) da proposição 2.27 para mostrar que:

V [Xn] = 1n2 (σ2 + ...+ σ2) = σ2

n

Daí, a desigualdade de Chebyshev nos dá

P (|Xn − µ| > t) 6 σ2

nt2

o qual tende para 0 quando n −→∞.

2.5 Grafos

É possível definir variáveis aleatórias para grafos porém antes disso segue umadefinição para grafos. Para um estudo mais profundo de grafos, veja [5].

Definição 2.33. Um grafo não orientado é uma estrutura G = G(V,E), constituída porum conjunto finito e não vazio V cujos elementos são denominados vértices, e um conjuntoE de pares não ordenados de vértices distintos denominados arestas.

2.5. Grafos 13

Dado um grafo G = (V,E), representamos seu conjunto de vértices por V =v1, . . . , vn e o conjunto de arestas por E = vi, vj; i 6= j, vi, vj ∈ V .

Se u, v ∈ E dizemos que os dois vértices u, v ∈ V são vizinhos e denotamos poru ∼ v. Denota-se por N(v) o conjunto dos vizinhos de v e sua cardinalidade |N(v)| = d(v), o grau de v. Ou seja, d(v) é o número de vértices de G adjacentes a v. Os grausmínimo e máximo em G são denotados respectivamente por δ(G) = mindi; vi ∈ V e∆(G) = maxdi; vi ∈ V .

Vejamos um exemplo de um grafo não orientado:

Exemplo 2.34. Seja G um grafo como na figura a seguir,

Figura 1 – Grafo com vértices A, B, C e D

O grafo G tem conjuntos de vértices dado por V = A,B,C,D e conjunto dearestas E = A,B; B,C; C,A; C,D. Além disso, grau máximo ∆ = 3.

Estamos interessados em eventos aleatórios associados a grafos, para isso definiremosvariáveis aleatórias de forma geral.

Definição 2.35. Uma variável aleatória é uma função X : Ω −→ Θ, onde Θ é um outroconjunto finito. Assim, também pode-se definir a distribuição da variável aleatória X comoa probabilidade PX sobre Θ tal que:

θ ∈ Θ : PX(θ) = P (X = θ) = P (ω ∈ Ω : X(ω) = θ).

Exemplo 2.36. Seja G um grafo finito com o conjunto de vértices V tal que |V | = n.Escolher um vértice de V uniformemente ao acaso significa considerar a variável aleatóriaX : Ω −→ V tal que

P (X = v) = 1n, ∀v ∈ V

Definição 2.37. Uma coloração Q = 1, ..., q no grafo G=(V,E) finito é uma funçãoCQ : V −→ Q. Dizemos que a coloração é própria se v ∼ u, então CQ(v) 6= CQ(u).

Exemplo 2.38. Dado o Grafo apresentado no exemplo 2.34, na figura 2 temos umacoloração qualquer e na figura 3 uma coloração própria.


Figura 2 – Grafo com uma coloração qualquer

Figura 3 – Grafo com uma coloração própria

Exemplo 2.39. Dado o grafo do exemplo 2.34, Tem-se que o número de colorações é34 (para cada vértice temos três cores possíveis), e o número de colorações próprias é 12(3 · 2 · 1 · 2).

Seja X uma coloração escolhida uniformemente entre todas as colorações possíveis(34 possibilidades ), então X é uma variável aleatória X : Ω −→ colorações de G talque

P (X = CQ) = 181 , para CQ ∈ colorações de G.

Agora, seja Y uma coloração própria escolhida uniformemente entre todas ascolorações próprias possíveis (3 · 2 · 1 · 2 possibilidades), então Y é uma variável aleatóriaY : Ω −→ colorações de G tal que

P (Y = CQ) =

1/12, se CQ é coloração própria;

0, caso contrário.

15

3 Cadeias de Markov

Estudaremos neste capítulo a definição e resultados de Cadeias de Markov. Nasequência esses conceitos serão aprofundados e aplicados nos próximos capítulos, o textoteve como base [6] e [7], onde podem ser extraídas mais informações.

3.1 Introdução

Antes de formalizar o conceito de Cadeia de Markov daremos início com um exemplosimples.

Exemplo 3.1. Consideremos uma cidade pequena que consiste em quatro ruas e quatroesquinas (v1, v2, v3 e v4), isto é, um grafo G . Definimos como Passeio Aleatório ao seguinteprocedimento:

• No tempo 0, o caminhante aleatório está na esquina v1;

• No tempo 1, ele joga uma moeda honesta e move-se imediatamente para v2 ouv4, de acordo com o resultado, com a regra de decisão que, se a moeda der cara, então elese move um passo no sentido horário, enquanto se der coroa, ele se move um passo nosentido anti-horário;

• No tempo 2, a moeda é lançada novamente para decidir qual dos dois vérticesadjacentes ele irá se mover, com a mesma regra de decisão;

• O processo é iterativo nos tempos 3,4,5...

Denotamos Xn para o índice da esquina, no qual o caminhante está no tempo n.Consequentemente, (X0, X1, ..) é um processo estocástico tomando valores 1, 2, 3, 4.

Vejamos a Figura 4, para melhor entendimento.

v3

v2v1

v4

Figura 4 – Grafo G para o passeio aleatório

16 Capítulo 3. Cadeias de Markov

Considerando que o passeador comece no tempo 0 em v1, nós temos

P (X0 = 1) = 1

No próximo passo, ele se move para v2 ou v4 com probabilidade 1/2 cada, então

P (X1 = 2) = 1/2

P (X1 = 4) = 1/2

Computar a distribuição de Xn para n ≥ 2 requer um pouco mais de trabalho. Paraisto é necessário considerar probabilidades condicionais. Suponhamos que no tempo n ocaminhante está em v2, então :

P (Xn+1 = 1|Xn = 2) = 1/2

eP (Xn+1 = 3|Xn = 2) = 1/2.

Devido ao mecanismo de cara ou coroa para decidir para onde ir. Se condicionarmosainda mais a história completa do processo até o momento n, teremos

P (Xn+1 = 1|X0 = i0, X1 = i1, ..., Xn−1 = in−1, Xn = 2) = 1/2 (3.1)

P (Xn+1 = 3|X0 = i0, X1 = i1, ..., Xn−1 = in−1, Xn = 2) = 1/2 (3.2)

Observação 3.2. Podemos observar no exemplo anterior que as equações 3.1 e 3.2 sãosatisfeitas para qualquer escolha de i0, ..., in−1. Isto é consequência do lançamento notempo n + 1 ser independente de todos os anteriores e, portanto, independente tambémde X0, ..., Xn−1. Este fenômeno é chamado de "perda de memória", também conhecidacomo propriedade de markov.

Observação 3.3. Outra característica interessante destes processos estocásticos é quea distribuição condicional de Xn+1 dado que Xn = 2 é o mesmo para todos os n. Estapropriedade é conhecida como a homogeneidade do tempo, ou simplesmente homo-geneidade. Essa propriedade será considerada para os casos que iremos tratar nestetrabalho.

Definição 3.4 (Cadeia de Markov). Uma sequência de variáveis aleatórias (X0, X1, ...) éuma Cadeia de Markov com espaço de estado S, se para todo si, sj ∈ S, com n ≥ 1, temos

P (Xn+1 = sj|X0 = si0 , X1 = si1 , ..., Xn−1 = sin−1 , Xn = sin) = P (Xn+1 = sj|Xn = si)(3.3)

3.1. Introdução 17

Matriz de Transição

Definição 3.5. Seja P uma matriz k × k com elementos Pi,j : i, j = 1, ..., k. Umprocesso aleatório (X0, X1, ...) com espaço de estado finito S = s1, s2, ..., sk é dito seruma Cadeia de Markov com matriz de transição P, se ∀n, todo i, j ∈ 1, ..., k e todoi0, ..., in+1 ∈ 1, ..., k, nós temos:

P (Xn+1 = sj|X0 = si0 , X1 = si1 , ..., Xn−1 = sin−1 , Xn = sin) = P (Xn+ 1 = sj|Xn = si) = Pi,j

Observação 3.6. Os elementos da matriz de transição P são chamados de probabilidadede transição e temos que satisfaz:

i) Pi,j ≥ 0 ∀i, j ∈ 1, .., k

ii)∑kj=1 Pi,j = 1 ∀i ∈ 1, ..., k

Exemplo 3.7. Consideremos o exemplo do Passeio aleatório, apresentado anteriormente,que é uma Cadeia de Markov, com o espaço amostral 1,2,3,4 e matriz de transição:

P =

0 1

2 0 12

12 0 1

2 00 1

2 0 12

12 0 1

2 0

Distribuição inicialConsideremos outra característica importante de uma Cadeia de Markov (X0, X1, X2, ...)

nomeado de distribuição inicial, que nos diz como começamos o processo. Representamostal distribuição como vetor linha µ(0) dado por:

µ(0) = (µ(0)1 , µ

(0)2 , ..., µ

(0)k ) = (P (X0 = s1), P (X0 = s2), ..., P (X0 = sk)).

Como µ(0) representa a distribuição de probabilidade, nós temos:k∑i=1

µ(0)i = 1

Similarmente os vetores linhas (µ(1), µ(2), ...) denotam a distribuição da cadeia notempo 1,2,3..., da seguinte forma

µ(n) = (µ(n)1 , µ

(n)2 , ..., µ

(n)k , ) = (P (Xn = s1), P (Xn = s2), ..., P (Xn = sk)).

O resultado a seguir nos mostra que uma vez que sabemos a distribuição inicialµ(0) e a matriz de transição P, podemos computar todas as distribuições µ(1), µ(2), ..., daCadeia de Markov.


Teorema 3.8. Para a Cadeia de Markov (X0, X1, ...) com espaço de estado finito S =s1, s2, ..., sk, a distribuição inicial µ(0) e a matriz de transição P, nós temos que paraqualquer n a distribuição no tempo n satisfaz:

µ(n) = µ(0)P n,

onde P n = P × P × ...× P .

Demonstração. A demonstração segue por indução. Consideremos o caso onde n = 1, paraj = 1, 2, ..., k, temos

µ(1)j = P (X1 = sj) =

k∑i=1

P (X0 = si, X1 = sj)

=k∑i=1

P (X0 = si)P (X1 = sj|X0 = si)

=k∑i=1

µ(0)i Pi,j = (µ(0)P )j (3.4)

onde (µ(0)P )j denota o j-ésimo elemento do vetor linha µ(0)P . Daí, µ(1) = µ(0)P .

Fixando n = m, vamos supor que µ(m) = µ(0)Pm é válido. Basta mostrar então quepara n = m+ 1 é válido. Temos,

µ(m+1)j = P (Xm+1 = sj) =

k∑i=1

P (Xm = si, Xm+1 = sj)

=k∑i=1

P (Xm = si)P (Xm+1 = sj|Xm = si)

=k∑i=1

µ(m)i Pi,j = (µ(m)P )j (3.5)

então µ(m+1) = µ(m)P . Mas µ(m) = µ(0)Pm pela hipótese de indução, então:

µ(m+1) = µ(m)P = µ(0)P nP = µ(0)P n+1

como queríamos provar.

Exemplo 3.9. Voltando ao exemplo 3.1 com a seguinte distribuição inicial:

µ(0) = (1, 0, 0, 0)

e com a seguinte matriz de transição:

P =

0 1

2 0 12

12 0 1

2 00 1

2 0 12

12 0 1

2 0

3.2. Cadeias de Markov irredutíveis e aperiódicas 19

temos que as distribuições seguintes são dadas por

µ(1) =(

0, 12 , 0,

12

)

µ(2) =(1

2 , 0,12 , 0

)

...

µ(n) = µ(0)P n =

(12 , 0,

12 , 0), se n é par;

(0, 12 , 0,

12), se n é ímpar.

3.2 Cadeias de Markov irredutíveis e aperiódicasTomamos nota agora de duas condições importantes na teoria central de Markov,

começamos por irredutibilidade, que é a propriedade que "todos os estados da cadeia podemser alcançados por todos os outros". Consideremos uma Cadeia de Markov (X0, X1, ...)com espaço de estado S = s1, ..., sk e matriz de transição P. Dizemos que o estado si secomunica com sj, escrevemos si −→ sj, se a cadeia tem probabilidade positiva de atingirsj, quando começamos de si. Em outras palavras, si se comunica com sj se existe n talque

P (Xm+n = sj|Xm = si) > 0

Se si −→ sj e sj −→ si, então dizemos que elas intercomunicam-se e escrevemos si ↔ sj.

Definição 3.10. Uma Cadeia de Markov (X0, X1, ...) com espaço de estado S = s1, ..., ske matriz de transição P é dita ser irredutível se para todo si, sj ∈ S temos que si ↔ sj.Caso contrário a cadeia é dita ser redutível.

Observação 3.11. Uma cadeia é irredutível se, e somente se, para todo si, sj ∈ S, existen tal que (P n)i,j > 0. Vejamos um exemplo em que não é irredutível.

Exemplo 3.12. (Uma Cadeia de Markov redutível) Considerando uma cadeia deMarkov (X0, X1, ...) com estado de espaço S = 1, 2, 3, 4 e matriz de transição

P =

0, 5 0, 5 0 00, 3 0, 7 0 0

0 0 0, 2 0, 80 0 0, 8 0, 2

. (3.6)

Essa cadeia pode ser representada pela figura abaixo


Figura 5 – Grafo para a Cadeia P em 3.6

Analisando o grafo, imediatamente vemos que se a cadeia começa em 1 e 2, entãoela se restringe aos estados 1 e 2 sempre. O caso é similar se começa dos estados 3 e 4.Portanto a cadeia é redutível.

Note que se a cadeia começar do estado 1 ou 2, então ela se comporta como sefosse uma Cadeia de Markov com estado de espaço 1, 2 e matriz de transição:

P1,2 = 0, 5 0, 5

0, 3 0, 7

E se começarmos em 3 ou 4, então se comporta como uma Cadeia de Markov com espaçode estado 3, 4 e matriz de transição:

P3,4 = 0, 2 0, 8

0, 8 0, 2

Isso ilustra uma característica de Cadeias de Markov redutíveis, que também explica otermo "redutível ".

Passamos a considerar o conceito de aperiodicidade. Porém antes é necessário quese definia o conceito de período.

Definição 3.13. Seja S = s1, ..., sk, o período p(si) de um estado si ∈ S é definidocomo

p(si) = mdcn ≥ 1 : (P n)i,i > 0

Em outras palavras, o período de si é o maior divisor comum do conjunto de vezesque a cadeia pode retornar( isto é, tem probabilidade positiva de retorno) a si, dado quecomeçamos com X0 = si. Se d(si) = 1, então dizemos que o estado si é aperiódico.

Definição 3.14. A cadeia de Markov é dita aperiódica se todos os estados são aperiódicos.Caso contrário é chamada de periódica.

3.3. Distribuição Estacionária 21

Exemplo 3.15. Considerando o exemplo 3.1, do Passeio Aleatório, inicialmente no tempo0 o caminhante está no vértice v1. Claramente, ele precisa tomar um número par de vérticespara voltar a v1. Isto significa que (P n)i,i > 0 apenas para n = 2, 4, 6.... Consequentemente,

mdcn > 1 : (P n)i,i > 0) = mdc2, 4, 6 = 2

portanto, a cadeia é periódica.

O teorema a seguir será de suma importância na demonstração do teorema deconvergência. Sua demonstração pode ser encontrada em [6].

Teorema 3.16. Suponhamos que temos uma Cadeia de Markov irredutível e aperiódica(X0, X1, ...) com espaço de estado s = s1, ..., sk e matriz de transição P . Então existeN <∞ tal que

(P n)i,j > 0 ∀i ∈ 1, 2, ..., k e ∀n > N.

3.3 Distribuição EstacionáriaNesta seção, iremos considerar uma das questões centrais na teoria de Markov :

Assintótica. Para o comportamento a longo prazo das Cadeias de Markov, o que podemosafirmar? Se a cadeia tem sido executada por um longo tempo, podemos encontrar teoremasassintóticos interessantes ?

Definição 3.17. Seja (X0, X1, ....) uma Cadeia de Markov com espaço de estado S =s1, ..., sk e matriz de transição P. Um vetor linha (π1, ..., πk) é dito ser uma distribuiçãoestacionária para a Cadeia de Markov, se satisfaz :

i) πi ≥ 0, para i = 1, ..., k e ∑ki=1 πi = 1

ii) πP = π , ou seja, ∑ki=1 πiPi,j = πj ∀j = 1, ..., k.

Observação 3.18. A propriedade i) ,da definição ??, traduz a ideia de que π descreveuma distribuição de probabilidade em s1, ..., sk. Enquanto a propriedade ii) implica quese a distribuição µ(0) = π então a distribuição da cadeia no tempo 1, satisfaz

µ(1) = µ(0)P = πP = π

Consequentemente, por iteração, teremos que µ(n) = π.

Agora, iremos tratar três questões: a existência da distribuição estacionária, aunicidade das distribuições estacionárias e a convergência a partir de qualquer distribuiçãoinicial. Para isso vamos considerar as condições introduzidas na seção anterior (irredutibi-lidade e aperiodicidade), embora para alguns dos resultados essas condições possam seresquecidas.


Antes de provar o teorema de existência, iremos enunciar um lema. Para isto,consideremos as seguintes definições:

Definição 3.19. Se uma Cadeia de Markov (X0, X1, ...) com espaço de estado s1, ..., ske matriz de transição P começa em si, então podemos definir o tempo de chegada a sj

Ti,j = minn > 1 : Xn = sj,

onde Ti,j =∞ quando a cadeia nunca visita sj. Nós também definimos o tempo médio dechegada como

τi,j = E[Ti,j]

Lema 3.20. Para qualquer Cadeia de Markov aperiódica e irredutível com estado de espaçoS = s1, ..., sk e matriz de transição P, nós temos para qualquer dois estados si, sj ∈ Sse a cadeia começa de si, então

P (Ti,j <∞) = 1 (3.7)

Além disso, o tempo médio de chegada é finito, isto é,

E[Ti,j] <∞ (3.8)

Demonstração. Se encontra no apêndice A.1.

Teorema 3.21 (Extistência de distribuição Estacionária). Para qualquer Cadeia deMarkov irredutível e aperiódica, existe pelo menos uma distribuição estacionária.

Demonstração. Escreva, como usualmente (X0, X1, ...) para uma Cadeia de Markov, S =s1, s2, ..., sk para espaço estado e P para a matriz de transição. Suponhamos que a cadeiacomeça em s1 e defina, para i = 1, ..., k ,

ρi =∞∑n=1

P (Xn = si, T1,1 > n)

em outras palavras, ρi é o número de visita do estado i até o tempo T1,1 − 1. Como otempo médio de retorno E[T1,1] = τ1,1 é finito e ρi < τ1,1, assim ρi é finito também.

Nosso candidato para a distribuição estacionária é

π = (π1, π2, ..., πn) =(ρ1

τ1,1,ρ2

τ1,1, ...,

ρnτ1,1

)

Vamos verificar que π satisfaz as condições (i) e (ii) da definição ??. Mostraremosprimeiro a relação ∑k

i=1 πiPi,j = πj , na condição (ii) para o caso em que j 6= 1 (O caso em


que j=1 será tratado separadamente). Temos,

πj = ρiτ1,1

= 1τ1,1

∞∑n=0

P (Xn = sj, T1,1 > n)

= 1τ1,1

∞∑n=1

P (Xn = sj, T1,1 > n− 1) (3.9)

= 1τ1,1

∞∑n=1

k∑i=1

P (Xn−1 = si, Xn = sj, T1,1 > n− 1) (3.10)

= 1τ1,1

∞∑n=1

k∑i=1

P (Xn−1 = si, T1,1 > n− 1)P (Xn = sj | Xn−1 = si) (3.11)

= 1τ1,1

∞∑n=1

k∑i=1

P (Xn−1 = si, T1,1 > n− 1)

= 1τ1,1

k∑i=1

Pi,j∞∑n=1

P (Xn−1 = si, T1,1 > n− 1)

= 1τ1,1

k∑i=1

Pi,j∞∑m−0

P (Xm = si, T1,1 > m)

=k∑i=1

ρiτ1,1

Pi,j =k∑i=1

πiPi,j (3.12)

onde nas linhas (3.9), (3.10) e (3.11) iremos assumir que j 6= 1; note também que em(3.11) usamos o fato de que o evento T1,1 > n− 1 é determinado somente pelas variáveisX0, X1, ..., Xn−1.

Agora vamos verificar a condição (ii) também para j = 1. Note primeiro que ρ1 = 1,isto segue da definição de ρi. Temos,

ρ1 = P (T1,1 <∞)

=∞∑n=1

P (T1,1 = n)

=∞∑n=1

k∑i=1

P (Xn−1 = si, T1,1 = n)

=∞∑n=1

k∑i=1

P (Xn−1 = si, T1,1 > n− 1)P (Xn = s1 | Xn−1)

=∞∑n=1

Pi,1k∑i=1

P (Xn−1 = si, T1,1 > n− 1)

=k∑i=1

Pi,1∞∑n=1

P (Xn−1 = si, T1,1 > n− 1)

=k∑i=1

Pi,1∞∑m=0

P (Xm = si, T1,1 > m)

=k∑i=1

ρi Pi,1


Consequentemente,

π1 = ρ1

τ1,1=

k∑i=1

ρiPi,1τ1,1

=k∑i=1

πiPi,1 (3.13)

Combinando a equação acima com (3.12), estabelecemos que a condição (ii) é válidapara nossa escolha de π.

Agora basta verificar a condição (i). Que πi ≥ 0, ∀i = 1, ..., k é imediato. Vamosverificar que ∑k

i=1 πi = 1, note que

τ1,1 = E[T1,1] =∞∑n=0

P (T1,1 > n) (3.14)

=∞∑n=0

k∑i=1

P (Xn = si, T1,1 > n)

=k∑i=1

∞∑n=0

P (Xn = si, T1,1 > n)

=k∑i=1

ρi (3.15)

usando (A.2) em (3.14).

Então,k∑i=1

πi = 1τ1,1

k∑i=1

ρi = 1

e a condição (i) é satisfeita.

Para demonstrar o Teorema 3.24, precisamos definir o que significa uma sequênciade distribuição de probabilidade ν(1), ν(2), ... convergir para outra distribuição. Para isto, énecessário definir uma métrica em distribuição de probabilidade. Em particular, iremosutilizar a métrica chamada distância de variação total. (Veja mais sobre isso no capítulo5)

Definição 3.22. Se ν(1) = (ν(1)1 , ..., ν

(1)k ) e ν(2) = (ν(2)

1 , ..., ν(2)k ) são distribuições de proba-

bilidade em S = s1, ..., sk, então definimos a distância de variação total entre ν(1) e ν(2)

como

dvt(ν(1), ν(2)) = 12

k∑i=1|ν(1)i − ν

(2)i | (3.16)

Dizemos que ν(n) converge para ν com n −→∞, e escrevemos ν(n) V T−→ ν, se

limn−→0

dvt(ν(n), ν) = 0


Observação 3.23. Tem-se que dV T é uma métrica no espaço das medidas de probabilidadesobre S = s1, s2, ..., sk.

Teorema 3.24 (Convergência de Cadeias de Markov). Seja (X0, X1, ...) uma cadeiade Markov irredutível e aperiódica com estado de espaço S = s1, ..., sk e matriz detransição P , e distribuição inicial arbitrária µ(0). Então, para qualquer distribuição π queé estacionária para a matriz de transição P , temos

µ(n) V T−→ π (3.17)

Demonstração. Inicialmente, definiremos duas funções para nos auxiliar a simular cadeiasde Markov. Fixando µ uma medida de probabilidade em S, defina para cada x ∈ [0, 1]:

ψµ(x) =

s1, para x ∈ [0, µ(s1)];

s2, para x ∈ [µ(s1), µ(s1) + µ(s2)];...

si, para x ∈ [∑i−1j=1 µ(sj),

∑ij=1 µ(sj)];

...

sk, para x ∈ [∑k−1j=1 µ(sj), 1].

(3.18)

Agora, defina φ : S × [0, 1] −→ R por:

φ(si, x) =

s1, para x ∈ [0, Pi,1];

s2, para x ∈ [Pi,1, Pi,1 + Pi,2];...

sj, para x ∈ [∑j−1l=1 Pi,l,

∑jl=1 Pi,l];

...

sk, para x ∈ [∑k−1l=1 Pi,l, 1].

(3.19)

Vamos simular a cadeia usando as funções acima. Para isso, considere (U0, U1, ...)uma sequência i.i.d. de variáveis uniforme [0, 1] e defina:

X0 =ψµ(0)(U0)X1 =φ(X0, U1)X2 =φ(X1, U2)

...Xn =φ(Xn−1, Un)

...


Observe que X0 ∼ µ(0), de fato,

P (X0 = s1) = P (0 ≤ U ≤ s1) = µ(0)(s1)P (X0 = s2) = P (s1 ≤ U ≤ s1 + s2) = µ(0)(s1).

Analogamente, as variáveis X0, X1, ..., Xn, ... tem distribuição dada por:

X0 =ψµ(0)(U0) ∼ µ(0)

X1 =φ(X0, U1) ∼ µ(0)P

X2 =φ(X1, U2) ∼ µ(0)P 2

...Xn =φ(Xn−1, Un) ∼ µ(0)P n

...

Em seguida, introduziremos uma segunda Cadeia de Markov (X ′0, X ′1, ...) com distri-buição inicial π. Para isso, utilizamos uma outra sequência (U ′0, U ′1, ...) i.i.d.(independentede (U ′0, U ′1, ...) ) uniforme [0, 1], e com configuração

X ′0 =ψπ(U0) ∼ π

X ′1 =φ(X ′0, U ′1) ∼ πP = π

X ′2 =φ(X ′1, U ′2) ∼ πP 2 = π

...X ′n =φ(X ′n−1, U

′n) ∼ πP n = π

...

Desde que π é distribuição estacionária, temos que X ′n tem distribuição π paraqualquer n. Também as cadeias (X0, X1, ...) e (X ′0, X ′1, ...) são independentes uma da outra,pelo pressuposto de que as sequências (U0, U1, ...) e (U ′1, U ′2, ...) são independentes.

Um passo-chave na prova é mostrar que, com probabilidade um, as duas cadeias "seencontrarão", significando que ∃n tal que Xn = X ′n. Para mostrar isso, defina o momentoem que eles se encontram como

T = minn : Xn = X ′n

escrevemos T =∞ se as cadeias nunca se encontram. Como a Cadeia de Markov (X0, X1, ...)é irredutível e aperiódica, podemos usar o teorema 3.16 que diz que existe M <∞ tal que

(PM)i,j > 0 ∀i, j ∈ 1, ..., k

eα = min(PM)i,j i ∈ 1, ..., k


e note que α > 0. Temos que,

P (T ≤M) ≥ P (XM = X ′M)≥ P (XM = s1, X

′M = s1)

= P (XM = s1)P (X ′M = s1)

=(

k∑i=1

P (X0 = si, XM = s1))(

k∑i=1

P (X ′0 = si, X′M = s1)

)

=(

k∑i=1

P (X0 = si)P (XM = s1|X0 = si))(

k∑i=1

P (X ′0 = si)P (X ′M = s1|X ′0 = si))

≥(α

k∑i=1

P (X0 = si))(

αk∑i=1

P (X ′0 = si))

= α2

então,P (X ≤M) ≤ 1− α2

Da mesma forma, dado tudo que aconteceu até M, temos probabilidade condicionalpelo menos α2 de ter X2M = X ′2M = s1, então

P (X2M 6= X ′2M |T > M) ≥ 1− α2

Consequentemente,

P (T > 2M) = P (T > M)P (T > 2M |T > M)≥ (1− α2)P (T > 2M |T > M)≥ (1− α2)P (X2M 6= X ′2M |T > M)≥ (1− α2)2

Iterando este argumento, temos para qualquer ` que

P (T > `M) ≤ (1− α2)`

que tende para zero quando ` −→∞. Consequentemente,

limn−→∞

P (T > n) = 0 (3.20)

Em outras palavras, mostramos que as duas cadeias se encontrarão com probabili-dade igual a um.

O próximo passo é construir uma terceira Cadeia de Markov (X ′′0 , X ′′1 , ...) onde

X ′′0 = X0 (3.21)

e para cada n,

X ′′n+1 =

φ(X ′′n, Un+1), se X ′′n 6= X ′n

φ(X ′′n, U ′n+1), se X ′′n = X ′n


Em outras palavras, a cadeia (X ′′0 , X ′′1 , ...) evolui exatamente como a cadeia (X0, X1, ...)até o momento T quando se encontram pela primeira vez com a cadeia (X ′0, X ′1, ...), evo-luindo da mesma forma que esta última cadeia após esse momento. É importante perceberque (X ′′0 , X ′′1 , ...) é realmente uma cadeia com matriz de transição P.

Isto pode exigir uma pausa no pensamento, mas a razão básica pela qual é verdadeiraé que em cada atualização, a função de atualização é exposta a uma nova variável uniforme"fresh"[0, 1], ou seja, uma que é independente de todas as outras variáveis aleatórias (sea nova cadeia é exposta a Un+1 ou a U ′n+1 depende dos valores anteriores das variáveisuniformes [0, 1], mas isso não importa, uma vez que Un+1 e U ′n+1 tem a mesma distribuiçãoe são independentes de tudo o que aconteceu até o tempo n).

Devido a (3.21), temos que X ′′0 tem distribuição µ(0). Consequentemente, paraqualquer n, X ′′n tem distribuição µ(n). Agora, para qualquer i ∈ 1, ..., k

µ(n)i − πi = P (X ′′n = si)− P (X ′n = si)

≤ P (X ′′n = si, X′n 6= si)

≤ P (X ′′n 6= X ′n)= P (T > n)

que tende a zero quando n −→∞, devido a (3.20). Usando o mesmo argumento, temosque

πi − µ(n)i ≤ P (T > n)

de mesmo modo, tende a zero quando n −→∞. Consequentemente,

limn−→∞

| µ(n)i − πi |= 0 (3.22)

Isto implica que

lim dV T (µ(n), π) = lim(

12

k∑i=1| µ(n)

i − πi |)

(3.23)

uma vez que cada termo do lado direito de (3.23) tende a zero. Concluímos então que(3.17) é válido.

Teorema 3.25 (Unicidade da distribuição Estacionária). Qualquer Cadeia de Markovirredutível e aperiódica tem exatamente uma distribuição estacionária.

Demonstração. Seja (X0, X1, ...) uma Cadeia de Markov irredutível e aperiódica commatriz de transição P. Sabemos, pelo teorema 3.21, que existe pelo menos uma distribuiçãoestacionária para P, então temos que mostrar que esta distribuição é única.

Suponhamos, por absurdo, que existem duas distribuições estacionárias, isto é,temos que π e π′ são distribuições estacionárias para P, temos que provar que π = π′.

3.4. Cadeias reversíveis 29

Agora suponha que a Cadeia de Markov começa com a distribuição inicial µ(0) = π′

então µ(n) = π′ ∀n, pois π′ é estacionária.Por outro lado, o teorema 3.24 diz que µ(n) V T−→ π,significa que

limn−→∞dvt(µ(n), π) = 0

Mas µ(n) = π′, isto é o mesmo que

limn−→∞dvt(π′, π) = 0

Mas dvt(π′, π) não depende de n e é igual a 0, isto implica que π = π′, como queríamos.

3.4 Cadeias reversíveisIntroduziremos, nesta seção, uma classe especial de Cadeias de Markov conhecida

como reversíveis, que são interessantes de serem estudas pois é uma propriedade fácil deser verificada e implica estacionariedade.

Definição 3.26. Seja (X0, X1, ....) uma Cadeia de Markov com espaço de estado S =s1, ..., sk e matriz de transição P. Uma distribuição de probabilidade π em S é ditareversível para a cadeia(ou para a matriz de transição P) se ∀i, j ∈ 1, ..., k temos

πiPi,j = πjPj,i (3.24)

Temos então que se a Cadeia é iniciada com a distribuição reversível, então o ladoesquerdo da equação 3.24 pode ser pensado como a quantidade de massa de probabilidadeque flui no tempo 1 do estado si ao estado sj. Similarmente, o lado direito é a massa deprobabilidade que flui de sj para si. Isto nos mostra uma forte forma de equilíbrio e oseguinte resultado nos mostrará isso.

Teorema 3.27. Seja (X0, X1, ....) uma Cadeia de Markov com espaço de estado S =s1, ..., sk e matriz de transição P. Se π é uma distribuição reversível da cadeia, então étambém uma distribuição estacionária para a cadeia.

Demonstração. A Propriedade (i) da Definição 3.17 é imediata. Assim só resta mostrarque para qualquer j ∈ 1, ..., k temos

πj =k∑i=1

πiPi,j.

Observe que,

πj = πjk∑i=1

Pj,i =k∑i=1

πjPj,i =k∑i=1

πiPi,j.

pois ∑ki=1 Pj,i = 1.


Exemplo 3.28 (Passeios Aleatórios em Grafos). Um grafo G = (V,E) consiste emum conjunto de vértices V = v1, ..., vk, juntamente com um conjunto de arestas E =e1, ..., el.

v7

v3v2

v6 v8

v4

v1

v5

Figura 6 – Um grafo

Um passeio aleatório em um gráfico G = (V,E) é uma Cadeia de Markov comestado de espaço V = v1, ..., vk e o seguinte mecanismo de transição: se o caminhantealeatório se posiciona num vértice vi no instante n, então move-se no tempo n+ 1 paraum dos vizinhos de vi escolhidos aleatoriamente, com igual probabilidade para cada umdos vizinhos. Assim, se denotamos o número de vizinhos de um vértice vi por di, então oselementos da matriz de transição são dados por

Pi,j =

1di, se vi e vjsão vizinhos

0, caso contrário

Acontece que os passeios aleatórios em grafos são Cadeias de Markov reversíveis,com distribuição reversível dada por

π =(d1

d,d2

d, ...,

dkd

)(3.25)

Onde d = ∑ki=1 di. Para ver que (3.24) se mantém para esta escolha de π, calculamos

πiPi,j =

did

1di

= 1d

= djd

1dj

= πjPj,i, se si e sjsão vizinhos

0, caso contrário

Para o grafo na figura 6, (3.25) torna-se

π =( 2

24 ,324 ,

524 ,

324 ,

224 ,

324 ,

324 ,

324 ,

)De modo que em equilíbrio, v3 é o vértice mais provável para o passeador aleatório estar,enquanto v1 e v5 são os menos prováveis.

31

4 Cadeias de Markov de Monte Carlo

Neste capítulo, faremos uma breve introdução sobre o método de Monte Carlo viaCadeias de Markov, mais especificamente o algoritmo de Metropolis. Foram utilizadas asseguintes referências [7] e [6], como texto base.

4.1 IntroduçãoNeste capítulo, vamos considerar o seguinte problema: dada uma distribuição π em

S = s1, ..., sk, como simulamos uma variável aleatória com distribuição π?

Para tentar responder a questão vamos considerar o exemplo seguinte.

Exemplo 4.1 (Modelo Hardcore). Seja G = (V,E) um grafo com o conjunto de vérticesV = v1, ..., vk e arestas E = e1, ..., ek. No chamado modelo Hardcore em G, atribuímoso valor 0 ou 1 a cada um dos vértices, de tal modo que nenhum dos dois vértices adjacentestomem o valor 1.

As atribuições 0′s e 1′s aos vértices são chamados configurações e podem se consi-deradas como elementos do conjunto 0, 1V . As configurações em quem nenhum dois 1′socupam vértices adjacentes são chamadas configurações permitidas.

Para escolhermos uma configuração aleatória possível, iremos tomar cada umadas configurações possíveis com igual probabilidade. Escrevemos µG para a medida deprobabilidade resultante em 0, 1V . Consequentemente, para ξ ∈ 0, 1V , temos

µG(ξ) =

1zG, se ξ é possível,

0, caso contrário.(4.1)

onde zG é o número total de configurações permitidas para G.

Veja a figura a seguir, para uma configuração aleatória escolhida de acordo com µG

no caso em que G é uma malha quadrada de tamanho 8× 8.

Figura 7 – Configuração possível para uma malha 8x8

32 Capítulo 4. Cadeias de Markov de Monte Carlo

Uma pergunta interessante a se fazer seria: qual é o número esperado de 1′s emuma configuração aleatória de acordo com µG? Se escrevemos n(ξ) para o número de 1′sna configuração ξ, e X para uma configuração aleatória escolhida de acordo com µG entãoeste valor esperado é dado por

E[n(X)] =∑

ξ∈0,1V

n(ξ)µG(ξ) = 1zG

∑ξ∈0,1V

n(ξ)Iξépossível (4.2)

Avaliar essa soma pode ser inviável a menos que o grafo seja muito pequeno,uma vez que o número de configurações(e portanto, o número de termos da soma) cresceexponencialmente no tamanho do grafo. Se a maioria dos termos tem valor 0, pode ajudarum pouco, mas o número de termos de zero cresce exponencialmente também. Observe queo cálculo de zG é não trivial computacionalmente.

Quando a expressão exata em (4.2) esta além do que nossos recursos computacionaispodem lidar, uma opção seria modificar para simulações. Se soubermos como simular umaconfiguração aleatória X com distribuição µG, então podemos fazer isso muitas vezes, eestimar E[n(X)] pelo número médio de 1′s nas simulações. Pela Lei de Grandes Números(Teorema 2.32), esta estimativa converge para o verdadeiro valor de E[n(X)].

Com este exemplo em mente, nos perguntamos: como podemos simular uma variávelaleatória X distribuída de acordo com uma dada distribuição de probabilidade π em umespaço de estado S = s1, ..., sk?

Para solucionar a questão acima, podemos considerar a variável aleatória

X = ψ(U),

onde U tem distribuição variável uniforme [0,1] e a função ψ : [0, 1] −→ S é dada por:

ψ(x) =

s1, para x ∈ [0, π(s1)];

s2, para x ∈ [π(s1), π(s1) + π(s2)];...

si, para x ∈ [∑i−1j=1 π(sj),

∑ij=1 π(sj)];

...

sk, para x ∈ [∑k−1j=1 π(sj), 1].

(4.3)

Vemos que com esta função obtemos a distribuição desejada π, pois

P (X = s1) = P (ψ(U) = s1) = P (U ∈ [0, π(s1)]) = π(sj),

seguindo de forma análoga para os outros casos.

4.1. Introdução 33

Na prática, no entanto, esta abordagem é inviável a menos que o espaço de estadoS seja pequeno pois π é desconhecido. Para o modelo Hardcore, apresentado anteriormente,em uma malha do tamanho de um tabuleiro de xadrez ou maior, a avaliação da função ψtorna-se demasiadamente complicada para este método ser de qualquer utilização prática,devido ao cálculo de zG que não é trivial.

Como podemos observar para alguns grafos pode ser um desafio construir direta-mente uma amostra aleatória. Um outro modo de resolver esse problema seria o seguinte :suponhamos que podemos construir uma Cadeia de Markov Xn irredutível e aperiódica,com distribuição estacionária π. Se iniciarmos a cadeia com uma distribuição inicial arbitrá-ria então do teorema de convergência para Cadeias de Markov (Teorema 3.24), garantimosque a distribuição da cadeia no tempo n converge para π, quando n −→∞. Este métodode amostragem a partir de uma dada distribuição de probabilidade é chamado MonteCarlo via Cadeias de Markov.

Contudo, como podemos construir uma Cadeia de Markov com essa propriedade?Por que isso seria mais fácil do que construir uma variável aleatória com distribuição πdiretamente? Vejamos o problema do modelo do Hardcore.

Exemplo 4.2 (Um algoritmo de Monte Carlo via Cadeias Markov para o modelo Hardcore).Consideremos o modelo Hardcore no Exemplo 4.1 com um Grafo G = (V,E). Para obterum algoritmo MCMC para este modelo, precisamos construir uma Cadeia de Markov cujoespaço de estado S é o conjunto de configurações permitidas para G, isto é,

S = ξ ∈ 0, 1V : ξ é permitida (4.4)

Além disso, queremos que a Cadeia de Markov seja irredutível, aperiódica e tenhadistribuição estacionária µG dada por (4.1).

Uma cadeia de Markov com as propriedades desejadas pode ser obtida utilizando oseguinte mecanismo de transição. Em cada tempo inteiro n+ 1, fazemos o seguinte:

1) Escolha um vértice v ∈ V aleatoriamente e de modo uniforme;

2) Jogue uma moeda justa;

3) Se a moeda der cara e todos os vizinhos de v tomam o valor 0 em Xn, entãofazemos Xn+1(v) = 1, caso contrário Xn+1(v) = 0;

4) Para todos os vértices w 6= v, deixe o valor em w inalterado, isto é, deixeXn+1(w) = Xn(w).

Vamos escrever d = d(ξ, ξ′) para o número de vértices em que ξ e ξ′ diferem. Este


este algoritmo define uma Cadeia de Markov em S com matriz de transição Pξ,ξ′:

Pξ,ξ′ =

12k , se d = 1;

0, se d ≥ 2;

1−∑

ξ′:d(ξ,ξ′)=1

12k se d = 0.

(4.5)

Esta cadeia é irredutível pois, segundo esse algoritmo, conseguimos atingir qualquerestado ξ′ a partir de qualquer estado ξ o que satisfaz a definição 3.10. Podemos verificartambém que é aperiódica pois é possível permanecer na mesma configuração a cada iteração,satisfazendo a definição 3.14. Portanto, resta mostrar apenas que µG é uma distribuiçãoestacionária para a cadeia. Pelo Teorema 3.27 basta mostrar que µG é reversível. SendoPξ,ξ′ denotam a probabilidade de transição do estado ξ para ξ′, precisamos verificar que

µG(ξ)Pξ,ξ′ = µG(ξ′)Pξ′,ξ (4.6)

para quaisquer duas configurações permitidas ξ e ξ′.

Para mostrar isso, considere d = d(ξ, ξ′) nos três casos: d = 0, d = 1 e d ≥ 2.

1ºcaso- O caso d = 0 significa que ξ = ξ′, neste caso a relação (4.6) é imediata.

2ºcaso- O caso d ≥ 2 é fácil de ser verificado, pois a cadeia nunca muda os valoresem mais de um vértice, fazendo com que ambos os lados de (4.6) sejam iguais a zero.

3ºcaso- No caso d = 1, temos que ξ e ξ′ diferem exatamente em um vértice v.Então todos os vizinhos de v devem tomar o valor zero em ξ e ξ′, pois caso contrário, umadas configurações não pode ser permitida. Conseguimos, portanto que

µG(ξ)Pξ,ξ′ = 1zG

12k = µG(ξ′)Pξ′,ξ

e (4.6) é verificado (lembre-se que k é o número de vértices). Assim, a cadeia tem µG

como uma distribuição reversível (e, portanto, estacionária).

Podemos agora simular esta Cadeia de Markov usando o método citado acima. Umaescolha conveniente da função de atualização é dividir o intervalo [0, 1] em 2k subintervalosde igual comprimento 1/2k, representando as escolhas computacionalmente, da seguinteforma

(v1, cara), (v1, coroa), (v2, cara), ..., (vk, coroa)

Na descrição do mecanismo de transição acima, se agora executarmos a cadeia porum tempo n longo, começando com uma configuração inicial possível arbitrária e a saídaXn, então obtemos uma configuração aleatória cuja distribuição é aproximadamente µG,segundo o Teorema 3.24.

4.2. Cadeia de Metropolis 35

Observação 4.3. Acima temos um algoritmo de Cadeia de Markov de Monte Carlotípico em vários aspectos. Note que, embora só seja necessário que a cadeia tenha adistribuição desejada como uma distribuição estacionária, encontramos uma cadeia comuma propriedade ainda mais forte, de que a distribuição é reversível. Este é o caso para agrande maioria dos algoritmos de Cadeia de Markov de Monte Carlo conhecidos.

Outro procedimento geral importante é a construção da chamada Cadeia deMetropolis que veremos na seção a seguir. Além disso, estenderemos a discussão nocapítulo 5, onde será tratado a discussão sobre o tempo para que a distribuição Xn seaproxime de π.

4.2 Cadeia de Metropolis

Dada alguma cadeia com estado de espaço S e uma distribuição estacionáriaarbitrária π′, essa cadeia pode ser modificada para que a nova cadeia tenha distribuiçãoestacionária π que desejamos? O algoritmo de Metropolis realiza isso. 1

Mostraremos agora como modificar as transições feitas de acordo com Q para obteruma cadeia com distribuição estacionária π, onde π é uma distribuição de probabilidadeem Ω. A nova cadeia evolui da seguinte maneira: quando no estado x, um candidato aomovimento é gerado a partir da distribuição Q(x, ·), se o novo estado proposto for y, entãoo movimento é impedido com probabilidade 1−a(x, y). Isto é, com probabilidade a(x, y), oestado y é "aceito"e com probabilidade 1− a(x, y) a cadeia permanece em x. Rejeitar essesmovimentos diminui a velocidade da cadeia e pode reduzir sua eficiência computacional,mas isso é necessário para atingir a distribuição estacionária que queremos.

Com base nessa modificação, criamos uma nova cadeia que tem matriz de transiçãoP dada por:

P (x, y) =

Q(x, y)a(x, y), se y 6= x,

1−∑z:z 6=x

Q(x, z)a(x, z), se y = x.

A distribuição π será estacionária para a cadeia P se for reversível, isto é, se

π(x)Q(x, y)a(x, y) = π(y)Q(y, x)a(y, x) (4.7)

para todo x 6= y.1 Como no exemplo do modelo Hardcore muitas vezes o espaço de estados de uma Cadeia de Markov

não é sempre o conjunto de vértices de um grafo, mas sim o conjunto das configurações sobre umgrafo. Assim, daqui em diante, vamos considerar o espaço de estados Ω como sendo o conjunto dasconfigurações sobre um grafo.


Suponha que Q seja uma matriz de transição simétrica. Neste caso, se escolhermosa probabilidade de aceitação da seguinte forma

a(x, y) = minπ(y)π(x) , 1

então a equação (4.7) será satisfeita. Assim a matriz de transição da cadeia modificadaserá

P (x, y) =

Q(x, y) min

π(y)π(x) , 1

, se x 6= y

1−∑z:z 6=x

Q(x, z) minπ(x)π(x) , 1

, se x = y

(4.8)

Agora, para o caso de uma matriz Q qualquer, tomaremos a probabilidade deaceitação a(x, y) igual a

minπ(y)Q(y, x)π(x)Q(x, y) , 1

.

Então a equação (4.7) também é satisfeita para este caso. Assim, a matriz detransição será

P (x, y) =

Q(x, y) min

π(y)Q(y, x)π(x)Q(x, y) , 1

; se x 6= y,

1−∑z:z 6=xQ(x, z) minπ(z)Q(z, x)π(x)Q(x, z) , 1

, se x = y.

(4.9)

Exemplo 4.4 (Escolher um vértice uniformemente ao acaso em um grafo desconhecido).Suponha que você não conhece nenhum vértice definido em V , nem o conjunto de arestasE de um grafo G. No entanto, você é capaz de realizar um simples passeio aleatório em G

(muitas redes de computadores e sociais tem esta forma, cada vértice sabe quem são seusvizinhos, mas não a estrutura global do grafo). Se o grafo não é regular, então a distribuiçãoestacionária não é uniforme, de modo que a distribuição do passeio não convergirá parauma distribuição uniforme.

Você deseja uma amostra uniforme de V . Podemos então usar o algoritmo de Me-tropolis para modificar o passeio aleatório simples e garantir uma distribuição estacionáriauniforme. A probabilidade de aceitação reduz-se neste caso a

mindidj, 1

Isso distorce o passeio contra a mudança dos vértices de grau mais alto, dando umadistribuição estacionária uniforme. Observe que não é necessário saber o tamanho doconjunto de vértices para executar essa modificação, o que pode ser uma consideraçãoimportante nas aplicações.

4.2. Cadeia de Metropolis 37

Exemplo 4.5 (Otimização). Seja f uma função de valor real definida no conjunto devértices Ω de um grafo, isto é, f : Ω −→ R. Em muitas aplicações, é desejável encontrarum vértice x onde f(x) é máximo. Se o domínio Ω for muito grande, uma busca exaustivapode ser muito custosa.

A hill climb é um algoritmo que tenta localizar os valores máximos de f do seguintemodo: quando em x, se y ∼ x e f(y) > f(x), mude para y. Quando f tem máximos locaisque não são máximos globais, o alpinista pode ficar preso antes de descobrir um máximoglobal - veja na figura a seguir.

Figura 8 – Um algoritmo de hill climb onde pode-se ficar preso no máximo local

Uma solução é aleatorizar movimentos para que em vez de permanecer sempre emum máximo local, com alguma probabilidade o alpinista se mover para estados mais baixos.

Suponha, por simplicidade, que Ω é um grafo regular, de modo que a caminhadaaleatória simples em Ω possui uma matriz de transição simétrica. Fixe λ ≥ 1 e defina,

πλ(x) = λf(x)

Z(λ)

onde Z := ∑x∈Ω λ

f(x) é a constante de normalização que cria uma medida de probabilidadeπλ.

Observação 4.6. Assim como no exemplo do Hardcore Z(λ) não deve ser calculado poispode ser muito difícil e custoso.

Como πλ(x) está aumentando em f(x), a medida πλ favorece vértices x para osquais f(x) é grande.

Se f(y) < f(x), a cadeia de Metropolis aceita uma transição de x para y comprobabilidade λ−[f(x)−f(y)].

Defina,Ω∗ = x ∈ Ω : f(x) = f∗ := max

y∈Ωf(y)


Entãolimλ−→∞

πλ(x) = limλ−→∞

λf(x)/λf∗

|Ω ∗ |+∑x∈Ω−Ω∗ λf(x)/λf∗

Assim, quando λ −→∞ a distribuição estacionária πλ desta cadeia de Metropolisconverge para a distribuição uniforme sobre o máximo global de f .

39

5 Distância de Variação Total e Tempo deMistura

Neste capítulo vamos discutir o comportamento a longo prazo das Cadeias deMarkov com espaço de estados finito. Para isto iremos apresentar alguns conceitos baseadosnas referências [7] e [8]. Para não atrapalhar a fluidez do texto, decidiu-se omitir asdemonstrações desse capítulo, essas se encontram nas referências e no apêndice.

5.1 Introdução

A pergunta que rege este capítulo é: qual a velocidade de convergência das Cadeiasde Markov? Para responder essa pergunta, precisamos escolher, antes de mais nada, umamétrica apropriada para medir a distância entre distribuições.

Primeiramente vamos definir essa métrica, a distância de variação total, e algunsde seus resultados. Com base no Teorema de Convergência 3.24 sabemos que quandotemos uma cadeia irredutível e aperiódica, a distribuição se aproxima da estacionária, ouseja, a distância de variação total entre elas se aproxima de zero. No restante do capítulo,apresentaremos a técnica de acoplamento e analisaremos o efeito da distribuição inicialna distância de estacionariedade e definiremos o tempo de mistura de uma cadeia, querepresenta o tempo necessário para que a cadeia se aproxime da estacionária.

5.2 Distância de variação total

Definição 5.1. A distância de variação total(dV T ) entre duas distribuições de probabili-dade µ e ν em Ω é definida por

‖ µ− ν ‖V T= maxA⊂Ω| µ(A)− ν(A) | . (5.1)

Definição probabilística: a distância entre µ e ν é a diferença máxima entre asprobabilidades distribuídas a um único evento pelas duas distribuições.

A Definição 5.1, o máximo é tomado sobre todos os subconjuntos de Ω. Portanto,usar esta definição nem sempre é a maneira mais conveniente de estimar a distância. Aseguir, daremos duas caracterizações alternativas úteis.

As proposições 5.2 e 5.5 reduzem a distância de variação total a uma simples somasobre o espaço de estados.

40 Capítulo 5. Distância de Variação Total e Tempo de Mistura

Proposição 5.2. Sejam µ e ν duas distribuições de probabilidade em Ω. Então:

‖ µ− ν ‖V T = 12∑x∈Ω| µ(x)− ν(x) |

Demonstração. Ver em [7].

Observação 5.3. Da Proposição 5.2 e da desigualdade triangular para números reais,verificamos imediatamente que a dV T satisfaz a desigualdade triangular para as distribuiçõesde probabilidade µ, ν e η.

‖ µ− ν ‖V T≤‖ µ− η ‖V T + ‖ η − ν ‖V T (5.2)

Definição 5.4 (Acoplamento). Um acoplamento de duas distribuições de probabilidade µe ν é um par de variáveis aleatórias (X,Y) definidas em um único espaço de probabilidadetal que a distribuição marginal de X é µ e a distribuição marginal de Y é ν. Isto é, umacoplamento (X,Y) satisfaz PX = x = µ(x) e PY = y = ν(y). Os acoplamentos sãoúteis porque uma comparação entre distribuições é reduzida a uma comparação entrevariáveis aleatórias.

O acoplamento é uma técnica geral e poderosa, podendo ser aplicado de muitasmaneiras diferentes. Aqui, oferecemos uma breve introdução mostrando a ligação entreacoplamento de duas variáveis aleatórias e a distribuição de variação total entre essasvariáveis.

Proposição 5.5. Seja µ e ν duas distribuições de probabilidade em Ω. Então:

‖ µ− ν ‖V T= infPX 6= Y : (X, Y )é um acoplamento de µ e ν (5.3)

Demonstração. A demonstração se encontra na referência [7].

A proposição acima caracteriza ‖ µ − ν ‖V T como o mínimo sobre todos osacoplamentos (X,Y) de µ e ν, da probabilidade de X e Y serem diferentes. Isto proporcionaum método eficaz para obter cotas superiores para a dV T .

5.3 Tempo de mistura

Limitar a distância máxima (sobre x0 ∈ Ω) entre P t(x0, ·) e π é um dos nossosprincipais objetivos. Por conseguinte, é conveniente definir

d(t) := maxx∈Ω ‖ P t(x, ·)− π ‖V T (5.4)

5.3. Tempo de mistura 41

Muitas vezes é possível cotar ‖ P t(x, ·)− P t(y, ·) ‖V T , uniformemente sobre todosos pares de estados (x,y). Portanto, fazemos a definição

d(t) := maxx,y∈Ω ‖ P t(x, ·)− P t(y, ·) ‖V T (5.5)

A relação entre d e d é dada pelo seguintes resultados:

Lema 5.6. Se d(t) e d(t) são como definidos em (5.4) e (5.5) respectivamente, então

d(t) ≤ d(t) ≤ 2d(t)

Demonstração. Encontra-se no Apêndice B.1.

Lema 5.7. A função d é submultiplicativa : d(s+t) ≤ d(s)d(t).

Demonstração. Pode ser encontrada em Apêndice B.2

Segue-se que quando c é qualquer inteiro não negativo assim como t, temos

d(ct) ≤ d(ct) ≤ d(t)c. (5.6)

É útil introduzir um parâmetro que mede o tempo necessário para que a distânciade uma Cadeia de Markov à estacionária seja pequena. Para isso definimos o tempo demistura como

tmix(ε) := mint : d(t) ≤ ε (5.7)

e,tmix := tmix

(14

)(5.8)

O lema B.1 e a relação (5.6) mostram que quando m é um inteiro não negativo,

d(m tmix(ε)) ≤ d(m tmix(ε)) ≤ d(tmix(ε))m ≤ (2ε)m (5.9)

Em particular, tomando ε = 14 , temos

d(m tmix) ≤ 2−m (5.10)

e,tmix ≤ [log2 ε

−1]tmix (5.11)

Assim, embora a escolha de 14 seja arbitrária na Definição 5.8 de tmix, é necessário

um valor de ε menor do que 12 para fazer a desigualdade

d(m tmix) ≤ (2ε)m.


5.4 Acomplamento de Cadeias de Markov

Como definimos na seção 5.2, um acoplamento de duas distribuições de proba-bilidade µ e ν é um par de variáveis aleatórias (X,Y) definidas em um único espaço deprobabilidade tal que a distribuição marginal de X é µ e a distribuição marginal de Y é ν.

A Proposição 5.5 caracteriza ‖ µ−ν ‖V T como mínimo, sobre todos os acoplamentos(X, Y ) de µ e ν, da probabilidade de X 6= Y . Isto proporciona um método eficaz paraobter limites superiores para a distância.

Nesta seção, extrairemos mais informações acoplando não apenas pares de distri-buições, mas toda a trajetória da Cadeia de Markov. Comecemos com um exemplo:

Exemplo 5.8. Um passeio aleatório simples no conjunto 0, 1, ..., N é uma Cadeia deMarkov que se move para cima ou para baixo em cada movimento com igual probabilidade.Ao tentar mover-se para fora o intervalo quando em um ponto limite, ela se mantém nomesmo estado. É intuitivo que P t(x, y) ≤ P t(y, n) sempre que x ≤ y, isto diz que a chancede atingir o topo não decresce quando partimos de uma condição inicial maior.

Uma prova desse fato usa um acoplamento das distribuições P t(x, ·) e P t(y, ·).Considere a sequência ∆1,∆2, ... independentes e identicamente distribuídas tal que P (∆i =+1) = P (∆i = −1) = 1

2 . Vamos definir juntos dois passeios aleatórios em 0, 1, ..., N: acaminhada (Xt) começa em x, enquanto a caminhada (Yt) começa em y.

Usamos a mesma regra para mover-se em ambos as cadeias (Xt) e (Yt): se ∆t = +1,mova a cadeia para cima se possível, e se ∆t = −1, mova a cadeia para baixo se possível.Daí as cadeias se movem ao mesmo tempo, embora sejam iniciadas em diferentes alturas.Uma vez que as duas cadeias se encontram (necessariamente 0 ou n), ficam juntas depoisdisso. Como podemos observar na figura a seguir.

Figura 9 – Passeios aleatórios em 0, 1, 2, 3, 4. Os passeios ficam juntos após o encontro.

Observe que a distribuição Xt é P t(x, ·) e a distribuição Yt é P t(y, ·) , para maisclareza veja a prova do teorema 3.24 . Temos que Xt e Yt são definidos no mesmo espaçode probabilidade, uma vez que ambas as cadeias usam a sequência ∆t para determinar seusmovimentos.

5.4. Acomplamento de Cadeias de Markov 43

É claro que se x ≤ y, então Xt ≤ Yt para todo t. Em particular, se Xt = n entãodeve-se ter Yt = n também. A partir disso podemos concluir que

P t(x, n) = PXt = n ≤ PYt = n = P t(y, n) (5.12)

Este argumento mostra o poder da técnica de acoplamento. Podemos juntar asduas cadeias de tal maneira que Xt ≤ Yt sempre, e deste fato sobre as variáveis aleatóriaspoderíamos obter informações sobre as distribuições.

No restante desta seção, veremos como construir duas cópias simultâneas de umaCadeia de Markov. Usar uma fonte comum de aleatoriedade, como fizemos no exercícioanterior, pode ser útil para obter limites na distância à estacionariedade.

Definição 5.9 (Acoplamento de Cadeias de Markov). Um acomplamento de Cadeias deMarkov com matriz de transição P e pontos iniciais x0 e y0 é um processo (Xt, Yt)∞t=0 talque (Xt)∞ é uma Cadeia de Markov com matriz P e com X0 = x0, e (Yt)∞ é uma Cadeiade Markov com matriz P e Y0 = y0.

Notação: Se (Xt, Yt)∞t=0 é um acomplamento de Cadeias de Markov com X0 = x eY0 = y0, então escrevemos Px,y para a probabilidade no espaço onde (Xt)∞ e (Yt)∞ estãodefinidas.

Qualquer acoplamento de Cadeia de Markov com matriz de transição P pode sermodificado de modo que as duas cadeias permaneçam juntas em todos os momentos apóssua primeira visita simultaneamente a um único estado, mais precisamente, de modo que

se Xs = Ys, então Xt = Yt para t ≥ s. (5.13)

Para construir um acoplamento que satisfaça a equação acima , basta executar ascadeias de acordo com o acoplamento original até se encontrarem. Em seguida, executá-losjuntos. Essa construção foi feita com mais detalhes no teorema de convergência 3.24.

Como de costume, fixaremos uma matriz de transição P no espaço de estado Ω eescrevemos π para sua distribuição estacionária. O teorema seguinte nos diz como obteruma cota superior para d.

Teorema 5.10. Seja (Xt, Yt)∞t=0 um acoplamento satisfazendo

se Xs = Ys, então Xt = Yt para t ≥ s, (5.14)

para o qual X0 = x e Y0 = y. Seja τcouple a primeira vez que as cadeias se encontram :

τcouple := mint : Xt = Yt. (5.15)

Então,‖ P t(x, ·)− P t(y, ·) ‖V T≤ Px,yτcouple > t = Px,yXt 6= Yt. (5.16)


Demonstração. Note que P t(x, z) = Px,yXt = z e P t(y, z) = Py,zYt = z. Consequen-temente, (Xt, Yt)∞t=0 é um acoplamento de P t(x, ·) com P t(y, ·). Usando a Proposição 5.5,temos que

‖ P t(x, ·)− P t(y, ·) ‖V T≤ Px,yXt 6= Yt. (5.17)

Por (5.14), Px,yXt 6= Yt = Px,yτcouple > t. Assim, temos que (5.16) estáprovado.

Observe que o teorema anterior estabelece uma ligação entre acoplamento e tempode mistura. Além de nos fornecer uma ferramenta para mostrar a convergência rápida deCadeias de Markov, como apresentado na próxima seção.

5.5 Convergência RápidaConsidere d uma métrica qualquer em Ω satisfazendo d(x, y) ≥ 1 sempre que x 6= y.

Então o lado direito de (5.16) é limitado por Ed(Xt, Yt), ou seja, P (Xt 6= Yt) ≤ Ed(Xt, Yt).Isto sugere uma abordagem de contração: encontrar um acoplamento tal que

Ed(Xt, Yt) ≤ e−γEd(Xt−1, Yt−1), (5.18)

para algum γ > 0, de modo que

‖ P t(x, ·)− P t(y, ·) ‖V T ≤ Ed(Xt, Yt)≤ e−γEd(Xt−1, Yt−1)≤ e−γtd(x, y)≤ e−γtDiam(Ω),

onde Diam(Ω) é a maior distância entre x e y, para x, y ∈ Ω.

Resolvendo para o tempo t que faz esta distância menor ou igual a ε, obtemos umacota superior para o tempo de mistura

tmix(ε) ≤1γ

log Diam(Ω)ε

. (5.19)

A questão é como verificar a condição de contração (5.18) para um valor razoávelde γ. Para obter a mistura do tempo polinomial, com um fator de contração γ que seja daordem 1

n, precisamos encontrar uma distância que contrai na média.

45

6 Aplicações

Neste capítulo, iremos aplicar alguns conceitos estudados sobre Cadeias de Markov.Apresentaremos inicialmente o problema da Coloração em Grafos com base em [7]. Emseguida, daremos uma ideia geral para o problema de Decodificação, proposto em [1].

6.1 Coloração em Grafo

6.1.1 Introdução

Seja G=(V,E) um grafo não orientado finito com grau máximo ∆. Fixe um conjuntoQ = 1, 2, ..., q de cores e seja f : V −→ Q uma coloração em G. Uma q-coloração própriaem um grafo G=(V,E) é uma distribuição de cores nos vértices V, sujeita à restrição deque os vértices vizinhos não recebem a mesma cor, ou seja, se x é vizinho de y, entãof(x) 6= f(y). Temos que o "q"mínimo para o qual existe uma q-coloração apropriadachama-se o número cromático de G, denotado X(G).

Se uma amostra aleatória puder ser produzida, então o tamanho de Ω pode serestimado. Além disso, se é possível amostrar a partir de Ω, as características médias dascolorações podem ser estudadas através da simulação (via lei dos grande números em 2.32).

Para alguns grafos, existem métodos recursivos simples para gerar uma coloraçãoprópria uniformemente. No entanto, para outros grafos pode ser um desafio construirdiretamente uma amostra aleatória. Uma abordagem é usar o método de Monte Carlo viaCadeias de Markov.

6.1.2 Cadeia de Metropolis para Colorações em Grafos e seu Tempo de Mistura

Para um grafo G com conjunto de vértice V, seja Ω o conjunto de coloraçõespróprias para G, e seja π a distribuição uniforme em Ω.

Dada uma q-coloração própria, podemos gerar uma nova coloração utilizando aCadeia de Metropolis. Primeiro, escolhemos um vértice v uniformemente ao acaso e depoisseleciona-se uma cor k uniformemente em 1,2,...,Q . Se a cor k for permitida no vérticev (isto é, se nenhum vizinho de v tiver a cor k), então ao vértice v é atribuído a cor k.Caso contrário, não é feito nenhuma transição.

Esta regra garante que se começarmos a partir de uma coloração própria, a dinâmicacontinuará a produzir colorações próprias.

O teorema abaixo mostra que o tempo de mistura para a dinâmica de Metropolis

46 Capítulo 6. Aplicações

para colorações é polinomial.

Teorema 6.1. Seja G um grafo com n vértices e grau máximo ∆. Para a Cadeia deMetropolis em q-coloração próprias de G, se q > 3∆ e cmet(∆, q) := 1− (3∆/q), então

tmix(ε) ≤ cmet(∆, q)−1n[log n+ log(1/ε)]. (6.1)

Demonstração. Assim como para uma única cadeia de Metropolis em colorações, o aco-plamento em cada movimento gera um único par de vértice e cor (v,k), uniformemente aoacaso em V × 1, ..., q e independente do passado. Para cada v ∈ Ω′, a coloração Xx

t éatualizada tentando recolorir o vértice v com a cor k, aceitando a atualização se, e somentese, a nova cor proposta for diferente das cores nos vértices vizinhos v.

Observação 6.2. O ponto essencial é que o mesmo par de vértice e cor é usado paratodas as cadeias (Xx

t ).

Para utilizar a ideia apresentada na seção 5.5 do capítulo anterior, é necessárioencontrar uma métrica que contrai na média. Então para duas colorações x, y ∈ Ω′, defina

ρ(x, y) :=∑v∈V

1(x(v)6=y(v)) (6.2)

para o número de vértices em que x e y são diferentes, e note que ρ é uma métrica em Ω′.

Suponha que ρ(x, y) = 1, de modo que x e y concordem em todas os vértices excetono vértice v0. Escreva N para o conjunto de cores que aparecem entre os vizinhos de v0 emy. Lembre-se de que v representa uma amostra uniforme de V e k uma amostra uniforme de1,...,q, independente de v. Consideramos a distância após atualizar x e y em uma etapa,isto é, ρ(Xx

1 , Xy1 ). Essa distância vai para zero se, e somente se, o vértice v0 for selecionado

para atualização e a cor proposta não estiver em N. Isso ocorre com probabilidade

Pρ(Xx1 , X

y1 ) = 0 =

( 1n

)(q − |N |

q

)≥ q −∆

nq, (6.3)

onde ∆ denota o maior grau do grafo.

Para um vértice w que é um vizinho de v0, note que o conjunto de cores entre osvizinhos de w diferentes de v0 é o mesmo das cores x e y. Suponha que nem x(v0) nemy(v0) pertencem a este conjunto de cores. Neste caso, se w for o vértice selecionado paraatualizar e a cor x(v0) for proposta, então a configuração y será atualizada em w (para acor x(v0)), enquanto a configuração x não será atualizada. Veja a figura 10 . Isso fará comque a diferença entre x e y aumente para dois. Da mesma forma, a diferença aumentaráse w for selecionado e a cor y(v0) for proposta. Estes são os únicos cenários que levamρ(Xx

1 , Xx1 ) = 2, e concluímos que

Pρ(Xx1 , X

y1 ) = 0 ≤

(∆n

)(2q

)(6.4)

6.1. Coloração em Grafo 47

Figura 10 – Duas colorações com apenas o vértice v0 diferente

Usando (6.3) e (6.4),

E(ρ(Xx1 , X

y1 )− 1) ≤ 2∆

nq− (q −∆)

nq= 3∆− q

nq

e então,E(ρ(Xx

1 , Xy1 )) ≤ −q − 3∆

nq

Se q > 3∆, então cmet(∆, q) = 1− (3∆/q) > 0 e

E(ρ(Xx1 , X

y1 )) ≤ 1− cmet(∆, q)

n< 1 (6.5)

Agora, suponha que x e y são colorações com ρ(x, y) = r. Existem coloraçõesx0 = x, x1, ..., xr = y tais que ρ(xk, xk−1) = 1, isto é, ρ(x, y) = ρ(x0, x1) + ...+ ρ(xr−1, xr)

Como ρ é uma métrica e a desigualdade (6.5) pode ser aplicada a cada um dosvalores E(ρ(Xx

1 , Xx−11 )), assim

E(ρ(Xx1 , X

y1 )) ≤

r∑k=1

E(ρ(Xx1 , X

x−11 ))

≤ r

(1− cmet(∆, q)

n

)= ρ(x, y)

(1− cmet(∆, q)

n

)

Condicionando no evento Xxt−1 = xt−1 e Xy

t−1 = yt−1, o vetor aleatório (Xxt , X

yt )

tem a mesma distribuição que (Xxt−1, X

yt−1). Consequentemente,

E(ρ(Xxt , X

yt )|Xx

t−1 = xt−1, Xyt−1 = yt−1) = E(ρ(Xxt−1

t , Xyt−1t ))

≤ ρ(xt−1, yt−1)(

1− cmet(∆, q)n

)


Tomando a esperança sobre (Xxt−1, X

yt−1), tem-se que

E(ρ(Xxt , X

yt )) ≤ E(ρ(Xx

t−1, Xyt−1))

(1− cmet(∆, q)

n

)

Iterando esta igualdade, temos

E(ρ(Xxt , X

yt )) ≤ ρ(x, y)

(1− cmet(∆, q)

n

)t

Além disso, pela desigualdade de Markov, uma vez que ρ(x, y) ≥ 1 quando x 6= y,

PXxt 6= Xy

t = Pρ(Xxt , X

yt ) ≥ 1

≤ ρ(x, y)(

1− cmet(∆, q)n

)t≤ n exp−t(cmet(∆,q)/n)

Como o valor acima é válido para todas as colorações x, y ∈ Ω′, em particular,é válido para todas as colorações próprias x, y ∈ Ω. Pelo teorema 5.10 e a desigualdadeacima,

d(t) ≤ n exp−t(cmet(∆,q)/n)

assim, set > cmet(∆, q)−1n[log n+ log(1/ε)],

então d(t) < ε e portanto, o teorema está provado.

6.1.3 Implementação

Com base nas seções anteriores utilizou-se a linguagem JAVA para implementaro problema que consiste em encontrar uma coloração inicial para um grafo dado, eposteriormente, encontrar uma coloração própria uniforme aplicando Metropolis. Utilizandoo DOT foi possível gerar a imagem que contém o grafo original e o grafo colorido, com oauxilio do pacote GraphViz, que possui funções para gerar cada linha de comando para oscript em DOT.

Como dito anteriormente, para a elaboração dos grafos utilizou-se a linguagemDOT que é executado como um programa de linha de comando, serviço de visualização naweb ou com uma interface gráfica compatível. Seus recursos incluem algoritmos de layoutbem definidos para colocar vértices e arestas para melhor visualização dos grafos, porcompletude (veja [9] e [10]). Onde, foram implementados em Java, que é uma linguagemde programação orientada a objetos, com o auxilio de um ambiente de desenvolvimentointegrado chamado NetBeans. [11]

6.1. Coloração em Grafo 49

Em linhas gerais, o problema consiste em escolher uma coloração própria unifor-memente entre todas as colorações próprias possíveis. Para isso, usaremos os conceitosdesenvolvidos nos capítulos anteriores.

Um grafo G=(V,E) não orientado de modo que nenhum vértice adjacente possua amesma cor. Inicialmente, criou-se um grafo, onde o usuário digita o número de vértices, ograu e as arestas, como mostrado na figura a seguir:

Figura 11 – Definindo as arestas do grafo a ser colorido

Após a criação do grafo, este inicialmente foi colorido com uma coloração própria,onde nenhum vértice adjacente poderá conter a mesma cor, seguindo o algoritmo decoloração utilizando busca em profundidade:

Principal:

- montar a lista de adjacências

- inicializar a estrutura de cores

- escolher o vértice Vi de maior grau para ser colorido primeiro

- chamar o método Colore_Vertice para colorir o vértice Vi escolhido

Colore_Vertice: Vk

- se o vértice Vk ainda não foi colorido

—- procurar a cor C apropriada

—- se não existir cor apropriada para colorir o vértice Vk

——– criar uma nova cor C

—- fim se

—- colorir o vértice Vk com a cor C

—- para todo vértice Vj adjacente a Vk faça

—- chamar novamente o método Colore_Vertice para colorir o vértice Vj

- fim se

Observação 6.3. Embora tenhamos escolhido a coloração inicial utilizando o algoritmoanterior, tudo que se segue independe da configuração inicial escolhida.


Contudo o objetivo não é apenas encontrar uma coloração própria para o grafo,mas encontrar uma coloração própria uniformemente entre todas as colorações próprias.Para isso utilizou-se a algoritmo de Metropolis que consiste em:

Colore_Metropolis:

- para o valor de i=1 até n · log n

—- sortear um vértice aleatório

—- sortear uma cor aleatória

—- verificar se os vértices adjacentes não possuem a mesma cor

—- se nenhum vértice adjacente tem a mesma cor

——- atualiza o vértice sorteador com a cor sorteada

—- fim se

- fim para

Para os desenhos dos grafo foi utilizado um software chamado Graph Visualizationque possui funções pra gerar grafos no DOT. O GraphViz é um software totalmenteindependente e foi necessário baixar um API, que cria o arquivo texto de acordo com o quese quer e assim se pode gerar o grafo da forma correta antes e depois de colorizado comonas figuras 12 e 13. Para mais informações sobre essas linguagens e software veja [12].

Figura 12 – Grafo original antes da coloração

6.2. Decodificação 51

Figura 13 – Grafo gerado com uma coloração uniforme

A base da implementação utilizada foi encontrada em [13] , sendo modificada eadaptada para o problema aqui apresentado. O código adaptado se encontra em anexo.

6.2 DecodificaçãoCriptografia é o estudo de algoritmos para criptografar e descriptografar mensagens

entre remetentes e receptores. Os algoritmos de Monte Carlo via Cadeia de Markov sãométodos populares de amostragem a partir de distribuições de probabilidade complicadas.Tradicionalmente, esses dois assuntos foram bastante distintos. No entanto, recentemente osalgoritmos de Monte Carlo via Cadeia de Markov foram utilizados para convergir de formaiterativa para soluções que nos permitem quebrar códigos de substituição simples. Estaabordagem foi introduzida pela primeira vez por Marc Coram e Phil Beineke no serviçode consultoria estatística de Stanford. Nos basearemos então neste estudo, apresentado noartigo The Markov Chain Monte Carlo Revolution de P. Diaconis [1].

Será discutido então, o uso de Monte Carlo via Cadeia de Markov para quebrarcódigos. Para esta aplicação, a cadeia de Markov tem espaço de estado Ω, consistindo emtodas as possíveis chaves de descriptografia (um espaço de estado grande, mas finito). Oproblema consiste em decodificar mensagens onde cada carácter (letra, número, pontuaçãoou espaço) tenha sido substituído por um símbolo. Isto é, procuramos uma função

x : espaço de códigos −→ alfabeto usual (6.6)

que desfaça tal substituição e devolva a mensagem ao alfabeto usual. Assim, nosso espaço deestados consiste em todas as possíveis chaves de descriptografia, ou seja, as 26! permutaçõespossíveis de 26 letras.

Utiliza-se um longo texto como referência, por exemplo Guerra e Paz. Para cadapar de caracteres β1 e β2 (por exemplo, β1 = T e β2 = H), denotaremos r(β1, β2) onde serágravado o número de vezes que o par específico (por exemplo, "TH") aparece consecutiva-mente no texto de referência. Da mesma forma, para uma chave de descriptografia x ∈ X,


utiliza-se fx(β1, β2) para registrar o número de vezes que esse par aparece quando o textocifrado é descriptografado usando a chave de descriptografia x. Para evitar problemas dezeros, também adicionamos um a cada r(β1, β2) e fx(β1, β2).

Para uma determinada chave de descriptografia x, definimos sua função score daseguinte maneira:

π(x) =∏β1,β2

r(β1, β2)fx(β1,β2). (6.7)

Essa função pode ser considerada como um produtório de cada par consecutivo de letrasno texto descriptografado, o número de vezes que esse par ocorreu no texto de referência.Intuitivamente, a função é maior quando as freqüências do par no texto descriptografadocorrespondem mais às do texto de referência, e a chave de descriptografia é, portanto, maisprovável que esteja correta.

Afim de maximizar a função score π(x), utiliza-se o algoritmo de Metropolis como

apresentado no exemplo 4.5, a transição de x para y é feita com probabilidade π(y)π(x) . Isso

pode ser realizado com o seguinte algoritmo:

1. Comece com um x qualquer;

2. Calcule π(x);

3. Troque para y fazendo uma transposição dos valores de f referentes a dois símbolos;

4. Calcular π(y); Se esta for maior do que π(x), aceitar y;

5. Senão, jogue uma moeda com probabilidade π(y)π(x) . Se der cara, fique com y;

6. Se der coroa, fique com x.

O algoritmo continua, tentando melhorar a função π(x) fazendo transposiçõesaleatórias. Os lançamentos de moedas permitem que ele vá para pontos menos plausíveis,e impedindo-a de ficar preso em máximos locais.

Em outras palavras, considerando um grafo, cada vértice é uma correspondênciaentre símbolos e letras do alfabeto onde temos 26! possibilidades. Para passear neste grafoé necessário verificar os vizinhos, portanto será uma transição de uma atribuição paraoutra mais provável de estar correta. Calcula-se a plausibilidade dos vértices e quantomaior a plausibilidade temos que o vértice está mais proximo das decifrações corretas,para o cálculo da plausibilidade é necessário calcular a frequência de pares de letras emum texto em português, que é uma ideia melhor que frequências de apenas uma letra.

Portanto a ideia principal é contruir uma cadeia que possua como distribuiçãoestacionária exatamente a plausibilidade, para isso utiliza-se o algoritmo de Metropolisdescrito anteriormente.

53

7 Considerações finais

Neste trabalho, procuramos cobrir os aspectos teóricos e práticos de Cadeias deMarkov. Em relação aos aspectos teóricos, construímos a teoria básica de Cadeias deMarkov apresentando suas definições, exemplos, propriedades e resultados. Destacamoso Teorema de Convergência para a distribuição estacionária que motivou a criação doalgoritmo de Monte Carlo via Cadeias de Markov e além disso, também impulsionou adiscussão a respeito do tempo dessa convergência, tempo de mistura.

Outra vertente não menos interessante deste trabalho, é a possibilidade de colocarem prática através de aplicações e implementações os resultados teóricos estabelecidos.Nesta oportunidade, apresentamos duas aplicações utilizando o algoritmo de Metropolis,onde a primeira contitui em amostrar uma coloração própria uniformemente ao acaso e asegunda descriptografar um texto cifrado utilizando esse método de Monte Carlo.

Adicionamente, propomos os seguintes tópicos que podem ser abordados comocontinuação deste trabalho:

- Estender a discussão sobre o tempo de mistura, que possui muita atividade napesquisa atual;

- Mostramos no trabalho para o caso de colorações que o algoritmo converge emtempo polinomial se o número de cores for maior que 3∆, onde ∆ é o grau máximo do grafo.Contudo é possivel mostrar, que a mesma conclusão continua válida para q > 2∆([14]),ou até mesmo para q > 11∆

6 ([15] ). Além disso, a seguinte pergunta continua em aberto:q > ∆ + C é suficiente para garantir tempo de convergência polinomial?

- Implementar computacionalmente o problema de decodificação, utilizando oalgoritmo aqui apresentado. Além de estudar o tempo necessário para a convergência domesmo, problema que ainda continua em aberto [1].

55

Referências

1 DIACONIS, P. The markov chain monte carlo revolution. Bulletin (New Series) of theAmerican Mathematical Society, v. 46, n. 2, p. 179–205, 2009. Citado 4 vezes nas páginas1, 45, 51 e 53.

2 ROLLA, L. T. Introdução a Probabilidade. Rio de Janeiro- RJ., 2016. Citado napágina 3.

3 MAGALHãES, M. N. Probabilidade e Variáveis Aleatórias. Rio de Janeiro- RJ: Edusp,2006. Citado na página 3.

4 JAMES, B. R. Probabilidade: um curso em nível intermediário. Rio de Janeiro- RJ:Sociedade Brasileira de Matemática, 2015. Citado na página 3.

5 DIESTEL, R. Graph Theory. Springer-Verlag New York: Electronic Edition 2000, 1997.Citado na página 12.

6 ABRAHAM, R.; MARSDEN, J. E.; RATIU, T. Finite Markov Chains and AlgorithmicApplications. Cambridge- Inglaterra: Cambridge University Press, 2002. Citado 3 vezesnas páginas 15, 21 e 31.

7 LEVIN, D. A.; PERES, Y.; WILMER, E. L. Markov Chains and Mixing Times.Providence, EUA: American Mathematical Society. Citado 5 vezes nas páginas 15, 31, 39,40 e 45.

8 PERES, Y. Mixing for Markov Chains and Spin Systems. Califórnia, EUA: U.C.Berkeley, 2005. Citado na página 39.

9 THE DOT Language. 2017. Disponível em: <http://www.graphviz.org/content/dot-language>. Citado na página 48.

10 DRAWING graphs with dot. 2017. Disponível em: <http://www.graphviz.org/Documentation/dotguide.pdf>. Citado na página 48.

11 JAVA. Accessed: 2017-06-20. Disponível em: <https://www.java.com/pt_BR/download/faq/whatis_java.xml>. Citado na página 48.

12 GRAPHVIZ - Graph Visualization Software. 2017. Disponível em: <http://www.graphviz.org/>. Citado na página 50.

13 RAMOS, C. Coloracao Grafos - Parte 1 - Java. 2017. Disponível em:<https://www.youtube.com/watch?v=bWsRkREQQZY>. Citado na página 51.

14 R., J. M. A very simple algorithm for estimating the number of k-colourings of alow-degree graph. Random Structures and Algorithms, v. 7, n. 2, p. 157165, 1995. Citadona página 53.

15 R., J. M. Improved bounds for sampling colorings. Journal of Mathematical Physics,v. 41, n. 3, p. 1555–1569, 2000. Citado na página 53.

http://www.graphviz.org/content/dot-language

http://www.graphviz.org/content/dot-language

http://www.graphviz.org/Documentation/dotguide.pdf

http://www.graphviz.org/Documentation/dotguide.pdf

https://www.java.com/pt_BR/download/faq/whatis_java.xml

https://www.java.com/pt_BR/download/faq/whatis_java.xml

http://www.graphviz.org/

http://www.graphviz.org/

https://www.youtube.com/watch?v=bWsRkREQQZY

Apêndices

59

APÊNDICE A – Demonstrações do Capítulo3

Lema A.1. Para qualquer Cadeia de Markov aperiódica e irredutível com estado de espaçoS = s1, ..., sk e matriz de transição P, nós temos para qualquer dois estados si, sj ∈ Sse a cadeia começa de si, então

P (Ti,j <∞) = 1 (A.1)

Além disso, o tempo médio de chegada é finito, isto é,

E[Ti,j] <∞ (A.2)

Demonstração. Seja M <∞ tal que (PM)i,j > 0 ∀i, j ∈ 1, ..., k. Seja α tal que

α = min(PM)i,j : i, j ∈ 1, ..., k

e note que α > 0. Fixando dois estados si e sj por hipótese, e suponhamos que a cadeiacomeça em si. Temos que,

P (Ti,j > M) 6 P (XM 6= sj) 6 1− α

Além disso, dado que tudo que ocorreu até o tempo M, temos a probabilidade condicionalα de chegar no estado sj no tempo 2M, então

P (Ti,j > 2M) = P (Ti,j > M)P (Ti,j > 2M |Ti,j > M)6 P (Ti,j > M)P (X2M 6= sj|Ti,j > M)6 (1− α)2 (A.3)

Iterando o argumento acima, pegando qualquer `, temos

P (Ti,j > `M) = P (Ti,j > M)P (Ti,j > 2M |Ti,j > M)...P (Ti,j > `M |Ti,j > (`− 1)M)6 (1− α)` (A.4)

Que tende para 0 quando ` −→ ∞. Consequentemente, usamos (2.2) para esperança,

60 APÊNDICE A. Demonstrações do Capítulo 3

temos

E[Ti,j] =∞∑n=1

P (Ti,j > n) =∞∑n=0

P (Ti,j > n)

=∞∑`=0

(`+1)M−1∑n=2`

P (Ti,j > n)

6∞∑`=0

(`+1)M−1∑n=2`

P (Ti,j > `M)

= M∞∑`=0

P (Ti,j > `M)

6M∞∑`=0

(1− α)`

= M1

1− (1− α) = M

2 <∞. (A.5)

61

APÊNDICE B – Demonstrações do Capítulo5

Lema B.1. Se d(t) e d(t) são como definidos em 5.4 e 5.5 respectivamente, então

d(t) ≤ d(t) ≤ 2d(t)

Demonstração. • d(t)≤ d(t), é imediato a partir da desigualdade triangular para distânciade variação total.

• Para mostrar que d(t) ≤d(t), observe primeiro que, uma vez que π é estacionário,temos π(A) = ∑

y∈Ω π(y)P t(y, A) para qualquer conjunto A.

A definição de estacionaridade é um ???singletox. Para obter isto para A arbitrário,basta somar sobre os elementos de A. Usando isso, temos que:

‖ P t(x, ·)−π ‖TV = maxA∈Ω | P t(x,A)−π(A) |= maxA∈Ω

π(y)∑y∈Ω

[P t(x,A)− P t(y, A)]

Podemos usar a desigualdade triangular e o fato de que o máximo de uma somanão é maior que a soma sobre os máximos,

maxA∈Ωπ(y)∑y∈Ω| P t(x,A)− P t(y, A) | ≤

∑y∈Ω

π(y)maxA∈Ω | P t(x,A)− P t(y, A) |

=∑y∈Ω

π(y) ‖ P t(x, ·)− P t(y, ·) ‖TV (B.1)

Uma vez que uma média ponderada de um conjunto de números nunca é maior doque seu elemento máximo, o lado direito de 3.12 é limitado por

maxy∈Ω ‖ P t(x, ·)− P t(y, ·) ‖TV

Lema B.2. A função d é submultiplicativa : d(s+t) ≤ d(s)d(t).

Demonstração. Fixe x, y ∈ Ω, e seja (Xs, Ys) um acoplamento ótimo de P s(x, ·) e P s(y, ·)cuja existência pe garantida pela proposição 5.5. Consequentemente,

‖ P s(x, ·)− P s(y, ·) ‖TV = PXs 6= Ys (B.2)

62 APÊNDICE B. Demonstrações do Capítulo 5

Como P s+t é o produto matricial de P t e P s e a distribuição Xs é P s(x, ·), temos

P s+t(x,w) =∑z

P s(x, z)P t(z, w)

=∑z

PXs = zP t(z, w)

= E(P t(Xs, w)) (B.3)

Combinando com a identidade similar P s+t(y, w) = E(P t(Ys, w)) permite-nosescrever

P s+t(x,w)− P s+t(y, w) = E(P t(Xs, w))− E(P t(Ys, w)= E(P t(Xs, w)− P t(Ys, w)) (B.4)

Combinando as expectativas é possível uma vez que Xs e Ys são definidos juntosno mesmo espaço de probabilidade.

Somando B.4 sobre w ∈ Ω e aplicando a proposição 5.2 temos que

‖ P s+t(x, ·)− P s+t(y, ·) ‖TV = 12∑| E(P t(Xs, w)− P t(Ys, w)) |

≤ E(1

2 | Pt(Xs, w)− P t(Ys, w) |

)(B.5)

Aplicando novamente a proposição 5.2, vemos que a quantidade dentro da expecta-tiva é exatamente a distribuição, ‖ P t(x, ·)− P t(y, ·) ‖TV , que é zero sempre que Xs = Ys.Além disso, é sempre limitada por d(t). Isso mostra que,

‖ P s+t(x, ·)− P s+t(y, ·) ‖TV = d(t)E(1Xs 6=Ys)= d(t)PXs 6= Ys (B.6)

Finalmente, uma vez que (Xs, Ys) é um acoplamento ótimo, a probabilidade nolado direito é igual a ‖ P t(x, ·)− P t(y, ·) ‖TV . Maximizando sobre x,y completa a prova.

Anexos

65

ANEXO A – Código fonte Java daimplementação do problema da q-coloração

1

2 package g r a f o c o l o r ;3

4

5 impor t j a v a x . swing . JOptionPane ;6 impor t j a v a . u t i l . Comparator ;7 impor t j a v a . u t i l . C o l l e c t i o n s ;8

9 impor t j a v a . i o . ∗ ;10 impor t j a v a . u t i l . A r r a y L i s t ;11 impor t j a v a . u t i l . Random ;12

13 p u b l i c c l a s s Desenha14 15 A r r a y L i s t <Ve r t i c e > v e r t i c e s ;16 A r r a y L i s t <Aresta > a r e s t a s ;17 A r r a y L i s t <Cor> c o r e s ;18 i n t q v e r t i c e s ;19 i n t grau ;20

21 p u b l i c s t a t i c vo i d main ( S t r i n g [ ] a r g s )22 23 Desenha p = new Desenha ( ) ;24 p . s t a r t ( ) ;25

26 27 p r i v a t e vo i d s t a r t ( )28 29

30 v e r t i c e s = new A r r a y L i s t <Ve r t i c e >() ;31 a r e s t a s = new A r r a y L i s t <Aresta >() ;32 c o r e s = new A r r a y L i s t <Cor >() ;33

34 // pede o numero de v e r t i c e s e popu la a l i s t a de v e r t i c e s35 q v e r t i c e s = I n t e g e r . p a r s e I n t ( JOptionPane . showInputD ia l og (36 " In fo rme a quant i dade de v e r t i c e s : " ) ) ;37 grau = I n t e g e r . p a r s e I n t ( JOptionPane . showInputD ia l og (38 " In fo rme o grau do g r a f o : " ) ) ;39

40 i n t c ;

66 ANEXO A. Código fonte Java da implementação do problema da q-coloração

41 f o r ( i n t i =0; i <q v e r t i c e s ; i ++)42 c = 65 + i ;43 char ca=(char ) c ;44 v e r t i c e s . add ( new V e r t i c e ( ca ) ) ;45 46

47

48 // pede as a r e s t a s com as r e g r a s de v a l o r e s i n v a l i d o s49 c = 65 + v e r t i c e s . s i z e ()−1;50 char u l t imo =(char ) c ;51

52 S t r i n g a , atemp ;53 a=" " ;54 boo l ean v a l i d o ;55 v a l i d o = t r u e ;56 do 57

58

59 v a l i d o = t r u e ;60 a = JOptionPane . showInputD ia l og ( n u l l ,61 " De f i na as a r e s t a s dos v e r t i c e s A . . . "62 +u l t imo+" separando por v i r g u l a s ( exemplo : AB,AC,BC ) : " , a ) ;63 a = a . toUpperCase ( ) ;64 a = a . r e p l a c e ( " " , " " ) ;65 a = a . r e p l a c e ( " ; " , " , " ) ;66 a = a . r e p l a c e ( " . " , " , " ) ;67 i f ( a . s u b s t r i n g (0 , 1 ) . e q u a l s ( " , " ) )68 a = a . s u b s t r i n g ( 1 ) ;69 70 i f ( a . s u b s t r i n g ( a . l e n g t h ()−1) . e q u a l s ( " , " ) )71 a = a . s u b s t r i n g (0 , a . l e n g t h ()−1) ;72 73

74 atemp = a . r e p l a c e ( " , " , " " ) ;75

76 char cv [ ] = atemp . toCharAr ray ( ) ;77

78 f o r ( cha r d : cv ) 79 i f ( d>u l t imo )80 JOptionPane . showMessageDia log ( n u l l , " V e r t i c e "+d+" i n v a l i d o . " ) ;81 v a l i d o=f a l s e ;82 83 84

85 atemp = a ;86

87 do S t r i n g av = " " ;

67

88 i f ( atemp . indexOf ( " , ")>−1)89 av = atemp . s u b s t r i n g (0 , atemp . indexOf ( " , " ) ) ;90 atemp = atemp . s u b s t r i n g ( atemp . indexOf ( " , " )+1);91 92 e l s e93 94 av = atemp ;95 atemp = " " ;96 97 i f ( av . l e n g t h () >2)98 JOptionPane . showMessageDia log ( n u l l ,99 " A r e s t a s sao d e f i n i d a s de um v e r t i c e a t e ou t ro . C o r r i j a "+av+" . " ) ;

100 v a l i d o=f a l s e ;101 102

103 w h i l e ( atemp . l e n g t h () >0);104

105 w h i l e ( ! v a l i d o ) ;106 // popu la a l i s t a de a r e s t a s107 atemp = a ;108

109 do 110 S t r i n g av = " " ;111 i f ( atemp . indexOf ( " , ")>−1)112 av = atemp . s u b s t r i n g (0 , atemp . indexOf ( " , " ) ) ;113 atemp = atemp . s u b s t r i n g ( atemp . indexOf ( " , " )+1);114 115 e l s e116 117 av = atemp ;118 atemp = " " ;119 120

121 a r e s t a s . add ( new Are s t a ( b u s c a v e r t i c e ( av . s u b s t r i n g (0 , 1 ) ) ,122 b u s c a v e r t i c e ( av . s u b s t r i n g ( 1 , 2 ) ) ) ) ;123

124

125 w h i l e ( atemp . l e n g t h () >0);126

127 // ordena os v e r t i c e s em ordem d e c r e s c e n t e de grau128 C o l l e c t i o n s . s o r t ( v e r t i c e s , new Compa ra to rVe r t i c e s ( f a l s e ) ) ;129

130 // C o l o r i r v e r t i c e s , i n i c i a n d o pe l o p r i m e i r o da l i s t a ( de maior grau )131

132 // popu la l i s t a de c o r e s133 p o p u l a c o r e s ( ) ;134


135 f o r ( V e r t i c e v i : v e r t i c e s ) 136 // C o l o r i r v e r t i c e137 C o l o r e _ V e r t i c e ( v i ) ;138 139

140 // impr ime o g r a f o c o l o r i d o no a r q u i v o c o l o r i d o . g i f141 p r i n t g r a f o ( t r u e ) ;142

143 // C o l o r i r de modo un i f o rme144 Co lo r e_d inamicaG laube r ( ) ;145 // impr ime o g r a f o sem cor no a r q u i v o o r i g i n a l . g i f146 p r i n t g r a f o ( f a l s e ) ;147

148 // impr ime o g r a f o c o l o r i d o no a r q u i v o c o l o r i d o . g i f149 p r i n t g r a f o ( t r u e ) ;150

151 JOptionPane . showMessageDia log ( n u l l ,152 " Seus g r a f o s foram c r i a d o s nos a r q u i v o s153 o r i g i n a l . g i f e c o l o r i d o . g i f . " ) ;154

155 156

157 p r i v a t e V e r t i c e b u s c a v e r t i c e ( S t r i n g n )158 V e r t i c e r e t o r n o ;159 r e t o r n o = n u l l ;160 f o r ( V e r t i c e v : v e r t i c e s ) 161 i f ( v . getnome ( ) . e q u a l s ( n ) )162 r e t o r n o = v ;163 break ;164 165 166 r e t u r n ( r e t o r n o ) ;167 168

169 p r i v a t e vo i d p o p u l a c o r e s ( )170

171 c o r e s . c l e a r ( ) ;172 c o r e s . add ( new Cor ( "#f f 0 0 0 0 " , "#f f f f f f " ) ) ;173 c o r e s . add ( new Cor ( "#f f 0 0 f f " , "#000000" ) ) ;174 c o r e s . add ( new Cor ( "#0000 f f " , "#f f f f f f " ) ) ;175 c o r e s . add ( new Cor ( "#00 f f f f " , "#000000" ) ) ;176 c o r e s . add ( new Cor ( "#00 f f 0 0 " , "#000000" ) ) ;177 c o r e s . add ( new Cor ( "#f f f f 0 0 " , "#000000" ) ) ;178 c o r e s . add ( new Cor ( "#7f0000 " , "#f f f f f f " ) ) ;179 c o r e s . add ( new Cor ( "#7f 0 0 7 f " , "#f f f f f f " ) ) ;180 c o r e s . add ( new Cor ( "#00007 f " , "#f f f f f f " ) ) ;181 c o r e s . add ( new Cor ( "#007 f 7 f " , "#f f f f f f " ) ) ;

69

182 c o r e s . add ( new Cor ( "#007 f00 " , "#f f f f f f " ) ) ;183 c o r e s . add ( new Cor ( "#827 f00 " , "#000000" ) ) ;184 c o r e s . add ( new Cor ( "#000000" , "#f f f f f f " ) ) ;185 c o r e s . add ( new Cor ( "#333333" , "#f f f f f f " ) ) ;186 c o r e s . add ( new Cor ( "#4c4c4c " , "#f f f f f f " ) ) ;187 c o r e s . add ( new Cor ( "#b2b2b2 " , "#000000" ) ) ;188 c o r e s . add ( new Cor ( "#f f f f f f " , "#000000" ) ) ;189 190

191 p r i v a t e vo i d C o l o r e _ V e r t i c e ( V e r t i c e vk )192 Cor c ;193 c=n u l l ;194 i f ( ! vk . c o l o r i d o ( ) ) 195 f o r ( Cor cc : c o r e s ) 196 boo l ean podeu sa r co r ;197 podeu sa r co r=t r u e ;198 f o r ( V e r t i c e v j : vk . g e t a d j a c e n c i a ( ) ) 199 i f ( v j . c o l o r i d o ( ) ) 200 i f ( v j . g e t c o r ( ) . e q u a l s ( cc ) )201 podeu sa r co r=f a l s e ;202 break ;203 204

205 206 207 i f ( podeu sa r co r )208 c=cc ;209 break ;210 211 212

213 vk . s e t c o r ( c ) ;214 f o r ( V e r t i c e v j : vk . g e t a d j a c e n c i a ( ) ) 215 C o l o r e _ V e r t i c e ( v j ) ;216 217 218

219

220 221

222 p r i v a t e vo i d Co lo r e_d inamicaG laube r ( )223 i n t a l e a t ;224

225 Cor co r e ;226 V e r t i c e v e r t ;227

228 Random ge rado r = new Random ( ) ;


229 f o r ( i n t i =1; i<= 1−(3∗ grau )/(3∗ grau +1)∗ Math . l og10 ( q v e r t i c e s ) ; i ++)230 // s o r t e a r um v e r t i c e a l e a t o r i o231 i n t v = ge rado r . n e x t I n t ( q v e r t i c e s ) ;232 v e r t = v e r t i c e s . ge t ( v ) ;233

234 System . out . p r i n t l n ( " V e r t i c e s o r t e a d o : " + v ) ;235

236

237 i n t co= ge rado r . n e x t I n t (3∗ grau ) ;238 co r e= c o r e s . ge t ( co ) ; // s o r t e a r uma co r a l e a t o r i a239

240 System . out . p r i n t l n ( " Cor s o r t e a d a : " + co ) ;241

242 // v e r i f i c a as c o r e s a d j a c e n t e s243 boo l ean podeu sa r co r ;244 podeu sa r co r=t r u e ;245 f o r ( V e r t i c e v j : v e r t . g e t a d j a c e n c i a ( ) ) 246 i f ( v j . g e t c o r ( ) . e q u a l s ( co r e ) )247 podeu sa r co r=f a l s e ;248 break ;249 250 251 i f ( podeu sa r co r )252 v e r t . s e t c o r ( co r e ) ;253 break ;254 255

256 257

258 259

260 p r i v a t e vo i d p r i n t g r a f o ( boo l ean c o l o r i d o )261 S t r i n g s a i d a ;262 i f ( c o l o r i d o )263 s a i d a = " c o l o r i d o . png " ;264 265 e l s e266 267 s a i d a = " o r i g i n a l . png " ;268 269

270 // i n s t a n c i a o o b j e t o para p r i n t do g r a f o271 GraphViz gv = new GraphViz ( ) ;272 gv . add ln ( gv . s t a r t_g r aph ( ) ) ;273

274 f o r ( V e r t i c e v : v e r t i c e s ) 275 i f ( c o l o r i d o )

71

276 gv . add ln ( v . getnome ()+ " [ c o l o r =\""+v . g e t c o r ( ) . g e t c o r ()+277 " \" , f o n t c o l o r =\""+v . g e t c o r ( ) . g e t c o r f o n t e ()+278 " \" , s t y l e= f i l l e d ] ; " ) ;279 280 e l s e281 282 gv . add ln ( v . getnome ()+ " ; " ) ;283 284 285

286 f o r ( A r e s t a aa : a r e s t a s )287 gv . add ln ( aa . ge to r i g em ( ) . getnome ()+ " −− "+aa . g e t d e s t i n o ( ) . getnome ( ) ) ;288 289

290

291 gv . add ln ( gv . end_graph ( ) ) ;292

293 System . out . p r i n t l n ( gv . getDotSource ( ) ) ;294

295 F i l e out = new F i l e ( s a i d a ) ;296 gv . w r i t eG r aphToF i l e ( gv . getGraph ( gv . getDotSource ( ) ) , out ) ;297 298

299 300

301 // implementacao de comparador pa r a r u t i l i z a r s o r t da l i s t a302 c l a s s Compa ra to rVe r t i c e s implements Comparator 303 boo l ean c r e s c e n t e = t r u e ;304

305 p u b l i c Compa ra to rVe r t i c e s ( boo l ean c r e s c e n t e ) 306 t h i s . c r e s c e n t e = c r e s c e n t e ;307 308

309 p u b l i c i n t compare ( Object o1 , Object o2 ) 310 V e r t i c e p1 = ( V e r t i c e ) o1 ;311 V e r t i c e p2 = ( V e r t i c e ) o2 ;312 i f ( c r e s c e n t e ) 313 r e t u r n p1 . ge tg r au ( ) < p2 . ge tg r au ( ) ? −1 :314 ( p1 . ge tg r au ( ) > p2 . ge tg r au ( ) ? +1 : 0 ) ;315 e l s e 316 r e t u r n p1 . ge tg r au ( ) < p2 . ge tg r au ( ) ? +1 :317 ( p1 . ge tg r au ( ) > p2 . ge tg r au ( ) ? −1 : 0 ) ;318 319 320

Documents

Cadeias de Markov e Aplicações · Prof. Dr. Adriano de Oliveira Caminha –UFF Orientador Prof. Dr. Alan Prata de Paula –UFRJ ... A probabilidade condicional é uma nova medida