Instituto Tecnológico de Aeronáutica Divisão de Engenharia Mecânica-Aeronáutica

MOQ-12 Cadeias de Markov

Professora: Denise Beatriz T. P. do Areal Ferrari [email protected]

Roteiro Introdução Processos Estocásticos Motivação Cadeias de Markov • • • • • • •

Definição Propriedade Markoviana Propriedade de Estacionariedade Matriz de Transição Equação de Chapman-Kolmogorov Vetor de Probabilidades Iniciais Classificação de Estados

Introdução Hipótese de Independência Cadeias de Markov: • podem ser considerados como a generalização mais simples do esquema de experimentos independentes.

Esses processos são o ponto inicial para o desenvolvimento de um novo e importante ramo da Teoria das Probabilidades: Teoria dos Processos Estocásticos.

Processos Estocásticos Funções Aleatórias • Intervalo de tempo: série temporal Exemplos: • flutuações de câmbio; • sinais (fala, áudio e vídeo); • dados médicos (eletrocardiograma, pressão sangüínea e temperatura); • movimentos aleatórios (Movimento Browniano e Passeio Aleatório)

• Região do espaço: campo aleatório Exemplos: • imagens estáticas; • topografias aleatórias (satélite); • variações de composição em um material não homogêneo.

Motivação (1) Problema em estudo: Estamos medindo a temperatura do ambiente externo a cada hora, durante um dia. Temperatura fl fenômeno aleatório. (resulta de uma conjuminação de fatores meteorológicos que não podem ser determinados com exatidão)

Motivação (2) Para medir esta temperatura, usamos um termômetro que mede desde 0°C até 50°C, com divisões de 10°C. • temos um conjunto finito de resultados ou estados possíveis: 0°C, 10°C, 20°C, 30°C, 40°C e 50°C.

Sejam: X1 = temperatura medida no início do período (primeira observação) X2 = temperatura medida na segunda observação (1 hora depois de X1) Xn = temperatura medida no n-ésimo período observado, n = 1,2,... A seqüência X1, X2,..., X24 é um exemplo de Processo Estocástico.

Motivação (3) A seqüência X1, X2,..., X24 é um exemplo de Processo Estocástico.

Processo estocástico de parâmetro discreto: instantes pontuais de tempo (intervalos a cada hora) X1 = estado inicial do processo Xn = estado do processo no instante n. Processo estocástico de parâmetro contínuo: Se estivéssemos monitorando a temperatura continuamente.

Motivação (4) Espaço de estados (E): Xn œ E • Discreto: E = {x œ | x≥0°C} = {0°C, 10°C, 20°C, 30°C, ... } O termômetro utilizado pode medir apenas um número definido de temperaturas (variações de 10°C). • Contínuo: E = {x œ | x ≥ 0°C} O termômetro utilizado pode medir qualquer temperatura.

Cadeias de Markov É um tipo especial de processo estocástico, que satisfaz as seguintes condições: • o parâmetro n é discreto (ex: tempo) • o espaço de estados E é discreto (coleção de estados possíveis) E pode ser finito ou infinito e enumerável. Vamos considerar E finito. As cadeias de Markov deste tipo são chamadas Cadeias de Markov Finitas.

• o estado inicial do processo ou o espaço de estados é conhecido. • vale a propriedade markoviana • vale a propriedade de estacionariedade

Propriedade Markoviana Para n = 1,2,..., e qualquer seqüência de estados possíveis s1, s2,...,sn+1, com Xn, Xn-1,..., X1 conhecidos:

P ( X n +1 = sn +1 | X 1 = s1 , X 2 = s2 ,..., X n = sn ) = = P( X n +1 = sn +1 | X n = sn ) Em palavras: As probabilidades de todos os estados futuros Xj (j>n) dependem somente do estado atual Xn, mas não dependem dos estados anteriores X1,..., Xn-1. O estado “futuro” do sistema depende do “presente”, mas não depende do “passado”.

Propriedade de Estacionariedade P(Xn+1=sj|Xn=si) = pij P(Xn+1=si|Xn=si) = pii

si

sj

Probabilidades de transição: P(Xn+1=sj|Xn=si) Probabilidades de transição estacionárias: P( X n +1 = s j | X n = si ) = cte. = pij

n = 1,2,...

A cadeia de Markov é dita homogênea ou estacionária.

Matriz de Transição Cadeia de Markov Finita e Estacionária k possíveis estados: s1, s2,...,sk

s1 s1 ⎡ p11 P = s2 ⎢⎢ p21 s3 ⎢⎣ p31

s2

s3

p12 p22 p32

p13 ⎤ p23 ⎥⎥ p33 ⎥⎦

pij ≥ 0 k

∑ pij = 1, j =1

i = 1,...k

Exemplo Suponha que na Terra de Oz, nunca há dois dias ensolarados consecutivos. • Se em um dia qualquer faz sol, no dia seguinte pode tanto nevar quanto chover. • Se chover, metade das vezes continua chovendo no dia seguinte e nas outras ocasiões pode tanto fazer sol ou nevar. • Se nevar, apenas metade das vezes o dia seguinte também neva.

Queremos: Representar graficamente a Cadeia de Markov Construir sua matriz de transição Determinar a probabilidade de nevar daqui a dois dias?

Equação de Chapman-Kolmogorov Sejam: • P a matriz de transição de uma cadeia de Markov. • O elemento pij(n) da matriz P(n) representa a probabilidade de que o processo, iniciado no estado si, estará no estado sj, depois de n passos. • u um instante qualquer entre 0 e n. k

pij( n ) = ∑ pir(u ) . prj( n −u ) ,

0