t3-2010-2gab

Prévia do material em texto

MAB-515 2010-1 
1 
Terceiro Teste MAB-515 2010-2 (2/12/2010) 
(50 pontos) 
 
Nome: GABARITO 
 
 
 
1ª Questão: (25 pontos) (CMTD) 
 
Para seleção de uma vaga olímpica, dois atletas competem entre si, por várias disputas. As 
disputas têm sempre um vencedor e não há empate. Quando um dos atletas acumula um 
saldo de três vitórias sobre o outro, ele se classifica para a vaga. Um atleta está melhor 
preparado e tem uma probabilidade p de vencer uma disputa, enquanto o outro, menos 
treinado, tem probabilidade q (=1-p) de vencer uma disputa. Queremos calcular a 
probabilidade de cada atleta obter a vaga olímpica em função de p e q, e também o número 
médio de disputas até a definição. 
Resolva o problema utilizando Cadeia de Markov 
 
a) (5) Desenhe uma cadeia de Markov que permita obter as probabilidades solicitadas. Dica: 
Não existe estado absorvente nesta cadeia! 
 
b) (5) Indique em função das probabilidades de equilíbrio: P{ganho da vaga pelo atleta mais 
preparado} e P{ganho da vaga pelo atleta menos preparado}. Atenção: estas duas 
probabilidades tem que somar a 1, pois um deles é que ganha a vaga olímpica. 
 
c) (5) Obtenha as probabilidades de equilíbrio em função de p e q. Use q e não 1-p. Escreva 
o sistema de equações, enumere as equações que serão utilizadas, e resolva o sistema 
indicando claramente qual equação está sendo utilizada a cada passo. 
 
d) (5) Calcule as probabilidades de ganho da vaga com p = 2/3 e q = 1/3. Cheque se elas 
somam a 1. 
 
e) (5) Quantas disputas em média ocorrerão até a definição da vaga? 
Dê a resposta literal e a resposta numérica. 
 
Solução: 
a) (5) 
 
 
 
 
 
 
 
b) (5) 
P{vaga ganha pelo atleta menos preparado} =
2* 2*
2* 2
1 1
3 3
1 2
3 3
F
pi pi
pipi pi
=
+
 
 
P{vaga ganha pelo atleta mais preparado} =
2 2
2* 2
2 2
3 3
1 2
3 3
F
pi pi
pipi pi
=
+
 
 
2* 1* 1 
2/3 2/3 2/3 0 2 
1 
2/3 
F 
1/3 1/3 1/3 1/3 
2/3 1/3 
MAB-515 2010-1 
2 
A disputa termina quando se alcança o estado F (Final). Este estado é alcançado a partir de 
E2 e de E2*, pois 2* 2
1 2
3 3F
pi pi pi= + . Em um número n de transições, o estado F é visitado 
chegando por E2 um número médio de vezes dado por 2
2
3
tpi e o estado F é visitado em 
média Ftpi vezes. Logo, a probabilidade do mais capacitado vencer é dada pela relação 
entre estes dois valores e raciocínio idêntico pode ser aplicado para obter a probabilidade do 
menos capacitado ganhar a vaga. 
 
c) (10) Circundando cada estado para obter cinco equações linearmente independentes: 
 
0 1 1*
1 0 2
1* 2* 0
2 1
2* 1*
{ 0} (1)
{ 1} (2)
{ 1*} (3)
{ 2} (4)
{ 2*} (5)
FE q p
E p q
E p q
E p
E q
pi pi pi pi
pi pi pi
pi pi pi
pi pi
pi pi
= + +
= +
= +
=
=
 
 
Substituindo (4) em (2): 
 
0
1 0 1 1 (6)1
p
p pq
pq
pi
pi pi pi pi= + ∴ =
−
 
Substituindo (5) em (3): 
0
1* 1* 0 1* (7)1
q
pq q
pq
pi
pi pi pi pi= + ∴ =
−
 
Substituindo (6) e (7) em (1): 
0 0 0
0
(1 3 ) (8)
1 1 1F F
pq pq pq
pq pq pq
pi pi pi
pi pi pi
−
= + + ∴ =
− − −
 
 
Substituindo (6) e (7) em (4) e (5) nos permite escrever 
2 2
0 0
2 2*(9) , (10)1 1
p q
pq pq
pi pi
pi pi= =
− −
 
A sexta equação a ser usada é a conservação de probabilidade 
0 1 2 1* 2* 1Fpi pi pi pi pi pi+ + + + + = . Usando (6 a10), temos 
2 2
0 0 0 0 0
0
0 2 2
(1 3 ) 1
1 1 1 1 1
1 1 (11)
4 62 4
p q p q pq
pq pq pq pq pq
pq pq
pqpq p q p q
pi pi pi pi pi
pi
pi
−
+ + + + + =
− − − − −
− −
∴ = =
−− + + + +
 
 
 Substituindo os valores de p=2/3 e q = 1/3 obtemos: 
 
MAB-515 2010-1 
3 
1 1*
0
0 2
1
02*
1*
1
2
1*
2*
2{ 0} (1)
3 3
2{ 1} (2)
3 3
2{ 1*} (3)
3 3
2{ 2} (4)
3
{ 2*} (5)
3
FE
E
E
E
E
pi pi
pi pi
pi pi
pi
pipi
pi
pi
pi
pi
pi
= + +
= +
= +
=
=
 
Substituindo (4) em (2): 
 
0 0 01 1
1 1
2 2 62 7 (6)
3 9 9 3 7
pi pi pipi pi
pi pi= + ∴ = ∴ = 
Substituindo (5) em (3): 
0 0 01* 1*
1* 1*
32 7 (7)
9 3 9 3 7
pi pi pipi pi
pi pi= + ∴ = ∴ = 
Substituindo (6) e (7) em (1): 
0 0 0
0
2 2 3 (8)
7 7 7F F
pi pi pi
pi pi pi= + + ∴ = 
 
Substituindo (6) e (7) em (4) e (5) nos permite escrever 
0 0
2 2*
4 (9) , (10)
7 7
pi pi
pi pi= = 
A sexta equação a ser usada é a conservação de probabilidade 
0 1 2 1* 2* 1Fpi pi pi pi pi pi+ + + + + = . Usando (6 a10), temos 
0 0 0 0 0
0 0
6 4 3 3 71 (11)
7 7 7 7 7 24
pi pi pi pi pi
pi pi+ + + + + = ∴ = 
 
Foi solicitada apenas a dedução literal e substituição final pelos valores numéricos. 
A dedução completa e repetida é para facilitar correções. 
 
d) (5) Com os valores numéricos temos 
0 1 2 1* 2*
7 6 4 3 1 3
, , , , ,
24 24 24 24 24 24F
pi pi pi pi pi pi= = = = = = . 
Então, 
 
P{vaga ganha pelo atleta menos preparado} = 2* 1
3 9F
pi
pi
= = , e 
 
P{vaga ganha pelo atleta mais preparado} = 22 8
3 9F
pi
pi
= = . 
 
e) (5) E[número de disputas]= 1 211 7
3Fpi
− = = . 
Explicação: após atingir o estado F retornamos a E0 com probabilidade 1. Logo, saindo de 
E0, o número médio de transições ou disputas até alcançar F será dado pelo tempo médio 
entre retornos ao estado F menos 1. 
MAB-515 2010-1 
4 
 
 
2ª Questão: (25 pontos) (CMTC) 
 
Uma fila de atendimento num posto possui dois fiscais de plantão que atendem à fila 
simultaneamente. O tempo de atendimento de cada pessoa é exponencial com média 1 / µ . 
Os fregueses chegam à fila segundo um processo Poisson com taxa λ , mas desistem de 
esperar com probabilidade ( )1 kp− , onde k é o número de fregueses na fila da espera, e 
vão embora. Atenção, pois k = 0 quando há menos de 3 pessoas no posto. 
 
a) (5) Desenhe a cadeia de Markov cujo estado é o número de pessoas no posto. Se você 
não tiver certeza do seu desenho peça para confirmar e pague 2 pontos. Se estiver errado e 
solicitar mais uma confirmação, mais 2 pontos. Solução imediata são 5 pontos. Você não 
pode errar a solução deste item para não comprometer o restante da questão. 
 
b) (5) A fila é estável quando ela fica ociosa com probabilidade maior que zero. Qual a 
condição para a cadeia ter estados recorrentes positivos? Justifique. 
 
c) (5) Escreva o conjunto de equações para obtenção das probabilidades em equilíbrio. 
 
d) (5) Indique em função de 0 , 2λpi ρ µ= ,k e p a expressão fechada para , 2i ipi ≥ . 
Cuidado ao generalizar expressões. 
 
e) (5) Para as pessoas que decidem ficar e esperar por atendimento, calcule o tempo médio 
desde o instante de chegada até o instante de partida do posto em função de ipi . 
 
Solução: 
 
a) (5) 
 
 
 
 
 
 
 
 
 
 
b) (5) Existirá sempre um determinado i tal que 1, ,
2
ipλ λ µ
µ
< ∀ ∀ finitos. Logo, , teremos 
1,
2
Jp j iλ
µ
< ∀ > e então o sistema será sempre recorrente positivo, pois a tendência será 
da cadeia de Markov visitar os estados à esquerda em longo prazo, não importando a 
situação inicial das taxas para os estados com número de pessoas menor do que i O sistema 
será então sempre estável. Esta conclusão é intuitiva, pois à medida que a fila de espera 
aumenta, diminui a taxa de chegada de pessoas à fila de espera. O que acontece em um 
congestionamento de trânsito é semelhante. Quando há indicação de que o trânsito está 
congestionado, os motoristas tentam outras vias ou desistem e retornam para casa. Para 
qualquer estado j > i, o incremento médio de pessoas à fila é negativo, indicando que 
retornaremos a este estado com certeza no futuro. Logo, ele será recorrente. Havendo a 
solução por Foster podemos garantirque será recorrente positivo. Calcular as probabilidades 
será passo adiante, mas a solução do estado E0, embora exista, não é uma fórmula fechada. 
 
0 1 3 2 5 4 
λ λ λ pλ 2pλ 
µ 2µ 2µ 2µ 2µ (1) (2) (3) (4) (5) 
MAB-515 2010-1 
5 
c) (5) As equações podem ser obtidas pela igualdade de fluxos entre os estados em 
equilíbrio e usando a conservação de probabilidade. Usaremos 
2
λρ
µ
= . 
 
0 1 1 0
2
1 2 2 0
3
2 3 3 0
4
3 4 4 0
2 3 5
4 5 5 0
3 6 6
5 6 6 0
5 10 7
6 7 7 0
0
(1) 2
(2) 2 2
(3) 2 2
(4) 2 2
(5) 2 2
(6) 2 2
(7) 2 2
1i
i
p p
p p
p p
p p
λ pi µpi pi ρpi
λ pi µpi pi ρ pi
λ pi µpi pi ρ pi
λ pi µpi pi ρ pi
λ pi µpi pi ρ pi
λ pi µpi pi ρ pi
λ pi µpi pi ρ pi
pi
∞
=
= ∴ =
= ∴ =
= ∴ =
= ∴ =
= ∴ =
= ∴ =
= ∴ =
=∑
�
 
 
d) (5) Se representarmos a expressão para 02ka kk ppi ρ pi= , em função de ka , expoente 
do parâmetro p, então podemos ver que 1 3, 3.k ka a k k−= + − ≥ Então, 
( 3)( 3 1) ( 3)( 2)1 2 3 4 ( 3) , 3
2 2k
k k k k
a k k− − + − −= + + + + + − = = ≥� . 
Podemos ver que 2 0a = , e a expressão fornece o valor corretamente. Então, 
( 3)( 2)
2
02 , 2
k k
k p kpi ρpi
− −
= ≥ 
e) (5) Devemos usar Little, [ ] [ ]E N E Tβ= , onde E[N] é o número médio de pessoas na fila 
e β é a taxa média de chegada de pessoas que não desistem. 
2 3
0 1 2 3 4 5
1 2 3 4
1 0 1 0 1
0
1
0 1
2 2 2
2 (1 ) 2 2
[ ]
[ ]
2 2
i
i
i
i
p p p
E N i
i
E T
β λpi λpi λpi λ pi λ pi λ pi
µpi µpi µpi µpi
µpi µ pi pi µ µpi µpi
pi
pi
µ µpi µpi
∞
=
∞
=
= + + + + + +
= + + + +
= + − − = − −
=
∴ =
− −
∑
∑
�
�