Lista de Exercícios 2 - Modelagem de Sistemas Discretos

Prévia do material em texto

1 
Mod. Sist. Disc. 
Lista de Exercícios II - Cadeias de Markov 
 
 
 
1) Recentemente a revista Veja anunciou que irá nascer nos próximos dias o bebê que fará a 
população mundial alcançar 7 bilhões de habitantes. Considerando o número de habitantes como o 
estado de um processo estocástico, explique: 
1.a) Este processo é uma cadeia em tempo continuo ou discreto? 
1.b) O estado 7 bilhões poderá ocorrer mais de uma vez em um curto espaço de tempo. E a longo 
período? 
1.c) O estado 7 bilhões é absorvente, recorrente ou transiente? 
 
2) Seja P0 e P1 duas matrizes de transição em Cadeias de Markov, com as seguintes estruturas: 
 
Existe diferença entre as distribuições de probabilidades dos estados associadas às matrizes P0 e 
P1? Explique sua resposta de “maneira matemática”. 
 
3) Seja P a seguinte matriz de transição da Cadeia de Markov dada abaixo: 
 
Essa cadeia é Irredutível e/ou Ergódica? É possível determinar a distribuição de probabilidade dos 
estados através da resolução das equações de estados estáveis? Qual é essa distribuição? 
 
4) Considere uma cadeia de Markov em tempo discreto na qual existem estados transientes. A cada 
passo ocorre um custo diferente de zero associado ao estado que o processo assume. Explique quais 
serão os custos esperados em longo prazo associados aos estados transientes. 
5) Mensalmente é realizada a verificação do estado de um sistema eletrônico. O espaço de estados é 
{0, 1, 2}. A tabela abaixo apresenta os estados que o processo assumiu no período de jan/06 à 
dez/11. 
 
Faça as considerações que achar necessário e estime a matriz de transição para esta cadeia de 
Markov. 
 2 
6) Verifique se o lim pij
(n)
 = πj, i existe para a seguinte cadeia de Markov. Caso afirmativo, calcule 
π. 
 
7) Qual o maior período t que um estado i pode assumir em uma cadeia de Markov em tempo 
discreto? Justifique. 
8) Para quais valores de a o tempo de recorrência do estado 1 é igual a 1,5, dada a seguinte matriz 
de transição de uma cadeia de Markov? 
 
9) Uma máquina em uma linha de produção pode assumir os seguintes estados (tabela 1) e uma 
análise de dados passados permitiu a construção da seguinte matriz P de transição: 
 
 
 
 
Tabela1: classificação dos estados. 
 
De acordo com o estado da máquina, algumas decisões podem ser tomadas com respectivos custos: 
substituir a máquina por uma outra nova, o que implica na perda de uma semana a um custo de 
$2000,00 mais o custo da máquina nova por $4000,00. Quando a máquina opera no estado 1, há um 
custo de $1000,00 e quando a máquina opera no estado 2, há um custo de $3000,00, ambos devido à 
produção de itens defeituosos. Realizar a manutenção da máquina não é viável quando esta se 
encontra nos estados 0 e 1. A manutenção da máquina faz com que esta retorne ao estado 1, quando 
está operando no estado 2 a um custo de $2000,00 e a produção é perdida por uma semana. 
Determine a melhor linha de ação visando minimizar o custo de produção. 
 
 
 
 
 
 
 3 
Gabarito 
 
1.a) Este processo é uma cadeia, uma vez que os estados são sempre inteiros. Em tempo continuo 
ou discreto depende de como for considerado o processo estocástico. Se for população por dia, por 
exemplo, o tempo é discreto, se for população instantânea é tempo continuo. 
1.b) Sim, o estado 7 bilhões poderá ocorrer mais de uma vez em um curto espaço de tempo, uma 
vez que logo após o bebê 7 bilhões nascer poderá alguém morrer, o estado do processo voltará para 
o estado 6.999.999 (6 bilhões, novecentos e noventa e nove milhões, novecentos e noventa e nove) 
e então nascer outro bebê e o processo voltar ao estado 7 bilhões. Já, a longo período, o estado 7 
bilhões poderá voltar somente se este for recorrente. Para este estado ser recorrente é necessário 
esperar que a população mundial vá regredir e voltar a aumentar indefinidamente. 
1.c) Como já respondido na questão1.b, para este estado ser recorrente é necessário esperar que a 
população mundial vá regredir e voltar a aumentar indefinidamente. Caso isso não seja esperado, o 
estado será transiente. Este estado é impossível de ser absorvente em tempo contínuo, uma vez que 
é impossível nascer e morrer duas pessoas exatamente no mesmo instante. 
 
2) Para P0 e P1, as distribuições de probabilidade dos estados a longo período são: 
 
Assim, não existe diferença entre as distribuições de probabilidades dos estados associadas às 
matrizes P0 e P1. 
 
3) Essa cadeia não é Irredutível (o estado 1 não é comunicante com os demais) e não é Ergódica (os 
estados 0 e 2 são transientes). 
 
Resolvendo os sistemas de equações de estados estáveis 
π = [0 1 0] 
 
Sim, é possível determinar a distribuição de probabilidade dos estados através da resolução das 
equações de estados estáveis. 
 
4) A probabilidade em longo prazo associadas a um estado transiente é sempre zero, uma vez que o 
tempo de recorrência esperado associado a este estado é infinita. Assim, o custo esperado associado 
ao estado transiente é zero também, porque o custo esperado do estado é igual à probabilidade no 
longo prazo do estado multiplicada pelo custo esperado do estado. 
 
5) Espaço de estados = {0, 1, 2} 
 
Para estimar a probabilidade de transição pi de um estado i para um estado j a partir de uma série 
histórica (realização do processo estocástico) basta contabilizar o número de transições entre esses 
dois estados que ocorrem e então dividir pelo número de transições que ocorreram entre o estado i e 
os demais estados. 
 
 4 
Uma vez que não ocorreu na série nenhuma vez o estado 1, considerou-se que as probabilidades de 
transição do estado 1 para todos os demais são iguais. 
 
 
 
6) Uma vez que a cadeia é ergódica o lim pij
(n)
 = πj, i. 
A solução do sistema é: π = [1/7; 3/7; 3/7] 
 
7) t = M, onde M é o número de estados da cadeia. Qualquer estado que tenha um tempo de 
recorrência maior que M é aperiódico. Para haver um período t > M para algum estado i, o processo 
teria que ficar recorrendo entre outros estados de um conjunto fechado diferentes de i, porém assim, 
o processo seria absorvido para os estados desse conjunto fechado, não retornando mais a i. 
 
8) Uma vez que o tempo de recorrência do estado 1 é 1/π1, faz-se necessário que π1 = 2/3 a fim de se 
ter o tempo de recorrência 1/π1 = 3/2. Por inspeção se a = 1/3 a matriz P fica: 
 
Como todas as linhas de P são iguais, conclui-se que π = (1/3; 2/3) 
 
9) Política 1: Custo total esperado = $ 1923,03; π = ( 0,1538; 0,5386; 0,1538; 0,1538) 
 Política 2: Custo total esperado = $ 1666,67; π = ( 0,095; 0,715; 0,095; 0,095)