t3-2010-1gab

Prévia do material em texto

2010-1 MAB-515 Avaliação e Desempenho – Prof. Paulo Aguiar DCC/IM/UFRJ 
Teste 3 
Duração: 2h , 100 pontos, SEM CONSULTA, 1/07/2010 -GABARITO 
 
Aluno: _________________________________________________ 
 
1ª questão (20 pontos) 
Quantos lançamentos em média são necessários para se observar uma diferença 
de k entre o número de caras e o número de coroas em lançamentos consecutivos 
de uma moeda não viciada? Seja E[N] o valor a ser calculado. 
 
a) (5) A CM abaixo permite resolver o problema. Explique a construção desta 
cadeia, justificando as transições entre os estados. Supondo que as probabilidades 
de estado em equilíbrio ipi foram obtidas, indique como seria obtido E[N]. 
 
 
 
 
 
 
 
b) (5) Escreva o sistema de equações em equilíbrio. 
 
c) (10) Resolva para as probabilidades em equilíbrio. Obtenha kpi como uma 
expressão fechada em função de k. Não pode conter somatórios não resolvidos. 
 
Solução: 
 
a) (5) A cadeia representa a diferença entre o número de caras e coroas. A transição do 
estado i para o estado i+1 ocorre quando o lançamento acumula a favor da diferença. Caso 
o lançamento diminua a diferença, ocorre a transição de i para i-1. Quando estamos no 
estado 0, o número de caras e coroas até o momento é o mesmo. Este também é o estado 
inicial. Após um lançamento neste estado, iremos para o estado 1 necessariamente, pois a 
diferença será de 1, qualquer que seja o resultado. E[N] será o número médio de 
lançamentos até alcançar o estado k saindo do estado 0. Para que possamos calcular este 
valor, retornamos a 0 após atingir k com probabilidade1. 
Então, 
1[ ] [ ] 1 1k
k
E N E M
pi
= − = − . 
b) (5) e c) (10) Podemos escrever as equações a partir do estado k. 
1
1
2
1 1 2 1
3 1
2 2 3 2 1
4 2
3 3 4 3 2
: 2 ( .1)
2
: 2 4 ( .2)
2
: 2 6 ( .3) ) 2
2 2
: 2 8 ( .4)
2 2
k
k k k k
k
k k k k k
k k
k k k k k k
k k
k k k k k k
E eq
E eq
E eq
E eq
pi
pi pi pi
pi
pi pi pi pi
pi pi
pi pi pi pi pi
pi pi
pi pi pi pi pi
−
−
−
− − − −
− −
− − − − −
− −
− − − − −
= ∴ =
= ∴ = =
= + ∴ = − = + + +
= + ∴ = − =
�
 
0 1 3 
1/2 1/2 1/2 2 k-1 1/2 
1 
k 
1/2 1/2 1/2 1/2 
1 
2010-1 MAB-515 Avaliação e Desempenho – Prof. Paulo Aguiar DCC/IM/UFRJ 
[ ]
( )
2 4
3 3 2 3 4
31
2 2 1 2 3
2 2
1 1 0 0 1
0
: 2 2( 2) ( . 2)
2 2
: 2 2( 1) ( . 1)
2 2
: 2( 1) ( 2) ( . )
2 2
1 1 2 4 6 8 2( 2) 2( 1) 1 ( . 1)
1 2 1 2 3 ( 1)
k
k
k k k
k
i k
i
k
E k eq k
E k eq k
E k k k eq k
k k k eq k
k k
pi pi
pi pi pi pi pi
pipi
pi pi pi pi pi
pi pi
pi pi pi pi pi pi pi
pi pi
pi
=
= + ∴ = − = − −
= + ∴ = − = − −
= + ∴ = − = − − − =
= ⇒ + + + + + + − + − + = +
 + + + + + − +
∑ �
� ( ) ( )2
2
1 ( 1) 1 1
1
1
k k
k
k k k k
k
pi pi
pi
 = + + − = + =
∴ =
+
 
 
A resposta da questão então é 2[ ]E N k= . 
 
 
2ª questão (30 pontos) 
Seja dada a cadeia: 
 
 
 
 
 
 
 
Assuma que os estados são recorrentes positivos e que as probabilidades de 
estado em equilíbrio foram calculadas. 
 
Considerando um tempo longo t, calcule: 
 
a) (5) E[número de chegadas em t] 
b) (5) E[número de chegadas que encontram a cadeia em Ei] 
c) (5) P{chegada encontrar a cadeia em Ei} 
d) (5) E{número de partidas que deixam a cadeia para trás no estado Ei} 
e) (5) P{partida deixar a cadeia para trás no estado Ei} 
f) (5) Compare os resultados dos itens (e) e (c), e justifique. 
 
 
Solução: 
a) (3) E[número de chegadas]=
0
j j
j
tλ pi
∞
=
∑ . 
b) (2) E[número de chegadas que encontram a cadeia em Ei]= i itλ pi . 
c) (5) P{chegada encontrar a cadeia em Ei}=
0
i i
j j
j
t
t
λ pi
λ pi
∞
=
∑
. 
d) (2) E[número de partidas que deixam a cadeia em Ei]= 1 1i i tµ pi+ + 
0 1 3 2 
0λ 1λ 2λ 3λ 
1µ 2µ 3µ 4µ 
2010-1 MAB-515 Avaliação e Desempenho – Prof. Paulo Aguiar DCC/IM/UFRJ 
e) (3) P{partida deixar a cadeia para trás no estado Ei}= 1 1
1
i i
j j
j
t
t
µ pi
µ pi
+ +
∞
=
∑
. 
f) (5) Observando que para uma cadeia em equilíbrio fluxo entrante = fluxo sainte, então é 
fácil ver que 1 1i i i iµ pi λ pi+ + = . E também, taxa média de chegada é igual à taxa média de 
partida, indicando que os numeradores e denominadores dos itens (e) e (c) são 
rigorosamente iguais, implicando, conseqüentemente, que as duas probabilidades são iguais. 
 
 
3ª questão (20 pontos) 
Classifique completamente as cadeias que se seguem e seus estados. Caso ocorra 
conjunto fechado, identifique-os e classifique seus estados. Indique se estados são 
periódicos e o período, quando for o caso. Indique se estados são também 
ergódicos, se for o caso. 
 
a) (10) 
 
 
 
 
 
b) (10) 
 
 
 
Solução: 
 
a) (10) 
(1) A Cadeia é homogênea e redutível. 
 
(1) Os estados 0 e 1 são transientes, pois uma vez que alcancemos o estado 2, nunca mais 
voltaremos a estes estados. 
 
(1) Os estados {2, 3, ...} formam um conjunto fechado. 
 
(2)Analisando este conjunto fechado como uma C.M. irredutível, podemos verificar que a 
partir do estado 4, as probabilidades de se ocorrerem transições para a direita ou para a 
esquerda são iguais e o ganho médio é zero (em termos de deslocamento). Logo, iremos 
retornar ao estado 4 se formos para o estado 5 certamente no futuro, implicando que o 
estado é recorrente. 
 
(2) Contudo, se aplicarmos o critério de Foster, tentando encontrar uma solução em 
equilíbrio, veremos que não há uma solução estacionária para as probabilidade de estado 
em equilíbrio e estes estados não podem ser recorrentes positivos. 
 
(2) Isso é mostrado abaixo. 
 
0 1 2 
1 1 1 
1/2 1/2 
3 
… infinitos estados à direita 0 1 2 
1/2 
4 
2/3 
1/3 
3/4 
1/4 1/4 1/3 
2/3 1/2 
1/2 
3 5 1/2 
1/2 
3/4 
2010-1 MAB-515 Avaliação e Desempenho – Prof. Paulo Aguiar DCC/IM/UFRJ 
2 2 3 3 2
4
3 2 4 3 2 2
3 5 4 3
4 5 2
64
5 6 5 4 2
3 2 3
4 3 8
1 1 12
4 2 2 4
6 2 1
3 2 3 4
12
2 2 4
pi pi pi pi pi
pi
pi pi pi pi pi pi
pi pi pi pi
pi pi pi
pipi
pi pi pi pi pi
= + ∴ =
= + ∴ = − =
−
= + ∴ = =
= + ∴ = − =
 
 
E assim sucessivamente. Logo, se o estado 2 tiver uma probabilidade de estado >0, então 
todos os outros também terão e a soma das probabilidades tenderá para infinito, o que é 
impossível. Conseqüentemente, não pode haver uma solução estacionária (com as 
probabilidades diferentes de zero) e os estados não podem ser recorrentes positivos. Logo, 
serão recorrentes nulos. 
 
(1) Do ponto de vista de periodicidade, é fácil ver que 0)(22 ≠np para quaisquer valores de n, 
implicando que o MDC do conjunto {n} é 1 e os estados do conjunto fechado são 
aperiódicos. 
 
b) (10) 
(2) Cadeia homogênea, irredutível e finita. 
(3) Logo, todos os estados são recorrentes positivos. 
(3) Período =2, pois 0)(33 ≠np para valores pares de n >1, implicando que o MDC do 
conjunto {n} é 2 e este é o período para todos os estados da cadeia. 
(2) Como os estados são periódicos, eles não são ergódicos. 
 
4ª questão (30 pontos) 
Um pedicuro atende seus clientes individualmente o que leva um tempo médio 
exponencial com taxa µ . Existem apenas três lugares para a fila de espera. 
Clientes chegam individualmente segundo um fluxo Poisson com taxa 1λ , ou em 
grupos de dois com taxa 2λ e ou grupos de três com taxa 3λ . Quando os clientes 
chegam, eles ocupam os lugares que estiverem vagos e aqueles que sobram vão 
embora, ainda que parte do grupo tenha ficado na espera. 
a) (5) Desenhe a cadeia de Markov que representa o número de clientes no 
pedicuro (fila de espera maisserviço). 
b) (5) Escreva as equações para as probabilidades em equilíbrio, mas não resolva. 
c) (10) Assumindo que as probabilidades foram obtidas, calcule o tempo médio 
gasto na sala de espera do pedicuro. 
d) (10) Num tempo longo t, quantos clientes deixam de ser atendidos por falta de 
espaço no setor de espera? 
 
2010-1 MAB-515 Avaliação e Desempenho – Prof. Paulo Aguiar DCC/IM/UFRJ 
Solução: 
a) (5) 
 
 
 
 
 
 
 
 
 
As transições se devem ao número de pessoas que chegam. Nos estados 0 e 1 há espaço para 
mais três pessoas, de modo que todos que chegam ficam no pedicuro e ninguém é forçado a 
desistir por falta de espaço. Quando estamos no estado 2 e chegam três pessoas, apenas 
duas ficam no pedicuro e uma vai embora. No estado 3, quando chegam grupos de duas ou 
três pessoas, apenas uma fica e as outras vão embora. No estado 4 todas as pessoas que 
chegam vão embora, pois os espaços de espera estão todos ocupados. 
 
b) (5) 
0 1 2 3 1
1 1 2 3 1 0 2
2 1 2 3 2 0 1 1 3
4 3 1 2 3 2 1 2 3 3
0 1 2 3
( )
( )
( )
( ) ( )
1
pi λ λ λ µpi
pi λ λ λ µ λ pi µpi
pi λ λ λ µ λ pi λ pi µpi
µpi λ pi λ λ pi λ λ λ pi
pi pi pi pi
+ + =
+ + + = +
+ + + = + +
= + + + + +
+ + + =
 
 
c) (5) 
3
0
[ ] [ ] [ ] [ ] 1 /
[ ] . [ ]i
i
E W E T E X E T
E N i taxa média dos fregueses que são atendidos E T
µ
pi
=
= − = −
= =∑
 
A taxa média (fregueses/segundo) dos fregueses que são atendidos tem que ser calculada 
levando-se em conta que nem todas as pessoas do grupo fica no pedicuro. Assim, por 
exemplo, quando estamos no estado 2 e chega um grupo com três pessoas com taxa 3λ , 
apenas duas pessoas ficam no pedicuro e portanto a taxa real de chegada de pessoas para 
este tipo de grupo seria 2 3λ . Neste estado a taxa média de fregueses seria dada 
por 1 2 32( )λ λ λ+ + . A taxa média tem que ser ponderada pela probabilidade de estado. 
Assim, 
 
Taxa média de fregueses que são atendidos pelo pedicuro 
( )
1 2 3 0 1 2 3 1 1 2 3 2 1 2 3 3
1 2 3 4
( 2 3 ) ( 2 3 ) ( 2 2 ) ( )λ λ λ pi λ λ λ pi λ λ λ pi λ λ λ pi
µ pi pi pi pi
= + + + + + + + + + + +
= + + +
 
= Taxa média de fregueses que são atendidos (pelo equilíbrio de fluxo). 
 
Obter a taxa média de fregueses servidos é mais fácil e direta e com menos chances de erro. 
 
d) (5) Num tempo longo t chegam ao pedicuro 1 2 3( 2 3 )tλ λ λ+ + e destes apenas 
( )1 2 3 4 tµ pi pi pi pi+ + + são de fato atendidos em média. Então o número médio de fregueses 
que não são atendidos é dado pela diferença entre estes dois valores. 
0 1 2 
1 2 3λ λ λ+ +
3 4 
1λ 1λ 1λ 
2 3λ λ+ 2λ 2λ 
3λ 3λ 
µ µ µ µ 
2010-1 MAB-515 Avaliação e Desempenho – Prof. Paulo Aguiar DCC/IM/UFRJ 
 
Outra forma de calcular seria obter diretamente as taxas de perda em cada estado e 
multiplicar pelo tempo t. Assim, o número médio de fregueses que deixam de ser atendidos é 
[ ]3 2 2 3 3 1 2 3 4( 2 ) ( 2 3 ) tλ pi λ λ pi λ λ λ pi= + + + + + . 
 
Estes dois valores são iguais e isso pode ser facilmente comprado pela igualdade de fluxos 
em equilíbrio.