Cadeia de Markov em tempo discreto - Discrete-time Markov chain

Uma cadeia de Markov com dois estados, A e E .

Em probabilidade , uma cadeia de Markov de tempo discreto ( DTMC ) é uma sequência de variáveis ​​aleatórias, conhecida como um processo estocástico , em que o valor da próxima variável depende apenas do valor da variável atual, e não de quaisquer variáveis ​​no passado . Por exemplo, uma máquina pode ter dois estados, A e E . Quando ele se encontra no estado A , existe uma possibilidade de 40% de que se deslocam para o estado de E e uma possibilidade de 60% de ele permanece no estado Uma . Quando se está em estado E , há uma chance de 70% do que se mudar para A e 30% de chance de ele ficar em E . A sequência de estados da máquina é uma cadeia de Markov. Se denotarmos a cadeia por, então é o estado em que a máquina começa e é a variável aleatória que descreve seu estado após 10 transições. O processo continua para sempre, indexado pelos números naturais . ${\ displaystyle X_ {0}, X_ {1}, X_ {2}, ...}$${\ displaystyle X_ {0}}$${\ displaystyle X_ {10}}$

Um exemplo de um processo estocástico que não é uma cadeia de Markov é o modelo de uma máquina que tem os estados A e E e se move para A de qualquer um dos estados com 50% de chance se já visitou A antes, e 20% de chance se tiver nunca visitou A antes (deixando 50% ou 80% de chance de que a máquina se mova para E ). Isso ocorre porque o comportamento da máquina depende de todo o histórico - se a máquina estiver em E , ela pode ter 50% ou 20% de chance de se mover para A , dependendo de seus valores anteriores. Portanto, ele não possui a propriedade Markov .

Uma cadeia de Markov pode ser descrita por uma matriz estocástica , que lista as probabilidades de se mover para cada estado a partir de qualquer estado individual. A partir dessa matriz, a probabilidade de estar em um determinado estado n etapas no futuro pode ser calculada. O espaço de estado de uma cadeia de Markov pode ser particionado em classes de comunicação que descrevem quais estados são alcançáveis ​​um do outro (em uma transição ou em muitas). Cada estado pode ser descrito como transitório ou recorrente, dependendo da probabilidade de a cadeia retornar a esse estado. As cadeias de Markov podem ter propriedades incluindo periodicidade, reversibilidade e estacionariedade. Uma cadeia de Markov de tempo contínuo é como uma cadeia de Markov de tempo discreto, mas move estados continuamente ao longo do tempo, em vez de como etapas de tempo discretas. Outros processos estocásticos podem satisfazer a propriedade de Markov, a propriedade de que o comportamento passado não afeta o processo, apenas o estado presente.

Definição

Uma cadeia de Markov de tempo discreto é uma sequência de variáveis ​​aleatórias com a propriedade de Markov , ou seja, que a probabilidade de passar para o próximo estado depende apenas do estado presente e não dos estados anteriores: ${\ displaystyle X_ {0}, X_ {1}, X_ {2}, ...}$

${\ displaystyle \ Pr (X_ {n + 1} = x \ mid X_ {1} = x_ {1}, X_ {2} = x_ {2}, \ ldots, X_ {n} = x_ {n}) = \ Pr (X_ {n + 1} = x \ mid X_ {n} = x_ {n}),}$se ambas as probabilidades condicionais são bem definidas, isto é, se${\ displaystyle \ Pr (X_ {1} = x_ {1}, \ ldots, X_ {n} = x_ {n})> 0.}$

Os valores possíveis de X _i formam um conjunto contável S denominado espaço de estado da cadeia.

As cadeias de Markov são frequentemente descritas por uma sequência de gráficos direcionados , onde as arestas do gráfico n são rotuladas pelas probabilidades de ir de um estado no tempo n para os outros estados no tempo n  + 1. A mesma informação é representada pela matriz de transição do tempo n ao tempo n  + 1. No entanto, as cadeias de Markov são freqüentemente assumidas como homogêneas no tempo (veja as variações abaixo), caso em que o gráfico e a matriz são independentes de n e, portanto, não são apresentados como sequências. ${\ displaystyle \ Pr (X_ {n + 1} = x \ mid X_ {n} = x_ {n}).}$

Essas descrições destacam a estrutura da cadeia de Markov que é independente da distribuição inicial. Quando homogênea no tempo, a cadeia pode ser interpretada como uma máquina de estado atribuindo uma probabilidade de salto de cada vértice ou estado para um adjacente. A probabilidade do estado da máquina pode ser analisada como o comportamento estatístico da máquina com um elemento do espaço de estados como entrada, ou como o comportamento da máquina com a distribuição inicial de estados como entrada, onde está o colchete de Iverson . ${\ displaystyle \ Pr (X_ {1} = x_ {1}).}$${\ displaystyle \ Pr (X_ {n} = x \ mid X_ {1} = x_ {1})}$${\ displaystyle x_ {1}}$${\ displaystyle \ Pr (X_ {1} = y) = [x_ {1} = y]}$${\ displaystyle [P]}$

Variações

• Cadeias de Markov homogêneas no tempo (ou cadeias de Markov estacionárias) são processos onde

${\ displaystyle \ Pr (X_ {n + 1} = x \ mid X_ {n} = y) = \ Pr (X_ {n} = x \ mid X_ {n-1} = y)}$

para todos n . A probabilidade da transição é independente de n .

• Uma cadeia de Markov com memória (ou uma cadeia de Markov de ordem m )

onde m é finito, é um processo que satisfaz

${\ displaystyle {\ begin {alinhado} & \ Pr (X_ {n} = x_ {n} \ mid X_ {n-1} = x_ {n-1}, X_ {n-2} = x_ {n-2 }, \ dots, X_ {1} = x_ {1}) \\ = {} & \ Pr (X_ {n} = x_ {n} \ mid X_ {n-1} = x_ {n-1}, X_ {n-2} = x_ {n-2}, \ pontos, X_ {nm} = x_ {nm}) {\ text {para}} n> m \ end {alinhado}}}$

Em outras palavras, o estado futuro depende dos m estados anteriores. É possível construir uma cadeia a partir da qual tenha a propriedade 'clássica' de Markov tomando como espaço de estado as m- duplas ordenadas de valores X , isto é. .${\ displaystyle (Y_ {n})}$${\ displaystyle (X_ {n})}$${\ displaystyle Y_ {n} = \ left (X_ {n}, X_ {n-1}, \ ldots, X_ {n-m + 1} \ right)}$

transições n -step

A probabilidade de ir do estado i para o estado j em n passos de tempo é

${\ displaystyle p_ {ij} ^ {(n)} = \ Pr (X_ {n} = j \ mid X_ {0} = i)}$

e a transição de uma única etapa é

${\ displaystyle p_ {ij} = \ Pr (X_ {1} = j \ mid X_ {0} = i).}$

Para uma cadeia de Markov homogênea no tempo:

${\ displaystyle p_ {ij} ^ {(n)} = \ Pr (X_ {k + n} = j \ mid X_ {k} = i)}$

e

${\ displaystyle p_ {ij} = \ Pr (X_ {k + 1} = j \ mid X_ {k} = i).}$

As probabilidades de transição de n passos satisfazem a equação de Chapman-Kolmogorov , que para qualquer k tal que 0 <  k  <  n ,

${\ displaystyle p_ {ij} ^ {(n)} = \ sum _ {r \ in S} p_ {ir} ^ {(k)} p_ {rj} ^ {(nk)}}$

onde S é o espaço de estado da cadeia de Markov.

A distribuição marginal Pr ( X _n  =  x ) é a distribuição sobre os estados no tempo n . A distribuição inicial é Pr ( X ₀  =  x ). A evolução do processo em uma etapa de tempo é descrita por

${\ displaystyle \ Pr (X_ {n} = j) = \ sum _ {r \ in S} p_ {rj} \ Pr (X_ {n-1} = r) = \ sum _ {r \ in S} p_ {rj} ^ {(n)} \ Pr (X_ {0} = r).}$

(O sobrescrito ( n ) é um índice e não um expoente ).

Comunicando classes e propriedades

Diz-se que um estado j é acessível a partir de um estado i (escrito i  →  j ) se um sistema iniciado no estado i tem uma probabilidade diferente de zero de fazer a transição para o estado j em algum ponto. Formalmente, o estado j é acessível a partir do estado i se existe um inteiro n _ij  ≥ 0 tal que

${\ displaystyle \ Pr (X_ {n_ {ij}} = j \ mid X_ {0} = i) = p_ {ij} ^ {(n_ {ij})}> 0.}$

Diz-se que um estado i se comunica com o estado j (escrito i  ↔  j ) se i  →  j e j  →  i . Uma classe de comunicação é um conjunto máximo de estados C, de modo que cada par de estados em C se comunica entre si. A comunicação é uma relação de equivalência e as classes comunicantes são as classes de equivalência dessa relação.

Uma classe comunicante é fechada se a probabilidade de deixar a classe é zero, ou seja, se i está em C, mas j não está, então j não é acessível a partir de  i . O conjunto de classes comunicantes forma um grafo acíclico direcionado , herdando as setas do espaço de estado original. Uma classe de comunicação é fechada se e somente se não houver setas de saída neste gráfico.

Um estado i é dito essencial ou final se para todo j tal que i  →  j também é verdade que j  →  i . Um estado i não é essencial se não for essencial. Um estado é final se e somente se sua classe de comunicação for fechada.

Uma cadeia de Markov é considerada irredutível se seu espaço de estado for uma única classe de comunicação; em outras palavras, se é possível chegar a qualquer estado a partir de qualquer estado.

Periodicidade

Um estado tem período se qualquer retorno ao estado deve ocorrer em múltiplos de intervalos de tempo. Formalmente, o período de estado é definido como ${\ displaystyle i}$${\ displaystyle k}$${\ displaystyle i}$${\ displaystyle k}$${\ displaystyle i}$

${\ displaystyle k = \ gcd \ {n> 0: \ Pr (X_ {n} = i \ mid X_ {0} = i)> 0 \}}$

(onde é o máximo divisor comum ) desde que este conjunto não esteja vazio. Caso contrário, o período não é definido. Observe que, embora um estado tenha ponto final , pode não ser possível atingir o estado em etapas. Por exemplo, suponha que seja possível retornar ao estado em intervalos de tempo; seria , embora não apareça nesta lista. ${\ displaystyle \ gcd}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle \ {6, ~ 8, ~ 10, ~ 12, \ dots \}}$${\ displaystyle k}$${\ displaystyle 2}$${\ displaystyle 2}$

Se , então, o estado é considerado aperiódico. Caso contrário ( ), o estado é considerado periódico com ponto final  . A periodicidade é uma propriedade da classe - ou seja, se um estado tem um período , todos os estados em sua classe de comunicação têm um período . ${\ displaystyle k = 1}$${\ displaystyle k> 1}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Transitoriedade e recorrência

Um estado i é considerado transitório se, dado que começamos no estado i , existe uma probabilidade diferente de zero de nunca retornarmos a i . Formalmente, deixe a variável aleatória T _i ser o primeiro tempo de retorno ao estado i (o "tempo de acerto"):

${\ displaystyle T_ {i} = \ inf \ {n \ geq 1: X_ {n} = i \}.}$

O número

${\ displaystyle f_ {ii} ^ {(n)} = \ Pr (T_ {i} = n \ mid X_ {0} = i)}$

é a probabilidade de retornarmos ao estado i pela primeira vez após n passos. Portanto, o estado i é transitório se

${\ displaystyle \ Pr (T_ {i} <\ infty \ mid X_ {0} = i) = \ sum _ {n = 1} ^ {\ infty} f_ {ii} ^ {(n)} <1.}$

O estado i é recorrente (ou persistente) se não for transitório. Recorrência e transitoriedade são propriedades de classe, isto é, elas são válidas ou não são igualmente válidas para todos os membros de uma classe comunicante.

Um estado i é recorrente se e somente se o número esperado de visitas a i for infinito:

${\ displaystyle \ sum _ {n = 0} ^ {\ infty} p_ {ii} ^ {(n)} = \ infty.}$

Recorrência positiva

Mesmo que o tempo de acerto seja finito com probabilidade 1 , ele não precisa ter uma expectativa finita . O tempo médio de recorrência no estado i é o tempo de retorno esperado M _i :

${\ displaystyle M_ {i} = E [T_ {i}] = \ sum _ {n = 1} ^ {\ infty} n \ cdot f_ {ii} ^ {(n)}.}$

O estado i é recorrente positivo (ou persistente não nulo) se M _i for finito; caso contrário, o estado i é recorrente nulo (ou persistente nulo). A recorrência positiva e nula são propriedades de classes.

Estados absorventes

Um estado i é denominado absorvente se for impossível sair desse estado. Portanto, o estado i está absorvendo se e somente se

${\ displaystyle p_ {ii} = 1 {\ text {e}} p_ {ij} = 0 {\ text {para}} i \ not = j.}$

Se cada estado pode atingir um estado absorvente, então a cadeia de Markov é uma cadeia de Markov absorvente .

Cadeia de Markov reversível

Uma cadeia de Markov é considerada reversível se houver uma distribuição de probabilidade π sobre seus estados de modo que

${\ displaystyle \ pi _ {i} \ Pr (X_ {n + 1} = j \ mid X_ {n} = i) = \ pi _ {j} \ Pr (X_ {n + 1} = i \ mid X_ {n} = j)}$

para todos os tempos n e todos os estados i e j . Esta condição é conhecida como condição de equilíbrio detalhada (ou equação de equilíbrio local).

Considerando um tempo arbitrário fixo n e usando a abreviação

${\ displaystyle p_ {ij} = \ Pr (X_ {n + 1} = j \ mid X_ {n} = i) \ ,,}$

a equação de equilíbrio detalhada pode ser escrita de forma mais compacta como

${\ displaystyle \ pi _ {i} p_ {ij} = \ pi _ {j} p_ {ji} \,}$

O único passo de tempo de n para n  + 1 pode ser pensado como cada pessoa i tendo π _i dólares inicialmente e pagando a cada pessoa j uma fração p _ij disso. A condição de saldo detalhado afirma que, a cada pagamento, a outra pessoa paga exatamente a mesma quantia de dinheiro de volta. Claramente, a quantia total de dinheiro π que cada pessoa possui permanece a mesma após o intervalo de tempo, uma vez que cada dólar gasto é compensado por um dólar correspondente recebido. Isso pode ser mostrado mais formalmente pela igualdade

${\ displaystyle \ sum _ {i} \ pi _ {i} p_ {ij} = \ sum _ {i} \ pi _ {j} p_ {ji} = \ pi _ {j} \ sum _ {i} p_ {ji} = \ pi _ {j} \ ,,}$

que essencialmente afirma que a quantidade total de dinheiro que a pessoa j recebe (incluindo de si mesma) durante o intervalo de tempo é igual à quantidade de dinheiro que ela paga aos outros, que é igual a todo o dinheiro que ele inicialmente tinha, porque foi assumido que todo o dinheiro foi gasto (que é, p _ji soma 1 sobre i ). A suposição é técnica, porque o dinheiro não realmente usado é simplesmente pensado como sendo pago pela pessoa j a ela mesma (ou seja, p _jj não é necessariamente zero).

Como n era arbitrário, esse raciocínio vale para qualquer n e, portanto, para cadeias de Markov reversíveis π é sempre uma distribuição de Pr ( X _{n +1}  =  j  |  X _n  =  i ) em estado estacionário para cada  n .

Se a cadeia de Markov começa na distribuição de estado estacionário, isto é, se , então para todos e a equação de equilíbrio detalhada pode ser escrita como ${\ displaystyle \ Pr (X_ {0} = i) = \ pi _ {i}}$${\ displaystyle \ Pr (X_ {n} = i) = \ pi _ {i}}$${\ displaystyle n}$

${\ displaystyle \ Pr (X_ {n} = i, X_ {n + 1} = j) = \ Pr (X_ {n + 1} = i, X_ {n} = j) \,}$

Os lados esquerdo e direito desta última equação são idênticos, exceto pela reversão dos índices de tempo n e  n  + 1.

O critério de Kolmogorov fornece uma condição necessária e suficiente para que uma cadeia de Markov seja reversível diretamente das probabilidades da matriz de transição. O critério requer que os produtos das probabilidades em torno de cada loop fechado sejam os mesmos em ambas as direções ao redor do loop.

Cadeias de Markov reversíveis são comuns em abordagens de Monte Carlo por cadeia de Markov (MCMC) porque a equação de equilíbrio detalhada para uma distribuição desejada π implica necessariamente que a cadeia de Markov foi construída de forma que π seja uma distribuição em estado estacionário. Mesmo com cadeias de Markov não homogêneas no tempo, onde múltiplas matrizes de transição são usadas, se cada uma dessas matrizes de transição exibe equilíbrio detalhado com a distribuição π desejada , isso necessariamente implica que π é uma distribuição de estado estacionário da cadeia de Markov.

Distribuições estacionárias

Uma distribuição é uma distribuição estacionária da cadeia de Markov com matriz estocástica se e somente se . Isso pode ser escrito como: ${\ displaystyle \ pi}$${\ displaystyle P}$${\ displaystyle \ pi P = \ pi}$

${\ displaystyle \ forall j \ in \ mathbb {S}: \ sum _ {i \ in \ mathbb {S}} \ pi _ {i} p_ {ij} = \ pi _ {j}}$

Esta condição implica que e, portanto, se a cadeia de Markov tem distribuição inicial, então (na distribuição) para qualquer . ${\ displaystyle \ pi P ^ {n} = \ pi}$${\ displaystyle (X_ {n}, n \ in \ mathbb {N})}$${\ displaystyle X_ {0} = \ pi}$${\ displaystyle X_ {n} = \ pi}$${\ displaystyle n \ in \ mathbb {N}}$

Se uma cadeia de Markov for irredutível, então ela terá uma distribuição estacionária se e somente se for recorrente positiva, caso em que a única distribuição é dada por onde é o tempo médio de recorrência de i . ${\ displaystyle \ pi _ {i} = {\ frac {1} {M_ {i}}}}$${\ displaystyle M_ {i} = \ mathbb {E} (T_ {i})}$

Se uma cadeia tiver mais de uma classe de comunicação fechada, suas distribuições estacionárias não serão exclusivas (considere qualquer classe de comunicação fechada na cadeia; cada uma terá sua própria distribuição estacionária única . Estendendo essas distribuições para a cadeia geral, definindo todos os valores para zero fora da classe de comunicação, resulta em que o conjunto de medidas invariantes da cadeia original é o conjunto de todas as combinações convexas de 's). No entanto, se um estado j é aperiódico, então e para qualquer outro estado i , seja f _ij a probabilidade de que a cadeia visite o estado j se começar em  i , ${\ displaystyle C_ {i}}$${\ displaystyle \ pi _ {i}}$${\ displaystyle \ pi _ {i}}$${\ displaystyle \ lim \ nolimits _ {n \ rightarrow \ infty} p_ {jj} ^ {(n)} = {\ tfrac {C} {M_ {j}}}}$${\ displaystyle \ lim \ nolimits _ {n \ rightarrow \ infty} p_ {ij} ^ {(n)} = C {\ tfrac {f_ {ij}} {M_ {j}}}.}$

Se um estado i for periódico com período k  > 1, o limite não existe, embora exista para todo inteiro  r . ${\ displaystyle \ lim \ nolimits _ {n \ rightarrow \ infty} p_ {ii} ^ {(n)}}$${\ displaystyle \ lim \ nolimits _ {n \ rightarrow \ infty} p_ {ii} ^ {(kn + r)}}$

Análise de estado estacionário e a cadeia de Markov não homogênea no tempo

Uma cadeia de Markov não precisa ser necessariamente homogênea no tempo para ter uma distribuição de equilíbrio. Se houver uma distribuição de probabilidade sobre os estados de tal forma que ${\ displaystyle {\ boldsymbol {\ pi}}}$

${\ displaystyle \ pi _ {j} = \ sum _ {i \ in S} \ pi _ {i} \, \ Pr (X_ {n + 1} = j \ mid X_ {n} = i)}$

para todo estado j e todo tempo n então é uma distribuição de equilíbrio da cadeia de Markov. Isso pode ocorrer em métodos de Monte Carlo por cadeia de Markov (MCMC) em situações em que várias matrizes de transição diferentes são usadas, porque cada uma é eficiente para um tipo particular de mistura, mas cada matriz respeita uma distribuição de equilíbrio compartilhada. ${\ displaystyle {\ boldsymbol {\ pi}}}$

Tempos de acerto

O tempo de acerto é o tempo, começando em um determinado conjunto de estados até que a cadeia chegue em um determinado estado ou conjunto de estados. A distribuição de tal período de tempo tem uma distribuição do tipo de fase. A distribuição mais simples é a de uma única transição distribuída exponencialmente.

Tempos de acerto esperados

Para um subconjunto de estados A  ⊆  S , o vetor k ^A de tempos de acerto (onde o elemento representa o valor esperado , começando no estado i em que a cadeia entra em um dos estados no conjunto A ) é a solução não negativa mínima para ${\ displaystyle k_ {i} ^ {A}}$

${\ displaystyle {\ begin {alinhado} k_ {i} ^ {A} = 0 & {\ text {for}} i \ in A \\ - \ sum _ {j \ in S} q_ {ij} k_ {j} ^ {A} = 1 & {\ text {para}} i \ notin A. \ end {alinhado}}}$

Teorema ergódico

Um exemplo de teoria ergódica , o teorema ergódico para estados que, para uma cadeia de Markov aperiódica irredutível, com quaisquer dois estados i e j ,

${\ displaystyle p_ {i, j} ^ {(n)} \ rightarrow {\ frac {1} {M_ {j}}}}$ Como ${\ displaystyle n \ rightarrow \ infty}$

Notas

Referências