Notes

Search

SearchSearch

Cadeia de Markov

Nov 25, 2024, 6 min read

Cadeia de Markov

Abstract

Uma cadeia de Markov é um processo estocástico que modela sistemas que evoluem de um estado para outro, de maneira probabilística, dependendo apenas do estado atual e não do caminho percorrido até ele. Esse conceito tem várias aplicações em diversas áreas, como modelagem de sistemas dinâmicos, economia e teoria de filas.

Introdução

Uma cadeia de Markov é um modelo matemático utilizado para descrever sistemas que transitam entre estados de forma probabilística.

A principal característica das cadeias de Markov é que a transição de um estado para outro depende apenas do estado atual, e não dos estados anteriores. Isso significa que o futuro de um processo é independente do passado, dado o presente, o que é conhecido como a propriedade de Markov.

Esse tipo de processo é amplamente utilizado em áreas como economia, biologia, física e ciência da computação, especialmente em algoritmos de aprendizado de máquina.

Definição

Formalmente, uma cadeia de Markov é um processo estocástico que é descrito por um conjunto de estados e uma matriz de probabilidades de transição. Uma cadeia de Markov pode ser definida como:

  1. Um conjunto de estados , que representam as possíveis condições do sistema.
  2. Uma probabilidade de transição entre os estados, que é dada por uma matriz de probabilidades, onde cada entrada representa a probabilidade de transição do estado para o estado .

A principal propriedade de uma cadeia de Markov é a propriedade de Markov, que pode ser expressa da seguinte forma:

Ou seja, a probabilidade de transitar para o estado no próximo passo depende apenas do estado atual e não de como o sistema chegou até esse estado.

Outra forma de representar a a propriedade da Cadeia de Markov é:

O qual representar a probabilidade de transição do estado no tempo ao estado no tempo .

Propriedades

1. Matriz de Transição

A matriz de transição é um componente fundamental da cadeia de Markov. Ela é uma matriz quadrada cujas entradas são as probabilidades de transição entre os estados. Cada elemento representa a probabilidade de transição do estado para o estado .

As probabilidades em cada linha da matriz somam 1:

Isso garante que, a partir de qualquer estado, o sistema deve transitar para algum outro estado (ou o mesmo), com probabilidade total de 1.

2. Propriedade de Markov

A propriedade de Markov é a condição de memória curta do processo. Isto é, o futuro é independente do passado, dado o estado atual.

Isso é útil, pois simplifica o modelo, pois não é necessário levar em conta toda a história do processo, apenas o estado atual.

3. Estados Absorventes e Transientes

  • Um estado absorvente é um estado que, uma vez alcançado, o sistema nunca deixa. Ou seja, a probabilidade de transitar para qualquer outro estado a partir de um estado absorvente é zero.
  • Um estado transiente é um estado que o sistema pode deixar eventualmente.

Exemplo

Exemplo 1: Cadeia de Markov com 2 estados

Vamos considerar um sistema com dois estados, , onde as transições entre os estados são governadas pela seguinte matriz de transição :

Misplaced &0.5 & 0.5 \\ 0.7 & 0.3 \end{bmatrix} $$ Aqui, a probabilidade de transitar de $s_1$ para $s_1$ é 0.5 e de $s_1$ para $s_2$ é 0.5. Da mesma forma, a probabilidade de transitar de $s_2$ para $s_1$ é 0.7 e de $s_2$ para $s_2$ é 0.3. Se o sistema está no estado $s_1$ no tempo $n$, então a probabilidade de estar no estado $s_1$ ou $s_2$ no tempo $n+1$ será dada por: - Para o estado $s_1$: $$ P(X_{n+1} = s_1 | X_n = s_1) = 0.5 \quad \text{e} \quad P(X_{n+1} = s_2 | X_n = s_1) = 0.5 $$ - Para o estado $s_2$: $$ P(X_{n+1} = s_1 | X_n = s_2) = 0.7 \quad \text{e} \quad P(X_{n+1} = s_2 | X_n = s_2) = 0.3 $$ Se o sistema começa em $s_1$, então a distribuição de probabilidade dos estados no próximo passo será: $$ P(X_1 = s_1) = 0.5 \quad \text{e} \quad P(X_1 = s_2) = 0.5 $$ Após várias iterações, a distribuição de probabilidade se estabiliza (dependendo das características da matriz de transição). Esse comportamento de estabilização é uma característica importante em cadeias de Markov, especialmente em processos que envolvem probabilidades de longo prazo. #### Exemplo 2: Cadeia de Markov com estado absorvente Considere uma cadeia de Markov com três estados $S = \{s_1, s_2, s_3\}$ e a seguinte matriz de transição: $$ P = \begin{bmatrix} 0.2 & 0.8 & 0 \\ 0 & 0.4 & 0.6 \\ 0 & 0 & 1 \end{bmatrix} $$ Neste caso, $s_3$ é um **estado absorvente**, pois uma vez que o sistema chega a $s_3$, ele nunca mais sai de $s_3$, pois $P_{33} = 1$ (uma vez no estado $s_3$ a chance de mudar para o estado $s_3$ é de $100\%$). Se o sistema começa no estado $s_1$, a evolução do sistema pode ser modelada pelas probabilidades de transição. Eventualmente, o sistema será absorvido no estado $s_3$. # Referências --- [[Aula 8 - Cadeia de Markov]]

Graph View

Backlinks