Processos Estocásticos aplicados à Computação
Prof. Magnos Martinello
Departamento de Informática-DI/CT-UFES
Lista de Exercı́cios
Considere a cadeia de Markov homogênea cujo diagrama de estados é dado pela Figura 1.
Figura 1: Cadeia de Markov discreta
1. Determine a matriz de probabilidades de transição P;
2. Sob que condições a cadeia será irredutı́vel e aperiódica?
3. Para que valores de α e p, ocorrerá a condição π1 = π2 = π3 ?
4. Dado que o sistema está no estado 2, qual a probabilidade do sistema estar no estado 2 em 4 passos ?
5. Qual a probabilidade do sistema estar no estado 2 em regime estacionário (no limite) ?
2) Considere um sistema de filas modelado pelo processo de chegada cuja taxa de chegada é λk = (k + 1)α;
para k ≥ 0 e cuja taxa de serviço é µk = k 2 β; para k ≥ 1.
1. Determine a probabilidade de haver k clientes no sistema Πk ;
2. Probabilidade do sistema estar ocioso Π0 ;
3. Determine a taxa média de chegadas λ =
P∞
k=0
λ k × Πk ;
3) Considere um sistema de filas onde a capacidade de serviço é infinita M/M/∞. Neste sistema, todos
os clientes que chegam são atendidos imediatamente. A taxa de serviço é n*µ quando existem n clientes no
sistema. Usando um modelo tradicional de Nascimento e Morte, desenhe o diagrama de transição de estados
para esse sistema e obtenha expressões para;
1. Probabilidade de haver n clientes no sistema Πn ;
2. Probabilidade do sistema estar ocioso Π0 ;
3. Número Médio de clientes no sistema;
4. Tempo médio de espera no sistema.
5. Vazão.
6. Utilização.
4) Seja Xn a variável aleatória que representa o máximo valor obtido após o n-ésimo arremesso de um dado
honesto.
1. Mostre que Xn ; n=1,2,... é uma Cadeia de Markov;
2. Determine a matriz de probabilidades de transição P;
3. Esta cadeia será irredutı́vel e aperiódica ?
1
5) Considere um sistema de filas cujos tempos de serviço são exponencialmente distribuı́dos, com média
1/µ. Suponha que a população é composta de apenas um usuário. Neste caso, o único usuário pode estar em
um dos seguintes estados: (i) sendo atendido, ou (ii) ”chegando”ao sistema. Uma vez no estado (ii), o tempo
decorrido até que o usuário demande serviço (chegue ao sistema) é uma variável aleatória exponencial com
média 1/λ. Determine a probabilidade de haver k clientes no sistema Πk em um instante t qualquer (i.e. em
regime estacionário);
6) Compare o Tempo Médio de Resposta (E[W ] ou R) em um modelo de fila M/M/1 tendo chegadas a
uma taxa média λ e serviços a uma taxa média 2µ com i) um modelo de fila M/M/2 com taxa de chegada λ e
cada servidor tem taxa de serviço µ e ii) um modelo composto por duas filas M/M/1 onde a carga é dividida
igualmente e chegadas acontecem a uma taxa λ/2 e serviços ocorrem a uma taxa µ.
1. Mostre os resultados obtidos para o Tempo Médio de Resposta (E[W ]) em ordem crescente, do melhor
para o pior.
2. O tempo médio de espera na fila (E[WQ ]) é definido como (E[WQ ] = E[W ] − E[S]), onde E[S] é definido
como o tempo médio de serviço. Mostre os resultados obtidos para o Tempo Médio de espera (E[WQ ])
em ordem crescente, do melhor para o pior.
7) Every second, a 100 bit packet arrives to a queue at rate 1000b/s. The maximum departure rate is 500b/s.
What is the average occupancy of the queue?
Solution: During each 1s cycle, the queue fills at rate 500b/s for 0.1s, then drains at rate 500b/s for 0.1s. Over
the first 0.2s, the average queue occupancy is therefore 0.5 × (0.1 × 500) = 25 bits. The queue is empty for 0.8s
every cycle, and so average queue occupancy: Q(t) = (0.2 × 25) + (0.8 × 0) = 5
2