Upload
internet
View
118
Download
1
Embed Size (px)
Citation preview
Teoria das Filas e AplicaçõesTeoria 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
...
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
Teoria da probabilidadeTeoria da probabilidade
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
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,)
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
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
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
Teoria da probabilidadeTeoria da probabilidade
P({2,4,6}) = P({2}) + P({4}) + P({6}) = = 1/6 + 1/6 + 1/6 = 1/2
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
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
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
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
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
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
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
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.
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
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)
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))
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?
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
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?
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
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)]
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?
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
Variáveis aleatóriasVariáveis aleatórias
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
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 ...
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
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
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)
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.
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
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
Variáveis aleatórias discretasVariáveis aleatórias discretas
1 2 3a
F(a)
1/2
15/6
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
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 )()()]([
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
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
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
Distribuições discretasDistribuições discretas
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
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
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:
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.}[
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
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
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
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.
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)
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.
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
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
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
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)
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
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
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)
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)
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)
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)
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
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
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...
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()(}{
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
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
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()(
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
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
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
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
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
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
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
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
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}
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.
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
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
Propriedade: falta de memóriaPropriedade: falta de memória
Exemplo relacionado com a distribuição geométrica, duas situações equivalentes:
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
Propriedade: falta de memóriaPropriedade: falta de memória
Propriedade: falta de memóriaPropriedade: falta de memória Demonstração:
Logo,
txP
tsxPtx |t sxP
txP
txtsxPtx |t sxP
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
a=1 : Rede da área locala=3 : Rede com enlaces menores a 500 Kma=10 : Rede de enlace satelital
ap
max=F(p,a)
max=F(p,a)
a=1,8
a=2,1
a=1,4a=1
max=F(p,a)p=0
p=0.2
p=0.4
p=0.6
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
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
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
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
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
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
Distribuição de PoissonDistribuição de PoissonParâmetrosParâmetros
E[X
Var[X
x
(t) e (e )t 1
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]
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]
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]
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
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
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
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
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
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
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