Cadeias de Markov
Em matemática, uma cadeia de Markov é um caso particular de processo estocástico com estados discretos com a propriedade de que a distribuição de probabilidade do próximo estado depende apenas do estado atual e não na sequência de eventos que precederam, uma propriedade chamada de Markoviana, chamada assim em homenagem ao matemático Andrei Andreyevich Markov. A definição dessa propriedade, também chamada de memória markoviana, é que os estados anteriores são irrelevantes para a predição dos estados seguintes, desde que o estado atual seja conhecido. Cadeias de Markov têm muitas aplicações como modelos estatísticos de processos do mundo real.
A cadeia de Markov é um processo estocástico com a propriedade de Markov. O termo "cadeia de Markov" refere-se à sequência de variáveis aleatórias, tais um processo move-se através de, com a propriedade de Markov definindo a dependência de série única entre períodos adjacentes (como em uma "cadeia"). Assim, pode ser usado para sistemas que seguem uma cadeia de eventos ligados, onde o que acontece em seguida depende apenas do estado atual do sistema descrevendo. Na literatura, diferentes tipos de processo de Markov são designados como "cadeia de Markov". Normalmente, o termo é reservado para um processo com um conjunto discreto de vezes, isto é, Cadeia de Markov de Tempo Discreto (DTMC). Por outro lado, alguns autores utilizam o termo "processo de Markov" para se referir a uma cadeia de Markov de tempo contínuo sem referência explícita. Enquanto o parâmetro de tempo é geralmente discreto, o espaço de estado de uma cadeia de Markov não tem quaisquer restrições geralmente aceitas: o termo pode referir-se a um processo em um espaço de estado arbitrário. No entanto, muitas aplicações de Cadeias de Markov empregam conjuntos contáveis finitos ou infinitos (isto é, espaços de estado discretos), que têm uma análise estatística mais simples. Além da hora do índice e os parâmetros de espaço de estado, há muitas outras variações, extensões e generalizações (ver Variações). Para simplificar, a maior parte deste artigo concentra-se no tempo discreto, discreta caso de espaço de estado, salvo indicação em contrário.
Uma cadeia de Markov é uma sequência X1, X2, X3, ... de variáveis aleatórias. O escopo destas variáveis, isto é, o conjunto de valores que elas podem assumir, é chamado de espaço de estados, onde Xn denota o estado do processo no tempo n. Se a distribuição de probabilidade condicional de Xn+1 nos estados passados é uma função apenas de Xn, então: onde x é algum estado do processo. A identidade acima define a propriedade de Markov. Cadeias de Markov são frequentemente descritas por uma sequência de grafos dirigidos, onde as arestas do gráfico n são rotulados por as probabilidades de ir de um estado no tempo n para outros estados no tempo n+1, Pr ( X n + 1 = x ∣ X n = x n ) {\displaystyle \Pr(X_{n+1}=x\mid X_{n}=x_{n})} . A mesma informação é representada pela matriz de transição de momento n para o tempo n+1. No entanto, as cadeias Markov são assumidas frequentemente como sendo tempo-homogêneas (ver variações abaixo), nesse caso o gráfico e a matriz são independentes de n e, portanto, não são apresentados como sequências.
Caracterização de um processo de Markov
Um processo de Markov é um processo estocástico em que a probabilidade de o sistema estar no estado i no período (n+1) depende somente do estado em que o sistema está no período n. Ou seja, para os processos de Markov, só interessa o estado imediato. Os principais elementos de um processo de Markov são dois :
Variações
para todo n. A probabilidade da transição de n é independente. Em outras palavras, o estado futuro depende dos passados m {\displaystyle m} estados. É possível construir uma cadeia ( Y n ) {\displaystyle (Y_{n})} de ( X n ) {\displaystyle (X_{n})} , que tem a propriedade de Markov "clássico", tendo como espaço de estado do m {\displaystyle m} -tuplas ordenadas de valores X {\displaystyle X} , ou seja, Y n = ( X n , X n − 1 , … , X n − m + 1 ) {\displaystyle Y_{n}=(X_{n},X_{n-1},\dots ,X_{n-m+1})} .
Cadeias de Markov em espaços de estados discretos
Um espaço de estados é representável por uma matriz. Chamada de matriz de transição, com o (i, j)-ésimo elemento igual a Para um espaço de estados discretos, as integrações na probabilidade de transição de k passos são somatórios, e podem ser calculados como a k-ésima potência da matriz de transição. Isto é, se P é a matriz de transição para um passo, então Pk é a matriz de transição para a transição de k passos. A distribuição estacionária π {\displaystyle \pi } é o vetor que satisfaz a equação: onde π T {\displaystyle \pi ^{T}} é o vetor transposto de π {\displaystyle \pi } . Em outras palavras, a distribuição estacionária π {\displaystyle \pi } é o autovetor (vetor próprio) esquerdo da matriz de transição, associado com o autovalor (valor próprio) 1.
Um diagrama de estado para um exemplo simples é mostrado na figura à direita, usando para imaginar as transições de estado de um grafo dirigido. Os estados representam se um mercado de ações hipotético está exibindo um mercado em alta, mercado em baixa, ou tendência do mercado estagnado durante uma determinada semana. De acordo com a figura, uma semana de alta é seguido por uma outra semana de alta 90% do tempo, de uma semana de baixa 7,5% do tempo, e uma semana estagnada outro 2,5% do tempo. Etiquetas de espaço de estado {1 = alta, 2 = baixa, 3 = estagnado} a matriz de transição para este exemplo é A distribuição por estados pode ser escrito como um vetor de linha estocástico x com x(n + 1) = x(n)P. Assim, se no tempo n o sistema está no estado x(n), e em seguida, três períodos de tempo mais tarde, no tempo n + 3 a distribuição é Em particular, se num momento n o sistema está no estado 2 (baixa), então no tempo n + 3, a distribuição é
A probabilidade de ir do estado i para o estado j em intervalos de tempo n é Para uma cadeia de Markov de tempo homogêneo: As probabilidades de transição de n-etapa satisfazem a equação Chapman-Kolmogorov, que para qualquer k tal que 0 < k < n, onde S é o espaço de estados da cadeia de Markov. A distribuição marginal Pr(Xn = x) é a distribuição mais estados no tempo n. A distribuição inicial é Pr(X0 = x). A evolução do processo através de um passo de tempo é descrita pela Nota: O expoente (n) é um índice e não um expoente.
Redutibilidade
Um estado j é dito ser acessível a partir de um estado i (escrito i → j) se um sistema começou no estado i tem uma probabilidade diferente de zero de transição para o estado j em algum ponto. Formalmente, o estado j é acessível a partir do estado i, se existe um inteiro nij ≥ 0 tal que Este inteiro é permitido para ser diferente para cada par de estados, portanto, os subscritos em nij. Permitindo que n seja zero significa que cada estado é definida para ser acessível a partir de si mesmo. Um estado i é dito para se comunicar com o estado j (escrito i ↔ j) se ambos i → j e j → i. Um conjunto de estados C é uma classe de comunicação se cada par de estados em C comunica com o outro. Uma classe comunicação está fechado se a probabilidade de deixar a classe é zero, ou seja, que se i estiver em C, mas j não, então j não é acessível a partir de i. Pode-se mostrar que a comunicação neste sentido é uma relação de equivalência e, assim, que as classes comunicantes são as classes de equivalência dessa relação.
Periodicidade
Um estado i tem período k se houver retorno ao estado i deve ocorrer em múltiplos de passos de tempo k. Formalmente, o período de um estado é definido como (Onde "mdc" é o maior divisor comum), desde que este conjunto não é vazio. Caso contrário, o período não está definido. Note-se que mesmo que um estado tem período k, pode não ser possível atingir o estado em k passos. Por exemplo, suponha que é possível voltar ao estado em {6, 8, 10, 12, ...} intervalos de tempo; k seria 2, embora 2 não aparece nesta lista. Se k = 1, então o estado é dito ser aperiódico: retorno ao estado i pode ocorrer em períodos irregulares. Pode ser demonstrado que um estado i é aperiódico se e somente se existe n tal que para todo n' ≥ n,
Transitoriedade
Um estado i é dito transitório, se, uma vez que começamos no estado i, existe uma probabilidade não nula de que nunca voltará a i. Formalmente, seja a variável aleatória Ti o primeiro tempo de retorno ao estado i (o "hitting time"): é a probabilidade de voltar para o estado i pela primeira vez após n passos. Portanto, o estado i é transitório se O estado i é recorrente (ou persistente) se não é transitório. Estados recorrentes tem garantidos (com probabilidade 1) um hitting time finito. Recorrência e transitoriedade são propriedades de classe, isto é, elas são válidas ou não de forma igual para todos os membros de uma classe comunicante. Mesmo que o hitting time seja finito com probabilidade 1, ele não precisa de ter uma expectativa finita. O tempo de recorrência média no estado i é o tempo de retorno esperado Mi:
Ergodicidade
Um estado i é dito ser ergódico se ele tem uma recorrência aperiódica e positiva. Em outras palavras, um estado i é ergódico se for recorrente, tem um período de 1 e tem tempo de recorrência média finita. Se todos os estados em uma cadeia de Markov irredutível são ergódicos, então a cadeia é ergódica. É possível mostrar que uma cadeia de Marvok irredutível de estado finito é ergódica se ela tem um estado aperiódico. A cadeia de Markov tem a propriedade ergódica se há um número finito N tal que qualquer estado pode ser alcançado a partir de qualquer outro estado em exatamente N passos. No caso de uma matriz de transição totalmente ligada, em que todas as transições têm uma probabilidade não nula, esta condição é preenchida com N = 1. A cadeia de Markov com mais de um estado e apenas uma transição de sair por estado não pode ser ergódica.
Análise de estado estacionário e distribuições limitantes
Se a cadeia de Markov é uma cadeia de Markov de tempo homogénea, de modo que o processo é descrito por uma única matriz que independe do tempo p i j {\displaystyle p_{ij}} , então o vetor π {\displaystyle {\boldsymbol {\pi }}} é chamado de distribuição estacionária (ou medida invariante) se ∀ j ∈ S {\displaystyle \forall j\in S} satisfaz Uma cadeia irredutível tem uma distribuição estacionária se e somente se todos os seus estados são recorrentes positivos. Nesse caso, π é único e está relacionada com o tempo de retorno esperado: onde C {\displaystyle C} é a constante de normalização. Além disso, se a cadeia positiva recorrente é irredutível e aperiódica, diz-se que tem uma distribuição limitante; para qualquer i e j,
Se o espaço de estados é finito, a distribuição de probabilidade de transição pode ser representada por uma matriz, chamada de matriz de transição, com o (i, j)-ésimo elemento de P igual Uma vez que cada fileira de P soma um e todos os elementos são não-negativos, P é uma matriz estocástica direita.
Relação distribuição estacionária de vetores próprios e simplices
Um π distribuição estacionária é um vetor (linha), cujos elementos são não-negativos e somam 1, mantém-se inalterado pela operação da matriz de transição P sobre ele e por isso é definida pela Ao comparar essa definição com a de um vetor próprio vemos que os dois conceitos estão relacionados e que é um múltiplo normalizado ( ∑ i π i = 1 {\displaystyle \textstyle \sum _{i}\pi _{i}=1} ) de um vetor próprio esquerdo e' da matriz de transição PT com um valor próprio de 1. Se houver mais do que uma unidade de vetor próprio em seguida, a soma ponderada dos correspondentes estados estacionários é também um estado estacionário. Mas para uma cadeia de Markov é geralmente mais interessados em um estado estacionário que é o limite das distribuições de sequência para alguma distribuição inicial.
Cadeia de Markov de tempo homogêneo com um espaço de estado finito
Se a cadeia de Markov é vez homogênea, em seguida, a matriz de transição P é o mesmo depois de cada passo, de modo que a probabilidade de transição do passo k pode ser calculado como a potência k da matriz de transição Pk. Se a cadeia de Markov é irredutível e aperiódica, então há uma distribuição estacionária única π. Além disso, neste caso Pk converge para uma matriz de posto um em que cada linha é o π distribuição estacionária, que é, onde 1 é o vetor coluna com todas as entradas iguais a 1. Isto é afirmado pelo teorema de Perron-Frobenius. Se, por qualquer meio, lim k → ∞ P k {\displaystyle \scriptstyle \lim _{k\to \infty }\mathbf {P} ^{k}} é encontrado, então a distribuição estacionária da cadeia de Markov em questão pode ser facilmente determinada para qualquer distribuição, tal como será explicado abaixo.
Velocidade de convergência para a distribuição estacionária
Como afirmado anteriormente, a partir da equação π = π P {\displaystyle \mathbf {\pi } =\mathbf {\pi P} } , (se existir) o estacionária (ou steady state) π distribuição é um autovetor esquerdo da linha da matriz estocástica P. Em seguida, assumindo que P é diagonalizável ou equivalentemente que P tem n autovetores linearmente independentes, a velocidade de convergência é elaborado da seguinte forma. (Para não diagonalizável, ou seja, matrizes defeituosos, pode-se começar com a forma normal Jordan de P e prosseguir com o conjunto um pouco mais envolvidos de argumentos de uma maneira similar.) Seja U a matriz de autovetores (cada um normalizado para ter uma norma L2 igual a 1), onde cada coluna é um vetor próprio esquerdo do P e deixe Σ a matriz diagonal de valores próprios à esquerda de P, ou seja, Σ = diag(λ1,λ2,λ3,...,λn). Então, por eigendecomposição
Uma cadeia de Markov é dita ser reversível se existe uma distribuição de probabilidade π sobre os seus estados tais que para todos os tempos n e todos os estados i e j. Esta condição é conhecida como condição de balanço detalhado (alguns livros chamam a equação de balanço local). Considerando-se um tempo arbitrário n fixo e usando a abreviação a equação do balanço detalhado pode ser escrita de forma mais compacta como O tempo de um só passo a partir de n a n+1 pode ser pensado como tendo cada pessoa i que inicialmente πi dólares e pagar cada pessoa j uma fração pij dela. A condição de balanço detalhado afirma que a cada pagamento, a outra pessoa paga exatamente a mesma quantidade de dinheiro de volta. É evidente que a quantidade total de dinheiro π que cada pessoa tem permanece o mesmo após o passo de tempo, uma vez que cada dólar gasto é equilibrado por um dólar correspondente recebida. Isto pode ser demonstrado mais formalmente pela igualdade
Cadeia de Markov reversível mais próxima
Para qualquer cadeia de Markov de tempo homogêneo dada por uma matriz de transição P ∈ R n × n {\displaystyle P\in \mathbb {R} ^{n\times n}} , qualquer norma | | ⋅ | | {\displaystyle ||\cdot ||} em R n × n {\displaystyle \mathbb {R} ^{n\times n}} que é induzido por um produto escalar, e qualquer vetor probabilidade π {\displaystyle \pi } , existe uma matriz de transição única P ∗ {\displaystyle P^{*}} que é reversível de acordo com a π {\displaystyle \pi } e que está mais próxima de P {\displaystyle P} de acordo com a norma | | ⋅ | | {\displaystyle ||\cdot ||} . A matriz P ∗ {\displaystyle P^{*}} pode ser calculada resolvendo um problema de otimização quadrático-convexa.
Um esquema de Bernoulli é um caso especial de uma cadeia de Markov, onde a matriz de probabilidades de transição tem linhas idênticas, o que significa que o próximo estado é ainda independente do estado corrente (para além de serem independentes dos estados anteriores). Um esquema de Bernoulli com apenas dois estados possíveis é conhecido como um processo de Bernoulli.
Para uma visão geral de cadeias de Markov em um espaço geral do estado, ver as cadeias de Markov artigo em um espaço de estado mensurável.
Cadeias Harris
Muitos resultados para cadeias de Markov com espaço de estados finitos podem ser generalizados para cadeias com espaço de estado incontável através de cadeias de Harris. A ideia principal é para ver se há um ponto no espaço de estado que os hits da cadeia com probabilidade um. Geralmente, não é verdadeiro para o espaço de estado contínuo, no entanto, podemos definir conjuntos A e B, juntamente com um número positivo ε e uma medida de probabilidade ρ, de tal modo que Em seguida, pode entrar em colapso os conjuntos em um ponto auxiliar α, e uma cadeia Harris recorrente pode ser modificado para conter α. Finalmente, o conjunto de cadeias Harris é um nível confortável de generalidade, a qual é ampla o suficiente para conter um grande número de exemplos interessantes, ainda restritiva suficiente para permitir uma teoria rica.
Cadeias de Markov interagindo localmente
Considerando-se uma coleção de cadeias de Markov cuja evolução leva em conta o estado de outras cadeias de Markov, está relacionada com a noção de interagir localmente cadeias de Markov. Isso corresponde à situação em que o espaço de estado tem uma forma de produto. Veja interagindo sistema de partículas e autômatos celulares estocástico (probabilística autômatos celulares). Ver, por exemplo Interação de Markov processos. ou
A pesquisa tem relatado a aplicação e utilidade das cadeias de Markov em uma ampla gama de tópicos, tais como a física, química, medicina, música, teoria dos jogos e esportes. O PageRank de uma página da web como usado pelo Google é definida por uma cadeia de Markov. É a probabilidade de estar em página i {\displaystyle i} displaystyle na distribuição estacionária sobre a seguinte cadeia de Markov em todas as páginas Web (conhecidas). Se N {\displaystyle N} é o número de páginas da Web conhecidas, e uma página i {\displaystyle i} tem k i {\displaystyle k_{i}} links para ela, então ele tem probabilidade de transição α k i + 1 − α N {\displaystyle {\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}} para todas as páginas que estão ligadas a ela e 1 − α N {\displaystyle {\frac {1-\alpha }{N}}} para todas as páginas que estão não ligadas. O parâmetro α {\displaystyle \alpha } é considerado como sendo cerca de 0,85.
Física
Sistemas Markovianos aparecem extensivamente em termodinâmica e mecânica estatística, sempre que as probabilidades são usados para representar detalhes desconhecidos ou não modelados do sistema, se pode presumir-se que a dinâmica é invariante no tempo, e que nenhuma história relevante precisa ser considerado que não estiver incluído na descrição do estado.
Química
Cadeias de Markov e processos de Markov de tempo contínuo são úteis em química quando os sistemas físicos aproximam a propriedade de Markov. O modelo clássico da actividade da enzima, a cinética de Michaelis-Menten, pode ser visto como uma cadeia de Markov, onde em cada etapa de tempo a reacção prossegue em algum sentido. Enquanto Michaelis-Menten é bastante simples, redes de reacção muito mais complicados também podem ser modeladas com cadeias de Markov. Um algoritmo baseado numa cadeia de Markov também foi utilizado para focar o crescimento baseado no fragmento de produtos químicos in silico no sentido de uma classe desejada de compostos, tais como fármacos ou produtos naturais. Como uma molécula é cultivada, um fragmento é seleccionado a partir da molécula nascente como o estado "corrente". Não é do conhecimento do seu passado (isto é, não está consciente de que já se encontra ligado a ele). É, em seguida, passa para o próximo estado, quando um fragmento é ligado a ele. As probabilidades de transição são treinados em bases de dados das classes autênticas de compostos.
Ensaio
Muitos teóricos têm proposto a ideia do teste estatístico cadeia de Markov (MCST), um método de conjunção cadeias de Markov para formar um "Markov cobertor", organizando essas cadeias em várias camadas recursiva ( "wafering") e produção de testes mais eficientes conjuntos-amostras -como um substituto para testes exaustivos. MCSTs também têm usos em redes baseadas no estado temporais; O artigo de Chilukuri et al. intitulado "temporais Networks Incerteza raciocínio para Evidence fusão com Aplicações para objeto de Detecção e Acompanhamento" (ScienceDirect) dá um estudo de fundo e caso para aplicar MCSTs a uma ampla gama de aplicações.
Reconhecimento de fala
Modelos ocultos de Markov são a base para a maioria dos sistemas de reconhecimento de voz automáticas modernas.
Ciências da informação
Cadeias de Markov são usados em todo o processamento da informação. famosa 1948 de papel uma teoria matemática de Claude Shannon de comunicação, que em uma única etapa criou o campo da teoria da informação, abre com a introdução do conceito de entropia através de modelagem Markov do idioma Inglês. Tais modelos idealizados pode capturar muitas das regularidades estatísticas de sistemas. Mesmo sem descrever a estrutura completa do sistema perfeitamente, tais modelos de sinal podem tornar possível a compressão de dados muito eficaz através de técnicas de codificação de entropia, como codificação aritmética. Eles também permitem que estimação de estado eficaz e reconhecimento de padrões. Cadeias de Markov também desempenham um papel importante no aprendizado por reforço.
Teoria de filas
Cadeias de Markov são a base para o tratamento analítico das filas (teoria de filas). Agner Krarup Erlang iniciou o assunto em 1917. Isso os torna crítico para otimizar o desempenho de redes de telecomunicações, em que as mensagens muitas vezes competem por recursos limitados (como a largura de banda).
