Correntes Markov

Por Victor Powell

com texto de Lewis Lehe

Correntes Markov, com o nome de Andrey Markov, são sistemas matemáticos que saltam de um “estado” (uma situação ou conjunto de valores) para outro. Por exemplo, se você fez um modelo em cadeia de Markov do comportamento de um bebê, você pode incluir “brincar”, “comer”, “dormir” e “chorar” como estados, que junto com outros comportamentos poderiam formar um “espaço de estados”: uma lista de todos os estados possíveis. Além disso, no topo do espaço de estados, uma cadeia de Markov diz-lhe a probabilidade de saltar, ou “transitar”, de um estado para qualquer outro estado – por exemplo, a hipótese de um bebé a brincar adormecer nos próximos cinco minutos sem chorar primeiro.

A simples cadeia de Markov de dois estados é mostrada abaixo.

velocidade

Com dois estados (A e B) no nosso espaço de estados, há 4 transições possíveis (não 2, porque um estado pode transitar de volta para si mesmo). Se estivermos em ‘A’ podemos fazer a transição para ‘B’ ou ficar em ‘A’. Se estivermos em ‘B’ podemos fazer a transição para ‘A’ ou ficar em ‘B’. Neste diagrama de dois estados, a probabilidade de transição de qualquer estado para qualquer outro é 0.5.

De fato, os modeladores reais nem sempre desenham os diagramas em cadeia de Markov. Ao invés disso, eles usam uma “matriz de transição” para totalizar as probabilidades de transição. Cada estado no espaço de estados é incluído uma vez como uma linha e outra vez como uma coluna, e cada célula na matriz diz-lhe a probabilidade de transição do estado da sua linha para o estado da sua coluna. Assim, na matriz, as células fazem o mesmo trabalho que as setas fazem no diagrama.

Se o espaço de estados adicionar um estado, adicionamos uma linha e uma coluna, adicionando uma célula a cada coluna e linha existente. Isto significa que o número de células cresce quadraticamente à medida que adicionamos estados à nossa cadeia de Markov. Assim, uma matriz de transição vem à mão muito rapidamente, a menos que você queira desenhar um diagrama de cadeia de Markov na selva.

Um uso de cadeias de Markov é incluir fenômenos do mundo real em simulações de computador. Por exemplo, podemos querer verificar com que freqüência uma nova represa transbordará, o que depende do número de dias chuvosos seguidos. Para construir este modelo, começamos com o seguinte padrão de dias chuvosos (R) e ensolarados (S):

Uma maneira de simular este tempo seria apenas dizer “Metade dos dias são chuvosos”. Portanto, todos os dias na nossa simulação terão cinquenta por cento de chance de chuva”. Esta regra geraria a seguinte sequência na simulação:

Viu como a sequência acima não se parece muito com a original? A segunda sequência parece saltar, enquanto a primeira (os dados reais) parece ter um “stickyness”. Nos dados reais, se num dia estiver sol (S), então no dia seguinte também é muito mais provável que esteja sol.

Podemos minicar esta “pegajosidade” com uma cadeia de Markov de dois estados. Quando a cadeia de Markov está no estado “R”, ela tem uma probabilidade de 0,9 de permanecer no estado “put” e uma probabilidade de 0,1 de sair para o estado “S”. Da mesma forma, o estado “S” tem uma probabilidade de 0,9 de ficar no estado “R” e uma probabilidade de 0,1 de transição para o estado “R”.

Nas mãos de metereólogos, ecologistas, cientistas da computação, engenheiros financeiros e outras pessoas que precisam modelar grandes fenômenos, as cadeias de Markov podem chegar a ser bastante grandes e poderosas. Por exemplo, o algoritmo que o Google usa para determinar a ordem dos resultados da pesquisa, chamado PageRank, é um tipo de cadeia de Markov.

Acima, incluímos uma cadeia de Markov “playground”, onde você pode fazer suas próprias cadeias de Markov mexendo com uma matriz de transição. Aqui estão algumas para trabalhar como exemplo: ex1, ex2, ex3 ou gerar uma aleatoriamente. O texto da matriz de transição ficará vermelho se a matriz fornecida não for uma matriz de transição válida. As linhas da matriz de transição devem totalizar 1. Também deve haver o mesmo número de linhas que as colunas.

Vocês também podem acessar uma versão em tela cheia em setosa.io/markov