Slide - Cadeias de Markov - Modelagem e Simulação de Sistemas de Produção - 2023-2

PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.1 Prof. Dr. Marco A. Mesquita 2. Cadeias de Markov Referências: - Winston, Operations Research, 4.ed., cap.17 - Ross, Intr. Probability Models, 4.ed., cap.4 - https://en.wikipedia.org/wiki/Markov_chain 4 Exemplo de uma Cadeia de Markov  Suponha que, em cada semana, a Bolsa de Valores esteja em um de três estados: (1) em alta, (2) em baixa e (3) estagnada.  Seja pij = Prob (ir para o estado j, dado que na semana anterior está no estado em i), conforme a matriz de probabilidades abaixo. 1. Dado que a bolsa está em alta esta semana, qual é a probabilidade de, em duas semanas, estar estagnada? (14,5%) 2. Em regime estacionário, quanto tempo ela deve permanecer em cada estado? (40%, 40%, 20%)            ,0 50 ,0 30 20 ,0 ,015 ,0 75 10 ,0 ,010 ,010 80 ,0 P PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.2 Prof. Dr. Marco A. Mesquita 5 Random Walk 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 6 Trajetórias possíveis... 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 2 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 3 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 Tempo Trajetória 4 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.3 Prof. Dr. Marco A. Mesquita 7 Definições  Processo Estocástico: sequência de variáveis aleatórias que determinam os estados de um sistema ao longo do tempo.  Exemplos: 1. Estoque de um produto ao final do dia 2. Número de clientes na fila do caixa 3. Volume de um reservatório ao final do mês 4. Cotação de um título na Bolsa de Valores  Os processos podem ser em tempo discreto ({Xn, n=0,1,2…}) ou em tempo contínuo ({X(t), t ≥0})  O espaço amostral, conjunto dos valores possíveis da variável de estado, também pode ser classificado em discreto ou contínuo. 8 Um processo estocástico {Xn, n=0,1,...} é uma Cadeia de Markov em tempo discreto se P(Xn+1 = j | Xn = i, Xn-1 = kn-1, . . . , X0 = k0 ) = P(Xn+1 = j | Xn = i ) para todo i, j, k0, . . . , kn-1 e todo n. Interpretação: os estados futuros dependem exclusivamente do estado atual “i” e independem de quaisquer que tenham sido os estados anteriores. Cadeia de Markov PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.4 Prof. Dr. Marco A. Mesquita 9 P(Xn+1 = j | Xn = i ) = P(X1 = j | X0 = i ) = pij (probabilidades não mudam com o tempo) Probabilidades de Transição Estacionárias Uma Cadeia de Markov é estacionária se, para todo n: Seja P = [ pij ] m x m, a matriz das probabilidades de transição, então: pij  0 e j pij = 1            ,0 50 ,0 30 20 ,0 ,0 15 ,0 75 10 ,0 ,0 10 ,0 10 80 ,0 P Exemplo: 10 Exemplos de Cadeias de Markov 1. Previsão do Tempo 2. Bolsa de Valores 3. Reparo de Máquinas 4. Random Walk 5. Apostador PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.5 Prof. Dr. Marco A. Mesquita 11 Exemplo 1 – Previsão do Tempo Estados: 0 (Chuva) 1 (Sol) 0,7 0,4 1 0 0,3 0,6      6,0 4,0 3,0 7,0 P Matriz das Probabilidades Diagrama de Transição 12 Exemplo 2 – Bolsa de Valores Matriz das Probabilidades            ,0 50 ,0 30 20 ,0 ,015 ,0 75 10 ,0 ,010 ,010 80 ,0 P 0,2 0,1 1 2 0,8 3 0,5 0,1 0,1 0,75 0,3 0,15 Diagrama de Transição Xn = estado onde se encontra (x=1, 2 e 3) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.6 Prof. Dr. Marco A. Mesquita 13 Exemplo 3 – Reparo de Equipamentos Considere uma célula com duas máquinas. Cada máquina, quando começa o dia funcionando, tem 10% de chance de quebrar durante o dia. Uma máquina quebrada, é reparada no dia seguinte, até o final do dia. Seja Xk o número de máquinas quebradas no início do dia k, determine as probabilidades de transição entre os estados. 14 Diagrama e Matriz Transição-Estado P=[ pij ] 3x3 No exemplo             0,0 0,0 0,1 0,0 ,010 90 ,0 ,0 01 ,018 81 ,0 P Diagrama Transição-Estado: Xk = qtd de máquinas quebradas no início do dia k Matriz Transição-Estado 1,0 0,18 0,81 0,1 0,9 0,01 0 1 2 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.7 Prof. Dr. Marco A. Mesquita 15 Exemplo 4 – Random Walk            0 1 0 5,0 0 5,0 0 1 0 P 0 +1 -1 0,5 1 1 0,5 Matriz das Probabilidades Diagrama de Transição Caso geral: 2m+1 estados e probabilidades “p” e “1-p” de deslocamento para a direita e a esquerda, respectivamente. Xn = posição (x= –1, 0, +1) 16 Exemplo 5 – Apostador                     1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 p p p p p p P Matriz das Probabilidades Diagrama de Transição entre Estados 1 1 1 - p 1 - p 1 2 3 4 0 p p p 1 - p Xn = qtd de grana para apostar (x=0,1,...,4; 0<p<1) Caso geral: x=0,1,2,...,n ou ainda sem limite superior (p<0,5) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.8 Prof. Dr. Marco A. Mesquita Probabilidades de Estados Objetivo: caracterizar a dinâmica do processo estocástico (cadeia de Markov) no regime transitório e permanente 18 Probabilidades de Estados Considere uma CMTD com espaço amostral S = {1, 2, . . . , m}. Sejam p(n) = [p1(n), . . . , pm(n)] as probabilidades de cada um dos m estados do espaço S após n transições. Então: p(1) = p(0) P p(2) = p(1) P . . . p(n) = p(n-1) P => p(n) = p(0) Pn onde p(0) é a distribuição do estado inicial. PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.9 Prof. Dr. Marco A. Mesquita 19 Exemplo da Bolsa Considere a seguinte distribuição inicial: p(0) = [1,0 0,0 0,0] Então: Probabilidades de estar nos estados 1, 2 e 3, na semana n=1, dado que estava no estado 1 na semana n=0.    1,0 1,0 8,0 ,0 50 ,0 30 20 ,0 ,015 ,0 75 10 ,0 ,010 ,010 80 ,0 0,0 0,0 0,1 )1( (0) P )1(               p p p 20 Exemplo da Bolsa (cont.) Para n=2: Probabilidades de estar nos estados 1, 2 e 3, na semana n=2, dado que estava no estado 1 na semana n=0.    ,0185 ,0185 670 ,0 ,0 50 ,0 30 20 ,0 ,015 ,0 75 10 ,0 ,010 ,010 80 ,0 1,0 1,0 8,0 2) ( P )1( 2) (               p p p PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.10 Prof. Dr. Marco A. Mesquita 21 Exemplo da Bolsa (cont.) 0,80 0,10 0,10 0,10 0,75 0,15 0,20 0,30 0,50 n p1(n) p2(n) p3(n) 0 1,0 0,0 0,0 1 0,8000 0,1000 0,1000 2 0,6700 0,1850 0,1450 3 0,5835 0,2493 0,1673 4 0,5252 0,2955 0,1794 5 0,4856 0,3279 0,1865 ... ... ... ... ∞ 0,4000 0,4000 0,2000 )1 P ( ( )    n n p p 22 Exemplo da Bolsa (cont.) 0,80 0,10 0,10 0,10 0,75 0,15 0,20 0,30 0,50 n p1(n) p2(n) p3(n) 0 0,0 1,0 0,0 1 0,1000 0,7500 0,1500 2 0,1850 0,6175 0,1975 3 0,2493 0,5409 0,2099 4 0,2955 0,4935 0,2110 5 0,3279 0,4630 0,2091 ... ... ... ... ∞ 0,4000 0,4000 0,2000 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.11 Prof. Dr. Marco A. Mesquita 23 Exemplo da Bolsa (cont.) 0,80 0,10 0,10 0,10 0,75 0,15 0,20 0,30 0,50 n p1(n) p2(n) p3(n) 0 0,0 0,0 1,0 1 0,2000 0,3000 0,5000 2 0,2900 0,3950 0,3150 3 0,3345 0,4198 0,2458 4 0,3587 0,4220 0,2193 5 0,3730 0,4181 0,2088 ... ... ... ... ∞ 0,4000 0,4000 0,2000 24 Exemplo do Random Walk 0,0 1,0 0,0 0,5 0,0 0,5 0,0 1,0 0,0 n p1(n) p2(n) p3(n) 0 1,0 0,0 0,0 1 0,00 1,00 0,00 2 0,50 0,00 0,50 3 0,00 1,00 0,00 4 0,50 0,00 0,50 ... ... ... ... 0,50 0,00 0,50 0,00 1,00 0,00 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.12 Prof. Dr. Marco A. Mesquita 25 Exemplo do Apostador (1) 1,00 0,00 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,00 1,00 n p0(n) p1(n) p2(n) p3(n) p4(n) 0 0 0 1 0 0 1 0,0000 0,7500 0,0000 0,2500 0,0000 2 0,5625 0,0000 0,3750 0,0000 0,0625 3 0,5625 0,2813 0,0000 0,0938 0,0625 4 0,7734 0,0000 0,1406 0,0000 0,0859 5 0,7734 0,1055 0,0000 0,0352 0,0859 ... ... ... ... ... ... ∞ 0,9000 0,0000 0,0000 0,0000 0,1000 26 Exemplo do Apostador (2) 1,00 0,00 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,00 1,00 n p0(n) p1(n) p2(n) p3(n) p4(n) 0 0 1 0 0 0 1 0,7500 0,0000 0,2500 0,0000 0,0000 2 0,7500 0,1875 0,0000 0,0625 0,0000 3 0,8906 0,0000 0,0938 0,0000 0,0156 4 0,8906 0,0703 0,0000 0,0234 0,0156 5 0,9434 0,0000 0,0352 0,0000 0,0215 ... ... ... ... ... ... ∞ 0,9750 0,0000 0,0000 0,0000 0,0250 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.13 Prof. Dr. Marco A. Mesquita 27 Exemplo do Apostador (3) 1,00 0,00 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,75 0,00 0,25 0,00 0,00 0,00 0,00 1,00 n p0(n) p1(n) p2(n) p3(n) p4(n) 0 0 0 0 1 0 1 0,0000 0,0000 0,7500 0,0000 0,2500 2 0,0000 0,5625 0,0000 0,1875 0,2500 3 0,4219 0,0000 0,2813 0,0000 0,2969 4 0,4219 0,2109 0,0000 0,0703 0,2969 5 0,5801 0,0000 0,1055 0,0000 0,3145 ... ... ... ... ... ... ∞ 0,6750 0,0000 0,0000 0,0000 0,3250 28 Probabilidades de Transição em n passos      6,0 4,0 3,0 7,0 P Matriz de Transição: A matriz P apresenta as probabilidades de transição em um único passo. Quais seriam as probabilidades de transição em dois ou mais passos? Exemplo 2: Previsão do Tempo Espaço Amostral: S = {0 (chuva), 1 (sol)} PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.14 Prof. Dr. Marco A. Mesquita 29 Probabilidades de Transição em n-Passos Seja {Xn: n = 0, 1,...} uma Cadeia de Markov com espaço amostral S e matriz de transição entre P. Então, define-se a probabilidade de transição de i para j em n passos: P(Xn = j |X0 = i) = pij (n) A matriz das probabilidades de transição em n- passos P(n) é dada por: P(n) = Pn 30 Probabilidades de Transição em 2 Passos  Exemplo 2 (cont.): Previsão do Tempo  A partir da matriz de transição em 2 passos, tem-se: p00 (2) = 0,61 é a probabilidade de estar chovendo depois de amanhã, dado que está chovendo hoje. p01 (2) = 0,39 é a probabilidade de fazer sol depois de amanhã, dado que está chovendo hoje.           ,0 48 52 ,0 ,0 39 61 ,0 6,0 4,0 3,0 7,0 2 P(2) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.15 Prof. Dr. Marco A. Mesquita 31 n Matriz de Transição, P(n) 1 2 3 4 5     ,0 444 556 ,0 ,0 417 583 ,0     ,0 4332 5668 ,0 ,0 4251 5749 ,0     ,0 4300 5700 ,0 ,0 4275 5725 ,0     6,0 4,0 3,0 7,0     ,0 48 52 ,0 ,0 39 61 ,0 Probabilidades de Transição em n-Passos Previsão do Tempo 32 n Matriz de Transição, P(n) 6 7 8 9 10     ,0 4286 5714 ,0 ,0 4285 5715 ,0     ,0 4286 5714 ,0 ,0 4286 5714 ,0     ,0 4286 5714 ,0 ,0 4286 5714 ,0     ,0 4290 5710 ,0 ,0 4283 5717 ,0     ,0 4287 5713 ,0 ,0 4285 5715 ,0 Probabilidades de Transição em n-Passos Previsão do Tempo (cont.) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.16 Prof. Dr. Marco A. Mesquita 33 Interpretação Neste exemplo: p00 (10) = p10 (10) = 0,5714 p01 (10) = p11 (10) = 0,4286 Ou seja, o estado futuro, para n grande, é independente do estado inicial. Neste caso, temos uma distribuição estacionária dos estados. 34 Distribuição Estacionária Sob determinadas condições, a probabilidade de estar em estado futuro qualquer torna-se independente do estado inicial. Esta distribuição assintótica é denominada distribuição em regime estacionário. p j = lim n pij (n) j=1,2,...,m p = [p1, p2, . . . , pm] PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.17 Prof. Dr. Marco A. Mesquita 35 Exemplo da Bolsa 𝑃2= 0,6700 0,1850 0,1450 0,1850 0,6175 0,1975 0,2900 0,3950 0,3150 P = 0,80 0,10 0,10 0,10 0,75 0,15 0,20 0,30 0,50 𝑃4= 0,5252 0,2955 0,1794 0,2955 0,4935 0,2110 0,3587 0,4220 0,2193 𝑃32= 0,4000 0,4000 0,2000 0,4000 0,4000 0,2000 0,4000 0,4000 0,2000 𝑃16= 0,4013 0,3989 0,1998 0,3989 0,4010 0,2002 0,3996 0,4003 0,2001 𝑃8= 0,4274 0,3767 0,1959 0,3767 0,4199 0,2034 0,3917 0,4068 0,2015 36 Reparo de Máquinas 𝑃2= 0,8281 0,1638 0,0081 0,8190 0,1720 0,0090 0,8100 0,1800 0,0100 P = 0,81 0,18 0,01 0,90 0,10 0,0 1,0 0,0 0,0 𝑃4= 0,8265 0,1653 0,0083 0,8264 0,1654 0,0083 0,8263 0,1654 0,0083 𝑃32= 0,8264 0,1653 0,0083 0,8264 0,1653 0,0083 0,8264 0,1653 0,0083 𝑃16= 0,8264 0,1653 0,0083 0,8264 0,1653 0,0083 0,8264 0,1653 0,0083 𝑃8= 0,8264 0,1653 0,0083 0,8264 0,1653 0,0083 0,8264 0,1653 0,0083 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.18 Prof. Dr. Marco A. Mesquita 37 Random Walk (1) 𝑃2= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 P = 0,0 1,0 0,0 0,5 0,0 0,5 0,0 1,0 0,0 𝑃4= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 𝑃32= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 𝑃16= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 𝑃8= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 38 Random Walk (2) 𝑃34= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 𝑃33= 0,00 1,00 0,00 0,50 0,00 0,50 0,00 1,00 0,00 𝑃32= 0,50 0,00 0,50 0,00 1,00 0,00 0,50 0,00 0,50 𝑃35= 0,00 1,00 0,00 0,50 0,00 0,50 0,00 1,00 0,00 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.19 Prof. Dr. Marco A. Mesquita 39 Qual é o significado deste resultado? Ruína do Apostador Não há uma distribuição estacionária neste caso. Considere o Problema do Apostador, com p=0,25:                   1 0 0 0 0 ,0 325 0 0 0 675 ,0 ,0100 0 0 0 900 ,0 ,0 025 0 0 0 975 ,0 0 0 0 0 1 P                  1 0 0 0 0 ,0 25 0 ,0 75 0 0 0 ,0 25 0 ,0 75 0 0 0 ,0 25 0 75 ,0 0 0 0 0 1 P 40 Interpretação  Algumas cadeias de Markov apresentam uma distribuição estacionária, outras não.  Uma Cadeia de Markov finita apresenta distribuição estacionária se for irredutível e aperiódica.  As cadeias que apresentam distribuição estacionária são chamadas de ergódicas.  Aqui, consideraremos apenas o caso de Cadeias de Markov com um número finito de estados (cadeias finitas) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.20 Prof. Dr. Marco A. Mesquita 43 As cadeias de Markov que apresentam distribuição estacionária são chamadas cadeias ergódicas. Cadeia de Markov Ergódica A distribuição estacionária é dada pela solução do sistema de equações lineares: Teorema: toda Cadeia de Markov finita, irredutível e aperiódica possui uma distribuição estacionária, que é independente das condições iniciais. 1 P    j p p p 44 Definições: Acessibilidade e Comunicação  Um estado j é acessível a partir de i se existe n, tal que pij(n) > 0 ( i → j )  Dois estado i e j comunicam-se, se i é acessível a partir do estado j e vice-versa. ( i ↔ j )  Todo estado i comunica-se consigo mesmo ( i ↔ i )  Propriedade: se i ↔ k e k ↔ j , então i ↔ j PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.21 Prof. Dr. Marco A. Mesquita 45 Definição: Classe  Classe é qualquer subconjunto de estados do espaço amostral que se comunicam entre si e não se comunicam com nenhum outro estado fora da classe.  Se todos os estados de uma Cadeia de Markov comunicam-se (isto é, a cadeia apresenta uma única classe), então a cadeia é irredutível. 46 Exemplo 6  Quantas classes temos na cadeia abaixo? 5 4 1 3 2 Duas classes: C1 = {1; 2} C2 = {3; 4; 5} PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.22 Prof. Dr. Marco A. Mesquita 47 Definições: Recorrência e Transitoriedade  Um estado i é transitório se existir um estado j que seja acessível a partir de i, mas o estado i não seja acessível a partir do estado j.  Um estado não transitório é chamado de recorrente.  Se i é recorrente (transitório) e comunica-se com j, então j também será recorrente (transitório)  A recorrência (transitoriedade) é uma propriedade da classe (não apenas dos estados)  Toda Cadeia de Markov finita e irredutível é recorrente, isto é, todos os seus estados são recorrentes. 48 Exemplo 6 (cont.)  Quais classes são recorrentes? Quais são transitórias? 5 4 1 3 2 C1 = {1; 2} é transitória C2 = {3; 4; 5} é recorrente PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.23 Prof. Dr. Marco A. Mesquita 49 Definição: Periodicidade  Define-se, para cada estado i, um período di como sendo o máximo divisor comum entre os valores de n para os quais pii (n) é positivo, ou seja, pii (n) > 0 se, e somente se, n = di, 2 di, 3 di, ...  Se di =1, então o estado i é classificado com aperiódico.  A periodicidade também é uma propriedade da classe. Se i ↔ j , então i e j têm o mesmo período di.  As cadeias irredutíveis podem, então, ser classificadas em periódicas e aperiódicas. 50 Exemplo 6 (cont.)  Quais classes são periódicas? 5 4 1 3 2 C1 = {1; 2} é transitória C2 = {3; 4; 5} é recorrente e periódica PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.24 Prof. Dr. Marco A. Mesquita 51 Exemplo 6b  Se p53>0, quais classes são periódicas? 5 4 1 3 2 C1 = {1; 2} é transitória C2 = {3; 4; 5} é recorrente e aperiódica 52 Exemplo 6c  Incluindo p51>0, quantas classes teremos? 5 4 1 3 2 Uma única classe: C1 = {1; 2; 3; 4; 5} recorrente e aperiódica Cadeia Finita, Irredutível e Aperiódica, ou seja, a cadeia é Ergódica PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.25 Prof. Dr. Marco A. Mesquita 53 As cadeias de Markov que apresentam distribuição estacionária são chamadas cadeias ergódicas. Cadeia de Markov Ergódica A distribuição estacionária é dada pela solução do sistema de equações lineares: Teorema: toda Cadeia de Markov finita, irredutível e aperiódica possui uma distribuição estacionária, que é independente das condições iniciais. 1 P    j p p p 54 Exemplo da Bolsa Matriz P            ,0 50 ,0 30 20 ,0 ,015 ,0 75 10 ,0 ,010 ,010 80 ,0 P Diagrama Transição-Estado A cadeia é finita, irredutível e aperiódica, portanto, é ergódica e possui distribuição estacionária. 0,2 0,1 1 2 0,8 3 0,5 0,1 0,1 0,75 0,3 0,15 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.26 Prof. Dr. Marco A. Mesquita 55 Exemplo da Bolsa (cont.)  Cálculo das Probabilidades Estacionárias     1 ,0 50 ,0 30 20 ,0 ,015 ,0 75 10 ,0 ,010 ,010 80 ,0 3 2 1 3 2 1 3 2 1                p p p p p p p p p 1 P    j p p p 56 Exemplo da Bolsa (cont.)  Descartar uma das três primeiras equações e resolver o sistema de equações lineares restante  Tem-se: π1 = 0,40 π2 = 0,40 π3 = 0,20 π1 = 0,80π1 + 0,10π2 + 0,20π3 π2 = 0,10π1 + 0,75π2 + 0,30π3 π3 = 0,10π1 + 0,15π2 + 0,50π3 π1 + π2 + π3 = 1 4 equações e 3 incógnitas. PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.27 Prof. Dr. Marco A. Mesquita 57 Três classes: {0}, {1, 2, 3} e {4}, portanto, a CM não é ergódica. Os estados 1, 2 e 3 apresentam período 2. Exemplo do Apostador 0 1 2 3 4 0 1 0 0 0 0 1 1-p 0 p 0 0 2 0 1-p 0 p 0 3 0 0 1-p 0 p 4 0 0 0 0 1 58 Distribuição Estacionária - Interpretação  Em uma cadeia ergódica, π = [ πj ] é a distribuição de probabilidade de se observar o sistema em cada um dos estados j, após um grande número de passos.  As probabilidades limite πj também pode ser interpretadas como porcentagem do tempo em que, no longo prazo, o processo permanece em cada j.  Quando a CM é finita, irredutível e periódica, tem-se também uma distribuição π = [ πj ], dada pela solução do sistema π = π · P . Neste caso, os valores deve ser interpretados apenas como a porcentagem do tempo em que a cadeia permanece em j (devido ao período). PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.28 Prof. Dr. Marco A. Mesquita 59 Distribuição Estacionária Resolução em Python (1/4) 60 Distribuição Estacionária Resolução em Python (2/4) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.29 Prof. Dr. Marco A. Mesquita 61 Distribuição Estacionária Resolução em Python (3/4) 62 Distribuição Estacionária Resolução em Python (4/4) PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.30 Prof. Dr. Marco A. Mesquita 63 “Mean First Passage Times” Seja mij = número médio de passos para, partindo do estado i, chegar pela primeira vez ao estado j. Em particular, para i=j:     j k kj ik ij p m m 1 j m jj p 1  Para uma cadeia ergódica, os valores de mij são dados pela solução do seguinte sistema linear: 64 Exemplo da Bolsa – mjj Determine o tempo médio de retorno ao mesmo estado no modelo da Bolsa de Valores. A partir da distribuição estacionária: tem-se: 0,5 1 5,2 1 5,2 1 3 33 2 22 1 11       p p p m m m 𝜋1 = 0,40 𝜋2 = 0,40 𝜋3 = 0,20 PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.31 Prof. Dr. Marco A. Mesquita 65 Exemplo da Bolsa – mij 𝑚12 = 1 + 𝑝11𝑚12 + 𝑝13𝑚32 𝑚13 = 1 + 𝑝11𝑚13 + 𝑝12𝑚23 𝑚21 = 1 + 𝑝22𝑚21 + 𝑝23𝑚31 𝑚23 = 1 + 𝑝21𝑚13 + 𝑝22𝑚23 𝑚31 = 1 + 𝑝32𝑚21 + 𝑝33𝑚31 𝑚32 = 1 + 𝑝31𝑚12 + 𝑝33𝑚32 𝑚11 = 1 𝜋1 𝑚22 = 1 𝜋2 𝑚33 = 1 𝜋3 M = 2,5 7,5 8,75 8,125 2,5 7,5 6,875 5 5 66 Exemplo 3b – Reparo em 2 dias Considere uma célula com duas máquinas. Cada máquina, quando começa o dia funcionando, tem 10% de chance de quebrar durante o dia. O conserto de uma máquina consome dois dias de trabalho de um único técnico habilitado. Assim, há a possibilidade de uma máquina ficar em fila. O problema pode ser formulado como uma CMTD? PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.32 Prof. Dr. Marco A. Mesquita 67 Modelagem Duas máquinas, um técnico, dois dias de reparo por máquina. Definição dos estados: s = (s1, s2) s1 = número de máquinas em reparo s2 = número de dias em reparo da primeira máquina # Estado Definição 0 s0 = (0, 0) Nenhuma máquina quebrada 1 s1 = (1, 1) Uma máquina quebrada, no primeiro dia de reparo 2 s2 = (1, 2) Uma máquina quebrada, no segundo dia de reparo 3 s3 = (2, 1) Duas máquinas quebradas e uma no primeiro dia de reparo 4 s4 = (2, 2) Duas máquinas quebradas e uma no segundo dia de reparo 68 Matriz Transição entre Estados                  0 0 0 1 0 1 0 0 0 0 0 0 0 ,010 90 ,0 ,010 0 ,0 90 0 0 0 ,0 01 0 ,018 81 ,0 P 4 3 0 2 1 0,81 0,10 0,01 0,90 0,18 0,90 0,10 1,0 1,0 Cadeia Finita, Irredutível e Aperiódica PRO 3342 – Cadeias de Markov USP – Poli – PRO 2.33 Prof. Dr. Marco A. Mesquita 69 Solução 1 P    j p p p  ,0 0225 ,0 0067 ,01418 ,01575 ,0 6715  p 4 3 0 2 1 0,81 0,10 0,01 0,90 0,18 0,90 0,10 1,0 1,0 70 Próxima aula  Winston (2004, cap.20)  20.1, 20.2 e 20.3