Cadeias de Markov com Python
Cadeias de Markov são modelos que descrevem uma sequência de eventos dos quais a probabilidade da ocorrência de cada evento, depende apenas da ocorrência anterior e não de toda sequência. A seguir veremos um famoso exemplo que ilustra bem este processo.
Na verdade, cadeias de Markov são processos um pouco mais gerais. Neste tutorial, por simplicidade, trabalharemos apenas as Cadeias de Markov de ordem 1.
Coca vs Pepsi
Suponha que determinada pessoa, ou um grupo de pessoas, só bebe Coca ou só bebe Pepsi numa determinada semana, além de seguir as seguintes regras:
- Bebe apenas uma lata por semana.
- Se bebeu Pepsi em uma determinada semana, na próxima semana beberá Pepsi com probabilidade de 70% ou beberá Coca com probabilidade de 30%. Essas probabilidades são fixas na sequência de eventos.
- Se bebeu Coca em uma determinada semana, na próxima semana ele beberá Pepsi com probabilidade de 10% ou beberá Coca com probabilidade de 90%. Essas probabilidades também são fixas.
Os números nesse exemplo são fictícios. Além disso, as probabilidades no mundo real são alteradas por campanhas de marketing e outros eventos. O exemplo acima é simplesmente para entender como as cadeias de Markov funcionam. Considere a seguinte pergunta:
Supondo que, nessa semana, 40% de um grupo de pessoas bebem Pepsi e 60% bebem Coca. Qual a porcentagem provável de pessoas, desse mesmo grupo, que beberão Coca na semana seguinte?
Em forma matricial, podemos representar esse processo do seguinte modo:
Denotando por Pi e Ci os eventos de pessoas bebendo Pepsi e Coca na semana i, respectivamente. Então, temos as seguintes propriedades:
Pelo Teorema de Bayes, temos:
Para o nosso exemplo, supondo que essa semana seja a semana 1 e a semana seguinte seja a semana 2:
Logo, é provável que 66% das pessoas no grupo tomem Coca na semana seguinte.
Observe a segunda igualdade de cada uma das expressões acima. Elas são obtidas da multiplicação da matriz de probabilidades pelo vetor de porcentagens do grupo na semana atual:
Isso quer dizer que, para encontrar as porcentagens após duas semanas, basta multiplicar a matriz de probabilidades duas vezes!
Para conferir as contas acima, usaremos Python e a biblioteca numpy:
Uma versão copiável do código pode ser encontrada aqui!
De forma geral, para descobrirmos como estará a preferência dos usuários na 11ª semana, podemos fazer o seguinte cálculo:
O código nesse caso fica:
E temos nossa resposta:
Caso queria saber a probabilidade de um único indivíduo beber Coca na 11ª semana, dado que nessa semana (semana 1) ele bebeu Pepsi, basta considerar o grupo com um só indivíduo e trocar (0.4, 0.6) por (1,0).
Vejamos um segundo exemplo.
Snakes and Ladders
Snakes and Ladders (cobras e escadas em português) é um jogo em que o jogador tem que avançar por casas de um tabuleiro até chegar a casa final.
Alan Golder é um ladrão de jóias e pretende roubar o baú de ouro que está na casa 9. Ele inicia sua empreitada na casa 1 e segue as seguintes regras:
- Movimenta-se apenas uma vez por rodada de acordo com os números obtidos na rolagem de dado.
- Na rolagem de dados, joga um único dado e, se o número for par, ele avança duas casas. Se for ímpar, ele avança apenas uma casa.
- Golder sempre avança a quantidade determinada pelos dados de acordo com a regra anterior e sempre na ordem numérica crescente, exceto quando seu movimento acaba nas casa 3 ou 8.
- Se o movimento acaba na casa 3, ele sobe a escada e, na mesma rodada, ocupa a casa 5.
- Se o movimento acaba na casa 8, ele é mordido pela cobra e, na mesma rodada, cai para a casa 6.
Alan Golder precisa saber qual a probabilidade de roubar o tesouro em até 21 rodadas, pois ele precisa ser rápido. Ele nos capturou e disse que só poderemos sair vivos se fizermos essa conta para ele. É uma questão de vida ou morte, não temos escolha. Ainda bem que sabemos cadeia de Markov!
Vejamos a representação em forma de tabela:
Observe que, quando ele chega na casa 9, nas próximas rodadas ele fica por lá. Isso é conveniente, pois queremos saber a probabilidade dele chegar antes da rodada 20.
Em forma matricial, após 20 rodadas, precisamos calcular:
Utilizando Python temos:
Estamos salvos! Alan tem 1,5% de chances de estar na casa 6 após 20 rodadas e apenas 0,9% de atingir a casa 8. Por outro lado, Alan tem 97,51% de chances de conseguir roubar o tesouro antes da 20ª rodada.
Sumário
Vimos como cadeias de Markov podem ser utilizadas para modelar uma sequência de eventos com probabilidades de transições fixas. Mais ainda, passamos por dois famosos exemplos, Pepsi vs Coca e Snake and Ladders.
Agora é sua vez! E se Alan Golder precisasse ser mais rápido! Faça os cálculos para no máximo 10 rodadas!
O jogo do céu e do inferno (Jnana Bagi)
“Este velho jogo indiano, conhecido popularmente como ‘Snakes and Ladders’, foi originalmente um instrumento para o ensino de ética. Cada casa apresenta, além de um número, uma lenda contendo virtudes e vícios . A mais longa escada encontra-se na casa 17 ‘Compaixão e amor’ e leva até à casa 69 ‘O mundo do absoluto’.”
Espero que tenham gostado!
Até a próxima \o
