pe-gab

Prévia do material em texto

PE - MAB515 - 2012-2
5 de marc¸o de 2013
130 pontos
Aluno: GABARITO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Questa˜o: Escolha aleato´ria (10 pontos)
Num shopping sa˜o dados coupons para as pessoas colocarem num sorteio, o nu´mero de coupons variando de acordo
com o valor da compra. As pessoas ricas gastam muito e recebem 10 coupons. A classe me´dia gasta menos e recebe
5 coupons. A classe mais pobre gasta pouco e recebe apenas 1 coupon. A populaca˜o rica corresponde a 20% dos que
visitam o shopping, a classe me´dia corresponde a 30% e a classe pobre a 50%. Quais as probabilidades do sorteado
ser uma pessoa rica, de classe me´dia ou pobre?
Dica: Em filas, vimos que a pdf do intervalo selecionado (varia´vel conto´nua) e´ dada por fXs = xfX(x)/E[X ].
Voceˆ pode pensar em termos de varia´vel discreta e aplicar ao problema proposto ou resolver probabilisticamente por
outro racioc´ınio.
Soluc¸a˜o
Podemos resolver pensando probabilisticamente. Se N pessoas va˜o ao shopping, o nu´mero de coupons de pessoas
ricas depositado na urna e´ dado por N.0, 20.10 = 2N , o nu´mero de coupons da classe me´dia e´ N.0, 30.5 = 1, 5N e
da classe pobre e´ 0, 50N . O total de coupons e´ 4N . Asssim, P(rico) = 2/4 = 0,50 , P(me´dia) = 1,5/4 = 0,375 e
P(pobre) = 0,5/4 = 0,125.
Aplicando a ide´ia do intervalo selecionado, temos E[nu´mero de coupons por pessoa] = 10 x0,20 + 5x0,3 + 0,5=
4. P(rico) = 10x 0,20/4 = 0,50, P(me´dia) = 5 x 0,30/4 = 0,375, P(pobre) = 0,50/4 = 0,125.
1
2 Questa˜o: M/G/1(20 pontos) (per´ıodo ocupado, T.Z., T.L.)
Um sistema processa tarefas que chegam segundo um processo Poisson com taxa λ e que sa˜o servidas FCFS, uma
a uma. O tempo de execuc¸a˜o de cada tarefa e´ uma v.a. X , com X∗(s) conhecida. Neste sistema, um processo de
backup e´ somente iniciado quando o sistema esta´ ocioso. O backup e´ um processo de baixa prioridade que dura um
tempo fixo de b segundos e somente roda quando na˜o ha´ tarefas no sistema. Quando o processo de backup esta´
rodando e uma tarefa chega, o backup e´ interrompido e, somente retoma de onde parou, quando na˜o mais existirem
tarefas para serem processadas. Seja K o nu´mero de interrupc¸o˜es que sofre o backup durante seu processamento.
Seja Y o tempo transcorrido desde o in´ıcio do backup ate´ o seu te´rmino.
a) (5) Calcule E[K].
b) (5) Qual o tempo me´dio entre o instante que o backup e´ interrompido ate´ ele retomar a execuc¸a˜o?
c) (5) Calcule E[Y ].
d) (5) Calcule Y ∗(s).
Soluc¸a˜o
a) (5) E[K] = λb, pois e´ o nu´mero me´dio de chegadas Poisson em b.
b) (5) A cada interrupc¸a˜o, o backup fica parado esperando o te´rmino do per´ıodo ocupado. Logo, o tempo me´dio de
interrupc¸a˜o e´ dado por E[G] = E[X ]/(1− ρ), onde E[X ] = −X∗
′
(0) e ρ = λE[X ].
c) (5) E[Y ] = b+ λbE[G] = b/(1− ρ). E[Y ] pode ser visto como um per´ıodo ocupado iniciado por b fixo.
d) (5) Y = b+G1+G2+ · · ·GK . Enta˜o, Y
∗(s) = E[e−sY ] = e−sbK(G∗(s)), onde K(z) = e−λ(1−z)b representa a T.Z.
do nu´mero de interrupc¸o˜es sofridas pelo backup ao longo de seu processamento. Assim, Y ∗(s) = e−sbe−λ(1−G
∗(s))b =
e−(s+λ−λG
∗(s))b .
Como Y pode ser visto como um per´ıodo ocupado iniciado por b fixo, e lembrando que a T.L. de um intervalo
fixo e´ dada por e−sb, a fo´rmula resulta imediatamente da T.L. da pdf do per´ıodo ocupado modificado G∗0(s) =
X∗0 (s+ λ− λG
∗(s)).
2
3 Questa˜o: Sistema de Recomendac¸a˜o (CMTD) (30 pontos)
Considere o seguinte conjunto de pa´ginas, onde as transic¸o˜es indicam os saltos poss´ıveis entre pa´ginas.
p1
p2
p3
p4
a) (5) Desenhe a CMTD que caracteriza o comportamento de um surfista que, ao sair de uma pa´gina, ele escolhe
de forma uniforme e aleato´ria entre os possiveis destinos (veja diagrama de transic¸a˜o).
b) Um usua´rio gostou da pa´gina 1, e deseja-se recomendar uma nova pa´gina, dentre as pa´ginas 2 e 3. A pa´gina a
ser recomendada e´ aquela que primeiro sera´ alcanc¸ada por um surfista aleato´rio que inicie seu passeio em 1. Ha´ pelo
menos duas maneiras de determinar qual a pa´gina sera´ primeiro alcanc¸ada pelo surfista, dentre as pa´ginas 2 e 3.
b1) (5) Calcule as probabilidades associadas aos eventos:
P{alcanc¸ar 2 antes de 3 sem retornar a 1}, P{alcanc¸ar 3 antes de 2 sem retornar a 1} e P{retornar a 1 sem passar
por 2 ou 3}.
Depois de calcular estas probabilidades numericamente, calcule a probabilidade da pa´gina recomendada ser a 2.
b2) (5) Mostre como usar CMTD para gerar a sua recomendac¸a˜o. Por este me´todo, calcule a probabilidade da
pa´gina a ser recomendada ser a 2. Fac¸a todos os passos.
c) O surfista inicia um novo passeio da pa´gina 1.
c1) (5) Quantas transic¸o˜es, em me´dia, para o surfista atingir a pa´gina 2? Voceˆ tera´ que calcular o valor nu´me´rico.
c2) (5) E para atingir a pa´gina 3? Se usarmos o nu´mero me´dio de transic¸o˜es para alcanc¸ar a pa´gina para balizar
nossa decisa˜o, qual pa´gina seria recomendada?
d) (5) Se visitarmos um nu´mero bem longo de paginas N , qual o nu´mero me´dio de visitas a`s pa´ginas 2 e 3? Se usar
probabilidades de estado em sua resposta, voceˆ tem que calcula´-las. A resposta somente pode ter N como varia´vel.
Se usarmos o maior nu´mero me´dio de visitas a cada pa´gina como crite´rio para recomendac¸a˜o, qual seria nesse caso
a pa´gina recomendada?
3
Soluc¸a˜o
p1
p2
p3
p4
1/3
1/3
1/3
1
1/2
1/2
1/2
1/2
a) (5) Vide figura da CMTD.
b1) (5) Calculando as probabilidades dos seguintes eventos exclusivos:
P{alcanc¸ar 2 antes de 3 sem retornar a 1} = 1/2.1/3 = 1/6
P{alcanc¸ar 3 antes de 2 sem retornar a 1} = 1/2 + 1/2.1/3 =4/6
P{retornar a 1 sem passar por 2 ou 3} = 1/2.1/3 = 1/6
Enta˜o, P{alcanc¸ar 2 primeiro saindo de 1} = 1/61/6+4/6 = 1/5 e a P{alcanc¸ar 3 primeiro saindo de 1} = 4/5.
b2) (5) Construa uma cadeia modificada onde, ao se alcancar um dos estados E3 ou E2, retornamos a E1 com
probabilidade 1. Enta˜o, para esta cadeia o nu´mero de transic¸o˜es que retornam por E2 e por E3 sera˜o dadas por
pi∗2/(pi ∗2 +pi
∗
3) e pi
∗
3/(pi
∗
2 + pi
∗
3) . Calculando estes valores obtemos pi
∗
2 = 1/14 e pi
∗
3 = 4/14, indicando que a probabili-
dade de se alcanc¸ar o estado E2 primeiro e´ 1/5 e o estado E3 primeiro e´ 4/5.
p1
p2
p3
p4
1/3
1/3
1/3
1
1/2
1/2
1
c) O tempo para atingir as pa´ginas 2 e 3, respectivamente, pode ser calculado usando as cadeias modificadas
abaixo.
p1
p2
p3
p4
1/3
1/3
1/3
1
1/2
1/2
1/2
1/2
p1
p2
p3
p4
1/3
1/3
1/3
1
1/2
1/2
1
c1) (5) A soluc¸a˜o estado estaciona´rio da primeira cadeia e´ (1/3, 1/10, 4/15, 3/10), logo 1/pi2 = 10.
c2) (5) Enquanto que a soluc¸a˜o estado estaciona´rio da segunda e´ (4/11, 1/11, 3/11, 3/11), logo 1/pi3 = 11/3, e a
pa´gina 3 seria a recomendada, como anteriormente.
d) (5) Resolvendo a cadeia original, obtemos (6/20, 1/20, 10/20, 3/20) para o vetor de estado estaciona´rio. Como
o nu´mero me´dio de visitas a Ei e´ dado por piiN , enta˜o a pa´gina recomendada seria a 3, por ter maior probabilidade
de ocorreˆncia. O sistema de equac¸o˜es a ser resolvido e´ dado abaixo:
(1) pi1 = pi3/2 + pi4/3
(2) pi2 = pi4/3
(3) pi4 = pi3/2 + pi2 + pi1/2
(4)
∑3
i=1 pii = 1
4
4 Questa˜o: Fila M/M/1 com Intervalo de Fe´rias U´nico (CMTC, T.Z.,
Eventos exponenciais) ( 60 pontos)
Considere uma fila FCFS que entra num intervalo u´nico de fe´rias apo´s o per´ıodo ocupado. O intervalo de fe´rias dura
um per´ıodo exponencialmente distribu´ıdo com me´dia 1/γ. Apo´s o te´rmino das fe´rias, o servidor imediatamente inicia
o per´ıodo ocupado atendendo os clientes pendentes, ou aguarda por novos clientes e inicia o atendimento assim que
o primeiro cliente chegar. Clientes chegam de acordo com um processoPoisson com taxa λ e o tempo de servic¸o de
um cliente e´ exponencialmente distribu´ıdo com me´dia 1/µ.
a) (5) Qual a T.Z. da pmf do nu´mero de clientes que chega nas fe´rias? Na˜o precisa demonstrar.
b) (5) Seja K o nu´mero de pessoas que chegam durante o intervalo de fe´rias.
Calcule pk = P (K = k), k ≥ 0, a probabilidade de que cheguem k clientes durante o intervalo de fe´rias.
Dica: Voceˆ pode usar a propriedade da transformada Z ou pode deduzir probabilisticamente, pensando na sequeˆncia
de ocorreˆncia de eventos exponenciais simultaˆneos (te´rmino das fe´rias e chegada de clientes).
c) (5) Calcule E[periodo ocioso | K=0]. Atenc¸a˜o: Eventos exponenciais em paralelo.
d) (5) Calcule E[periodo ocioso | K=k]. Atenc¸a˜o: Eventos exponenciais em paralelo.
e) (5) Use os resultados anteriores para mostrar que o per´ıodo ocioso me´dio vale 1γ +
γ
λ(λ+γ) .
f) (5) Deˆ uma interpretac¸a˜o para esta expressa˜o do per´ıodo ocioso me´dio, indicando fatores e seu significado, e
mostre como ela poderia ser deduzida sem ca´lculos a partir de considerac¸o˜es probabil´ısticas. Use a expressa˜o dada,
caso voceˆ na˜o tenha conseguido chegar a ela. Se na˜o conseguiu, os valores para as esperanc¸as condicionais ou para
pk podem estar errados. Se tiver tempo, reveja.
g) (5) Desenhe uma CMTC para o sistema, usando exatamente os estados definidos a seguir:
estado 0 = sistema ocioso com 0 pessoas, aguardando a chegada de cliente.
estado Fi, i ≥ 0 = em fe´rias e i pessoas esperando.
estado i, i ≥ 1 = i pessoas no sistema ocupado, uma em servic¸o e o restante na fila de espera.
h) (5) Indique o tempo me´dio gasto na visita a cada estado desta cadeia, ou seja, deˆ as expresso˜es paraE[Ti]eE[TFi ], i ≥
0 . Dica: Observe que o sistema ao ficar ocioso ele tem que percorrer certos estados antes de entrar no per´ıodo ocu-
pado.
i) (5) Usando a cadeia acima, indique como calcular o tempo me´dio que um cliente permanece no sistema.
j) (5) Pode-se substituir os estados Fi por um u´nico estado F , representando o intervalo de fe´rias. Fac¸a isso e
constru uma nova cadeia usando as probabilidades pk (deixe indicado, sem substituir o valor) para definir as taxas
de transic¸a˜o deste estado F para os outros estados 0, 1, 2, · · ·, permanecendo o significado destes estados como antes.
Atenc¸a˜o: Para corretude, e´ necessa´rio que o tempo me´dio gasto neste estado F seja E[Tf ] =
1
γ .
k) (5) Escreva o sistema de equac¸o˜es que permita achar a distribuic¸a˜o de probabilidades em estado estaciona´rio do
nu´mero de clientes no sistema.
l) (5)Indique, passo a passo, como calcular a durac¸a˜o me´dia de um per´ıodo ocupado do sistema considerado.
5
Soluc¸a˜o
a) (5) A T.L. da pdf do intervalo de fe´rias e´ dada por F ∗(s) = γγ+s e a T.Z da pmf do nu´mero de chegadas durante
este intervalo sera´ K(z) = F ∗ (λ− λz) = γ/(γ + λ− λz).
b) (5) A probabilidade de chegarem k clientes e´
(
γ
γ+λ
)(
λ
γ+λ
)k
. λγ+λ expressa a probabilidade de ocorrer uma chegada
antes do te´rmino das fe´rias. Como as varia´veis exponenciais sa˜o sem memo´ria, a partir desta chegada, a probabilidade
de ocorrer uma segunda chegada antes do te´rmino das fe´rias tem este mesmo valor e, assim sucessivamente, ate´
chegarem k clientes no periodo de fe´rias. A probabilidade das fe´rias acabarem antes da chegada do cliente k + 1 e´
dada por γγ+λ .
Pelas propriedades da transformada Z, sabemos que
P (K = k) =
1
k!
dk
dzk
K(z) |z=0=
1
k!
dk
dzk
(
γ
γ + λ− λz
)
=
1
k!
k!γλk
(γ + λ− λz)k+1
|z=0
=
(
γ
γ + λ
)(
λ
γ + λ
)k
c) (5) E[ocioso | K = 0] = 1γ+λ +
1
λ .
d) (5) E[ocioso | K = k] = k+1γ+λ , k ≥ 1.
e) (5) E[ocioso] =
∑
∞
k=0 E[ocioso | K = k]pk.
E[ocioso] =
(
1
γ + λ
+
1
λ
)
+
∞∑
k=1
k + 1
γ + λ
(
γ
γ + λ
)(
λ
γ + λ
)k
=
(
1
γ + λ
+
1
λ
)
+
γ
(γ + λ)2
∞∑
k=1
(k + 1)
(
λ
γ + λ
)k
=
(
1
γ + λ
+
1
λ
)
+
γ
(γ + λ)2
d
dβ
∞∑
k=1
βk+1
=
(
1
γ + λ
+
1
λ
)
+
γ
(γ + λ)2
d
dβ
(
β2
∞∑
k=1
βk−1
)
=
(
1
γ + λ
+
1
λ
)
+
γ
(γ + λ)2
d
dβ
(
β2(1− β)−1
)
=
(
1
γ + λ
+
1
λ
)
+
γ
(γ + λ)2
(
2β(1− β)−1 + β2(1− β)−2
)
=
(
1
γ + λ
+
1
λ
)
+
γ
(γ + λ)2
(
λ(λ + 2γ)
γ2
)
=
(
1
γ + λ
+
1
λ
)
+
λ(λ+ 2γ)
γ(γ + λ)2)
=
1
(γ + λ)2
(
γ +
λ(λ + 2γ)
γ
)
+
γ
λ(γ + λ)
=
γ2 + 2γλ+ λ2
γ(γ + λ)2
+
γ
λ(γ + λ)
=
1
γ
+
1
λ
γ
γ + λ
6
f) (5) O per´ıodo ocioso sera´ constitu´ıdo de pelo menos o intervalo de fe´rias, com duraca˜o me´dia 1γ . Ao final deste
intervalo, caso na˜o tenha chegado ningue´m, com probabilidade γγ+λ , e´ preciso aguardar a chegada de um cliente, o
que acontece em me´dia com 1λ .
g) (5) Taxas de transic¸a˜o entre estados:
q1,F0 = µ
qi,i+1 = λ, qFi,i = γ, i ≥ 0
qi+1,i = µ, qFi,Fi+1 = λ, i ≥ 1
h) (5) Direto da CMTC, temos: E[T0] =
1
λ ;E[Ti] =
1
λ+µ , i ≥ 1;E[TFi ] =
1
γ+λ , i ≥ 0. O tempo me´dio gasto num
estado e´ o inverso da soma das taxas de sa´ıdas do estado. Aqui vale observar que todos os estados do intervalo de
fe´rias possuem o mesmo tempo me´dio de visita 1γ+λ , ja´ que tanto na ocorreˆncia de uma chegada como no fim das
fe´rias temos dois eventos exponenciais ocorrendo em paralelo, e a ocorreˆnicia de qualquer de um deles sera´ sempre
em me´dia num tempo igual ao inverso da soma da taxas.
k) (5) Calculando o nu´mero me´dio de clientes E[N ] =
∑
∞
i=0 i(pii + piFi), o tempo me´dio e´ E[T ] = E[N ]/λ, usando
Little.
j) (5) Aqui pode-se observar que quando vamos para o estado F, o tempo me´dio de visita sera´ 1γ e poderemos iniciar
0 1 2 3 . . .
F
λ λ λ λ
µ
µ
p0 γ
µ
p1 γ
p2 γ p3 γ p4 γ
µ
um per´ıodo ocupado com probabilidade pk, k ≥ 1, trasicionando com taxa γpk para o estado k, ou podemos ir para
o estado 0 com taxa γp0 e aguardar a chega de um cliente, o que acontece com taxa λ.
k) (5) O sistema de equac¸o˜es independentes pode ser obtido a partir da igualdade de fluxo de entrada e sa´ıda em
qualquer superf´ıcie fechada, circundando um ou mais estados. Circundando cada estado ( a menos de 1) e usando a
conservac¸a˜o das probabilidades, obtemos:
λpi0 = p0γpiF
(λ+ µ)pi1 = λpi0 + µpi2 + p1γpiF
(λ+ µ)pi2 = λpi1 + µpi3 + p2γpiF
...
...
piF +
∞∑
i=0
pii = 1(indispensa´vel)
Observac¸a˜o:
Para calcular o nu´mero me´dio de pessoas nesta cadeia, e´ preciso calcular o nu´mero me´dio de pessoas em F. O tempo
7
me´dio gasto em F e´ dado por 1γ e o nu´mero me´dio de chegadas e´ dado por
λ
γ . Todavia, como as chegadas ocorrem de
forma uniformemente espalhada. Por exemplo, se durante as fe´rias chegaram k pessoas, enta˜o o intervalo de fe´rias
teve o tamanho me´dio de k+1γ+λ e a me´dia no nu´mero de pessoas no tempo seria
1+2+···+k
k+1 = k/2. Enta˜o, o nu´mero
me´dio de pessoas no estado F sera´ dado por λ2γ , para esta cadeia condensada.
l) (5) Para calcular a durac¸a˜o do me´dia do periodo ocupado, pode-se obeservar que a cadeia passa por ciclos a
cada retorno ao estado F, que coincide com o te´rmino do per´ıodo ocupado. Lembrando que o ciclo e´ formado
pela soma do per´ıodo ocioso e do per´ıodo ocupado , a duraca˜o me´dia do periodo ocupado pode ser dada por
E[ocupado] = E[RF ]− E[ocioso] =
E[TF ]
piF
− E[ocioso] = 1γpiF −
1
γ −
γ
λ(γ+λ) .
8