Cadeias de Markov em Python: tutorial para iniciantes

Uma cadeia de Markov é um sistema matemático geralmente definido como um conjunto de variáveis aleatórias que transitam de um estado para outro de acordo com certas regras probabilísticas. Esse conjunto de transições satisfaz a propriedade de Markov, que afirma que a probabilidade de transitar para qualquer estado específico depende apenas do estado atual e do tempo decorrido, e não da sequência de estados anteriores. Essa característica torna os processos de Markov sem memória.

Quer explorar mais tópicos de estatística com Python? Confira o curso Statistical Thinking in Python da DataCamp!

Vamos à transição...

Por que cadeias de Markov?

As cadeias de Markov têm uso prolífico em matemática. São amplamente empregadas em economia, teoria dos jogos, teoria da comunicação, genética e finanças. Surgem com frequência em contextos estatísticos, especialmente em estatística bayesiana, e em teoria da informação. Em problemas do mundo real, ajudam a propor soluções para estudar sistemas de piloto automático em veículos, filas de clientes chegando a um aeroporto, taxas de câmbio, entre outros. O algoritmo conhecido como PageRank, originalmente proposto para o mecanismo de busca do Google, é baseado em um processo de Markov. O Subreddit Simulator do Reddit é um subreddit totalmente automatizado que gera posts e comentários aleatórios usando cadeias de Markov — muito legal!

Cadeia de Markov

Uma cadeia de Markov é um processo aleatório com a propriedade de Markov. Um processo aleatório, ou estocástico, é um objeto matemático definido como um conjunto de variáveis aleatórias. Uma cadeia de Markov pode ter um espaço de estados discreto (conjunto de valores possíveis das variáveis aleatórias) ou um índice discreto (geralmente representando o tempo) — assim, existem muitas variações. Normalmente, o termo "cadeia de Markov" é reservado para um processo com um conjunto discreto de tempos, isto é, uma cadeia de Markov em tempo discreto (DTMC).

Cadeia de Markov em tempo discreto

Uma cadeia de Markov em tempo discreto envolve um sistema que, a cada passo, está em um certo estado, mudando aleatoriamente entre estados a cada passo. Os passos são frequentemente entendidos como momentos no tempo (mas também podem se referir a distância física ou outra medida discreta). Uma cadeia de Markov em tempo discreto é uma sequência de variáveis aleatórias X₁, X₂, X₃, ... com a propriedade de Markov, tal que a probabilidade de ir para o próximo estado depende apenas do estado atual e não dos anteriores. Em termos probabilísticos:

Pr( X_n+1 = x | X₁ = x₁, X₂ = x₂, …, X_n = x_n) = Pr( X_n+1 = x | X_n = x_n)

Como você vê, a probabilidade de X_n+1 depende apenas de X_n, que o precede. Ou seja, conhecer o estado anterior é suficiente para determinar a distribuição de probabilidade do estado atual, satisfazendo a regra de independência condicional (dito de outra forma: você só precisa conhecer o estado atual para determinar o próximo estado).

Os valores possíveis de X_i formam um conjunto contável S, chamado de espaço de estados da cadeia. O espaço de estados pode ser qualquer coisa: letras, números, placares de basquete ou condições do tempo. Embora o parâmetro de tempo seja geralmente discreto, o espaço de estados de uma cadeia de Markov em tempo discreto não tem restrições amplamente aceitas e pode ser arbitrário. No entanto, muitas aplicações usam espaços de estados finitos ou contáveis, pois sua análise estatística é mais direta.

Modelo

Uma cadeia de Markov pode ser representada por um autômato probabilístico (o nome assusta, mas é simples!). As mudanças de estado do sistema são chamadas de transições. As probabilidades associadas a essas mudanças são as probabilidades de transição. Um autômato probabilístico inclui a probabilidade de uma dada transição na função de transição, transformando-a em uma matriz de transição.

Você pode pensar nisso como uma sequência de grafos direcionados, em que as arestas do grafo n são rotuladas pelas probabilidades de ir de um estado no tempo n para outros estados no tempo n+1, Pr(X_n+1 = x | X_n = x_n). Leia assim: probabilidade de ir ao estado X_n+1 dado o valor do estado X_n. A mesma informação é representada pela matriz de transição do tempo n para n+1. Cada estado do espaço de estados aparece uma vez como linha e novamente como coluna, e cada célula indica a probabilidade de transitar do estado da linha para o estado da coluna.

Se a cadeia de Markov tem N estados possíveis, a matriz será N x N, em que a entrada (I, J) é a probabilidade de transitar do estado I para o estado J. Além disso, a matriz de transição deve ser estocástica: a soma das entradas de cada linha deve ser exatamente 1. Por quê? Porque cada linha representa sua própria distribuição de probabilidade.

Portanto, o modelo é caracterizado por um espaço de estados, uma matriz de transição descrevendo as probabilidades de transições específicas e um estado inicial no espaço de estados, dado pela distribuição inicial.

Muita teoria, né?

Vamos ver um exemplo simples para fixar os conceitos:

Quando Cj fica triste, o que não é muito comum: ela ou sai para correr, devora sorvete ou tira um cochilo.

Pelos dados históricos, se ela passou um dia triste dormindo, no dia seguinte há 60% de chance de ela sair para correr, 20% de continuar na cama e 20% de atacar o sorvete.

Quando ela está triste e sai para correr, há 60% de chance de correr no dia seguinte, 30% de se esbaldar no sorvete e apenas 10% de passar o dia dormindo.

Por fim, quando ela se entrega ao sorvete em um dia triste, há só 10% de chance de repetir o sorvete no dia seguinte, 70% de sair para correr e 20% de passar o dia dormindo.

A cadeia de Markov ilustrada no diagrama de estados tem 3 estados possíveis: dormir, correr, sorvete. Logo, a matriz de transição será 3 x 3. Note que as setas que saem de um estado sempre somam exatamente 1; da mesma forma, as entradas de cada linha da matriz de transição precisam somar 1 — representando uma distribuição de probabilidade. Na matriz de transição, as células cumprem o mesmo papel das setas no diagrama de estados.

Agora que você viu o exemplo, já deve ter uma ideia dos diferentes conceitos ligados a uma cadeia de Markov. Mas como e onde usar essa teoria na prática?

Com o exemplo acima, você pode responder perguntas como: "Começando no estado dormir, qual a probabilidade de Cj estar correndo (estado: correr) ao final de um período de 2 dias tristes?"

Vamos resolver: para ir do estado dormir ao estado correr, Cj pode ficar em dormir no primeiro movimento (ou dia) e ir para correr no segundo (0,2 · 0,6); ou ir para correr no primeiro dia e permanecer lá no segundo (0,6 · 0,6); ou ainda ir para sorvete no primeiro movimento e depois para correr no segundo (0,2 · 0,7). Então, a probabilidade é: ((0,2 · 0,6) + (0,6 · 0,6) + (0,2 · 0,7)) = 0,62. Ou seja, há 62% de chance de Cj passar para o estado correr após dois dias tristes, se começou em dormir.

Tomara que isso tenha dado uma boa noção das várias perguntas que você consegue responder usando uma rede de cadeia de Markov.

Com isso em mente, fica mais fácil entender algumas propriedades importantes das cadeias de Markov:

• Redutibilidade: uma cadeia de Markov é dita irredutível se for possível chegar a qualquer estado a partir de qualquer estado. Em outras palavras, é irredutível se existir uma sequência de passos entre quaisquer dois estados com probabilidade positiva.
• Periodicidade: um estado em uma cadeia de Markov é periódico se a cadeia puder retornar a ele apenas em múltiplos de algum inteiro maior que 1. Assim, começando no estado "i", a cadeia retorna a "i" apenas em múltiplos do período "k", e k é o maior desses inteiros. O estado "i" é aperiódico se k = 1 e periódico se k > 1.
• Transiência e recorrência: um estado "i" é dito transitório se, dado que começamos em "i", há probabilidade não nula de nunca mais retornarmos a "i". O estado i é recorrente (ou persistente) se não for transitório. Um estado recorrente é dito positivamente recorrente se o retorno for esperado em um número finito de passos e nulamente recorrente caso contrário.
• Ergodicidade: um estado "i" é dito ergódico se for aperiódico e positivamente recorrente. Se todos os estados em uma cadeia de Markov irredutível forem ergódicos, então a cadeia é ergódica.
• Estado absorvente: um estado i é chamado absorvente se for impossível sair dele. Portanto, o estado "i" é absorvente se p_ii = 1 e p_ij = 0 para i ≠ j. Se todo estado puder alcançar um estado absorvente, a cadeia de Markov é absorvente.

Dica: se você quiser ver também uma explicação visual de cadeias de Markov, visite esta página.

Cadeias de Markov em Python

Vamos codificar o exemplo acima em Python. Embora, na prática, você provavelmente use uma biblioteca que implemente cadeias de Markov de forma mais eficiente, o código a seguir vai te ajudar a começar...

Primeiro, importe as bibliotecas que você vai usar.

import numpy as np
import random as rm

Agora defina os estados e suas probabilidades: a matriz de transição. Lembre-se, a matriz será 3 x 3 porque você tem três estados. Você também precisa definir os caminhos de transição, o que pode ser feito com matrizes.

# The statespace
states = ["Sleep","Icecream","Run"]

# Possible sequences of events
transitionName = [["SS","SR","SI"],["RS","RR","RI"],["IS","IR","II"]]

# Probabilities matrix (transition matrix)
transitionMatrix = [[0.2,0.6,0.2],[0.1,0.6,0.3],[0.2,0.7,0.1]]

Sempre verifique se as probabilidades somam 1. E não custa nada deixar mensagens de erro — pelo menos durante o desenvolvimento!

if sum(transitionMatrix[0])+sum(transitionMatrix[1])+sum(transitionMatrix[1]) != 3:
    print("Somewhere, something went wrong. Transition matrix, perhaps?")
else: print("All is gonna be okay, you should move on!! ;)")

All is gonna be okay, you should move on!! ;)

Agora vamos ao que interessa. Você vai usar numpy.random.choice para gerar uma amostra aleatória do conjunto de transições possíveis. Embora a maioria dos argumentos seja autoexplicativa, o p talvez não seja. Ele é um argumento opcional que permite informar a distribuição de probabilidade para o conjunto de amostragem — neste caso, a matriz de transição.

# A function that implements the Markov model to forecast the state/mood.
def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    print("Start state: " + activityToday)
    # Shall store the sequence of states taken. So, this only has the starting state for now.
    activityList = [activityToday]
    i = 0
    # To calculate the probability of the activityList
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1  
    print("Possible states: " + str(activityList))
    print("End state after "+ str(days) + " days: " + activityToday)
    print("Probability of the possible sequence of states: " + str(prob))

# Function that forecasts the possible state for the next 2 days
activity_forecast(2)

Start state: Sleep
Possible states: ['Sleep', 'Sleep', 'Run']
End state after 2 days: Run
Probability of the possible sequence of states: 0.12

Você obtém um conjunto aleatório de transições possíveis, junto com a probabilidade de ocorrer, a partir do estado: Sleep. Estenda o programa para iterá-lo algumas centenas de vezes com o mesmo estado inicial e você verá a probabilidade esperada de terminar em cada estado. Vamos reescrever a função activity_forecast e adicionar novos loops para fazer isso...

def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    activityList = [activityToday]
    i = 0
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1    
    return activityList

# To save every activityList
list_activity = []
count = 0

# `Range` starts from the first count up until but excluding the last count
for iterations in range(1,10000):
        list_activity.append(activity_forecast(2))

# Check out all the `activityList` we collected    
#print(list_activity)

# Iterate through the list to get a count of all activities ending in state:'Run'
for smaller_list in list_activity:
    if(smaller_list[2] == "Run"):
        count += 1

# Calculate the probability of starting from state:'Sleep' and ending at state:'Run'
percentage = (count/10000) * 100
print("The probability of starting at state:'Sleep' and ending at state:'Run'= " + str(percentage) + "%")

The probability of starting at state:'Sleep' and ending at state:'Run'= 62.419999999999995%

Como aproximamos do desejado 62%?

Observação Isto é a "lei dos grandes números", um princípio da probabilidade que afirma que as frequências de eventos com a mesma chance de ocorrência tendem a se estabilizar — mas apenas quando há tentativas suficientes. Em outras palavras, conforme o número de experimentos aumenta, a razão real dos resultados converge para a razão teórica ou esperada.

No estado de espírito de Markov

Encerramos o tutorial sobre cadeias de Markov. Você foi apresentado a cadeias de Markov e a algumas de suas propriedades. Cadeias de Markov simples são um tema fundamental para começar em ciência de dados com Python. Se quiser mais recursos para começar com estatística em Python, confira esta página.

Quer explorar estudos de caso práticos com estatística em Python? Veja os cursos Case Studies in Statistical Thinking ou Network Analysis in Python da DataCamp.