Introdução às cadeias de Markov
Quando estudamos um sistema que pode mudar com o tempo, precisamos encontrar uma maneira de acompanhar essas mudanças. Uma cadeia de Markov é um modelo específico para rastrear sistemas que mudam de acordo com determinadas probabilidades. Como veremos, uma cadeia de Markov pode permitir a previsão de eventos futuros, mas as previsões tornam-se menos úteis para eventos mais distantes no futuro (muito parecido com as previsões do mercado de ações ou do clima).
Esta lição requer conhecimento prévio de aritmética de matrizes.
Definições
Um estado é qualquer situação particular possível no sistema. Por exemplo, se estivermos estudando dias chuvosos, existem dois estados:
- Está chovendo hoje.
- Não está chovendo hoje.
O sistema pode ter muito mais de dois estados, mas vamos nos limitar a dois para este pequeno exemplo.
O termo cadeia de Markov refere-se a qualquer sistema no qual há um certo número de estados e determinadas probabilidades de que o sistema mude de qualquer estado para outro.
Isso é muito para entender de uma vez, então vamos ilustrar usando nosso exemplo de dias chuvosos. As probabilidades de nosso sistema podem ser:
- Se chover hoje (R), há 40% de chance de chover amanhã e 60% de chance de não chover.
- Se não chover hoje (N), então há 20% de chance de chover amanhã e 80% de chance de não chover.
Pode ajudar a organizar esses dados no que chamamos de diagrama de estado .
A Matriz de Transição
Se uma cadeia de Markov consiste em k estados, a matriz de transição é a matriz k por k (uma tabela de números) cujas entradas registram a probabilidade de mudança de cada estado para outro estado (em forma decimal, em vez de porcentagem). As linhas da matriz correspondem ao estado atual e as colunas correspondem ao próximo estado. Por exemplo, a entrada na linha 1 e coluna 2 registra a probabilidade de passar do estado 1 para o estado 2. (Observe, a matriz de transição poderia ser definida ao contrário, mas então as fórmulas também seriam invertidas.)
Vamos construir uma matriz de transição juntos! Primeiro, escolhemos um pedido para nossos estados. Digamos que R sempre venha antes de N. Isso significa que a primeira linha e a primeira coluna se referem a R, enquanto a segunda linha e coluna se referem a N. Lembre-se, linhas significam » de » e colunas significam » para ».
A transição de R para R é 0,4, então colocamos 0,4 no canto superior esquerdo da matriz. A transição de R para N é 0,6 (canto superior direito). N a R é 0,2 (inferior esquerdo) e N a N é 0,8 (inferior direito).
Vetores de estado
No início do processo, podemos saber exatamente em que estado o sistema está (com chuva ou sem chuva), mas começando com o segundo estado e mais adiante, conhecemos apenas as probabilidades de o sistema estar em um determinado estado. Para acompanhar essas probabilidades, usamos um vetor de estado.
Um vetor de estado é um vetor (lista) que registra as probabilidades de que o sistema esteja em um determinado estado em uma etapa específica do processo.
Por exemplo, se sabemos com certeza que está chovendo hoje, o vetor de estado para hoje será (1, 0). Mas amanhã é outro dia! Sabemos apenas que há 40% de chance de chuva e 60% de chance de não chover, então o vetor de estado de amanhã é (0,4, 0,6).
Mas e depois de amanhã? Ou no dia seguinte? Usando a aritmética de matriz, podemos encontrar o vetor de estado para qualquer etapa do processo de Markov!
Fórmula Principal
Se P é a matriz de transição ev 0 é o vetor de estado inicial, então o vetor de estado após n etapas é:
Agora que sabemos o básico, vamos realmente examinar aquele exemplo de dia chuvoso! Suponha que esteja chovendo hoje. Então, qual é a probabilidade de chuva todos os dias durante os próximos 5 dias?
O vetor inicial será (1, 0). Amanhã ( n = 1 dia depois), o vetor de estado é:
Continue para cada dia após:
Esses resultados são resumidos a seguir:
Dia n depois de hoje | Chance de chover |
---|---|
0 | 100% |
1 | 40% |
2 | 28% |
3 | 25,6% |
4 | 25,1% |
5 | 25% |
Previsões de longo prazo
Após uma série de etapas, as probabilidades parecem convergir para um valor constante, independentemente do dia. Por exemplo, nos dias 3, 4 e 5 no exemplo acima, a chance de chuva se aproxima de 25%.
Pode ser surpreendente que o mesmo comportamento aconteça mesmo com um vetor de estado inicial diferente! Suponha que não esteja chovendo hoje, de modo que v 0 = (0, 1). Vamos fazer os cálculos novamente.
Dia n depois de hoje | Chance de chover |
---|---|
0 | 0% |
1 | 20% |
2 | 24% |
3 | 24,8% |
4 | 25% |
5 | 25% |
O comportamento do sistema a longo prazo é: 25% da chuva, independente do estado inicial. Portanto, este modelo pode ser útil apenas para previsões de curto prazo. Mantenha seu guarda-chuva à mão!
Resumo da lição
- Uma cadeia de Markov é um sistema que muda de estado para estado de acordo com determinadas probabilidades.
- A tabela de probabilidades é chamada de matriz de transição, e a lista de probabilidades de que o sistema se encontra em um determinado estado após um certo número de etapas é chamada de vetor de estado.
- Se P é a matriz de transição ev 0 é o vetor de estado inicial, então o vetor de estado após n passos é dado pela fórmula,
- O comportamento de longo prazo do sistema não depende do estado inicial (na maioria dos casos).