Cadeias de Markov – Exemplo prático

Pode-se chamar de processo de Markov um sistema finito e discreto  formado por estados, onde existem probabilidades de transição entre os estados. Uma cadeia de Markov é a execução repetida de um processo de Markov.

Por exemplo, imagine um sistema formado pelos estados A, B e C. A transição de A-> B tem uma probabilidade C1, de A->C tem probabilidade C2, A->A (se manter no estado A) C3, e assim por diante. Um fato importante nesta definição de processo de Markov (de primeira ordem, como tratado aqui) é que a probabilidade de transição depende somente do estado atual.

Um exemplo de utilização está no cálculo das probabilidades de que, partindo de um estado inicial A, qual é a probabilidade de um novo estado B ser alcançado após K iterações? Para isto, monta-se uma matriz M, onde o valor da célula Mi,j corresponde à probabilidade da transição i->j. Para saber a chance de se alcançar o estado Z partindo do estado X após K iterações, deve-se consultar a célula Mx,z após o cálculo de M^K (exponenciação).

Um tutorial completo (escrito pelo Fabrício Bueno) pode ser acessado em Cadeias de Markov: Práticas e Aplicações .

O problema Vampiros da sub-regional da maratona de programação de 2008 servirá como exemplo. Não descreverei o problema aqui, favor consultar o link =) .

1º Passo: simplificação da energia vital e capacidade de dano

A capacidade de dano D  é a mesma para os dois vampiros, então pode-se simplificar o problema, reduzindo o dano para 1 e ajustando a energia vital de cada vampiro. Por exemplo, se EV1 = 3, EV2 = 4 e D = 2, então pode-se reduzir o problema para: Ev1 = 2, EV2 = 2 e D = 1.

2º Passo: simplificação dos estados

Para que o vampiro 1 ganhe a batalha, a energia vital do vampiro 2 precisa ser reduzida para 0. Como o vampiro que ganhou um turno ganha uma  quantia de energia igual ao dano causado, pode-se dizer que o vampiro 1 ganha quando ficar com EV = EV1 + EV2. Esta simplificação permite que a batalha seja modelada utilizando a energia vital do vampiro 1 como estados.

3º Passo: modelagem

A energia vital do vampiro 1 será utilizada na modelagem, onde cada estado corresponde à um valor de energia, que vai de 0 (o vampiro 2 ganhou) até EV1 + EV2 (o vampiro 1 ganhou). O estado 0 (correspondente à EV = 0) acarreta na derrota, e não pode-se sair dele, logo, se o vampiro está no estado 0, ele permanecerá lá, então a transição 0->0 tem probabilidade 1. O mesmo ocorre para o estado EV1 + EV2, pois se o vampiro já ganhou, ele permanece vitorioso. Nos outros estados, a chance de transição do estado Sn para Sn+1 é igual a AT / 6, e de Sn para Sn-1 é de 1 – (AT / 6).

Visualização:

Tomando o 2º caso de teste (1 2 1 1) temos o seguinte processo de Markov:

Processo de Markov para o exemplo

A matriz de transição M fica assim:

Matriz de transição

Respondendo à pergunta do problema: qual é a chance do vampiro 1 vencer neste caso? Bem, a batalha pode ocorrer até o fim dos tempos, então temos que limitar o número de rodadas para um valor factível, que devolva uma resposta dentro da precisão estabelecida.  Como a exponenciação de matrizes pode ser implementada em ~ O(log K) em relação ao número de transições K, pode-se fixar o K como 1000.

Então, modela-se o problema, montando a matriz M. Computa-se então M^K (M elevado à K) e verifica-se o valor de Ma,b, onde a é a vida inicial e b é a vida correspondente à batalha ganha (EV1 + EV2).

A mesma ideia de exponenciação de matrizes pode ser utilizada para a contagem de caminhos de A para B com tamanho K em um determinado  grafo. Neste caso, M é a matriz de adjacências, onde Mi,j vale 1 se existir o caminho i->j, e 0 se o caminho não existir.