Cadeias de Markov

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Broom icon.svg
As referências deste artigo necessitam de formatação (desde fevereiro de 2014). Por favor, utilize fontes apropriadas contendo referência ao título, autor, data e fonte de publicação do trabalho para que o artigo permaneça verificável no futuro.
Cadeia de Markov simples.

Em matemática, a cadeia de Markov é um caso particular de processo estocástico com estados discretos (o parâmetro, em geral o tempo, pode ser discreto ou contínuo) e apresenta a propriedade Markoviana, chamada assim em homenagem ao matemático Andrei Andreyevich Markov. A definição desta 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.

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:

 \Pr(X_{n+1}=x|X_0, X_1, X_2, \ldots, X_n) = \Pr(X_{n+1}=x|X_n), \,

onde x é algum estado do processo. A identidade acima define a propriedade de Markov.

Uma maneira simples de visualizar um tipo específico de cadeia de Markov é através de uma máquina de estados finitos. Se você está no estado y no tempo n, então a probabilidade de que você se mova para o estado x no tempo n + 1 não depende de n, e somente depende do estado atual y em que você está. Assim em qualquer tempo n, uma cadeia de Markov finita pode ser caracterizada por uma matriz de probabilidades cujo elemento (x, y) é dado por  \Pr(X_{n+1}=x|X_n=y) \, e é independente do tempo n. Estes tipos de cadeia de Markov finitas e discretas podem também ser descritas por meio de um grafo dirigido (orientado), onde cada aresta é rotulada com as probabilidades de transição de um estado a outro sendo estes estados representados como os nós conectados pelas arestas.

Andrei Markov obteve os primeiros resultados para estes processos em 1906. Uma generalização para espaços de estados infinitos contáveis foi dada por Kolmogorov em 1936. Cadeias de Markov estão relacionadas ao movimento Browniano e à hipótese de ergodicidade, dois importantes tópicos da física nos primeiros anos do século XX, mas a motivação de Markov para o desenvolvimento da teoria parece ter sido estender a teoria dos números grandes para eventos dependentes.

Caracterização de um processo de Markov[editar | editar código-fonte]

Um processo de Markov é um processo estocástico em que a 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 [1] Os principais elementos de um processo de Markov são dois[1]  :

  • a probabilidade xi(n) de ocorrer o estado i no n-ésimo período de tempo, ou, alternativamente, a fração da população em questão que está no estado i no n-ésimo período de tempo
  • as probabilidades de transição mij, que representam as probabilidades de o processo estar no estado "i" no tempo (n+1) dado que está no estado "j" no tempo n. Estas probabilidades de transição são normalmente agrupadas numa matriz, que denominamos matriz de transição, matriz estocástica ou ainda matriz de Markov.

Cadeias de Markov em espaços de estados discretos[editar | editar código-fonte]

Um espaço de estados é representável por uma matriz. Chamada de matriz de transição, com o (i, j)-ésimo elemento igual a

P_{ij} = \Pr(X_{n+1}=j\mid X_n=i) \,

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 \pi é o vetor que satisfaz a equação:

 \pi^{T}\mathbf{P} = \pi^{T},

onde \pi^{T} é o vetor transposto de \pi. Em outras palavras, a distribuição estacionária \pi é o autovetor (vetor próprio) esquerdo da matriz de transição, associado com o autovalor (valor próprio) 1.

Como consequência, nem a existência nem a unicidade de distribuição estacionária é garantida para uma matriz de transição qualquer P. Contudo, se P é irredutível e aperiódica, então existe uma distribuição estacionária \pi. Além disso, Pk converge para uma matriz na qual cada linha é a (transposta da) distribuição estacionária \pi^T, que é dada por:

\lim_{k\rightarrow\infty}\mathbf{P}^k=\mathbf{1}\pi^T,

onde \mathbf{1} é o vetor coluna com todas as entradas iguais a 1. Isto é estabelecido pelo Teorema de Perron-Frobenius.

Exemplo de cadeia de Markov.

Isto significa que se nós simularmos ou observamos uma caminhada aleatória com matriz de transição P, então a probabilidade de longo prazo de que o indivíduo que faz a caminhada esteja em um certo estado é independente do estado em que essa caminhada começou, e é definida pela distribuição estacionária. A caminhada aleatória "ignora" o passado. Em suma, cadeias de Markov são o passo seguinte depois dos processos sem memória (isto é, uma sequência de variáveis aleatórias independentes distribuídas uniformemente).

Uma matriz de transição que é positiva (isto é, todo o elemento da matriz é positivo) é irredutível e aperiódica. Uma matriz é uma matriz estocástica se e somente se é uma matriz de probabilidades de transição de uma cadeia de Markov.

Um caso especial de probabilidade de transição independente do passado é conhecido como o esquema de Bernoulli. Um esquema de Bernoulli com somente dois estados possíveis é conhecido como um processo de Bernoulli.

Exemplo[editar | editar código-fonte]

Imagine um país onde só seja possível estar em três classes sociais, denominadas estados: A, B ou C. Em cada período de tempo, a probabilidade de uma pessoa mudar de um estado para outro é constante no tempo e só depende dos estados. Este processo é chamado de cadeia de Markov.[2]

Referências

  1. a b SIMON, Carl P. e BLUME, Lawrence. Matemática para economistas. Porto Alegre: Bookman, 2004. Reimpressão 2008. ISBN 978-85-363-0307-9. Seção 23.6 - Processos de Markov. Página 617.
  2. SANTOS Reginaldo J.Cadeias de Markov. Departamento de Matemática-ICEx, 22 de março de 2006. Disponível em: <http://www.mat.ufmg.br/~regi/gaalt/markov.pdf>. Aceso em 14 de julho de 2011.
  • A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135–156, 1906.
  • A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reimpresso no Apêndice B de: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
  • Leo Breiman. Probability. Edição original publicada pela Addison-Wesley em 1968; reimpressa pela Society for Industrial and Applied Mathematics em 1992. ISBN 0-89871-296-3. (ver Capítulo 7.)
  • J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.

Ligações externas[editar | editar código-fonte]

  • Um gerador de Letras de Música Markoviano que utiliza letras já existentes para criar aleatoriamente outras. Pode-se utilizar cadeias de várias ordens. O código-fonte em PHP está disponível.
  • Um compressor de textos baseado em cadeias de Markov feito em JavaScript, como trabalho de uma disciplina sobre processos estocásticos da Universidade de São Paulo (USP).
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.