Cadeia de Markov

Em matemática , uma cadeia de Markov é um processo de Markov em tempo discreto, ou tempo contínuo e espaço de estado discreto. Um processo de Markov é um processo estocástico que possui a propriedade de Markov : a informação útil para prever o futuro está inteiramente contida no estado presente do processo e não é dependente de estados anteriores (o sistema não tem "memória"). Os processos de Markov têm o nome de seu inventor, Andrei Markov .

Um processo de Markov em tempo discreto é uma sequência de variáveis aleatórias com valores no espaço de estados , que observaremos a seguir. O valor é o estado do processo no instante.As aplicações onde o espaço de estado é finito ou contável são inúmeras: fala-se então de cadeia de Markov ou de cadeias de Markov com espaço de estado discreto . As propriedades essenciais dos processos de Markov gerais, por exemplo as propriedades de recorrência e ergodicidade , podem ser declaradas ou provadas de forma mais simples no caso de cadeias de Markov em espaço de estado discreto . Este artigo trata precisamente das cadeias de Markov com espaço de estado discreto . ${\ displaystyle X_ {0},}$ ${\ displaystyle X_ {1},}$ ${\ displaystyle X_ {2},}$ ${\ displaystyle X_ {3}, \ \ dots}$ $E$ $X_ {n}$ $não.$ $E$

Andrei Markov publicou os primeiros resultados sobre cadeias de Markov no espaço de estado finito em 1906 . Uma generalização para um espaço de estado infinito contável foi publicada por Kolmogorov em 1936 . Processos de Markov estão relacionados com o movimento Browniano ea hipótese ergódica , dois tópicos de física estatística que eram muito importantes no início do XX ° século .

Propriedade de Markov fraca

Definições

Esta é a propriedade característica de uma cadeia de Markov: a previsão do futuro a partir do presente não é tornada mais precisa por informações adicionais sobre o passado, porque todas as informações úteis para a previsão do futuro estão contidas no estado presente de o processo. A propriedade de Markov fraca tem várias formas equivalentes que equivalem a observar que a lei condicional de conhecer o pretérito, ou seja, conhecer é uma função de apenas: $X _ {{n + 1}}$ ${\ displaystyle \ left (X_ {k} \ right) _ {0 \ leq k \ leq n},}$ $X_ {n}$ ${\ begin {alinhados} \ forall n \ geq 0, \ forall (i_ {0}, \ ldots, i _ {{n-1}}, i, j) & \ in E ^ {{n + 2}} , \\ {\ mathbb {P}} {\ Big (} X _ {{n + 1}} = j & \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1} , \ ldots, X _ {{n-1}} = i _ {{n-1}}, X_ {n} = i {\ Big)} = {\ mathbb {P}} \ left (X _ {{ n + 1}} = j \ mid X_ {n} = i \ right). \ end {alinhado}}$

Uma variante comum das cadeias de Markov é a cadeia de Markov homogênea , para a qual a probabilidade de transição é independente de : $não$ ${\ displaystyle \ forall n \ geq 1, \ forall (i, j) \ in E ^ {2}, \ quad \ mathbb {P} (X_ {n + 1} = j \ mid X_ {n} = i) = \ mathbb {P} (X_ {n} = j \ mid X_ {n-1} = i)}$

No restante do artigo, apenas cadeias de Markov homogêneas serão consideradas. Para uma aplicação interessante de cadeias de Markov não homogêneas para otimização combinatória , consulte o artigo Simulated annealing . Existe uma propriedade de Markov forte , ligada à noção de tempo de parada : esta propriedade de Markov forte é crucial para a prova de resultados importantes (vários critérios de recorrência, lei forte de grandes números para cadeias de Markov). É afirmado no artigo " Propriedade de Markov ".

Critério

Critério fundamental - Seja uma sequência de variáveis aleatórias independentes da mesma lei, com valores em um espaço , e um mapa mensurável de em. Suponha que a sequência seja definida pela relação de recorrência: ${\ displaystyle Y = (Y_ {n}) _ {n \ geq 1}}$ $F$ $f$ $E \ times F$ ${\ displaystyle E.}$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ $\ forall n \ geq 0, \ qquad X _ {{n + 1}} = f \ left (X_ {n}, Y _ {{n + 1}} \ right),$ e suponha que a sequência seja independente de Então é uma cadeia de Markov homogênea. $Y$ ${\ displaystyle X_ {0}.}$ $X$

Exemplo: o problema do coletor de adesivos :

Petit Pierre reúne retratos dos onze jogadores da seleção nacional de futebol, que encontra em adesivos dentro das embalagens das barras de chocolate; toda vez que ele compra um tablet, ele tem 1 chance em 11 de encontrar o retrato do jogador n ° (para tudo ). Observe o status da coleção de Pierre Petit, depois de abrir a embalagem do seu e barra de chocolate. é uma cadeia de Markov a partir de , porque se encaixa no quadro anterior para a escolha desde $k$ $k$ ${\ displaystyle X_ {n} \ in {\ mathcal {P}} ([\! [1,11] \!])}$ $não$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ ${\ displaystyle X_ {0} = \ emptyset}$ ${\ displaystyle F = [\! [1,11] \!], \ E = {\ mathcal {P}} (F), \ f (x, y) = x \ xícara \ {y \},}$ $X _ {{n + 1}} = X_ {n} \ xícara \ {Y _ {{n + 1}} \},$ onde as variáveis aleatórias são variáveis aleatórias independentes e uniformes sobre : são os números sucessivos das vinhetas tiradas das barras de chocolate. O tempo médio necessário para completar a coleção (aqui o número de comprimidos que Petit Pierre deve comprar em média para completar sua coleção) é, para uma coleção de vinhetas no total, onde está o º número harmônico . Por exemplo, barras de chocolate. ${\ displaystyle Y_ {n}}$ ${\ displaystyle [\! [1,11] \!]}$ $NÃO$ ${\ displaystyle N \, H_ {N},}$ ${\ displaystyle H_ {N}}$ $NÃO$ ${\ displaystyle 11 \, H_ {11} = 33,2 \ dots \ quad}$

Notas:

A propriedade de Markov deriva da independência do que permanece verdadeira quando há leis diferentes e quando a "relação de recorrência" depende de As suposições feitas além da independência existem apenas para garantir a homogeneidade da cadeia por Markov. ${\ displaystyle Y_ {i} \;}$ $Y_ {i}$ ${\ displaystyle X_ {n + 1} = f_ {n} \ left (X_ {n}, Y_ {n + 1} \ right)}$ $não.$
O critério é fundamental no sentido de que qualquer cadeia de Markov homogênea pode ser simulada por meio de uma recorrência da forma para uma função bem escolhida. Podemos até escolher e escolher variáveis independentes e uniformes no intervalo [0,1], o que é conveniente para o estudo de cadeias de Markov usando métodos de Monte-Carlo . ${\ displaystyle X_ {n + 1} = f \ left (X_ {n}, Y_ {n + 1} \ right),}$ $f$ ${\ displaystyle F = [0,1],}$ ${\ displaystyle Y_ {j}}$

Probabilidades de transição

Definição

Definição - O número é chamado de probabilidade de transição de estado para estado em uma etapa ou probabilidade de transição de estado para estado se não houver ambigüidade. Freqüentemente observamos este número ${\ displaystyle \ mathbb {P} \ left (X_ {1} = j \ mid X_ {0} = i \ right)}$ $eu$ $j$ $eu$ ${\ displaystyle j,}$ ${\ displaystyle p_ {i, j}:}$ $p _ {{i, j}} = {\ mathbb {P}} \ left (X _ {{1}} = j \ mid X_ {0} = i \ right).$

Os números da família são chamados de matriz de transição , o núcleo de transição ou operador de transição da cadeia de Markov. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$

A terminologia matriz de transição é a mais utilizada, mas é adequada, estritamente falando, apenas quando, para um inteiro Quando é finito, por exemplo de cardinal, pode-se sempre numerar os elementos de arbitrariamente de 1 até o que define o problema, mas de forma imperfeita, porque essa renumeração é contra-intuitiva em muitos exemplos. ${\ displaystyle n \ geq 1,}$ ${\ displaystyle E = \ {1,2, \ ldots, n \}.}$ $E$ ${\ displaystyle n,}$ $E$ ${\ displaystyle n,}$

Modelo Ehrenfest: os dois cães e suas pulgas:

Dois cães compartilham pulgas da seguinte maneira: a cada momento, uma das pulgas é escolhida ao acaso e depois pula de um cão para outro. O estado do sistema é descrito por um elemento onde $NÃO$ $NÃO$ ${\ displaystyle x = (x_ {1}, x_ {2}, \ dots, x_ {N}) \ in \ {0,1 \} ^ {N},}$ $x _ {{i}} = 0 {\ text {ou}} 1 {\ text {dependendo se o chip n}} ^ {{\ circ}} \ i {\ text {está no primeiro ou no segundo cão .}}$

Então tem elementos, mas numerá-los de 1 a seria difícil acompanhar a evolução do sistema, que consiste em escolher uma das coordenadas de ao acaso e alterar seu valor. Se quisermos entender o sistema com menos detalhes (porque não somos capazes de reconhecer um chip de outro), podemos simplesmente estudar o número de chips no cão # 1, o que equivale a escolher Novamente, para entender, seria uma pena renumerar os estados de 1 para Observe que, para esta nova modelização, $E$ $2 ^ {N}$ $2 ^ {N}$ $NÃO$ $x$ ${\ displaystyle E = \ {0,1,2, \ dots, N \}.}$ ${\ displaystyle N + 1.}$ $p _ {{k, k + 1}} = {\ tfrac {Nk} N} {\ text {et}} p _ {{k, k-1}} = {\ tfrac {k} N},$ já que, por exemplo, o número de fichas nas costas do cachorro n ° 1 vai de k para k-1 se for uma dessas k fichas que for escolhida para pular, entre as N fichas presentes no “sistema”. Este modelo é mais frequentemente referido como o “ Modelo de Urnas Ehrenfest ”. Foi introduzido em 1907 por Tatiana e Paul Ehrenfest para ilustrar alguns dos "paradoxos" que surgiram nos fundamentos da mecânica estatística nascente e para modelar o ruído rosa . O modelo de urna Ehrenfest foi considerado pelo matemático Mark Kac como "provavelmente um dos modelos mais instrutivos em toda a física".

Em vez de renumerar os estados de 1, é, portanto, mais ergonômico em muitos casos aceitar matrizes finitas ou infinitas cujas linhas e colunas são "numeradas" usando os elementos de O produto de duas dessas "matrizes" e , então, é definido muito naturalmente de ${\ displaystyle E.}$ ${\ displaystyle A = \ left (a_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ ${\ displaystyle B = \ left (b_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $(AB) _ {{i, j}} = \ sum _ {{\ ell \ in E}} a _ {{i, \ ell}} b _ {{\ ell, j}},$ por analogia com a fórmula mais clássica do produto de duas matrizes quadradas de tamanho ${\ displaystyle n,}$ $(AB) _ {{i, j}} = \ sum _ {{k = 1}} ^ {n} a _ {{i, k}} b _ {{k, j}}.$

Propriedades

Proposição - A matriz de transição é estocástica : a soma dos termos de qualquer linha sempre dá 1. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $P$ $\ forall i \ in E, \ quad \ sum _ {{j \ in E}} p _ {{i, j}} = 1.$

Proposição - A lei da cadeia de Markov é caracterizada pelo par formado por sua matriz de transição e sua lei inicial (a lei de ): para toda a lei conjunta de é dada por ${\ displaystyle X = \ left (X_ {n} \ right) _ {n \ geq 0}}$ ${\ displaystyle P,}$ $X_ {0}$ $n \ geq 1$ ${\ displaystyle (X_ {0}, X_ {1}, \ ldots, X_ {n})}$ ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0}, X _ {{1}} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n -1}}, X _ {{n}} = i_ {n} \ direita) = {\ mathbb {P}} \ esquerda (X _ {{0}} = i_ {0} \ direita) \ p _ {{i_ {{0}}, i_ {1}}} \, p _ {{i _ {{1}}, i_ {2}}} \, \ ldots \, p _ {{i _ {{n-2}}, i _ {{n-1}}}} \, p _ {{i _ {{n-1}}, i_ {n}}}.$

Demonstração

Por indução, na classificação 0, ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right) = {\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right )$

Na fila , posando ${\ displaystyle n,}$ ${\ displaystyle P_ {k} = \ mathbb {P} \ left (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {k-1} = i_ {k- 1}, X_ {k} = i_ {k} \ right),}$ ${\ frac {P_ {n}} {P _ {{n-1}}}} = {\ mathbb {P}} {\ Grande (} X _ {{n}} = i_ {n} \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n-1}} {\ Big)} = p _ {{i _ {{n-1}}, i_ {n}}},$ em virtude da propriedade de Markov fraca, então se tem a expressão esperada, então também. ${\ displaystyle P_ {n-1}}$ $P_ {n}$

Ao estudar uma determinada cadeia de Markov, sua matriz de transição é geralmente bem definida e fixada ao longo do estudo, mas a lei inicial pode mudar durante o estudo e as notações devem refletir a lei inicial considerada no momento: se em um momento do estudo, consideramos uma cadeia de Markov de distribuição inicial definida até então, as probabilidades são anotadas e as expectativas são anotadas. Em particular, se dissermos que a cadeia de Markov começa a partir das probabilidades são anotadas e as expectativas são anotadas ${\ displaystyle \ forall i \ in E, \ quad \ mathbb {P} \ left (X_ {0} = i \ right) = \ mu _ {i}, \ quad}$ ${\ displaystyle \ mathbb {P} _ {\ mu} \ left (\ dots \ right), \ quad}$ ${\ displaystyle \ mathbb {E} _ {\ mu} \ left [\ dots \ right]. \ quad}$ ${\ displaystyle \ mathbb {P} \ left (X_ {0} = j \ right) = 1, \ quad}$ ${\ displaystyle j, \ quad}$ ${\ displaystyle \ mathbb {P} _ {j} \ left (\ dots \ right), \ quad}$ ${\ displaystyle \ mathbb {E} _ {j} \ left [\ dots \ right]. \ quad}$

Poderes da matriz de transição

Para a probabilidade de transição na etapa, não depende de : ${\ displaystyle k \ geq 1,}$ $k$ ${\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right),}$ $não$

Proposição - A matriz de transição em etapas , é igual à potência th da matriz de transição nota Nós $k$ ${\ displaystyle \ left (\ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right) \ right) _ {(i, j) \ in E ^ {2} },}$ $k$ $P.$ $p _ {{i, j}} ^ {{(k)}} = {\ mathbb {P}} \ left (X _ {{n + k}} = j \ mid X_ {n} = i \ right) ,$ e $P ^ {k} = \ left (p _ {{i, j}} ^ {{(k)}} \ right) _ {{(i, j) \ in E ^ {2}}}.$

Demonstração

Por recorrência. No posto 1, é uma consequência da homogeneidade da cadeia de Markov já mencionada na seção Propriedade de Markov fraca : ${\ mathbb {P}} \ left (X _ {{n + 1}} = j \ mid X_ {n} = i \ right) = {\ mathbb {P}} \ left (X _ {{1}} = j \ mid X_ {0} = i \ right).$

Classificação ${\ displaystyle k,}$ ${\ begin {alinhados} {\ mathbb {P}} \ left (X_ {n} = i {\ text {and}} X _ {{n + k}} = j \ right) & = \ sum _ {{ \ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{n + k-1}} = \ ell {\ text {e}} X _ { {n + k}} = j \ right) \\ & = \ sum _ {{\ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{ n + k- 1}} = \ ell \ right) \ {\ mathbb {P}} \ left (X _ {{n + k}} = j \ mid X_ {n} = i, \, X _ {{ n + k-1}} = \ ell \ right) \\ & = \ sum _ {{\ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{n + k-1}} = \ ell \ direita) \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ esquerda (X_ {n} = i \ direita) \ \ sum _ {{\ ell \ in E}} p _ {{i, \ ell}} ^ {{(k-1)}} \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ left (X_ {n} = i \ right) \ p _ {{i, j}} ^ {{(k)}}, \ end {alinhado}}$ ou

o 1 r igualdade é o terceiro axioma da probabilidade ,
o 2 nd igualdade é a definição de uma probabilidade condicional ,
o 3 º igualdade é devido a uma forma de baixa propriedade de Markov,
a 4 ª igualdade é a propriedade de recorrência não ${\ displaystyle k-1,}$
a 5 th igualdade é a fórmula do produto de dois "matrizes", aplicado ao produto do com ${\ displaystyle P ^ {k-1}}$ $P.$

Para concluir, dividimos os dois termos extremos desta sequência de igualdades por, a menos que este último termo seja zero, caso em que podemos definir arbitrariamente, portanto, por exemplo, igual a ${\ displaystyle \ mathbb {P} \ left (X_ {n} = i \ right),}$ ${\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right)}$ ${\ displaystyle p_ {i, j} ^ {(k)}.}$

Por uma simples aplicação da fórmula de probabilidade total , deduzimos as leis marginais da cadeia de Markov.

Corolário - A lei de é dada por ${\ displaystyle X_ {n + k}}$ ${\ mathbb {P}} \ left (X _ {{n + k}} = j \ right) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ left (X _ {{ n}} = i \ right) p _ {{i, j}} ^ {{(k)}}.$

Em particular, ${\ mathbb {P}} \ left (X _ {{n}} = j \ right) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ left (X _ {{0} } = i \ right) p _ {{i, j}} ^ {{(n)}}.$

Na escrita da matriz, se a lei de é considerada um vetor linha com que se reformula em: ${\ displaystyle X_ {n}}$ ${\ displaystyle \ mu _ {n} = (\ mu _ {n, i}) _ {i \ in E},}$ ${\ displaystyle \ mu _ {n, i} = \ mathbb {P} \ left (X_ {n} = i \ right),}$ $\ mu _ {{n + k}} = \ mu _ {{n}} P ^ {k} \ quad {\ text {e}} \ quad \ mu _ {{n}} = \ mu _ {{0 }} P ^ {n}.$

Classificação dos estados

Para , dizemos que é acessível a partir de , se e somente se existir tal que Denotaremos: ${\ displaystyle (i, j) \ in E ^ {2}}$ $j$ $eu$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0.}$ $\ {j \ leftarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {\ existe n \ geq 0 {\ text {tal como}} p _ {{i, j}} ^ {{(n)}}> 0 \ certo \}.$

Dizemos isso e comunicamos se e somente se eles existem de modo que e Denotamos: $eu$ $j$ ${\ displaystyle (n, m) \ in \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ mid X_ {0} = j)> 0.}$ $\ {j \ leftrightarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {j \ leftarrow i {\ text {e}} i \ leftarrow j \ right \}.$

A relação de comunicar , notada, é uma relação de equivalência . Quando falamos de classe quando falamos dos estados de uma cadeia de Markov, geralmente é às classes de equivalência da relação que estamos nos referindo. Se todos os estados se comunicam, a cadeia de Markov é considerada irredutível . ${\ displaystyle \ leftrightarrow,}$ $\ leftrightarrow$

A relação ser acessível , denotada, estende-se às classes de equivalência: para duas classes e , temos ${\ displaystyle \ leftarrow,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$ $\ {C \ leftarrow C ^ {{\ prime}} \} \ quad \ Leftrightarrow \ quad \ left \ {\ exists (i, j) \ in C \ times C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftrightarrow \ quad \ left \ {\ forall (i, j) \ in C \ times C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \}.$

A relação é uma relação de ordem entre as classes de equivalência. $\ seta esquerda$

Diz- se que uma classe é final se não conduz a nenhuma outra, ou seja, se a classe é mínima para a relação , caso contrário, diz-se que é transitória . Pertencer a uma classe final ou transitória tem consequências nas propriedades probabilísticas de um estado na cadeia de Markov, em particular no seu status como um estado recorrente ou um estado transiente . O número e a natureza das classes finais ditam a estrutura do conjunto de probabilidades estacionárias , que resumem com precisão o comportamento assintótico da cadeia de Markov, como pode ser visto na próxima seção e nos dois exemplos detalhados no final desta página. ${\ displaystyle \ leftarrow.}$

É $M _ {{ij}} = \ left \ {n \ geq 1 \ | \ p _ {{i, j}} ^ {{(n)}}> 0 \ right \}.$

O período de um estado é o GCD do conjunto.Se dois estados se comunicam, eles têm o mesmo período: podemos, portanto, falar do período de uma classe de estados. Se o período for 1, a aula é considerada aperiódica . A aperiodicidade dos estados de uma cadeia de Markov condiciona a convergência da lei de para a probabilidade estacionária, consulte a página Probabilidade estacionária de uma cadeia de Markov . $eu$ ${\ displaystyle M_ {ii}.}$ $X_ {n}$

A classificação dos estados e seu período podem ser facilmente lidos no gráfico da cadeia de Markov . No entanto, se todos os elementos da matriz de transição são estritamente positivos, a cadeia de Markov é irredutível e aperiódica: desenhar o gráfico da cadeia de Markov é então supérfluo.

Lei estacionária

Definição

Pode haver uma ou mais medidas no espaço de estado , como: ${\ displaystyle \ pi = (\ pi _ {i}) _ {i \ in E},}$ ${\ displaystyle E,}$ $\ pi = \ pi \, P,$ ou mesmo $\ forall j \ in E, \ qquad \ pi _ {j} = \ sum _ {{i \ in E}} \ pi _ {i} \, p _ {{i, j}}.$

Essa medição é chamada de medição estacionária . Uma medida estacionária é uma autofunção da transposta da matriz de transição, associada ao autovalor 1. É chamada de probabilidade estacionária ou lei estacionária se cumprir as condições adicionais: $\ pi$

$\ forall i \ in E, \ qquad \ pi _ {i} \ \ geq \ 0,$
$\ sum _ {{i \ in E}} \ pi _ {i} \ = \ 1.$

O termo " estacionário " justifica-se pela seguinte proposição:

Proposição - Se a lei inicial da cadeia de Markov (ou seja, a lei de ) é uma probabilidade estacionária, então para toda a lei de ainda é $X_ {0}$ ${\ displaystyle \ pi,}$ ${\ displaystyle n \ geq 0,}$ $X_ {n}$ ${\ displaystyle \ pi.}$

Demonstração

Isso segue das propriedades das potências da matriz de transição dadas acima: a lei μ n de X n é expressa como uma função da lei μ 0 de X 0 como segue: ou implica ${\ displaystyle \ mu _ {n} = \ mu _ {0} P ^ {n} = \ pi P ^ {n},}$ ${\ displaystyle \ pi P = \ pi}$ ${\ displaystyle \ pi P ^ {n} = \ pi. \}$

De maneira mais geral, a cadeia de Markov é um processo estacionário se e somente se sua lei inicial for uma probabilidade estacionária .

Existência e singularidade

No caso de cadeias de Markov de espaço de estado discreto, certas propriedades do processo determinam se há ou não uma probabilidade estacionária, e se ela é única ou não:

uma cadeia de Markov é irredutível se qualquer estado for acessível a partir de qualquer outro estado;
um estado é positivo recorrente se a expectativa do tempo de primeiro retorno a esse estado, a partir desse estado, for finita.

Se uma cadeia de Markov tem pelo menos um estado recorrente positivo, então há uma probabilidade estacionária. Se houver uma probabilidade estacionária tal , então o estado é recorrente positivo e vice-versa. $\ pi$ ${\ displaystyle \ pi _ {i}> 0}$ $eu$

Teorema - Se uma cadeia de Markov tem apenas uma classe final, então há no máximo uma probabilidade estacionária. Temos então a equivalência entre as 3 proposições: ${\ displaystyle C,}$

há uma probabilidade estacionária única, observada ${\ displaystyle \ pi,}$
há um estado recorrente positivo,
todos os estados da classe final são recorrentes positivos.

Também temos a equivalência $\ {\ pi _ {i}> 0 \} \ Leftrightarrow \ {i \ in C \} \ Leftrightarrow \ {i {\ text {é positivo recorrente}} \}.$

Este teorema é válido em particular para cadeias de Markov irredutíveis, uma vez que as últimas têm apenas uma classe (que é, portanto, necessariamente uma classe final); as irredutíveis cadeias de Markov verificam em particular ${\ displaystyle C = E.}$

Lei forte de grandes números e ergodicidade

No caso de uma cadeia de Markov positiva irredutível e recorrente, a lei forte dos grandes números está em vigor: a média de uma função nas instâncias da cadeia de Markov é igual à sua média de acordo com sua probabilidade estacionária. Mais precisamente, sob o pressuposto $f$ $\ sum _ {{i \ in E}} | f (i) | \, \ pi _ {i} \ <+ \ infty,$ nós quase com certeza : $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k}) \ = \ \ sum _ {{i \ in E}} f (i) \, \ pi _ {i} \ = \ \ pi f.$

A média do valor das instâncias é, portanto, no longo prazo, igual à expectativa de acordo com a probabilidade estacionária. Em particular, esta equivalência nas médias se aplica se for a função indicadora de um subconjunto do espaço de estado: $f$ $NO$ $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k }) \ = \ \ sum _ {{i \ in A}} \ \ pi _ {i} \ = \ \ pi (A).$

Isso torna possível aproximar a probabilidade estacionária pela distribuição empírica (que é um histograma construído a partir de uma determinada sequência), como no caso do passeio aleatório com barreira .

Em particular, se o processo é construído tomando a probabilidade estacionária como a lei inicial, a mudança definida por $\ theta$ $x = (x_ {0}, x_ {1}, x_ {2}, \ pontos) \ in E ^ {{{\ mathbb {N}}}} \ quad \ rightarrow \ quad \ theta \, x = (x_ {1}, x_ {2}, x_ {3}, \ pontos)$ preserva a medida, o que torna a cadeia de Markov um sistema dinâmico medido . A forte lei dos grandes números faz com que a cadeia de Markov seja um sistema ergódico dinâmico . A ergodicidade é mais forte do que a lei forte dos grandes números porque podemos deduzir, por exemplo, que tem um limite quase certo, mas também é mais fraca porque, em princípio, requer a estacionariedade da cadeia de Markov, o que não é o caso com o forte lei dos grandes números. ${\ displaystyle {\ frac {1} {n}} \; \ sum _ {k = 0} ^ {n-1} f (X_ {k}, X_ {k + 1}),}$ ${\ displaystyle \ sum _ {i, j \ in E} f (i, j) \, \ pi _ {i} p_ {i, j},}$

Convergência para a lei estacionária

Se a cadeia de Markov for irredutível , recorrente positiva e aperiódica, então converge para uma matriz em que cada linha é a distribuição estacionária única. Em particular, a lei de converge para independentemente da lei inicial. No caso de um espaço de estado acabado, isso é provado pelo teorema de Perron-Frobenius . Note que é natural que a sequência definida por indução pela relação tenha, possivelmente, por limite um ponto fixo desta transformação, ou seja, uma solução da equação ${\ displaystyle P ^ {k}}$ ${\ displaystyle \ pi.}$ $\ mu _ {n}$ $X_ {n}$ $\ pi$ ${\ displaystyle \ mu _ {0}.}$ ${\ displaystyle \ mu _ {n},}$ ${\ displaystyle \ mu _ {n + 1} = \ mu _ {n} P,}$ ${\ displaystyle \ pi = \ pi P.}$

Cadeias de Markov no espaço de estados finitos

Se uma cadeia de Markov for irredutível e seu espaço de estados for finito, todos os seus estados são recorrentes positivos. A forte lei dos grandes números entra então em vigor.

De maneira mais geral, todos os elementos de uma classe final finita são recorrentes positivos, seja o espaço de estados finito ou contável infinito.

Distribuições quase estacionárias de uma cadeia de Markov absorvida

Let Ser uma cadeia de Markov sobre o conjunto de números naturais . Suponha que o estado 0 seja absorvente e a cadeia seja absorvida em 0 quase com certeza. Seja o tempo de absorção em 0. Dizemos que uma probabilidade em é uma distribuição quase estacionária se para todos e para todos , $(X_ {n})$ ${\ displaystyle \ {0,1,2, ... \}}$ ${\ displaystyle T_ {0} = \ inf \ {n \ geq 0, X_ {n} = 0 \}}$ $\nu$ ${\ displaystyle \ {1,2,3, ... \}}$ ${\ displaystyle j \ geq 1}$ $n \ geq 1$

{\ displaystyle \ sum _ {i \ geq 1} \ nu _ {i} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ nu _ { j}.}

Dizemos que uma probabilidade em é um limite de Yaglom se para tudo e todos , $\ mu$ ${\ displaystyle \ {1,2,3, ... \}}$ $i \ geq 1$ ${\ displaystyle j \ geq 1}$

{\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ mu _ {j}.}

Um limite de Yaglom é uma distribuição quase estacionária . Se existir, o limite de Yaglom é único. Por outro lado, pode haver várias distribuições quase estacionárias.

Se for uma distribuição quase estacionária, então existe um número real como esse . $\nu$ ${\ displaystyle \ rho (\ nu) \ in] 0,1 [}$ ${\ displaystyle \ sum _ {i} \ nu _ {i} \ mathbb {P} (T_ {0}> n | X_ {0} = i) = \ rho (\ nu) ^ {n}}$

Avaliação

Nas fórmulas acima, o elemento ( ) é a probabilidade da transição de para . A soma dos elementos de uma linha é sempre igual a 1 e a distribuição estacionária é dada pelo autovetor esquerdo da matriz de transição. $eu j$ $eu$ $j$

Às vezes, encontramos matrizes de transição nas quais o termo ( ) é a probabilidade de transição de para , caso em que a matriz de transição é simplesmente a transposição daquela descrita aqui. A soma dos elementos de uma coluna vale então 1. Além disso, a distribuição estacionária do sistema é dada pelo autovetor direito da matriz de transição, em vez do autovetor esquerdo. $eu j$ $j$ $eu$

Exemplo: Doudou, o hamster

O hamster Doudou conhece apenas três lugares em sua gaiola: as aparas onde dorme, o comedouro onde se alimenta e a roda onde se exercita. Seus dias são bastante semelhantes e sua atividade é facilmente representada por uma cadeia de Markov. A cada minuto, ele pode mudar sua atividade ou continuar a que estava fazendo. O nome processo sem memória não é exagerado para falar de Doudou.

Quando ele dorme, ele tem 9 em 10 chances de não acordar no minuto seguinte.
Quando ele acorda, há uma chance de 1 em 2 de que ele vá comer e uma chance de 1 em 2 de que ele vá se exercitar.
A refeição dura apenas um minuto, depois do qual ele faz outra coisa.
Depois de comer, há 3 chances em 10 de ele correr na roda, mas especialmente 7 em 10 de que ele volte a dormir.
Correr é cansativo para Doudou; há uma chance de 8 em 10 de que ele volte a dormir após um minuto. Caso contrário, ele continua esquecendo que já está um pouco cansado.

Diagramas

Os gráficos podem mostrar todas as setas, cada uma representando uma probabilidade de transição. No entanto, é mais legível se:

não desenhamos as setas de probabilidade zero (transição impossível);
não desenhamos os laços (seta de um estado em sua direção) . No entanto, eles existem; sua probabilidade está implícita porque sabemos que a soma das probabilidades das setas saindo de cada estado deve ser igual a 1.

Exemplo com loops implícitos
Exemplo com loops desenhados

Matriz de transição

A matriz de transição deste sistema é a seguinte (as linhas e colunas correspondem em ordem aos estados representados no chip , alimentador , gráfico de roda ): $P = {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}}$

Previsões

Suponhamos que Doudou durma durante o primeiro minuto do estudo. ${\ mathbf {x}} ^ {{(0)}} = {\ begin {bmatrix} 1 e 0 & 0 \ end {bmatrix}}$

Depois de um minuto, podemos prever: ${\ mathbf {x}} ^ {{(1)}} = {\ mathbf {x}} ^ {{(0)}} P = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}} = {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \ end {bmatrix} }$

Assim, após um minuto, há 90% de chance de Doudou ainda estar dormindo, 5% de comer e 5% de correr.

${\ mathbf {x}} ^ {{(2)}} = {\ mathbf {x}} ^ {{(1)}} P = {\ mathbf {x}} ^ {{(0)}} P ^ {2} = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatriz}} ^ {2} = {\ begin {bmatrix} 0,885 e 0,045 e 0,07 \ end {bmatrix}}$

Após 2 minutos, há 4,5% de chance de o hamster comer.

De um modo geral, por minutos: $não$ ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(n-1)}} P$ e ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(0)}} P ^ {n}$

A teoria mostra que depois de certo tempo, a lei da probabilidade é independente da lei inicial. Vamos observá-lo : $q$ ${\ mathbf {q}} = \ lim _ {{n \ to \ infty}} {\ mathbf {x}} ^ {{(n)}}$

Obtemos convergência se e somente se a cadeia é aperiódica e irredutível . Este é o caso em nosso exemplo, então podemos escrever: ${\ begin {alinhado} P & = {\ begin {bmatriz} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatriz}} \\ {\ mathbf {q} } P & = {\ mathbf {q}} \ qquad {\ mbox {(}} {\ mathbf {q}} {\ mbox {é a lei invariante em relação a}} P {\ mbox {.)}} \ \ & = {\ mathbf {q}} I \\ {\ mathbf {q}} (IP) & = {\ mathbf {0}} \\ & = {\ mathbf {q}} \ left ({\ begin { bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\\ end {bmatrix}} - {\ begin {bmatrix} 0,9 e 0,05 e 0,05 \\ 0,7 & 0 & 0,3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}} \ right) \\ & = {\ mathbf {q}} {\ begin {bmatrix} 0.1 & -0.05 & -0.05 \\ - 0.7 & 1 & -0.3 \ \ - 0.8 & 0 & 0, 8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} {\ begin {bmatrix} 0,1 & -0, 05 & -0,05 \\ - 0,7 & 1 & -0,3 \\ - 0,8 & 0 & 0,8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} 0 & 0 & 0 \ end {bmatrix}} \ end {alinhado}}$

Sabendo disso , obtemos: $q_ {1} + q_ {2} + q_ {3} = 1$ ${\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} = {\ begin {bmatrix} 0,884 & 0,0442 & 0,0718 \ end {bmatrix}}$

Doudou, portanto, passa 88,4% do tempo dormindo, 4,42% comendo e 7,18% correndo.

Ilustração do impacto do modelo

O exemplo a seguir tem como objetivo mostrar a importância da modelagem do sistema. Uma boa modelagem torna possível responder a questões complexas com cálculos simples.

Estudamos uma civilização (fictícia) composta por várias classes sociais e na qual os indivíduos podem passar de uma classe para outra. Cada etapa representará um ano. Consideraremos uma linhagem em vez de um indivíduo, para evitar a obtenção de cidadãos bicentenários. Existem quatro diferentes status sociais:

escravo ;
gratuitamente;
cidadão;
alto funcionário.

Nesta empresa:

escravos podem permanecer escravos ou tornar-se homens livres (comprando sua liberdade ou sendo liberados liberalmente por seu senhor);
homens livres podem permanecer livres ou então vender sua liberdade (para pagar suas dívidas, etc.) ou mesmo se tornarem cidadãos (novamente por mérito ou comprando o título de cidadão);
os cidadãos são cidadãos para toda a vida e transmitem a sua cidadania à sua linhagem (pode-se acreditar que o número de cidadãos tende a aumentar e que depois de um certo tempo, todos são cidadãos mas historicamente, nas civilizações que seguiram este padrão, os cidadãos são dizimados por as guerras e novos escravos chegam regularmente do exterior). Eles também podem ser candidatos em eleições anuais para se tornarem altos funcionários (magistrados). No final do seu mandato, podem ser reeleitos ou tornar-se novamente cidadãos comuns.

Para complicar um pouco o exemplo e assim mostrar a extensão das aplicações das cadeias de Markov, consideraremos que os servidores públicos são eleitos por vários anos. Portanto, o futuro de um funcionário público depende de quanto tempo ele é funcionário público. Estamos, portanto, no caso de uma cadeia de Markov não homogênea. Felizmente, podemos facilmente voltar a uma cadeia homogênea. Na verdade, é suficiente adicionar um estado artificial para cada ano de mandato. Em vez de ter um estado 4: Oficial , teremos um estado:

4: Funcionário público no início do mandato;
5: Funcionário público no segundo ano de mandato;
etc.

As probabilidades que conectam dois estados artificiais consecutivos (terceiro e quarto ano, por exemplo) são de valor 1 porque consideramos que qualquer mandato iniciado termina (poderíamos modelar o oposto mudando o valor dessas probabilidades). Fixemos a duração dos mandatos em dois anos, sendo o contingente de funcionários renováveis por meio de cada ano. Temos então o seguinte gráfico:

Para modelar eleições não anuais, também seria necessário adicionar estados fictícios (ano eleitoral, um ano desde a última eleição, etc.).

A matriz é então escrita: $P$ ${\ mathbf {P}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 \\ {\ frac {2} { 73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac { 1} {13}} & 0 \\ 0 & 0 & 0 & 0 & 1 \ \ 0 & 0 & {\ frac {7} {8}} & {\ frac {1} {8}} & 0 \ end {bmatrix}}$

Conforme explicado acima, forneça as probabilidades de transição em estágios. O mesmo ocorre com a probabilidade de ficar no estado depois de anos para uma linhagem que faz parte da classe social . Para saber o que acontece com um escravo depois de anos, basta escrever: $P ^ {{n}}$ $não$ $p _ {{ij}} ^ {{n}}$ $j$ $não$ $eu$ $não$ ${\ displaystyle {\ begin {bmatrix} 1 & 0 & 0 & 0 & 0 \ end {bmatrix}} \ times \ mathbf {P} ^ {(n)} = {\ begin {bmatrix} p_ {1} ^ { (n)} & p_ {2} ^ {(n)} & p_ {3} ^ {(n)} & p_ {4} ^ {(n)} & p_ {5} ^ {(n)} \ fim {bmatrix}}}$

Onde está a probabilidade de estar na classe social depois de anos sabendo que a linha estudada deixou o estado de escravo? $p_ {i} ^ {{n}}$ $eu$ $não$

Se sabemos os números de cada classe social no ano 0, basta calcular: ${\ frac 1 {\ mathrm {lign {\ agudo} es}}} \ times {\ begin {bmatrix} {\ rm {escravos}} & {\ rm {livre}} & {\ rm {cidadãos}} & {\ rm {{\ agudo e} lus_ {1}}} & {\ rm {{\ agudo e} lus_ {2}}} \ end {bmatrix}} \ times {\ mathbf P} ^ {{n}} = Y$

Obtemos assim a distribuição da população nas diferentes classes sociais (no final dos anos). Multiplicando esse vetor pelo tamanho total da população, obtemos o tamanho de cada classe ao final dos anos. $não$ $Y$ $não$

Coloquemo-nos agora a seguinte questão: "No final dos anos, quantas linhas já terá um alto funcionário terminado o seu mandato?" " $não$

A resposta difere do número de mandatos cumpridos em anos porque existe a possibilidade de ser reeleito. Responder a esta pergunta parece difícil (ainda deve ser possível). Na verdade, basta mudar a modelagem do problema. Então, vamos passar para um novo modelo para responder a essa pergunta. (Por outro lado, não responde às questões anteriores, daí a apresentação dos dois modelos.) $não$

Basta modificar o gráfico da seguinte forma:

Adicionamos um tampo absorvente porque, uma vez que uma linha termina um mandato, ela não é mais levada em consideração.

Se alguns leitores forem críticos, eles podem dizer que o modelo está errado porque as filas com uma autoridade eleita não participam mais das eleições. Não é assim. Na verdade, o número de funcionários eleitos é proporcional ao número de cidadãos. A não reinjeção de ex-altos funcionários entre os candidatos, portanto, não altera a probabilidade de um cidadão ser eleito porque, sendo a população de cidadãos menor, o número de cargos oferecidos também o é. Este modelo permite que você responda com precisão à pergunta feita.

Portanto, temos uma nova matriz de transição: ${\ mathbf {Q}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 & 0 \\ {\ frac {2 } {73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac {1} {13}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \ \ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 e 1 \ end {bmatrix}}$

Fazendo os mesmos cálculos das questões anteriores, obtemos na última linha do vetor de solução a percentagem de linhas que cumpriram pelo menos um mandato ou o número (se multiplicarmos pelo número total da população). Em outras palavras, modelar novamente o problema torna possível responder à questão que parecia tão complicada por um simples cálculo de potências de uma matriz.

Formulários

Um processo de Bernoulli é um exemplo simples de uma cadeia de Markov.
Os sistemas markovianos estão muito presentes na física, principalmente na física estatística . De forma mais geral, a hipótese markoviana é freqüentemente invocada quando as probabilidades são usadas para modelar o estado de um sistema, assumindo, entretanto, que o estado futuro do sistema pode ser deduzido do passado com um histórico bastante baixo.
O famoso artigo de 1948 de Claude Shannon , A Mathematical Theory of Communication , que fundamenta a teoria da informação , começa apresentando o conceito de entropia a partir de uma modelagem de Markov da língua inglesa . Mostra assim o grau de previsibilidade da língua inglesa, fornecido com um modelo simples de ordem 1. Embora simples, tais modelos permitem representar bem as propriedades estatísticas dos sistemas e fazer previsões eficientes sem descrever a estrutura completa dos sistemas.
Na compressão , a modelagem Markoviana permite a realização de técnicas de codificação de entropia muito eficientes, como a codificação aritmética . Muitos algoritmos de reconhecimento de padrões ou de inteligência artificial , como o algoritmo de Viterbi , usado na grande maioria dos sistemas de telefonia móvel para correção de erros, pressupõem um processo Markoviano subjacente.
O índice de popularidade de uma página da web ( PageRank ) usado pelo Google é definido por uma cadeia de Markov. É definido pela probabilidade de estar nesta página de qualquer estado da cadeia de Markov que representa a web. Se for o número de páginas da web conhecidas e uma página tiver links, então sua probabilidade de fazer a transição para uma página vinculada (para a qual aponta) é e para todas as outras (páginas não relacionadas). Observe que temos . O parâmetro é aproximadamente 0,15. $NÃO$ $eu$ $k_ {i}$ $p_ {i} ^ {l} = {\ tfrac {1-q} {k_ {i}}} + {\ tfrac qN}$ $p_ {i} ^ {{nl}} = {\ tfrac qN}$ $k_ {i} p_ {i} ^ {l} + (N-k_ {i}) p_ {i} ^ {{nl}} = 1$ $q$
As cadeias de Markov são uma ferramenta fundamental para modelar processos em teoria e estatística de filas .
Cadeias de Markov são comumente usadas em confiabilidade para cálculos de confiabilidade e disponibilidade de sistemas técnicos , particularmente para modelagem de tipo de falha de sequências de eventos, reparo, alterações de configuração.
As cadeias de Markov são a base dos sistemas Bonus / Malus desenvolvidos por atuários de seguradoras de automóveis (a probabilidade de haver n acidentes no ano t sendo condicionada pelo número de acidentes em t-1)
As cadeias de Markov também são utilizadas em bioinformática para modelar as relações entre símbolos sucessivos de uma mesma sequência (de nucleotídeos, por exemplo), indo além do modelo polinomial. Modelos ocultos de Markov também têm vários usos, como segmentação (definição de limites regionais dentro de sequências de genes ou proteínas com propriedades químicas variáveis), alinhamento múltiplo , previsão de função ou descoberta de genes. (Os modelos ocultos de Markov são mais "flexíveis" do que os definições estritas de tipo códon de início + códons múltiplos + códons de parada e, portanto, são mais adequados para eucariotos (devido à presença de íntrons no genoma destes) ou para a descoberta de pseudogenes).

Notas e referências

Veja também

Bibliografia

Bruno Sericola: Cadeias de Markov - Teoria, algoritmos e aplicações . Hermes / Lavoisier, 2013.
Sylvie Méléard: Modelos aleatórios em ecologia e evolução . Springer, 2016.
Paolo Baldi, Laurent Mazliak, Pierre Priouret, redes Martingales e Markov. Teoria elementar e exercícios corrigidos , ( ISBN 2-7056-6425-4 ) , Hermann (edições) , 2001

links externos

Philippe Gay, " Markov and Sleeping Beauty " , em Images des Maths ,5 de setembro de 2014
(en) [PDF] Charles M. Grinstead e J. Laurie Snell, cap. “ Cadeias de Markov ”, em Introdução à probabilidade , AMS
(pt) Markov Chain Marvelous
Exercícios corrigidos ( wims da Universidade de Nice Sophia Antipolis )

Cadeia de Markov

Propriedade de Markov fraca

Definições

Critério

Probabilidades de transição

Definição

Propriedades

Poderes da matriz de transição

Classificação dos estados

Lei estacionária

Definição

Existência e singularidade

Lei forte de grandes números e ergodicidade

Convergência para a lei estacionária

Cadeias de Markov no espaço de estados finitos

Distribuições quase estacionárias de uma cadeia de Markov absorvida

Avaliação

Exemplo: Doudou, o hamster

Diagramas

Matriz de transição

Previsões

Ilustração do impacto do modelo

Formulários

Notas e referências

Veja também

Artigos relacionados

Bibliografia

links externos