Calculadora de Cadeias de Markov

O que uma cadeia de Markov modela

Uma cadeia de Markov descreve um sistema que se move entre um conjunto finito de estados um passo de cada vez, onde a única coisa que governa o próximo estado é o atual.

Essa única suposição, de que o futuro depende do presente mas não do caminho que levou ali, é a propriedade de Markov, e basta para construir um modelo que prevê onde o sistema estará muito adiante no tempo, acha o equilíbrio de longo prazo em que se assenta e mede quanto os processos demoram para terminar.

Todo o modelo vive num único objeto, a matriz de transição: uma grade quadrada cuja entrada na linha i e coluna j é a probabilidade de passar do estado i ao estado j, com cada linha somando um porque o sistema sempre vai a algum lugar.

A razão pela qual uma ideia tão pequena chega tão longe é que uma quantidade surpreendente de sistemas reais são, em boa aproximação, sem memória no nível dos estados. Um cliente está ativo, inativo ou perdido; uma máquina está operando, degradada ou em falha; um empréstimo está em dia, atrasado, inadimplente ou quitado; uma marca mantém um cliente ou o perde para um rival.

Em cada caso o próximo estado é bem previsto pelo atual, e a história importa sobretudo por onde deixou o sistema agora.

Uma vez que você aceita esse enquadramento, a matriz de transição captura a dinâmica, e um punhado de cálculos padrão responde as perguntas que as pessoas de fato fazem: qual é a participação de longo prazo, quanto falta para isso terminar, e quais são as probabilidades de cada desfecho.

Esta calculadora toma qualquer matriz de transição que você escrever e faz essa análise padrão por você. Acha a distribuição de estado estacionário à qual a cadeia converge, classifica cada estado como recorrente, transitório ou absorvente e reporta seu período, prevê a distribuição após qualquer número de passos a partir de um ponto de partida que você escolher, e desenha como as probabilidades de estado convergem passo a passo. Quando detecta uma cadeia absorvente, muda para a análise que importa ali e reporta o número esperado de passos até a absorção e a probabilidade de terminar em cada estado absorvente. Tudo roda no seu navegador, e nada do que você informa é guardado.

Como usar esta calculadora, passo a passo

Comece pela matriz de transição. Escreva-a um estado por linha, com as probabilidades de mover-se a cada estado separadas por espaços ou vírgulas, mantendo os estados na mesma ordem em cada linha. Cada linha deve somar um, já que de qualquer estado o sistema certamente se move a algum lugar; a calculadora verifica isso e indica qual linha está errada se alguma não somar um. A ferramenta abre com um exemplo resolvido de troca de marca de três estados para que você veja um resultado completo, a participação de mercado de longo prazo de três marcas, antes de mudar qualquer coisa.

Opcionalmente você pode nomear os estados na segunda caixa, separados por vírgulas, para que os resultados se leiam como Marca A, Operando ou Em dia em vez de S1, S2, S3. A terceira caixa guarda um vetor de estado inicial, que é onde a cadeia começa para a previsão passo a passo; deixe-a e a ferramenta supõe que a cadeia começa no primeiro estado. A última caixa fixa quantos passos à frente prever. Assim que a matriz é válida a calculadora resolve ao vivo, então editar uma probabilidade ou um rótulo atualiza cada resultado e o gráfico imediatamente.

O painel de resultados encabeça com o principal, a distribuição de estado estacionário para uma cadeia comum ou um resumo de absorção para uma absorvente. Abaixo, uma tabela lista cada estado com sua probabilidade de longo prazo, sua classificação e seu período, e um conjunto de fichas mostra a distribuição após o número de passos que você escolheu.

Para uma cadeia absorvente aparecem duas tabelas extras: os passos esperados até a absorção a partir de cada estado transitório, e a probabilidade de terminar em cada estado absorvente.

Um gráfico de convergência traça cada probabilidade de estado ao longo dos passos para que você veja a aproximação ao longo prazo, e você pode baixar os resultados como PDF ou CSV ou compartilhá-los.

Ler a matriz de transição e o estado estacionário

Vale a pena parar na matriz de transição porque todo o resto se deriva dela. Cada linha é um estado em que você está atualmente, e ler ao longo dessa linha dá as probabilidades de onde você estará depois. Uma entrada da diagonal é a probabilidade de ficar; uma diagonal grande significa um estado grudento que o sistema tende a manter, enquanto uma pequena significa que o sistema raramente se demora. Como cada linha é um conjunto completo de possibilidades, deve somar um, e este é o erro de digitação mais comum, uma linha que soma um pouco mais ou menos de um, por isso a calculadora o valida de forma explícita.

A distribuição de estado estacionário responde a pergunta de longo prazo. Formalmente é o vetor de probabilidade pi que satisfaz pi P = pi, o que significa que uma vez que o sistema atinge esta distribuição, aplicar outro passo a deixa sem mudança; as proporções pararam de se mover mesmo que os membros individuais continuem trocando de estado.

Para uma cadeia ergódica, uma que é irredutível e aperiódica, esta distribuição é única e o sistema converge a ela sem importar onde começou, que é justamente por que pode representar a participação de mercado de longo prazo, a ocupação de máquina de longo prazo ou a fração de tempo em qualquer estado.

A calculadora resolve pi P = pi como sistema linear e normaliza a resposta para que some um, recorrendo à multiplicação repetida se o cálculo direto estiver mal condicionado.

Ajuda separar o estado estacionário do ponto de partida. O vetor inicial e a contagem de passos respondem uma pergunta diferente e de horizonte mais curto: dado onde o sistema está agora, onde estará após n passos? No início esta distribuição transitória pode não se parecer em nada com o estado estacionário, e o gráfico de convergência a mostra deslizando rumo aos valores de longo prazo passo a passo. Ambas as visões servem: a previsão a n passos para planejar alguns períodos à frente, o estado estacionário para o equilíbrio de longo prazo. Lê-las juntas costuma ser mais informativo que qualquer uma sozinha, porque mostra não só onde o sistema termina mas quão rápido chega lá.

Cadeias ergódicas e cadeias absorventes: duas perguntas diferentes

As cadeias de Markov se dividem em dois tipos amplos que pedem perguntas diferentes, e a calculadora reconhece qual você informou. Uma cadeia ergódica continua se movendo entre todos os seus estados para sempre; nunca fica presa, e o resultado interessante é a distribuição de estado estacionário, a fração de tempo de longo prazo em cada estado. A troca de marca onde os clientes continuam mudando, o clima que continua ciclando, uma máquina que é consertada e volta ao serviço, todas são ergódicas, e sua história é contada pela distribuição estacionária e por quão rápido a cadeia converge a ela.

Uma cadeia absorvente é diferente porque tem estados que, uma vez atingidos, nunca são deixados. Estes modelam processos que terminam em vez de ciclar: um cliente que abandona de vez, um empréstimo que é quitado ou baixado, um jogo que se ganha ou se perde, um paciente que recebe alta.

Para tal cadeia a pergunta de estado estacionário é quase trivial, no longo prazo o sistema é absorvido com certeza, então as perguntas úteis passam a ser quanto falta para terminar e em qual desfecho.

Esses são justamente os resultados que a calculadora produz para uma cadeia absorvente: o número esperado de passos até a absorção a partir de cada estado transitório, e a probabilidade de terminar em cada estado absorvente. Ela detecta os estados absorventes de forma automática, pelas linhas cuja probabilidade de ficar é um, e muda sua saída para se adequar.

Saber qual tipo você tem é o primeiro passo analítico, porque decide quais números importam. Se o seu processo genuinamente nunca termina, leia o estado estacionário. Se tem desfechos terminais definidos, os resultados de absorção são a recompensa, e o estado estacionário sozinho seria uma distração. Muitos modelos reais são majoritariamente ergódicos com um ou dois estados absorventes acrescentados, por exemplo um modelo de estados do cliente onde todo estado ativo pode chegar com o tempo a uma perda permanente; a calculadora os trata considerando o estado de perda como absorvente e reportando quanto os clientes duram e quão provável é cada desfecho.

Cinco exemplos resolvidos que você pode seguir

Exemplo 1: participação de mercado de longo prazo

A calculadora abre com um modelo de troca entre três marcas. Cada linha dá a probabilidade de que um cliente de uma marca neste período compre cada marca no próximo, e a diagonal, as entradas maiores, capta a lealdade. O resultado de estado estacionário, cerca de 43,5% para a Marca A, 37,0% para a Marca B e 19,6% para a Marca C, é a participação de mercado de longo prazo à qual o sistema converge sem importar em que marca você comece um cliente. Mude uma única probabilidade de lealdade ou de troca e observe como as participações de longo prazo se movem, que é a forma mais rápida de ver que a retenção impulsiona a participação mais que a aquisição.

Exemplo 2: uma previsão de horizonte curto

Mantenha a mesma matriz mas leia a distribuição após n passos em vez do estado estacionário. Começando cada cliente na Marca A e avançando, a distribuição desliza de tudo-A rumo ao estado estacionário; após dez períodos já está perto mas não idêntica à participação de longo prazo. Esta é a diferença prática entre onde um segmento está agora e para onde se dirige, e o gráfico de convergência torna visível a velocidade dessa aproximação, que importa quando você planeja só alguns períodos à frente em vez de ao infinito.

Exemplo 3: um modelo absorvente de abandono de clientes

Acrescente um estado de abandono no qual os clientes podem entrar mas nunca sair, dando a ele uma linha que é um na própria diagonal, e faça os estados ativos poderem atingi-lo. A calculadora agora detecta uma cadeia absorvente e reporta o número esperado de períodos antes que um cliente abandone a partir de cada estado ativo e, se você tiver mais de um desfecho terminal, a probabilidade de cada um. Os passos esperados até a absorção são uma estimativa limpa da vida do cliente em períodos, derivada direto das probabilidades de troca em vez de suposta.

Exemplo 4: a caminhada aleatória da ruína do jogador

Uma cadeia clássica de ensino: um jogador com algum dinheiro aposta uma unidade repetidamente, os estados são a fortuna atual, e as duas pontas, na falência e a meta, são absorventes. Informe as probabilidades de subir e descer nos estados interiores e uns nas duas pontas. A calculadora devolve a probabilidade de atingir a meta antes de falir a partir de cada fortuna inicial, que para um jogo justo é igual à fração inicial da meta, e o número esperado de apostas antes de o jogo terminar. É uma forma compacta de ver probabilidades de absorção e duração esperada num modelo familiar.

Exemplo 5: uma cadeia pequena que você pode conferir à mão

Experimente uma cadeia de dois estados como uma máquina que está no ar ou fora, com probabilidades redondas simples que você possa conferir. Resolva pi P = pi no papel e confirme que a calculadora coincide, depois leia a coluna de período para confirmar que ambos os estados são aperiódicos. Uma cadeia de dois estados é pequena o bastante para ser conferida por completo, o que dá confiança antes de confiar na ferramenta numa matriz maior onde o cálculo à mão é impraticável. Mexer numa probabilidade e resolver de novo mostra quão sensível é o equilíbrio de longo prazo às taxas de transição.

Três dicas de especialista para uma análise limpa

A matemática por trás dos resultados

Vale a pena entender os cálculos mesmo que a calculadora faça a aritmética. A previsão a n passos é pura multiplicação de matrizes: se a distribuição atual é um vetor linha x, após um passo é x vezes P, após dois passos x vezes P ao quadrado, e após n passos x vezes P à n. A ferramenta usa exponenciação rápida, então até um número grande de passos é instantâneo. O estado estacionário é o vetor pi que essa multiplicação já não muda, pi P = pi, que é um sistema de equações lineares; combinado com a exigência de que as probabilidades somem um, tem solução única para uma cadeia ergódica, e a ferramenta o resolve direto por eliminação gaussiana, usando a multiplicação repetida como reserva.

A análise de absorção se apoia na matriz fundamental. Reordene os estados para que os transitórios venham primeiro, e a matriz de transição se parte num bloco Q de movimentos entre transitórios e um bloco R de movimentos de transitório para absorvente. A matriz fundamental N é a inversa da identidade menos Q, e suas entradas contam o número esperado de visitas a cada estado transitório antes da absorção. De N saem dois resultados de imediato.

O número esperado de passos até a absorção a partir de cada estado é a soma ao longo da linha de N desse estado, porque o tempo total é o total de visitas esperadas. A probabilidade de ser absorvido em cada estado absorvente é N vezes R, que reparte a trajetória esperada entre os desfechos possíveis.

A calculadora forma Q e R da sua matriz, inverte a identidade menos Q e reporta ambos os resultados, então o método da matriz fundamental que enche uma página de livro acontece num clique.

A classificação de estados usa a alcançabilidade. Dois estados se comunicam se cada um pode ser alcançado a partir do outro por alguma sequência de passos, e isso agrupa os estados em classes.

Um estado é recorrente se todo estado alcançável a partir dele pode voltar a ele, então a cadeia sempre volta; é transitório se pode alcançar um estado que não pode voltar, então há probabilidade de nunca voltar; e é absorvente se simplesmente nunca é deixado.

O período de um estado é o máximo divisor comum dos tempos possíveis de retorno, e um período de um significa que o estado é aperiódico. A calculadora calcula a alcançabilidade ao longo de toda a matriz, rotula cada estado conforme isso e calcula cada período, que juntos lhe dizem a estrutura da cadeia num relance.

Onde as cadeias de Markov são usadas

A gama de aplicações é uma das razões pelas quais o modelo é um fixo da pesquisa operacional. Em marketing, as matrizes de troca de marca dão a participação de mercado de longo prazo e mostram como a lealdade e as taxas de recuperação a impulsionam.

Em analítica de clientes, os estados de ativo passando por inativo a perdido convertem uma matriz de troca numa estimativa da vida do cliente e da probabilidade de abandono. Em finanças e crédito, as classificações que deslizam entre graus e à inadimplência são modeladas como cadeia de Markov, e a análise de absorção dá o tempo esperado até a inadimplência e a probabilidade de inadimplência por grau inicial.

Em operações e manutenção, os estados de condição de máquina de operando passando por degradada a falha alimentam a confiabilidade e o planejamento de manutenção.

O alcance vai além. O clima e a demanda muitas vezes são modelados como cadeias sobre condições discretas; os níveis de estoque e de fila se movem entre estados com probabilidades de passo; a progressão de doenças por estágios, alguns absorventes, é um modelo de Markov natural em analítica de saúde.

A caminhada aleatória que fundamenta o ranqueamento de páginas web é uma cadeia de Markov gigante cujo estado estacionário é o próprio ranking, e o Monte Carlo por cadeias de Markov, um cavalo de batalha da estatística e do aprendizado de máquina modernos, constrói uma cadeia cujo estado estacionário é a distribuição que ele quer amostrar.

Em todos eles o mesmo punhado de resultados, a matriz de transição, o estado estacionário, a classificação e a análise de absorção, fazem o trabalho, por isso aprender a lê-los uma vez rende em muitos campos.

Dentro deste conjunto de ferramentas a cadeia de Markov fica no grupo de filas de espera e estocástico ao lado da teoria das filas, e as duas são parentes próximas: o número no sistema de uma fila é em si uma cadeia de Markov sobre os níveis de ocupação possíveis, e as fórmulas de fila de estado estacionário são a distribuição estacionária dessa cadeia.

Onde a teoria das filas empacota os modelos padrão de chegada e serviço em fórmulas prontas, a calculadora de cadeias de Markov lida com qualquer estrutura de estados que você possa escrever como matriz, o que a torna a ferramenta mais geral quando o seu sistema não cabe numa fila de livro. Volte ao hub de Pesquisa Operacional para o conjunto completo de modelos.

Montar um sistema real como cadeia

Transformar uma situação real numa cadeia de Markov trata sobretudo de escolher bem os estados e estimar probabilidades de transição honestas. Os estados devem ser uma descrição completa e mutuamente exclusiva de onde o sistema pode estar, de modo que a qualquer momento esteja em exatamente um, e devem ser definidos num nível onde a suposição sem memória seja razoável, ou seja que o próximo estado realmente seja bem previsto pelo atual. Escolher poucos estados esconde dinâmicas importantes; escolher demais torna as probabilidades difíceis de estimar e o modelo frágil. A arte está em escolher estados distintos o bastante para importar e grossos o bastante para se medir.

As probabilidades de transição costumam vir de dados. Se você tem um histórico do sistema se movendo entre estados, a probabilidade de ir do estado i ao j é estimada como a fração de vezes que, estando em i, ele se moveu a j depois, e essas frações naturalmente formam linhas que somam um.

Quando os dados são escassos, as probabilidades podem ser julgadas por experiência, mas ainda assim devem ser contrastadas com o histórico que existir, e uma linha que soma algo diferente de um é sinal de um erro de contagem ou arredondamento e não de um traço real.

O comprimento do passo também importa: uma cadeia mensal e uma semanal do mesmo sistema têm matrizes diferentes, e o passo deve coincidir com o horizonte que lhe interessa.

Por fim, decida o que está perguntando antes de ler a saída. Se você quer o equilíbrio de longo prazo, o estado estacionário é a resposta e o vetor inicial mal importa. Se quer uma previsão para um horizonte específico, fixe o vetor inicial na distribuição de hoje e leia o resultado a n passos. Se o seu processo termina, marque os estados terminais como absorventes e leia o tempo esperado e as probabilidades de absorção. Fazer a pergunta coincidir com o resultado certo é o que transforma uma matriz resolvida numa decisão, e vale a pena ser explícito sobre a pergunta primeiro para que os números que você cite sejam os que a respondem.

Quando o modelo simples não encaixa

A cadeia de Markov é deliberadamente simples, e sua simplicidade é também a sua fronteira. A suposição central é que o próximo estado depende apenas do atual, e quando o futuro do sistema real depende de mais de sua história, a cadeia simples é a forma errada. Um processo onde há quanto tempo você já está num estado muda as chances de sair, por exemplo, quebra a suposição sem memória; às vezes você pode resgatar o modelo acrescentando estados que codificam a história extra, mas isso aumenta a matriz e pode ficar incontrolável, ponto no qual um modelo mais rico é mais honesto.

O tempo é outra fronteira. Esta calculadora lida com cadeias em tempo discreto, onde o sistema avança em intervalos fixos; os sistemas que mudam em tempo contínuo, onde os eventos podem ocorrer a qualquer momento, são modelados como cadeias de Markov em tempo contínuo com taxas de transição em vez de probabilidades, uma ferramenta relacionada mas distinta.

A não estacionariedade é uma terceira: se as probabilidades de transição mesmas deslizam com o tempo, por exemplo porque um mercado muda estruturalmente, uma única matriz fixa descreve apenas um instantâneo, e os resultados devem ser lidos como válidos enquanto a matriz se sustentar.

Nenhuma dessas ressalvas diminui o valor da cadeia nos muitos sistemas que são genuinamente discretos, sem memória e estáveis; elas apenas marcam as bordas onde um modelo mais elaborado ganha sua complexidade extra, e reconhecer a forma do seu sistema antes de modelar é o que mantém a resposta significativa.

Ler além da cifra principal

Uma cadeia resolvida oferece mais de um número, e a melhor análise lê vários juntos. O estado estacionário lhe diz o destino, mas o gráfico de convergência lhe diz a velocidade, e uma cadeia que atinge seu longo prazo em três passos sustenta um planejamento muito diferente de uma que leva quarenta, mesmo quando seus estados estacionários são idênticos. Ver o gráfico é a forma mais rápida de julgar se uma cifra de longo prazo é guia justa para o seu horizonte real ou se o comportamento transitório domina o período que lhe importa, e essa distinção muda uma decisão de forma rotineira.

A classificação e os períodos merecem atenção em vez de serem pulados. Um estado transitório com residência esperada longa pode importar muito no médio prazo mesmo que sua probabilidade estacionária seja zero, e ler só o estado estacionário o passaria por alto por completo. Um período maior que um é um aviso de que a cadeia cicla e de que suas cifras de longo prazo são médias sobre o ciclo, não uma distribuição em que o sistema descansa; citar um estado estacionário para uma cadeia estritamente periódica sem essa ressalva é um erro comum e enganoso. A ferramenta mostra ambos para que você os leia, e a disciplina de conferi-los transforma um resultado de aparência plausível num confiável.

Por fim, trate a matriz como uma estimativa e ponha a conclusão à prova. Se uma pequena mudança numa probabilidade de transição move bruscamente o estado estacionário ou o tempo esperado de absorção, o resultado é sensível e a sua estimativa dessa probabilidade merece mais cuidado; se a conclusão é estável diante de variações razoáveis, você pode confiar mais nela. Resolver de novo com algumas matrizes perturbadas é rápido e lhe diz quanto a decisão realmente depende dos números exatos, que costuma ser mais valioso que a única cifra principal que o modelo entrega primeiro.

Uma breve história da ideia

O modelo leva o nome do matemático russo Andrey Markov, que o introduziu nos primeiros anos do século vinte, por volta de 1906, enquanto defendia um ponto da teoria da probabilidade. A lei dos grandes números vigente havia sido provada para eventos independentes, e um crítico afirmava que a independência era essencial a ela.

Markov se propôs a refutá-lo construindo sequências dependentes que ainda assim obedeciam à lei, e para tornar o argumento concreto analisou a sequência de vogais e consoantes num longo poema de Pushkin, tratando o tipo de cada letra como um estado cuja probabilidade dependia da letra anterior.

Esse exercício literário, contar com que frequência uma vogal seguia uma consoante e o contrário, foi o primeiro exemplo trabalhado do que hoje chamamos cadeia, e estabeleceu a dependência sem memória que define o modelo.

Por algumas décadas a ideia permaneceu em grande medida teórica, um tema de probabilidade pura. Sua carreira prática decolou em meados do século conforme a pesquisa operacional amadureceu e os computadores tornaram rotineira a aritmética de matrizes.

A mesma estrutura acabou por descrever filas, estoques, confiabilidade e incontáveis sistemas mais, e depois se tornou o motor por trás do ranqueamento de páginas web e dos métodos de simulação que impulsionam a estatística e o aprendizado de máquina modernos. É um arco notável: uma construção inventada para vencer uma discussão sobre um poema se tornou um dos modelos mais aplicados na ciência e na indústria.

Entendê-la hoje significa estar sobre cem anos de uso em campos que seu inventor jamais imaginou, que é parte de por que ela continua sendo um básico de todo curso de pesquisa operacional.

Formato de entrada e referência rápida

Escreva a matriz de transição um estado por linha, probabilidades separadas por espaços ou vírgulas, cada linha somando um. Opcionalmente nomeie os estados e dê um vetor inicial e uma contagem de passos para a previsão. A referência abaixo explica cada parte do resultado.

Perguntas frequentes

Fontes, aviso legal e transparência editorial

Esta calculadora analisa cadeias de Markov finitas em tempo discreto com métodos padrão de pesquisa operacional: resolve a distribuição estacionária de pi P = pi, prevê distribuições a n passos por potências de matrizes, classifica estados por alcançabilidade e período e, para cadeias absorventes, usa a matriz fundamental N = (I menos Q) elevado a menos um para calcular os passos esperados até a absorção e as probabilidades de absorção. Esta calculadora e este guia são criados e revisados pela equipe da OpsCalculators; consulte a nossa Política Editorial para saber como cada ferramenta é pesquisada, construída e testada.

Os resultados são estimativas precisas para planejamento e educação, não consultoria de engenharia certificada, e pressupõem que a propriedade de Markov se cumpre, que o próximo estado depende apenas do atual, e que a matriz de transição é estacionária no horizonte em que você a aplica. Valide a matriz contra os seus próprios dados antes de agir sobre os resultados. Consulte o nosso Aviso Legal completo. OpsCalculators.com é operado pela MAFHH INTERNATIONAL LTD. Os seus dados são processados no seu navegador e nunca são guardados; consulte a nossa Política de Privacidade.