Upload
dinhkiet
View
223
Download
0
Embed Size (px)
Citation preview
Aula 4
Introducao a Probabilidade eaos Processos Estocasticos
Vinıcius A. Armentano1 Paulo A. Valente Ferreira2
1Departmento de Engenharia de Sistemas
2Departamento de Telematica
Faculdade de Engenharia Eletrica e ComputacaoUniversidade Estadual de Campinas
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
Aula 4
Conteudo
1 IndependenciaConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
2 Contagemk-PermutacoesCombinacoesParticoes
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Independencia pode ser utilizada na modelagem desistemas complexos compostos por varios componentes.
E bastante comum assumir que os comportamentos doscomponentes sao desacoplados (independentes).
Exemplo (Conectividade de Redes)
Uma rede de computadores conecta dois nos, A e B, atravesde nos intermediarios C, D, E e F.
Para cada par ij de nos conectados diretamente, existeuma dada probabilidade pij do link estar funcionando.
Assume-se que a falha num link e independente dasfalhas nos demais links. Qual a probabilidade de queexista um caminho conectando A e B?
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
PSfrag replacements
1
1
2
2
3
3
A B
C
D
E
F
Coneccao Paralelo
Coneccao Serie0.90.9
0.8
0.95
0.95
0.75
0.85
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Exemplo (Continuacao)
Um sistema como a rede do exemplo pode ser dividido emsubsistemas, subconjuntos de componentes.
Os subsistemas conectam componentes nasconfiguracoes serie ou paralelo.
Seja um subsistema com componentes 1, 2, . . . , m. Sejapi a probabilidade de funcionamento do componente i.
Na coneccao serie, todos os componentes devemfuncionar: P(serie funciona) = p1p2 · · ·pm. Na coneccaoparalelo, basta qualquer componente funcionar:
P(paralelo funciona) = 1 − P(paralelo nao funciona)
= 1 − (1 − p1)(1 − p2) · · · (1 − pm).
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Exemplo (Continuacao)
Comecando pelo fim, calcula-se inicialmente pCB:
pCB = 1 − (1 − pCEpEB)(1 − pCF pFC) = 0.946.
As probabilidades relativas as coneccoes serie de A a Bpassando por C ou por D sao:
pACB = pACpCB = 0.851, pADB = pADpDB = 0.712.
Finalmente, para a coneccao paralelo a partir de A,
pAB = 1 − (1 − pACB)(1 − pADB) = 0.957.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Ensaios Independentes
Num experimento envolvendo uma sequencia de estagiosindependentes e identicos, tem-se ensaios independentes.
Se existem apenas dois resultados possıveis em cadaestagio, obtem-se ensaios independentes de Bernoulli.
Os dois resultados possıveis podem ser qualquer coisa,mas constuma-se raciocinar com ”cara” e ”coroa”.
Um experimento consiste de n lancamentos de uma moeda. Aprobabilidade de cara e p (0 ≤ p ≤ 1).
Independencia significa que os eventos A1, A2, . . . , An,sendo Ai = o i-esimo lancamento e cara, saoindependentes.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Deescricao Sequencial (n = 3)
PSfrag replacements
p
p
p
p
p
p
p
1 − p
1 − p
1 − p
1 − p
1 − p
1 − p
1 − p
HHH Prob = p3
HHT Prob = p2(1 − p)
HTH Prob = p2(1 − p)
HTT Prob = p(1 − p)2
THH Prob = p2(1 − p)
THT Prob = p(1 − p)2
TTH Prob = p(1 − p)2
TTT Prob = (1 − p)3
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
No experimento,
Numa sequencia de tamanho 3, a probabilidade de k (≤ n)caras (e n − k coroas) e pk (1 − p)3−k .
No caso de uma sequencia de tamanho n, k caras e n − kcoroas tem probabilidade pk (1 − p)n−k , k = 0, 1, . . . , n.
Deseja-se a probabilidade
p(k) = P(k caras em n lancamentos)
=
(nk
)
pk (1 − p)n−k,
na qual(
nk
)
significa ”numero de sequencias de tamanho n
contendo k caras”.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Os numeros(
nk
)
, referidos como k-combinacoes de n,
sao chamados de coeficientes binomiais.Ainda na aula, demonstra-se que
(nk
)
=n!
k !(n − k)!, k = 0, 1, . . . , n,
i! = i · (i − 1) · · ·2 · 1. (0! = 1.)
A soma das probabilidades binomiais p(k) deve ser 1. Aigualdade
n∑
k=0
p(k) =n∑
k=0
(nk
)
pk (1 − p)n−k = 1
e chamada de Formula Binomial.Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
ConfiabilidadeEnsaios Independentes e Probabilidades Binomiais
Independencia
Exemplo (Gradacao de Servico)
Um provedor de internet tem instalados c modens para atenderuma populacao de n usuarios.
Num dado instante, cada usuario acessa o provedor comprobabilidade p, independentemente dos demais.
Qual a probabilidade de que existam mais usuarios do quemodens tentando acessar o provedor?
A probabilidade de que mais do que c usuarios acessem oprovedor e
n∑
k=c+1
(nk
)
pk (1 − p)n−k.
Se n = 100, p = 0.1 e c = 15, a probabilidade e de 0.04.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
O calculo de probabilidades frequentemente envolve contar onumero de resultados em varios eventos.
Se Ω possui um numero finito de resultados igualmenteprovaveis, para qualquer evento A,
P(A) =# de elementos de A# de elementos de Ω
.
Se a probabilidade de cada resultado e conhecida e iguala p, entao P(A) = p · (# de elementos de A).
Exemplo: quantas sequencias de tamanho n resultantesde n lancamentos de uma moeda contem k caras?
Questoes deste tipo constituem grande parte do areaconhecida como Analise Combinatoria
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Princıpio da ContagemConsidere um processo consistindo de r estagios. Suponhaque
Existem n1 resultados possıveis no estagio 1.
Para cada resultado possıvel no estagio 1, existem n2
resultados possıveis no estagio 2.
Genericamente, para qualquer resultado possıvel noestagio i − 1, existem ni resultados possıveis no estagio i .
Entao o numero total de resultados possıveis num processo der estagios e o produto
n1n2 · · ·nr .
Os valores n1, n2, . . . , nr podem ser diferentes, mas ni deveser constante para cada resultado do estagio i − 1.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Exemplo
Considere um conjunto de n elementos S = s1, s2, . . . , sn.Quantos subconjuntos de S podem ser formados, incluindoS e o conjunto vazio, ∅?
O calculo do numero de subconjuntos pode ser visto comum processo de n estagios.
No estagio i, o elemento si pode ou nao estar contido(duas possibilidades) num subconjunto de S .
Apos n estagios, o numero total de subconjuntos de Sseria
2 · 2 · · ·2︸ ︷︷ ︸
n vezes= 2n
.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Considere n objetos distintos. Seja k um inteiro positivo(k ≤ n). De quantas maneiras diferentes e possıvel arranjarsequencias de k objetos a partir dos n objetos dados?
O primeiro elemento da sequencia pode ser escolhido den maneiras diferentes.O i-esimo elemento da sequencia pode ser escolhido den − (i − 1) maneiras diferentes.
Pelo Princıpio da Contagem, o numero total de k-permutacoese igual a
n(n − 1) · · · (n − k + 1) =n · (n − 1) · · · (n − k) · · ·2 · 1
(n − k) · · ·2 · 1
=n!
(n − k)!
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
PermutacoesSe k = n, o numero de n-permutacoes, chamadassimplesmente de permutacoes, e
n(n − 1) · · ·2 · 1 = n!.
Exemplo
Numero de palavras que podem ser formadas a partir de quatroletras distintas do alfabeto (26 letras, incluindo K, W e Y):
n!
(n − k)!=
26!
22!=
26 · 25 · 24 · 23 · 22!
22!= 358800.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Exemplo
Voce tem n1 CD’s de musica classica, n2 CD’s de rock e n3
CD’s de musica sertaneja. Quantos arranjos diferentes existemtais que CD’s do mesmo tipo sejam contıguos?
Existem 3! maneiras de arranjar os CD’s de diferentestipos (rock/classica/sertaneja, classica/rock/sertaneja,. . . ).
Existem n1! (n2!, n3!) arranjos de CD’s de musica classica(rock, sertaneja). O numero total de arranjos e
3!n1!n2!n3!.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Exitem n pessoas interessadas em formar um ”comite” de kpessoas. Quantos diferentes comites sao possıveis?
Abstratamente, deseja-se saber o numero decombinacoes de k objetos selecionados de n objetosdistintos.
Diferentemente da k-permutacao, a ordem dos elementosna combinacao nao e levada em conta.
ExemploAs 2-permutacoes de A, B, C e D sao
AB,AC,AD,BA,BC,BD,CA,CB,CD,DA,DB,DC.
As combinacoes de 2 letras de A, B, C e D seriamAB,AC,AD,BC,BD,DC.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
O numero de combinacoes de k objetos dentre n objetosdistintos pode ser calculado da seguinte maneira:
O numero de k-permutacoes e igual ao numero decombinacoes vezes o numero de permutacoes de kobjetos. Logo
n!
(n − k)!= (# combinacoes) · k !.
Representando o numero de combinacoes de k objetos
dentre n por(
nk
)
, obtem-se
(nk
)
=n!
k !(n − k)!.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Uma combinacao e uma escolha de k objetos dentre umconjunto de n elementos.
Uma combinacao pode ser vista como uma particao doconjunto. Uma parte contem k elementos, a outra n − k .
A ideia pode ser gereralizada para uma particao em rsubconjuntos disjuntos.
Sejam n1, n2, . . . , nr numeros inteiros nao-negativos tais que
n1 + n2 + · · ·nr = n.
Considere uma particao do conjunto em r subconjuntosdisjuntos. O i-esimo subconjunto contem ni elementos.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
O numero total de particoes pode ser obtido da seguinte forma:
Existem(
nn1
)
maneiras de formar os elementos do
primeiro subconjunto.
Existem(
n − n1
n2
)
maneiras de formar os elementos do
segundo subconjunto.
Existem(
n − n1 · · · − ni−1
ni
)
maneiras de formar os
elementos do i-esimo subconjunto.Pelo Princıpio da Contagem, o numero total de escolhas e
(nn1
) (n − n1
n2
)
· · ·
(n − n1 · · · − nr−1
nr
)
.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Apos cancelar termos fatoriais, obtem-se o chamadocoeficiente multinomial:
(n
n1, n2, . . . , nr
)
=n!
n1!n2! · · ·nr !.
Exemplo
Uma classe consiste de 4 alunos de graduacao e 12 alunos depos-graduacao. Qual a probabilidade de cada grupo incluir umaluno de graduacao?
Um resultado tıpico do experimento e uma particao de 16alunos em grupos de 4 alunos. O total de particoes e
(16
4, 4, 4, 4
)
=16!
4!4!4!4!.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Exemplo (Continuacao)
Os 4 alunos de graduacao podem ser distribuıdos de 4!maneiras distintas entre os 4 grupos.
Os restantes 12 alunos podem ser distribuıdos de(
123, 3, 3, 3
)
=12!
3!3!3!3!
maneiras distintas.
Pelo Princıpio da Contagem, o evento de interesse podeocorrer de
4!12!
3!3!3!3!
maneiras diferentes.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos
IndependenciaContagem
k-PermutacoesCombinacoesParticoes
Contagem
Exemplo (Continuacao)
A probabilidade de que o evento ocorra e portanto
4!12!
3!3!3!3!16!
4!4!4!4!
=12 · 8 · 4
15 · 14 · 13≈ 0.14.
Vinıcius,Valente Introducao a Probabilidade e aos Processos Estocasticos