cadeias de markov

cadeias de markov

(Parte 1 de 3)

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 1

Cadeias de Markov

1. Introdução

Nestas notas de aula serão tratados modelos de probabilidade para processos que evoluem no tempo de maneira probabilística. Tais processos são denominados Processos Estocásticos.

1.2. Processos Estocásticos

Um Processo Estocástico é definido como uma coleção de variáveis randômicas

(X(t)) indexadas por um parâmetro t pertencente a um conjunto T. Freqüentemente T é tomado para ser o conjunto dos inteiros não-negativos (porém, outros conjuntos são perfeitamente possíveis) e X(t) representa uma característica mensurável de interesse no tempo t. Exemplificando, X(t) pode representar o nível de estoque de um produto no fim da semana t.

Processos Estocásticos são de interesse para descrever o procedimento de um sistema operando sobre algum período de tempo, com isso, em termos formais, a variável randômica X(t) representa o estado do sistema no parâmetro (geralmente tempo) t. Portanto, pode-se afirmar que X(t) é definido em um espaço denominado Espaço de Estados. Os Processos Estocásticos podem ser classificados como:

a) Em relação ao Estado ¾ Estado Discreto (cadeia): X(t) é definido sobre um conjunto enumerável ou finito.

¾ Estado Contínuo (seqüência): X(t) caso contrário.

b) Em relação ao Tempo (Parâmetro) ¾ Tempo Discreto: t é finito ou enumerável.

¾ Tempo Contínuo: t caso contrário.

Exemplos: 1. Número de usuários em uma fila de banco em um determinado instante: Estado

Discreto e Tempo Contínuo. 2. Índice pluviométrico diário: Estado Contínuo e Tempo Discreto. 3. Número de dias chuvosos: Estado Discreto e Tempo Discreto.

Existem vários "tipos" de Processos Estocásticos, porém, nestas notas de aula será apenas abordado um tipo de Processo Estocástico denominado Processo Markoviano.

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 2

Andrei Andreyevich Markov (*1856, Ryazan, Russia; 1922, São Petersburgo, Russia).

2. Processos Markovianos Um Processo Estocástico é dito ser um Processo Markoviano se:

A expressão (1) pode ser "traduzida" por: a probabilidade condicional de qualquer evento futuro, dado qualquer evento passado e o estado presente X(tk) = xk, é independente do evento passado e depende somente do estado presente.

Em termos mais resumidos: um Processo Estocástico é dito ser um Processo

Markoviano se o estado futuro depende apenas do estado presente e não dos estados passados.

Este tipo de Processo Estocástico é também denominado de memoryless process (processo sem memória), uma vez que o passado é "esquecido" (desprezado).

As probabilidades condicionais {}kk1k1kx)t(Xx)t(XP==++ são denominadas

Probabilidades de Transição e representam, portanto, a probabilidade do estado )t(X1k+ ser 1kx+ no instante tk+1 dado que o estado )t(Xk é kx no instante tk. Sem demais formalismo, segue-se o exemplo seguinte:

Exemplo A

O estado no ano de 1993 do uso da terra em uma cidade de 50 quilômetros quadrados de área é:

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 3

Iuso residencial 30%
Iuso comercial 20%
Iuso industrial 50%

Tabela 1 - Estado do uso da terra em 1993.

Os valores da tabela 1 podem ser dispostos em um vetor x, denominado Vetor de Estados:

As probabilidades de cada Estado (probabilidade não-condicional) podem também ser dispostos em um vetor π, denominado Vetor de Probabilidade de Estado (para distingui-las das probabilidades de transição):

Assumindo que as probabilidades de transição para intervalos de 5 anos são dadas pela seguinte tabela: Tabela 2 - Probabilidades de Transição para Ipara IIpara I de I0.8 0.1 0.1 de II0.1 0.7 0.2 de III0 0.1 0.9

As probabilidades condicionais na tabela 2, em termos informais, podem ser entendidas como:

¾ de I para I ⇒ a probabilidade do estado ser I após 5 anos, dado que o estado atual (presente) é I é 0.8, ou {}8.0I)t(XI)5t(XP===+. Para t =1993,

¾ de I para I ⇒ a probabilidade do estado ser I após 5 anos, dado que o

¾ de I para I ⇒ a probabilidade do estado ser I após 5 anos, dado que o estado atual (presente) é I é 0.1, ou {}1.0I)t(XIII)5t(XP===+. Para t =1993,

¾ de I para I ⇒ a probabilidade do estado ser I após 5 anos, dado que o estado atual (presente) é I é 0.1, ou {}1.0I)t(XI)5t(XP===+. Para t =1993,

¾ de I para I ⇒ a probabilidade do estado ser I após 5 anos, dado que o estado atual (presente) é I é 0.7, ou {}7.0I)t(XI)5t(XP===+. Para t =1993,

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 4

Os valores da tabela 2 podem ser então dispostos em uma matriz P, denominada Matriz de Transição:

Assim, a partir de P e o vetor de probabilidade de estado π para 1993, denominado π(0) , pode-se calcular o vetor de probabilidade de estado π para 1998, denominado π(1) :

2.1 Cadeias de Markov

Um Processo Markoviano é dito ser uma Cadeia de Markov quando as variáveis randômicas X(t) estão definidas em um espaço de estados discreto E. O exemplo dado acima é então uma Cadeia de Markov porque o espaço de estados é discreto.

Quando o tempo é discreto, a Cadeia de Markov é dita ser uma Cadeia de Markov em Tempo Discreto. Neste caso, tem-se:

As Probabilidades de Transição {}k1kx)k(Xx)1k(XP==++ representam, portanto, a probabilidade do estado )1k(X+ ser 1kx+ no tempo k + 1 dado que o estado )k(X é kx no tempo k.

Se para cada xk+1 e xk, tem-se:

então, as Probabilidades de Transição são ditas Estacionárias. Assim, tendo-se Probabilidades de Transição Estacionárias implica que as Probabilidades de Transição não mudam em relação ao tempo. Ainda, de acordo com a expressão (7), as Probabilidades de Transição são denominadas Probabilidades de Transição de Passo 1. A existência de Probabilidades de Transição Estacionárias de Passo 1 implica que para cada xk+n e xk e n (n = 0, 1, 2,...), tem-se:

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 5

Estas probabilidades condicionais são chamadas Probabilidades de Transição de Passo n.

Para simplificação da notação, adotando xk+1 ou xk+n de j e xk de i, pode-se definir:

Porque )n(ijp são probabilidades condicionais, estas precisam ser não negativas e desde que o processo precisa realizar uma transição em algum estado, estas precisam satisfazer as seguintes propriedades:

Uma maneira conveniente de mostrar todas as Probabilidades de Transição de Passo n é:

Estado0 1M
0 )n(00p)n(01p)n(
1 )n(10p)n(11p)n(
1Mp)n(MMp

0Mp )n( ou, equivalentemente, por uma matriz P(n):

nMMn 1Mn 0M

p...p p...p p...p

A matriz P(n) é denominada Matriz de Transição de Passo n. Quando n = 1, a matriz é denominada apenas Matriz de Transição, como exemplificado na expressão (4).

As Cadeias de Markov, consideradas nestas notas de aula possuem as seguintes propriedades:

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 6

1. Um número finito de estados. 2. Probabilidades de Transição Estacionárias.

Ainda será assumido como conhecido o vetor de probabilidade de estado inicial π(0) (vetor composto por P{X0 = i} para todo i).

Exemplo B

comprada semanalmente do fornecedor. D1, D2,, representa a demanda para esta câmera

Uma loja de câmeras fotográficas armazena um modelo de câmera que pode ser (o número de unidades que deveriam ser vendidas se o estoque não é esgotado) durante a

semana 1, semana 2,, respectivamente. É assumido que Di são variáveis randômicas

independentes e identicamente distribuídas (i.i.d∗) tendo uma distribuição de Poisson com média igual a 1. Dado X0 representar o número de câmeras inicialmente, X1 o número de câmeras no fim da semana 1, X2 o número de câmeras no fim da semana 2 e assim por diante. Assume-se que X0 = 3. No sábado a noite a loja faz o pedido de câmeras para o fornecedor, o qual realizará a entrega apenas na próxima segunda-feira. A loja utiliza a seguinte política de compra: se não há câmeras no estoque, a loja compra 3 câmeras. Entretanto, se há alguma câmera no estoque, nenhuma câmera é comprada. Vendas são

perdidas quando a demanda excede o estoque. Assim, {}tX para t = 0, 1, 2,é um

Processo Estocástico. Os Estados possíveis do processo são os inteiros 0, 1, 2, 3, representando o número de câmeras no fim da semana t, ou seja, o espaço de estados, para este exemplo é {}3210E=. As variáveis randômicas Xt são dependentes e podem ser avaliadas iterativamente pela expressão:

t1tt

1tpara t = 0, 1, 2, . . .

A expressão (14) é o processo estocástico (o qual foi modelado a partir do enunciado). Ainda faz-se necessário definir a matriz de transição P, porém, primeiramente, a título de revisão segue:

∗ Duas variáveis aleatórias são independentes se ()()()()()BP.APBP.BAPBAP==∩. Duas variáveis aleatórias são identicamente distribuídas se possuem a mesma distribuição de probabilidade.

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 7

Distribuição de Poisson

Siméon Denis Poisson (*1781 Pithiviers, França; 1840, Sceaux, França).

A distribuição de Poisson é uma distribuição discreta empregada em situações probabilísticas onde a área de oportunidade de ocorrência de um evento é grande, mas a oportunidade de ocorrência em um intervalo particular (ou em um ponto) é muito pequena. Exemplo: ¾ Número de defeitos ao longo de um fio de uma linha de transmissão de energia.

¾ Erros de datilografia em um livro.

¾ Acidentes industriais.

¾ Chegadas em modelos de fila de espera.

Matematicamente: A probabilidade de exatamente r ocorrências de um evento é:

rλ−λ=

erP (15) onde: λ é a média da distribuição A variância de P(r) é λ também.

Exemplo:

O número médio de defeitos em laminas de vidro é 5. A probabilidade que a lamina tenha 6 defeitos é:

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 8

Retomando o exemplo do estoque da loja de câmeras, dado que o estado corrente

Xt= i, o processo só depende de Dt+1 (veja expressão (14)). Uma vez que Xt+1 é independente do passado, este processo é um processo Markoviano. Considerando ainda que o espaço de estado é discreto, este processo Markoviano é uma Cadeia de Markov.

Uma vez que Dt+1 tem distribuição de Poisson com média λ = 1 pode-se calcular:

+==, para n = 0, 1,

Atribuindo valores para n, onde n representa o número de câmeras necessárias para repor o estoque na próxima semana, fica:

De posse das probabilidades de Dt+1 para os valores de n e do processo estocástico

(expressão 14), as probabilidades de transição pij (elementos da matriz de transição) podem ser definidas:

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 9

Para as demais pij, o raciocínio é análogo. A matriz de transição P então fica:

Uma maneira alternativa para representar as probabilidades de transição é utilizar uma representação denominada Diagrama de Transição de Estado. Neste os sentidos das flechas indicam a probabilidade de transição de um estado i para um estado j. Para a matriz de transição P dada pela expressão (26) o diagrama fica:

Fig. 1 - Diagrama de Transição de Estado.

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 10

2.2 Equações de Chapman - Kolmogorov

Sidney Chapman∗ (*1888, Eccles, Inglaterra; 1970, Boulder, Estados Unidos).

Andrey Nikolaevich Kolmogorov (*1903, Tambov, Russia; 1987, Moscow, Russia).

passos no tempo, ou seja, de t para t+1, de t para t+2,, de t para t+n.

A matriz de transição P é a matriz de transição de probabilidades de estado para um passo no tempo, ou seja, de t para t+1. Pode se dizer, de maneira simplista, que as equações de Chapman-Kolmogorov fornecem um método para computar a matriz de transição para n

Seja )n(ijp a probabilidade de transição do estado i para o estado j de passo n, pode-se escrever que:

0k mnkjmiknijppp

e qualquer m = 1, 2,, n-1
e qualquer n = m+1, m+2,

M,...,1,0j=∀ Em notação matricial, a expressão (27) fica:

∗ Não é certeza que Sidney Chapman é o "Chapman" das equações de Chapman-Kolmogorov

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 1 onde: P(n) é a matriz de transição de passo n. A partir de (28) pode-se concluir, portanto, que:

A expressão (29) afirma que a matriz de transição de passo n é igual à matriz de transição de passo 1 elevada a n-ésima potência.

Cabe ressaltar neste momento que a expressão (29) só é válida para Cadeias de

Markov cujas probabilidades de transição de estados são constantes em relação ao tempo (Probabilidades de Transição Estacionárias). A este tipo de Cadeia de Markov, denomina-se Cadeia de Markov Homogênea e a matriz de transição P é então uma matriz homogênea.

Retomando o exemplo do estoque da loja de câmeras, a matriz de transição de passo 2 (n = 2), é:

O vetor probabilidade de estado π para o exemplo da câmera no tempo 0 é: []1000)0(=π (31) uma vez que X0 = 3. Para o tempo 1, π(1) pode ser calculado como:

Para o tempo 2, π(2) pode ser calculado como:

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 12

2.3 Classificação de Estados em Cadeias de Markov 2.3.1 Estados Alcançáveis e Comunicantes

Um estado j é dito ser alcançável (accessible) a partir de um estado i se ()0pnij> para algum 0n≥. Isto implica que é possível o sistema entrar no estado j eventualmente quando este começa no estado i.

Exemplo 1: os estados da matriz de transição P(2) na expressão (30).

Exemplo 2: Um jogador tem um $1,0 e a cada vez que joga ganha $1,0 com probabilidade p>0 ou perde $1,0 com probabilidade 1-p. O jogo termina quando o jogador acumula $3,0 ou $0,0. Este jogo é uma Cadeia de Markov cujos estados representam a quantia esperada de dinheiro que o jogador possui a cada vez que joga. O espaço de estados é {}3210E= e a matriz de transição P é dada por:

Estado0 1 2 3

Nesta Cadeia de Markov, o estado 2, por exemplo, não é alcançável a partir do estado 3. Isto pode ser observado a partir do contexto, uma vez que se o jogador alcançar o estado 3, este nunca deixará este estado, o que implica que ()0pn32= para todo 0n≥. Entretanto, o estado 3 é alcançável a partir do estado 2, uma vez que ()0p123>.

Um estado j é dito comunicante com o estado i se o estado j é alcançável a partir do estado i e o estado i é alcançável a partir do estado j.

Exemplo 3: os estados da matriz de transição P(2) na expressão (30). Exemplo 4: estados 2 e 3 do exemplo 2 não são comunicantes.

A seguinte regra pode ser definida a partir das Equações de Chapman-Kolmogorov:

"Se um estado i é comunicante com um estado k e o estado k é comunicante com um estado j, então o estado i é comunicante com o estado j".

Se dois estados se comunicam entre si, diz-se que eles pertencem à mesma classe. Se todos os estados são comunicantes, portanto todos os estados pertencem a uma única classe, a Cadeia de Markov é dita ser Irredutível.

Exemplo 5: A Cadeia de Markov do exemplo do estoque da loja de câmeras.

Modelagem e Simulação - Cadeias de Markov

Notas de Aula - Fernando Nogueira 13

2.3.2 Estados Recorrentes e Transientes

Um estado é dito ser Transiente (Temporário, Efêmero, Transitório) se, entrando neste estado, o processo pode nunca retornar novamente para este estado. Portanto, o estado i é transiente se e somente se existe um estado j ()ij≠ que é alcançável a partir do estado i mas não vice-versa, isto é, o estado i não é alcançável a partir do estado j. Assim, se o estado i é transiente e o processo visita este estado, há uma probabilidade positiva que o processo irá mover-se para o estado j e assim nunca irá retornar para o estado i. Conseqüentemente, um estado transiente será visitado somente um número finito de vezes.

Um estado é dito ser Recorrente se entrando neste estado, o processo definitivamente irá retornar para este estado. Portanto, um estado é recorrente, se e somente se, não é transiente. Uma vez que o estado recorrente será "revisitado" após cada visita (não necessariamente no próximo passo do processo), este será visitado infinitamente para o processo em tempo infinito. Um estado é dito ser Absorvente se entrando neste estado, o processo nunca irá deixar este estado. Portanto, um estado i é absorvente se e somente se pii = 1. Com isso, pode-se afirmar que um estado absorvente é um caso especial de um estado recorrente.

(Parte 1 de 3)

Comentários