122
Teoria das Filas e Teoria das Filas e Aplicações Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Embed Size (px)

Citation preview

Page 1: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria das Filas e AplicaçõesTeoria das Filas e Aplicações

Celso C. Ribeiro

Reinaldo Vallejos

PETROBRAS

Novembro 1998

Page 2: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

ProgramaPrograma Teoria da probabilidade Variáveis aleatórias Distribuições discretas Distribuições contínuas Variáveis aleatórias conjuntas e probabilidade

condicional Teoria das filas Cadeias de Markov discretas

...

Page 3: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

ProgramaPrograma

… Cadeias de Markov de tempo contínuo Lei de Little Aplicações da Lei de Little Processos de nascimento e morte Filas M/M/1 Filas M/M/C Aplicações

Page 4: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Page 5: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Modelagem de fenômenos aleatórios quantidades não previsíveis antecipadamente variação inerente que deve ser considerada

Permitir que o modelo tenha natureza probabilística modelo probabilístico

Page 6: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Experimento cujo resultado não seja previsível antecipadamente

Espaço amostral: S = {resultados possíveis} Lançamento de uma moeda: S = {cara,coroa} Lançamento de um dado: S = {1,2,3,4,5,6} Lançamento de duas moedas: Acara,

Bcoroa S = {(A,A),(A,B),(B,A),(B,B)} Vida útil de um carro: S = [0,)

Page 7: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Evento: subconjunto E do espaço amostral S E = {cara}, E = {coroa} E = {2,4,6}: resultado do lançamento é par E = {(A,A),(A,B)}: primeira moeda é cara E = [1,2): carro dura pelo menos um ano sem

completar o segundo

Page 8: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Eventos E e F Evento união: EF Evento interseção: EF Evento vazio: E e F mutuamente exclusivos: EF =

E ={cara}, F ={coroa}: ou dá cara, ou dá coroa Evento complementar: Ec = S\E

Page 9: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Espaço S, evento E Probabilidade P(E) do evento E:

0 P(E) 1 P(S) = 1 E1E2 = P(E1E2) = P(E1) + P(E2)

P({cara}) = P({coroa}) = 1/2 Moeda viciada, com chance duas vezes maior

de dar cara: P({cara}) = 2/3, P({coroa}) = 1/3

Page 10: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

P({2,4,6}) = P({2}) + P({4}) + P({6}) = = 1/6 + 1/6 + 1/6 = 1/2

Page 11: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

P(Ec) = 1 - P(E)

1 = P(S) = P(EEc) = P(E) + P(Ec)

P(E) + P(F) = P(EF) + P(EF)

P(EF) = P(E) + P(F) - P(EF)

EF = P(EF) = P(E) + P(F) P(EFG) = P(E) + P(F) + P(G) - P(EF) - -

P(EG) - P(FG) + P(EFG)

FE

EF

EF

Page 12: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Probabilidade condicional: probabilidade de que um determinado evento ocorra, conhecendo-se a ocorrência de outro

Dois dados são lançados e todas os 36 pares de resultados são equiprováveis. Qual é a probabilidade da soma dos dois valores ser igual a 10?

P({4,6}) + P({5,5}) + P({6,4}) = 31/36 =1/12

Page 13: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Sabendo-se que a primeira observação é um 4, qual é a probabilidade da soma dos dois valores ser igual a 10?

Resultados possíveis, sendo 4 o primeiro valor: (4,1), (4,2), (4,3), (4,4), (4,5), (4,6)

Se o primeiro valor é 4, a probabilidade (condicional) de cada um destes pares é 1/6

Probabilidade dos 30 pares restantes: zero

Probabilidade da soma ser igual a 10: 1/6

Page 14: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Probabilidade condicional do evento E dado que o evento F ocorre:

P(E|F) = P(EF)/P(F)FE

EF

Page 15: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Uma moeda é lançada 2 vezes. Qual é a probabilidade condicional de que sejam observadas duas caras, dado que pelo menos uma cara é observada?

E = {(cara,cara)} = {(A,A)} cara A

F = {(A,B),(B,A),(A,A)}

P(E|F) = P(EF)/P(F) = P({(A,A)})/ P({(A,B),(B,A),(A,A)}) = (1/4)/(3/4) = 1/3

Page 16: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Uma urna contém sete bolas pretas e cinco bolas brancas. Duas bolas são retiradas. Qual a probabilidade de que ambas sejam pretas, considerando-se que a primeira bola não é devolvida para a urna após ser retirada?

F = primeira é preta E = segunda é preta

P(EF) = P(E|F) P(F) = 6/117/12 = 7/22

Page 17: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Uma urna contém sete bolas pretas e cinco bolas brancas. Duas bolas são retiradas. Qual a probabilidade de que ambas sejam pretas, considerando-se que, neste caso, a primeira bola é devolvida para a urna após ser retirada?

F = primeira é preta E = segunda é preta

P(EF) = P(E|F) P(F) = 7/127/12 = 49/144

Page 18: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Cada uma de três pessoas possui uma ficha de cor diferente que é lançada em uma urna. Em seguida, cada pessoa retira aleatoriamente uma ficha da urna. Qual é a probabilidade de que ninguém recupere sua ficha original?

Idéia: calcular a probabilidade do evento complementar, isto é, de que pelo menos uma pessoa recupere sua ficha original.

Page 19: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Ei: i-ésima pessoa recupera sua ficha; i=1,2,3

P(Ei) = 1/3, i=1,2,3

P(EiEj) = P(Ej|Ei) P(Ei) = 1/21/3 = 1/6 ij

P(E1E2E3) = P(E3|E1E2) P(E1E2) = 1/6

P(E1E2E3) = P(E1) + P(E2) + P(E3) - - P(E1E2) - P(E1E3) - P(E2E3) + + P(E1E2E3) = 3 1/3 - 3 1/6 + 1/6 = 2/3

P(ninguém recuperar) = 1 - 2/3 = 1/3

Page 20: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

E e F independentes: P(EF) = P(E) P(F)

P(E|F) = P(E)

P(F|E) = P(F)

Page 21: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Espaço amostral S, eventos E e F

E = ES = E(FFc) = (EF) (EFc)

EF e EFc mutuamente exclusivos

P(E) = P((EF)(EFc)) =

= P(EF) + P(EFc) =

= P(E|F) P(F) + P(E|Fc) P(Fc) =

= P(E|F) P(F) + P(E|Fc) (1-P(Fc))

Page 22: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

A primeira de duas urnas contém 2 bolas brancas e 7 bolas pretas, enquanto a segunda contém 5 brancas e 6 pretas. Uma moeda é lançada e uma bola é retirada da primeira ou da segunda urna, dependendo do resultado ter sido cara ou coroa, respectivamente. Qual é a probabilidade (condicional) de ter ocorrido uma cara, dado que a bola retirada foi branca?

Page 23: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Deseja-se calcular P(cara|branca)

P(cara|branca) = P(cara e branca) / P(branca) =

= P(branca|cara) P(cara) / P(branca)

P(branca) = P(branca|cara) P(cara) + + P(branca|coroa) P(coroa)

P(cara|branca) = = 2/91/2/(2/91/2+5/111/2) = 22/67

Page 24: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Um teste detecta com 95% de certeza uma determinada doença, quando ela está presente. Entretanto, este teste aponta “falsos positivos” em 1% das pessoas que não contraíram a doença. Sabendo-se que 0.5% da população estão contaminados por esta doença, qual é a probabilidade de que determinada pessoa tenha a doença dado que o resultado de seu teste foi positivo?

Page 25: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Deseja-se calcular P(doente|positivo)

P(doente|positivo) = P(doente e positivo) / / P(positivo) =

= P(positivo|doente) P(doente) / P(positivo)

P(positivo) = P(positivo|doente) P(doente) + + P(positivo|sadia) P(sadia)

P(doente|positivo) = 0.950.05/(0.950.005+0.010.995) = 95/294

Page 26: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Fórmula de Bayes:

eventos F1, F2, …, Fn mutuamente exclusivos

F1 F2 … Fn= S

P(E) = P(ES) = P(EF1) + … + P(EFn) =

= P(E|F1) P(F1) + … + P(E|Fn) P(Fn)

P(Fj|E) = P(EFj) / P(E) = P(E|Fj) P(Fj) / P(E)

P(Fj|E) = P(E|Fj) P(Fj) / / [P(E|F1) P(F1) + … + P(E|Fn) P(Fn)]

Page 27: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Sabe-se que determinada carta está em uma de três pilhas diferentes, com a mesma probabilidade. A probabilidade da carta ser encontrada examinando-se rapidamente a pilha em que ela realmente está é 20%. Suponha que a pilha 1 foi verificada, mas a carta não foi encontrada. Qual a probabilidade da carta efetivamente estar na pilha 1?

Page 28: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Teoria da probabilidadeTeoria da probabilidade

Fi: carta está na i-ésima pilha; i=1,2,3

E: carta não encontrada na pilha 1

Deseja-se calcular P(F1|E)

P(F1|E) = P(E|F1) P(F1) / / [P(E|F1)P(F1)+P(E|F2)P(F2)+P(E|F3)P(F3)]

P(F1|E) = 0.81/3 / (0.81/3 + 11/3 + 11/3)= = 0.8/2.8 = 2/7

Page 29: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

Page 30: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

Variável aleatória: função real definida sobre o espaço amostral soma dos valores obtidos após o lançamento de

dois dados número de caras após um certo número de

lançamentos de uma moeda tempo entre duas chegadas sucessivas a uma fila tempo de processamento de uma tarefa

Page 31: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

Valor de uma variável aleatória (v.a.) é determinado pela saída de um experimento é possível associar probabilidades aos valores que podem ser assumidos por uma

X: v.a. definida pela soma dos valores obtidos após o lançamento de dois dados

P{X=1} = P{} = 0

P{X=2} = P{(1,1)} = 1/36

P{X=3} = P{(1,2),(2,1)} = 2/36 = 1/18 ...

Page 32: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

Y: v.a. definida pelo número de caras observadas após dois lançamentos de uma moeda

P{Y=0} = P{(B,B)} = 1/4 Acara Bcoroa

P{Y=1} = P{(A,B),(B,A)} = 1/2

P{Y=2} = P{(B,B)} = 1/4

P{Y=0} + P{Y=1} + P{Y=2} = 1

Page 33: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

N: v.a. definida pelo número de lançamentos de uma moeda até aparecer a primeira cara, sendo p a probabilidade de observar-se cara em cada lançamento

P{N=1} = P{A} = p

P{N=2} = P{(B,A)} = (1-p)p

P{N=3} = P{(B,B,A)} = (1-p)2p

P{N=n} = P{(B,B,…,B,A)} = (1-p)n-1p

Page 34: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

Função de distribuição acumulada (fda) ou função de distribuição F(.) da v.a. X: F(b) = P{X b} - < b < +

F(b): probabilidade de que a v.a. X assuma um valor menor ou igual a b

Propriedades: F(b) é uma função não-decrescente de b limbF(b) = F() =1, limb-F(b) = F(-) = 0 p{a<Xb} = P{Xb} - P{Xa} = F(b) - F(a)

Page 35: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatóriasVariáveis aleatórias

Variáveis aleatórias discretas: a v.a. assume um número finito ou contável de valores possíveis.

Variáveis aleatórias contínuas: a v.a. assume valores dentro de um contínuo de valores possíveis.

Page 36: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatórias discretasVariáveis aleatórias discretas

Variáveis aleatórias discretas: a v.a. assume um número finito ou contável de valores possíveis.

Função de massa de probabilidade: p(a) = P{X=a}

Se X pode assumir os valores x1, x2,… então p(xi) > 0, i=1,2,…

p(x) = 0, outros valores de x

Page 37: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Função de distribuição acumulada: F(a) = p(xi)

Exemplo: p(1) = 1/2, p(2) = 1/3, p(3) = 1/6 0, a < 1,

F(a) = 1/2, 1 a < 2 5/6, 2 a < 3 1, 3 a

i=1,2,…: xi a

Variáveis aleatórias discretasVariáveis aleatórias discretas

Page 38: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatórias discretasVariáveis aleatórias discretas

1 2 3a

F(a)

1/2

15/6

Page 39: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Variáveis aleatórias discretasVariáveis aleatórias discretas

Seja X uma v.a. discreta. Então, seu valor esperado é dado por:

0)(:

)(.][Expx

xpxX

Page 40: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Funções de variáveis aleatóriasFunções de variáveis aleatórias

g(X) função da v.a. X

Caso discreto:

Caso contínuo:

Exemplo: a,b R

E[a.X+b] = a.E[X] + b

0)(:

)()()]([xpx

xpxgXgE

dxxfxgXgE )()()]([

Page 41: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Funções de variáveis aleatóriasFunções de variáveis aleatórias

Variância da v.a. X:

Pelo resultado anterior:

Logo,

]])[E[(E][VAR 2XXX

]][E][E.2[E][VAR 22 XXXXX 22 ][E][E].[E2][E][VAR XXXXX

22 ][E][E][VAR XXX

Page 42: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Funções de variáveis aleatóriasFunções de variáveis aleatórias

Variância da v.a. X:

22 ][E])[(E][VAR XXX

][E][E][E][VAR 22 XXXX 2222 ][E][E][VAR XXX

)][E][(E][VAR 222 XXX ][VAR][VAR 2 XX

Page 43: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Funções de variáveis aleatóriasFunções de variáveis aleatórias

X e Y variáveis aleatórias independentes:

)]([E)].([E)]()([E YhXgYhXg

][VAR][VAR][VAR YXYX

Page 44: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuições discretasDistribuições discretas

Page 45: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Um experimento de Bernoulli tem somente dois resultados aleatórios possíveis:

sucesso fracasso

A variável aleatória que corresponde ao experimento anterior é uma variável aleatória de Bernoulli.

A notação de uma distribuição de Bernoulli é Be(p), onde 0 p 1 é a probabilidade de obter-se sucesso.

Distribuição de BernoulliDistribuição de Bernoulli

Page 46: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Lançamento de uma moeda Caso obtenha-se uma cara: sucesso Caso obtenha-se uma coroa: fracasso

A direção que segue um veículo em uma bifurcação (caminho A ou B) Se segue o caminho A: sucesso Se segue o caminho B: fracasso

(o resultado deste experimento é uma v.a. somente para um observador externo, mas não para o condutor)

Distribuição de BernoulliDistribuição de BernoulliExemplosExemplos

Page 47: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

X v.a. Be(p) (X é uma variável aleatória discreta do experimento de Bernoulli de parâmetro p).

Domínio de X: X {0, 1}

Função de massa de probabilidade: P{X = 0} = P(0) = 1 - p

P{X = 1} = P(1) = p

Distribuição de BernoulliDistribuição de Bernoulli

Os resultados possíveis deste experimento podem ser “mapeados” nos números reais, logo:

Page 48: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Função de distribuição acumulada:

Distribuição de BernoulliDistribuição de Bernoulli

)X()(0

xPhxFlimh

1

1 , 1)(

x1,

xpxF

0

Valor esperado: pppXE 0).1(1.}[

Page 49: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Função de distribuição acumulada

Distribuição de BernoulliDistribuição de BernoulliGráficosGráficos

Função de massa de probabilidade

F(X)

1

p

1-p

0 1 X

0 1 X

1-p

p

1

p(X)

E[X]

2 X

p

Graficos3D

Page 50: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Considerando as funções anteriores tem-se para Be(p):

Distribuição de BernoulliDistribuição de BernoulliParâmetrosParâmetros

E X p

VAR X p 1 p

p 1 p

z p z 1 1

E X p

X

n

Valor esperado

Variância

Desvio padrão

Função geradora de momento

n-ésimo momento

Page 51: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Um pacote de informações é enviado pelo transmissor ao receptor através de uma conexão, sendo p a probabilidade de que o pacote chegue corretamente ao receptor. info chega corretamente a R: X = 1 info não chega corretamente a R: X = 0

Distribuição de BernoulliDistribuição de BernoulliExemplo em comunicaçõesExemplo em comunicações

T Rinfo

Page 52: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomial

Considere n experimentos independentes identicamente distribuídos (iid), cada um com distribuição Bernoulli de parâmetro p.

Se a variável de interesse Y corresponde ao número de sucessos obtidos nestes n experimentos, então Y é conhecida como uma variável aleatória binomial de parâmetros n e p.

Page 53: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Sejam X1, X2, …, Xn, onde as variáveis {Xi}, i=1,2,…,n são v.a.’s iid Be(p). Seja a v.a. Y definida por sua soma:

Distribuição binomialDistribuição binomial

n

iiXY

1

Y Bi(n, p)

Page 54: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomial

Uma distribuição binomial de parâmetros n e p se denota Bi(n,p), onde: n é o número de experimentos de Bernoulli

independentes realizados. p é a probabilidade de obter um sucesso em

cada um dos n experimentos, 0 p 1.

Page 55: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Uma moeda é lançada n vezes. Se em cada lançamento se obtém cara (sucesso) com probabilidade p, qual é a probabilidade de que em 0 i n experimentos se obtenha sucesso?

Observam-se n veículos em uma bifurcação. Cada veículo segue o caminho A (sucesso) com probabilidade p. Qual é a probabilidade de que 0 i n veículos sigam o caminho A (sucesso)?

Distribuição binomialDistribuição binomialExemplosExemplos

Page 56: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Seja Y v.a. Bi(n,p) (Y é v.a. binomial de

parâmetros n e p), onde n N+ e 0 p 1 Domínio de X:

Y {0, 1, 2, …, n} Função de massa de probabilidade:

Distribuição binomialDistribuição binomial

Função de distribuição acumulada:

nippi

niPiYP in i

0 , )1()(}{

nip ipj

niYP

jnji

j

0 , }{

0

Page 57: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Valor esperado:

E[X]=

=

=

Seja k=i-1, então E[X]=

Como então, E[X]=np

n

i

inn

i

i ppi

niiip

0 0)1()(

inin

ipp

iinn

)1(

)!1()!(!

1

npn

n i ip p

i

ni n i

1

11

11

( )!

( )!( )!( )( )

knkn

kpp

k

nnp

11

0)1(

1

kn k n kn

kp p0

1 111 1( )

Distribuição binomialDistribuição binomial

Page 58: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Considerando-se as funções anteriores tem-se para Bi(n, p):

Distribuição binomialDistribuição binomialParâmetrosParâmetros

E Y np

VAR Y np 1 p

np 1 p

z p z 1 1

E Y

Y

k

Valor esperado

Variância

Desvio padrão

Função geradora de momento

n-ésimo momento

n

1 (k)

Page 59: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Observando-se a esperança e a variância da distribuição binomial se verifica que correspondem à soma de v.a.’s iid com distribuição de Bernoulli.

A transformada Z de uma fmp corresponde à sua função geradora de momento:

Distribuição binomialDistribuição binomial

][)

; )(010

XEnPdz

dP(z zPzP

nn

zn

nn

Page 60: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Função de massa de probabilidade Bi(10,0.7)

0

0.1

0.2

0.3

0 5 10y

P(Y

= y

)

2Y

E[Y]

Distribuição binomialDistribuição binomialGráficosGráficos

Y = 1.449

E[Y]=7

Graficos3D

Page 61: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomialGráficosGráficos

Função de massa de probabilidade Bi(10,0.5)

0

0.1

0.2

0.3

0 2 4 6 8 10 12

x

P(X

=x)

Função de distribuição acumulada Bi(10,0.5)

0

0.5

1

1.5

0 2 4 6 8 10 12

x

P(X

<=

x)

Page 62: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomialGráficosGráficos

Função de massa de probabilidade Bi(10,0.7)

0

0.1

0.2

0.3

0 2 4 6 8 10 12

x

P(X

=x)

Função de distribuição acumulada Bi(10,0.7)

0

0.5

1

1.5

0 2 4 6 8 10 12

x

P(X

<=

x)

Page 63: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomialGráficosGráficos

Função de massa de probabilidade Bi(10,0.5)

0

0.1

0.2

0.3

0 2 4 6 8 10 12

x

P(X

=x)

Função de distribuição acumulada Bi(10,0.5)

0

0.5

1

1.5

0 2 4 6 8 10 12

x

P(X

<=

x)

Page 64: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomialGráficosGráficos

Função de massa de probabilidade Bi(15,0.5)

00.050.1

0.150.2

0.25

0 5 10 15 20x

P(X

=x)

Função de distribuição acumulada Bi(15,0.5)

0

0.5

1

1.5

0 5 10 15 20

x

P(X

<=

x)

Page 65: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

01

23

45

67

89

10

p=0.1

p=0.3

p=0.6

p=0.9

0

0,05

0,1

0,15

0,2

0,25

0,3

0,35

0,4

Bi (10,p)

i

Bi (10,p)

Graficos3D

Page 66: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Com relação à fmp de uma binomial tem-se que: valor máximo se encontra em X = E[X] = np estritamente decrescente para X > E[X] simétrica em relação a p (e.g., p = 0.1 e p = 0.9)

Pelo teorema do limite central: a v.a. da soma infinita de experimentos independentes

(com qualquer distribuição) tende à distribuição gaussiana

Distribuição binomialDistribuição binomial

Page 67: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

n pacotes de informação são enviados pelo transmissor ao receptor através de uma conexão. A probabilidade de cada um dos pacotes chegar corretamente a R é igual a p. Qual é a probabilidade de que 0 i n pacotes de informação enviados cheguem corretamente ao receptor?

Distribuição binomialDistribuição binomialExemplo em comunicaçõesExemplo em comunicações

T Rinfon info2 info1...

Page 68: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

n: número de pacotes enviados

p: probabilidade de cada pacote chegar corretamente

Y = i: número de pacotes enviados que chegarão corretamente, 0 i n

Y v.a. ~ Bi(n,p), n {0,1,2,3, ...}

Distribuição binomialDistribuição binomialExemplo em comunicaçõesExemplo em comunicações

T Rinfon info2 info1...

nippi

niPiYP in i

0 , )1()(}{

Page 69: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Vários computadores executam um mesmo algoritmo. O resultado final do algoritmo se determina por votação dos computadores, por maioria simples. Por exemplo, se o resultado de dois ou mais computadores coincide, então esse é o resultado final. Cada computador tem probabilidade de falha igual a 1-p. Para que valores de p convém escolher 1, 3 ou 5 computadores?

Distribuição binomialDistribuição binomialExemplo em tolerância a falhasExemplo em tolerância a falhas

Page 70: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

n: número total de computadoresX: número de computadores funcionando corretamente (fornecem o resultado correto)X v.a. ~ Bi(n,p), n {1,3,5}Por exemplo: probabilidade de sucesso do sistema com n computadores (maioria proporciona o resultado correto)m = ((n-1)/2)+1: número mínimo de computadores (n ímpar) que devem dar o resultado correto para o sistema ter sucesso

Distribuição binomialDistribuição binomialExemplo em tolerância a falhasExemplo em tolerância a falhas

Page 71: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Para n {1,3,5}:

Caso n = 1

Caso n = 3

Caso n = 5

Distribuição binomialDistribuição binomialExemplo em tolerância a falhasExemplo em tolerância a falhas

Pe = (3

2) p2(1-p) +(3

3)p3

3

Pe = p1

Pe = (5

3) p (1-p) +(5

4)p43 2(1-p) +(5

5)p5

5

n

mi

ini ppi

nmXP )1()(

Page 72: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição binomialDistribuição binomialExemplo em tolerância a falhasExemplo em tolerância a falhas

Probabilidade de sucessoProbabilidade de sucesso

0

0.2

0.4

0.6

0.8

1

1.2

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1Probabilidade de sucesso de cada

computador

Pro

ba

bil

ida

de

de

su

ce

ss

o

do

sis

tem

a

Pe1

Pe3

Pe5

Page 73: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

Considere n experimentos de Bernoulli independentes, cada um com probabilidade de êxito p

X v.a. Ge(p) representando o número de tentativas até conseguir o primeiro êxito

Função de massa de probabilidade:

Função de distribuição:

,2,...1 n pp1npnXP 1n

pp)-(1 F(n) 1-kn

1k

Page 74: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Valor esperado:

E[X]=

Fazendo q = 1 - p:

E[X] = =

= =

=

Logo, E[X]=

n

nn p p1

11( )

pd

dqq

n

n

1( ) p

d

dqq

n

n

1

pd

dqq q

k

k

0p

d

dq

q

q1

p

q( )1 2

p1

Distribuição geométricaDistribuição geométrica

Page 75: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

Exemplo: lançar a moeda até o primeiro êxito Êxito = cara Fracasso = coroa

Exemplo: número de automóveis não específicos até que um siga o caminho A da bifurcação Êxito = A

Fracasso = B

Experimentos independentes

Page 76: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

0 5 10 15 20 25

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1F(n)

n

Função de distribuição

Função de massa de probabilidade

p=0.6

n0 5 10 15 20 25

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1F(n)

Função de distribuição

Função de massa de probabilidade

p=0.2

Page 77: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

p = 0.3

0

0,05

0,1

0,15

0,2

0,25

0,3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

p = 0.3

0

0,05

0,1

0,15

0,2

0,25

0,3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

p(n)

nE[X]

E[X]=3,33

x=2.79

Page 78: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

Função de massa para distintos valores de p

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1 2 3 4 5 6 7 8 9 10n

p(n

)

0.1

0.5

0.9

Page 79: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

1 3 5 7 9 11 13 15 17 19

0.1

0.3

0.5

0.7

0.9

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

P{X=n}

n

p

Page 80: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica

2 3 4 5 6 7 8 9 10 11 12 13 1415

0

0,2

0,4

0,6

0,8

1

0

0,05

0,1

0,15

0,2

0,25

n

p

P{X=n}

Page 81: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométrica P{X=n} decai mais rápidamente com n quando p

aumenta Distribuição em função de p varia com n:

para n = 1 é una reta crescente para n < 7 é crescente e logo decresce para n 7 é decrescente

Função de massa tem dois pontos degenerados: p = 0: necessárias infinitas tentativas (nunca se consegue

êxito) p = 1: êxito sempre é conseguido na primeira tentativa.

Page 82: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição geométricaDistribuição geométricaParâmetrosParâmetros

E X1

p

VAR X1 p

p

1

p1 p

tpe

1 1 p e

2

X

t

t

Page 83: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Propriedade: falta de memóriaPropriedade: falta de memória

Elevador em um prédio de três andares

Estado #n : elevador no andar n

Sem memória: estados #1 e #3

Com memória: estado #2

Page 84: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Propriedade: falta de memóriaPropriedade: falta de memória

Exemplo relacionado com a distribuição geométrica, duas situações equivalentes:

Page 85: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Propriedade: falta de memóriaPropriedade: falta de memória

Distribuição geométrica caracterizada pela seguinte propriedade:

A informação de nenhum sucesso até a tentativa t é “esquecida” nos cálculos subseqüentes.

sxPt>x|tsxP

Page 86: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Propriedade: falta de memóriaPropriedade: falta de memória

Page 87: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Propriedade: falta de memóriaPropriedade: falta de memória Demonstração:

Logo,

txP

tsxPtx |t sxP

txP

txtsxPtx |t sxP

Page 88: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Propriedade: falta de memóriaPropriedade: falta de memória

Substituindo-se

Logo,

com

portanto

P x s t 1 p p 1 p

P x t 1 p p 1 p

i s t

i 1s+t 1

i t 1

i 1t

1st

1ts

p1p1

p1tx|tsxP

P x s 1 p p 1 pi s

i 1s 1

P x s t x > t P x s | propriedade de falta de memória

Page 89: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Protocolo Stop & WaitProtocolo Stop & Wait

Protocolo de retransmissão mais simples Idéia básica: ter certeza de que cada pacote

transmitido é recebido corretamente antes de transmitir o seguinte

Protocolo half-duplex Retransmissão devido a:

erro na recepção do pacote time-out

Page 90: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Protocolo Stop & WaitProtocolo Stop & Wait

Numeração de pacotes: Se ocorre time-out no transmissor, retransmite

pacote i Receptor não sabe distinguir se é uma

retransmissão do pacote i ou uma primeira transmissão do pacote i+1

Logo, necessidade de numerar os pacotes, assim como os acks/nacks

Numeração módulo 2 é suficiente

Page 91: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Esquema físicoEsquema físico

Definições:ti = tempo de transmissão de um pacote

tp = tempo de propagação

tout = tempo máximo de espera de um reconhecimento (ack/nack)

tproc = tempo de processamento do pacote

RxTx

t I

tP

tAck

Page 92: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Diagrama temporalDiagrama temporal

t

Tx

Rx

Caso 2Retransmissão por erro

t i

t p

Tx

Rx

ti

tp

t out

t

t

t

F1

F1

N1

F1

A1

F2

t proc Tx

F1

A1

F2

tproc Tx

Caso 1Retransmissão por time-out

t proc Rx

t proc Rx

Fi = transmissão do frame i

Ni = mensagem de frame i recebida com problemas

Ai = reconhecimento do frame i

Page 93: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Q0

Q1

Q2

Q3

-M0

+Error-M1

+Ack 1

+Ack 0

+Error

Q2

Q0

Q3

Q5

Q1 Q4

-Ack

-Error+M1

-Error

+M1

+M0

+M0 -Ack

Diagrama de transição de estados

Transmissor Receptor

Q0: Transmite Mensagem 0Q1: Espera Ack 0Q2: Transmite Mensagem 1Q3: Espera Ack 1

Q0: Espera Mensagem 0Q1: Transmite Ack 0Q2: Transmite ErroQ3: Espera Mensagem 1Q4: Transmite Ack 1Q5: Transmite Erro

+ : Entradas

- : Saídas

Page 94: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Tabelas de transição de estadosTabelas de transição de estados

ReceptorEstado Entrada Saída Prox. Estado

Q0 Mensagem 0 Q1Q0 Mensage m1 Q2Q1 Ack 0 Q3Q2 Erro Q0Q3 Mensagem 0 Q5Q3 Mensagem 1 Q4

Q4 Ack 1 Q0Q5 Erro Q3

TransmisorEstado Entrada Saída Prox. Estado

Q0 - Mensagem 0 Q1Q1 Ack 0 - Q2Q1 Erro - Q0Q2 - Mensagem 1 Q3

Q3 Ack 1 - Q0Q3 Erro - Q2

Error: Devido a erro de bits no frame,ou erro devido a Timeout

Q0: Transmite Mensagem 0Q1: Espera Ack 0Q2: Transmite Mensagem 1Q3: Espera Ack 1

Q0: Espera Mensagem 0Q1: Transmite Ack 0Q2: Transmite ErroQ3: Espera Mensagem 1Q4: Transmite Ack 1Q5: Transmite Erro

Page 95: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Medidas de desempenhoMedidas de desempenho

Desempenho pode ser avaliado sob dois pontos de vista: do usuário:

menor tempo de resposta menor buffer

do sistema: máximo throughput menor memória

Espaço Tempo

Usuário Buffer tempo deresposta

Sistema Memória Throughput

Page 96: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Máximo throughputMáximo throughput

Transmissor sempre dispõe de pacotes para transmitir

Time-out é o menor possível

Tout = 2Tp + Tack Existem erros

Pe > 0 existem retransmissões

Page 97: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Definições:

Ii = i-ésima tentativa de transmitir o pacote

tT = ti + tout = ciclo de operação

p = probabilidade de receber o pacote com erro

n = número de tentativas até transmitir um pacote

pa= probabilidade de transmissão correta na n-ésima tentativa

tu = tempo utilizado nas n tentativas

E[t] = tempo médio de recepção com sucesso (1)

t

I

p

T

1

t Tt Tt T

I 2 I 3 I n

(1-p)p p

t0

Page 98: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Diagrama de lógica temporalDiagrama de lógica temporal

F1 F1 F1 F1

1-p 1-p 1-p

p p p Errado Errado Errado Errado

Correto Correto Correto

t

p: probabilidade de erro no pacote

Page 99: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Máximo throughputMáximo throughput

Certamente,

Por definição de valor médio

Da figura anterior:

Como n é uma v.a. com distribuição Ge(1-p):

max [ ]

1

E t

Ttnt(n)(3)

(2) E[ t ] t n p nn 1

(4) p(n) p (1 p)n 1

Page 100: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Máximo throughputMáximo throughput

Substituindo-se (2), (3) e (4) em (1), obtém-se:

Simplificando (4):

Por definição:

E t[ ]

n t p 1 pT

n 1

n 1

pt

tE T

1][

ir tap

tp

tE )1()1(

][1

max 1i

T

tt

acom

Page 101: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Throughput normalizadoThroughput normalizado

tp

ai

11

0

0

p 1 - p 1 - pp p p T

T

Transmissão

Transmissãoefetiva

tlim

T

Tempo em transmissoes efetivas

Ti

Page 102: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Máximo throughputMáximo throughput

O throughput normalizado pode ser interpretado como a percentagem do tempo ocupado na transmissão efetiva de pacotes

Se o tempo para receber um ack ou um nack é desprezível, também o é o time-out:

a = 1 = (1- p)

Page 103: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

a=1 : Rede da área locala=3 : Rede com enlaces menores a 500 Kma=10 : Rede de enlace satelital

ap

max=F(p,a)

Page 104: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

max=F(p,a)

a=1,8

a=2,1

a=1,4a=1

Page 105: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

max=F(p,a)p=0

p=0.2

p=0.4

p=0.6

Page 106: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição de PoissonDistribuição de Poisson

X v.a. discreta com domínio e com a seguinte função de massa de probabilidade:

X: distribuição de Poisson com parâmetro

Função de distribuição de probabilidade:

P X = i = i!

i

e , i 0

P X n = i!

i

e , i

n

n0

0

Page 107: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

00,020,040,060,080,1

0 5 10 15 20 25 30 35 40

i

P{X

=i}

Distribuição de PoissonDistribuição de Poisson Função de massa de probabilidadeFunção de massa de probabilidade

Page 108: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

0

0,2

0,4

0,6

0,8

1

1,2

0 5 10 15 20 25 30 35 40

n

P X n

Distribuição de PoissonDistribuição de Poisson Função de distribuição de probabilidadeFunção de distribuição de probabilidade

Page 109: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição de PoissonDistribuição de Poisson

0

0,2

0,4

0,6

0,8

1

1,2

0 5 10 15 20 25 30 35 40

Fn. de distribuição

Fn. de massa

= 20

Page 110: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

00,050,1

0,150,2

0,250,3

0,350,4

0 5 10 15 20 25 30 35 40i

P{X

=i}

Distribuição de PoissonDistribuição de PoissonFunção de massa de probabilidadeFunção de massa de probabilidade

Page 111: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Valor esperado:

E[X] =

=

Fazendo k = i - 1:

E[X] =

Como

E[X] =

i

i

iei0

!

e

ii

i

1

1

1( )!

!0 ke

k

k

e

k

k

k !0

Distribuição de PoissonDistribuição de Poisson

Page 112: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Distribuição de PoissonDistribuição de PoissonParâmetrosParâmetros

E[X

Var[X

x

(t) e (e )t 1

Page 113: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de contagemProcesso de contagem

Processo estocástico {N(t), t 0} é de contagem se N(t) representa o número total de eventos que ocorrem entre (0,t]

Por definição, N(t) satisfaz: N(t) 0 N(t) assume valores inteiros s < t N(s) N(t) s < t N(t) - N(s) = número de eventos durante o intervalo

(s,t]

Page 114: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de contagemProcesso de contagem

Número de pessoas que entraram em um supermercado no intervalo de

tempo (0,t]

Número de veículos que entraram em um túnel num intervalo dado

Número de gols que um determinado jogador fez num determinado intervalo (0,t]

Page 115: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de contagemProcesso de contagem

Incrementos independentes: processo de contagem no qual o número de eventos ocorridos em intervalos de tempos disjuntos são independentes

Exemplo: o processo de contagem no intervalo (5,10] não depende do processo de contagem em (0,5]

Page 116: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de contagemProcesso de contagem

Incrementos independentes Incrementos independentes Número de pessoas que entraram em um supermercado num intervalo de tempo

Incrementos não-independentesIncrementos não-independentes Número de nascimentos num intervalo de tempo, quando existe controle da natalidade

Page 117: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de contagemProcesso de contagem

Incrementos estacionários: número de eventos em (t1+s,t2+s] depende somente da amplitude do intervalo (t2-t1)

Ou seja, N(t2+s)-N(t1+s) tem a mesma distribuição que N(t2)-N(t1), onde t2 > t1 e s > 0

0 t1 t2 s+t1 s+t2

Page 118: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de contagemProcesso de contagem

Incrementos não-estacionáriosIncrementos não-estacionários

A quantidade de ligações telefônicas é maior em determinadas horas do dia

Incrementos estacionáriosIncrementos estacionários

Número de veículos que entram em um túnel num ano

Page 119: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de PoissonProcesso de Poisson

N(t) é um processo de Poisson se: N(t) é um processo de contagem N(0) = 0 (reset) Tem incrementos independentes e estacionários Número de eventos em qualquer intervalo

de amplitude t é distribuído como uma variável de Poisson com média t, ou seja:

0,; 1, 0,=i,!) ( e = } i=N(s)-s){N(t t -

tsitPi

0,;0,1,=i,!

)( e = } i= N(s)-s)P{N(t

t-

tsi

t i

Page 120: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de PoissonProcesso de Poisson

A última condição implica em incrementos estacionários

N(t) não se refere apenas a uma variável aleatória com uma distribuição de Poisson, mas sim que para cada t > 0 se tem uma v.a. com uma distribuição de Poisson de parâmetro t (dependente de t)

Esta coleção (infinita) de variáveis aleatórias é conhecida como um processo de Poisson

Page 121: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de PoissonProcesso de PoissonTempo entre chegadasTempo entre chegadas

0 t1 t2 t3 · · · tn-1 tn

T1 T2 T3 · · · Tn

Eventos (contagem do P.P.)

Conjunto de v.a.s com distribuição Exp()

Seqüência {Tn, n=1,2,...}, onde Tn representa o tempo entre o evento (chegada) n e o evento n-1

Page 122: Teoria das Filas e Aplicações Celso C. Ribeiro Reinaldo Vallejos PETROBRAS Novembro 1998

Processo de PoissonProcesso de PoissonTempo entre chegadasTempo entre chegadas

Evento {T1 > t } significa que não aconteceu chegada alguma do processo de Poisson no intervalo (0,t]

P{T1 > t} = P{N(t) = 0} = e-t

Além disso,

P{T2>t | T1=s} = P{0 eventos em (s,s+t]} = e-t

Repetindo-se o experimento, conclui-se que Tn, n=1,2,... são v.a. exponenciais independentes e identicamente distribuídas