Um vigia faz a ronda num corredor com quatro postos e tende a continuar andando no sentido em que vai. Para onde ele vai depende de onde está e do sentido em que andava, então a posição sozinha não é uma cadeia de Markov: dois vigias no mesmo posto podem ter futuros diferentes. O remédio não é uma teoria nova, e sim uma escolha melhor de estado. Ponha a memória que falta dentro do estado, e o processo volta a ser uma cadeia de Markov comum, com tudo dos capítulos anteriores à disposição: matriz de transição, πP = π, frações de longo prazo.
Ao final você vai conseguir
- Reconhecer quando os estados óbvios de um processo não são markovianos.
- Aumentar o estado só com a memória que a regra precisa, e listar só os estados que podem ocorrer.
- Montar a matriz de transição da cadeia aumentada, incluindo os movimentos forçados nas pontas.
- Resolvê-la e somar os estados de volta para responder sobre a grandeza original.
- Lidar com uma regra que olha dois passos para trás.
Numere os postos de 1 a 4, da esquerda para a direita. A regra: se o último passo foi para a direita, o próximo também é para a direita com probabilidade r = 0,5; se foi para a esquerda, o próximo também é para a esquerda com probabilidade l = 0,75. No posto 1 ou no posto 4 ele não tem escolha e volta. Chame de Xₙ a posição depois de n passos. Uma cadeia de Markov exige que P(Xₙ₊₁ = j | todo o passado) dependa só de Xₙ. Olhe para um vigia parado no posto 2:
A regra olha duas coisas: o posto e o sentido do último passo. Então o estado precisa guardar as duas: Yₙ = (Xₙ, Dₙ), em que Dₙ é → ou ← para o passo que o trouxe a Xₙ. Agora o próximo estado depende só do atual, porque tudo o que a regra lê está nele. Nem todo par pode ocorrer. Ele só chega ao posto 1 andando para a esquerda e ao posto 4 andando para a direita, então em vez de 4 × 2 = 8 estados há 6:
| Estado | Significado | Próximo estado (probabilidade) |
|---|---|---|
| 1← | no posto 1, chegou andando para a esquerda | 2→ (1): obrigado a voltar |
| 2→ | no posto 2, chegou andando para a direita | 3→ (r = 0,5), 1← (1 − r = 0,5) |
| 2← | no posto 2, chegou andando para a esquerda | 1← (l = 0,75), 3→ (1 − l = 0,25) |
| 3→ | no posto 3, chegou andando para a direita | 4→ (r = 0,5), 2← (1 − r = 0,5) |
| 3← | no posto 3, chegou andando para a esquerda | 2← (l = 0,75), 4→ (1 − l = 0,25) |
| 4→ | no posto 4, chegou andando para a direita | 3← (1): obrigado a voltar |
Leia os nomes com cuidado: a seta do próximo estado é o sentido do passo que acabou de ser dado. De 2→, continuar para a direita leva ao posto 3 ainda andando para a direita, 3→; virar leva ao posto 1 andando para a esquerda, 1←. Cada linha soma 1, como toda linha de uma matriz de transição. As voltas forçadas nas pontas são linhas com um único 1.
A distribuição estacionária satisfaz πP = π: em cada estado, a probabilidade que entra é igual à probabilidade que está lá. Escreva uma equação por estado, somando as setas que chegam nele. Chame π(1←) = A, π(2→) = B, π(2←) = C, π(3→) = D, π(3←) = E, π(4→) = F.
A pergunta era sobre postos, não sobre estados. O vigia está no posto 2 sempre que está em 2→ ou em 2←, então a fração de tempo num posto é a soma das probabilidades dos seus estados:
Um caminhante que não prefere um lado
Se r = l, então q = 1 e os seis estados são igualmente prováveis, 1/6 cada, por mais teimoso que seja o caminhante. Os postos das pontas têm um só estado cada, então ficam com 1/6 do tempo, e os postos do meio com 2/6. A teimosia muda a cara da caminhada (corridas longas em vez de vaivém), mas não para onde vai o tempo. Confira na figura: ponha r = l e mova os dois juntos.
As barras são a fração exata de longo prazo do tempo em cada posto: o π da cadeia aumentada, com os estados de cada posto somados. Os pontos são o que o caminhante fez de fato até agora; deixe-o andar (o botão rápido dá 200 passos de cada vez) e eles assentam nas barras. As etiquetas embaixo do corredor são os estados que podem ocorrer: o posto, depois o sentido do último passo e, no modo de dois passos, o sentido do passo anterior. Nas pontas só um sentido pode chegar, e por isso há menos estados que postos × sentidos. Ponha r = l, ou s = q, e veja o que não muda.
Algumas regras olham mais para trás. Num modelo simples de tempo, chover amanhã depende de hoje e de ontem: chuva amanhã com probabilidade 0,8 depois de dois dias de chuva, 0,6 se choveu hoje mas não ontem, 0,3 se choveu ontem mas não hoje, e 0,1 depois de dois dias secos. O tempo do dia sozinho não é markoviano. O estado precisa guardar os dois dias: (ontem, hoje), quatro estados, com R para chuva e D para seco (das palavras em inglês rain e dry). Avançando um dia, hoje vira ontem e amanhã vira hoje.
| Estado | Significado | Próximo estado (probabilidade) |
|---|---|---|
| RR | chuva ontem, chuva hoje | RR (0.8), RD (0.2) |
| DR | seco ontem, chuva hoje | RR (0.6), RD (0.4) |
| RD | chuva ontem, seco hoje | DR (0.3), DD (0.7) |
| DD | seco ontem, seco hoje | DR (0.1), DD (0.9) |
Um caminhante cuja regra depende dos dois últimos passos funciona do mesmo jeito: o estado é (posto, sentido do último passo, sentido do passo anterior). Só contam as combinações que realmente podem acontecer. Chegar ao posto 1 sempre significa que o último passo foi para a esquerda; no posto 2 de um corredor de só 3 postos os dois últimos passos sempre apontam para lados opostos. O segundo modo da figura monta esses estados para qualquer corredor e os lista embaixo das barras.
- Escreva em palavras a regra do próximo passo, incluindo o que acontece nas bordas.
- Liste tudo o que a regra olha: a posição, o último sentido, os dois últimos dias…
- Faça o estado ser exatamente essa lista. Menos, e a cadeia não é markoviana; mais, e ela é markoviana mas grande sem necessidade.
- Fique só com os estados que podem ocorrer: comece de um estado e siga as setas até não aparecer nenhum estado novo.
- Escreva cada linha de P e confira que ela soma 1.
- Resolva πP = π e some os estados para responder à pergunta sobre a grandeza original.
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Cada exercício é criado na hora, então uma rodada nova nunca é igual. O computador escolhe a resposta primeiro e monta a pergunta em volta dela, trabalhando com frações exatas, por isso o gabarito está sempre certo. As respostas são lidas de forma exata: 0,75, 3/4 e 6/8 contam como o mesmo número (quando a forma irredutível é pedida, 6/8 só recebe um lembrete). Uma resposta errada mostra a resolução linha por linha, na ordem em que a lição faz; o número novo de cada linha aparece colorido.
| Errado | Certo | Por quê |
|---|---|---|
| uma cadeia só com as posições | posição + sentido | o próximo passo depende do sentido, então ele precisa estar no estado |
| 8 estados para 4 postos | 6 estados | 1→ e 4← nunca ocorrem; estados inalcançáveis fazem πP = π ter muitas soluções ou nenhuma |
| esquecer a volta forçada | uma linha com um único 1 | nas pontas as probabilidades da regra não valem |
| responder com o π dos estados | some os estados de cada posto | a pergunta é sobre postos; 2→ e 2← são os dois o posto 2 |
| próximo estado com o sentido antigo | nomeie pelo passo que acabou de ser dado | senão as linhas apontam para as colunas erradas |
Ideias-chave
- Um processo é markoviano num conjunto de estados só se o próximo passo depende apenas do estado atual.
- Quando a regra olha mais do que a posição (o último sentido, o dia de ontem), ponha essa memória no estado.
- Fique só com os estados que podem ocorrer; nas pontas a regra dá lugar a movimentos forçados.
- A cadeia aumentada é uma cadeia de Markov comum: monte P, confira as linhas, resolva πP = π.
- Para responder sobre a grandeza original, some as probabilidades dos estados que a compartilham.
- Memória de dois passos: o estado são as duas últimas observações; um passo à frente as desloca.