Slide - Probabilidade B5 - Matemática Discreta - 2023-2

B5 - Probabilidade Jeroen van de Graaf DCC/UFMG Tópicos probabilidade Tópico 1: Axiomas ▶ Intro, definição de Laplace (6.1) ▶ Axiomas; eventos; combinação de eventos (6.2) ▶ Dois exemplos importantes ▶ Monty’s Hall ▶ Paradoxo do aniversário Tópico 2: Probabilidade condicional ▶ Probabilidade condicional, independência, Bayes ▶ As probabilidade dependem das informações disponíveis ▶ Probabilidade e raciocínio lógico Tópicos probabilidade Tópico 3: Variáveis estocásticas ▶ Váriaveis aleatórias/estocásticas ▶ Esperança ▶ Lineariedade de Esperança ▶ As distribuições de Bernoulli, binomial e a geométrica; ▶ Variança; ▶ Lineariedade de variança ▶ A variança da distribuição binomial Tópico 4 ▶ ∗ Duas distribuções discretas importantes ▶ ∗ A distribuição normal ▶ ∗ O comportamento asintático da distribuição binomial ▶ ∗ Algoritmos probabilísticos Revisão REVISÃO Variaveis Aleatórias Definição – Uma variável aleatória X modela um experimento probabilístico, atribuindo um valor numérico a cada resultado, x, com determinada probabilidade, p(X = x). – A distribuição de X em S é o conjunto de pares (x, p(X = x)) para todo x ∈ S, onde p(X = x) é a probabilidade de X assumir o valor x. Valor esperado Definição [6.4.1] O valor esperado ou esperança de uma variável aleatória X() num espaço amostral S é E(X) = \sum_{x \in S} p(X = x) \cdot x Muitos livros usam a letra μ para denotar o mean (value). Linearidade de esperança Teorema [6.4.3] Sejam X, X1, . . . , Xn variáveis aleatórias em S. Então, para a, b ∈ R temos (i) E(X1 + · · · + Xn) = E(X1) + · · · + E(Xn) (ii) E(aX + b) = aE(X) + b Ensaio de Bernoulli Definição [Veja antes Exemplo 6.2.8] Um ensaio de Bernoulli é um experimento com apenas dois resultados possíveis, chamado de Sucesso ou 1 com probabilide p, ou de Fracasso ou 0, com probabilidade q = 1 − p. Distribuição binomial Exemplo [Veja Exemplo 6.2.8] Quatro bits são gerados, cada resultando em um símbolo 1 com probabilidade p. Qual é a probabilidade de ter um 1 e três 0s? Distribuição binomial Exemplo [Veja Exemplo 6.2.8] Quatro bits são gerados, cada resultando em um símbolo 1 com probabilidade p. Qual é a probabilidade de ter um 1 e três 0s? Resposta p q p q p q (3 1)p¹q³ Distribuição binomial Teorema [6.2.2] A distribuição binomial representa a probabilidade de se ter k sucessos em n testes de Bernoulli com probabilidade de sucesso p, e é dada por Binn,p(k) = (n k)pᵏqⁿ⁻ᵏ Distribuição geométrica p=0.2 p=0.5 p=0.8 P(X=x) 0 0.2 0.4 0.6 0.8 1.0 0 2 4 6 8 10 Distribuição geométrica Definição [6.4.2] Uma variável aleatória X tem uma distribuição geométrica de parâmetro p se, para k = 1, 2, 3, . . ., Pr[X = k] = qk−1p Teorema [6.4.4] O valor esperado nesse caso é E(X) = 1/p Distribuição geométrica Definição [6.4.2] Uma variável aleatória X tem uma distribuição geométrica de parâmetro p se, para k = 1, 2, 3, . . ., Pr[X = k] = qk−1p Teorema [6.4.4] O valor esperado nesse caso é E(X) = 1/p Variança Definição [6.4.4] Denote o valor esperado de X por μ. Ou seja, μ = E(X). - A variância de X é V(X) = ∑ (x - μ)^2 p(x) x∈S - O desvio-padrão de X é a raiz-quadrada da variância, σ(X) = √V(X) Variança Teorema [6.4.6] V (X) = E(X 2) − µ2 = E(X 2) − E(X)2 – Na prática é a forma mais fácil de se calcular V (X) e σ(X) Variança da distribuição binomial 1 A VARIANÇA DA DISTRIBUIÇÃO BINIMIAL Variança Queremos mostrar que Teorema [6.4.7] Se X1 e X2 são variaveis aleatórias independentes, então V (X1 + X2) = V (X1) + V (X2) Em geral, V (X1 + . . . + Xn) = V (X1) + . . . + V (Xn) Observação: a independência não é condição necessária no teorema da linearidade da esperança. Variaveis aleatórias independentes Definição [6.4.3] As variaveis aleatórias X e Y são independentes se as duas distribuições correspondentes são independentes. Ou seja, se Pr[X = x ∧ Y = y] = Pr[X = x] · Pr[Y = y] para todos os pares (x, y). Variaveis aleatórias independentes Exemplo [6.4.11] Considere o produto cartesiano de dois dados; ou seja, os pares (x1, x2): 1 2 3 4 5 6 1 1/36 1/36 1/36 1/36 1/36 1/36 1/6 2 1/36 1/36 1/36 1/36 1/36 1/36 1/6 3 1/36 1/36 1/36 1/36 1/36 1/36 1/6 4 1/36 1/36 1/36 1/36 1/36 1/36 1/6 5 1/36 1/36 1/36 1/36 1/36 1/36 1/6 6 1/36 1/36 1/36 1/36 1/36 1/36 1/6 1/6 1/6 1/6 1/6 1/6 1/6 Observamos independência porque Pr[X1 = x1 ∧ X2 = x2] = Pr[X1 = x1] · Pr[X2 = x2] Variaveis aleatórias independentes Exemplo [6.4.12] O resultado dos dois dados, X1 e X2 são independentes, mas a soma de dois dados, Z = X1 + X2, depende de X1 (e também de X2). Variaveis aleatórias independentes Teorema [6.4.5] Se X e Y são independentes, então E(XY ) = E(X)E(Y ) Variança Teorema [6.4.7] Se X1 e X2 são variaveis aleatórias independentes, então V (X1 + X2) = V (X1) + V (X2) Em geral, V (X1 + . . . + Xn) = V (X1) + . . . + V (Xn) Observação: a independência não é condição necessária no teorema da linearidade da esperança. Variança Exemplo [6.4.17] Variança de dois dados: Suponha dois dados são lançados. Defina Z = X_1 + X_2 = (soma dos resultados) Calcule V(Z) usando o teorema. Variança Exemplo [6.4.17] Variância de dois dados: Suponha dois dados são lançados. Defina Z = X_1 + X_2 = (soma dos resultados) Calcule V(Z) usando o teorema. Resposta Temos que X_1 (resp. X_2) eh o resultado do primeiro (segundo) dado. Já calculamos que V(X_1) = V(X_2) = 35/12, portanto V(Z) = V(X_1 + X_2) = V(X_1) + V(X_2) = 35/6 E o desvio-padrão é √35/6. Variança distribuicao binomial Corolário [Exemplo 6.4.18] A variança de n testes de Bernoulli com probabilidade p, ou seja, a variança da distribuição binomial Binn,p é npq e o desvio -padrão é √npq Prova V (X) = V (X1 + . . . + Xn) = V (X1) + . . . + V (Xn) = n · V (Xi) = npq Variança distribuicao binomial Corolário [Exemplo 6.4.18] A variança de n testes de Bernoulli com probabilidade p, ou seja, a variança da distribuição binomial Binn,p é npq e o desvio -padrão é √npq Prova V (X) = V (X1 + . . . + Xn) = V (X1) + . . . + V (Xn) = n · V (Xi) = npq Resumo distribuição esperança variança Bernoulli p pq binomial np npq geométrica 1 p 1−p p2 hypergeométrica(*) . . . . . . Poisson(*) λ λ normal µ σ Mais duas distribuições discretas 2 DUAS DISTRIBUIÇÕES DISCRETAS A distribuição hipergeométrica* Lembre que a distribuição binomial serve para modelar amostragem com reposição: Uma urna contém 3 bolas brancas e 7 bolas pretas. Tirando 6 vezes uma bola com reposição, qual é a probabilidade de ter 2 bolas brancas e 4 pretas? Solução n = 6, p = 3/(3 + 7) = 0.3, k = 2 então Binn=6,p=0.3(k = 2) = C(6, 2) · 0.32 · 0.74 A distribuição hipergeométrica* Lembre que a distribuição binomial serve para modelar amostragem com reposição: Uma urna contém 3 bolas brancas e 7 bolas pretas. Tirando 6 vezes uma bola com reposição, qual é a probabilidade de ter 2 bolas brancas e 4 pretas? Solução n = 6, p = 3/(3 + 7) = 0.3, k = 2 então Binn=6,p=0.3(k = 2) = C(6, 2) · 0.32 · 0.74 A distribuição hipergeométrica* A distribuição hipergeométrica serve para modelar amostragem sem reposição: Uma urna contém 3 bolas brancas e 7 bolas pretas. Tirando 6 vezes uma bola sem reposição, qual é a probabilidade de ter 2 bolas brancas e 4 pretas? Solução p = 2 bolas brancas · 4 bolas pretas 10 bolas = (3 2)(7 4) (10 6) A distribuição hipergeométrica* A distribuição hipergeométrica serve para modelar amostragem sem reposição: Uma urna contém 3 bolas brancas e 7 bolas pretas. Tirando 6 vezes uma bola sem reposição, qual é a probabilidade de ter 2 bolas brancas e 4 pretas? Solução p = 2 bolas brancas · 4 bolas pretas 10 bolas = (3 2)(7 4) (10 6) A distribuição hipergeométrica* A distribuição hipergeométrica serve para modelar amostragem sem reposição: Amostramos n vezes, sem reposição, de uma urna com N bolas, das quais m são brancas e N − m bolas são pretas. Seja X o número de bolas brancas retiradas, então Pr[X = k] = (m k)(N−m n−k ) (N n) A distribuição Poisson* A distribuição de Poisson serve para modelar eventos ‘esporádicos’: ▶ A quantidade de erros de impressão numa página de um livro; ▶ O número de pessoas numa comunidade que vivem até 100 anos; ▶ A quantidade de pacotes de um determinado produto numa loja ▶ O número de pessoas entrando nos Correios no dia; ▶ O número de pessoas usando o celular durante uma hora; ▶ O número de partículas α descarregadas num intervalo de tempo. A distribuição Poisson* Definição A distribuição Poisson com parâmetro λ é dada por Poissonλ(X = k) = e−λ λk k! Por exemplo, a distribuição de Poisson com λ = 1 dá: k 0 1 2 3 4 5 e−1 0! e−1 1! e−1 2! e−1 3! e−1 4! e−1 5! .368 .368 .184 .061 .015 .003 A distribuição Poisson* Exemplo Suponha que o número de erros tipográficos por página de um livro tem uma distribuição Poisson com parâmetro λ = 1 2. Qual é a probabilidade que há pelo menos um erro numa página? Resposta Poissonλ=1/2(X ≥ 1) = 1 − Poissonλ=1/2(X = 0) = 1 − e−1/2 ≈ .393 A distribuição Poisson* Exemplo Suponha que a probabilidade que um item produzido por uma determinada máquina tem defeito é de 0.1. Qual é a probabilidade que uma amostra de 10 itens tem no máximo um item com defeito? Resposta Pela distribuição binomial. a resposta é \( \Bigg( \begin{array}{c} 10 \\ 0 \end{array} \Bigg) 0.1^0 \cdot 0.9^{10} + \Bigg( \begin{array}{c} 10 \\ 1 \end{array} \Bigg) 0.1^1 \cdot 0.9^9 \approx 0.7361 \) enquanto a aproximação com \( \lambda = 10 \cdot 0.1 = 1 \) dá \( \text{Poisson}_{\lambda=1}(X = 0) + \text{Poisson}_{\lambda=1}(X = 1) = e^{-1} + e^{-1} \approx 0.7358 \) Distribuição normal 3 A DISTRIBUIÇÃO NORMAL Distribuição normal N = 3,226 Mean = 3.39 kg SD = 0.55 kg Distribuição normal Standard normal distribution Distribuição normal A distribuição normal padrão (ou distribuição Gaussiana ou curva de sino) é dada pela fórmula f (x) = 1 √ 2π e− 1 2 x2 ▶ descresce exponencialmente ▶ simétrica relativo a 0 ▶ área abaixo da curva é 1 ▶ continua Distribuição normal Normal CDF Distribuição normal ϕ_{μ,σ^2}(x) μ=0, σ^2=0.2, μ=0, σ^2=1.0, μ=0, σ^2=5.0, μ=-2, σ^2=0.5, Distribuição normal A distribuição normal generalizada é dada pela fórmula Nµ,σ(x) = 1 σ √ 2π e− 1 2 ( x−µ σ )2 ▶ µ representa o máximo de f (deslocamento para esquera ou direita). ▶ σ represente os pontos de inflexão e corresponde ao desvio-padrão. ▶ A área abaxo da curva é 1. Distribuição normal ▶ O ‘volume’ de probabilidade no interval [−σ, +σ] é mais de 2 3 da probabilidade; ▶ O ‘volume’ de probabilidade no interval [−2σ, +2σ] é mais de 95 % da probabilidade; ▶ Qualidade ‘six sigma’ corresponde a uma probabilidade de erro de ≈ 0.000 000 001 973 < 2 · 10−9 Distribuição binomial e normal Para n grande, a distribuição binomial pode ser aproximada pela distribuição normal. Para n = 50; p = 0.8 temos que µ = np = 40; σ = √npq = √ 50 · 0.8 · 0.2 = √ 8 ≈ 2.82842 Distribuição binomial e normal Binomial vs. Normal PDF (n=50, p=0.8) Binomial Distribuição binomial e normal ▶ Na medida que n cresce, a aproximação fica melhor ▶ Na medida que n cresce, a massa da probabilidade fica cada vez mais concentrada perto do valor esperado porque ▶ a razão esperança por n fica constante: E n = np n = p; ▶ a razão desvio-padrão por n diminui: σ n = √npq n = pq √n Distribuição binomial e normal N=10 N=100 N=1000 As probabilidade dependem das informações disponíveis 4 PROBABILIDADE DEPENDE DA INFORMAÇÃO DISPONÍVEL As probabilidade dependem das informações disponíveis Uma urna tem 13 bolas brancas e 39 pretas. Alice seleciona k = 2 bolas sem olhar. Qual é a probabilidade que a próxima bola que ela seleciona é preta? Primeira abordagem: Pr[3a bola branca] = Pr[BBB] + Pr[PBB] + Pr[BPB] + Pr[PPB] = 13 52 12 51 11 50 + 39 52 13 51 12 50 + 13 52 39 51 12 50 + 39 52 38 51 13 50 = 13·(12·11+39·12+39·12+39·38) 52·51·50 = 13·(12·(11+39)+39(12+38) 52·51·50 = 13·51·50 52·51·50 = 13 52 = 1 4 As probabilidade dependem das informações disponíveis Uma urna tem 13 bolas brancas e 39 pretas. Alice seleciona k = 2 bolas sem olhar. Qual é a probabilidade que a próxima bola que ela seleciona é preta? Primeira abordagem: Pr[3a bola branca] = Pr[BBB] + Pr[PBB] + Pr[BPB] + Pr[PPB] = 13 52 12 51 11 50 + 39 52 13 51 12 50 + 13 52 39 51 12 50 + 39 52 38 51 13 50 = 13·(12·11+39·12+39·12+39·38) 52·51·50 = 13·(12·(11+39)+39(12+38) 52·51·50 = 13·51·50 52·51·50 = 13 52 = 1 4 As probabilidade dependem das informações disponíveis Para a segunda abordagem, vamos primeiro estudar umas outras questões: 1. João embaralha um baralho com 52 cartas. Em seguida, ele descarta as primeiras duas cartas. Qual é a probabilidade que a terceira carta é de naipe espada? 2. Pedro embaralha um baralho com 52 cartas. Em seguida, ele coloca todas as cartas, fechada, numa fileira. Pedro pode ver as primeiras duas cartas, mas Maria, não. Qual é a probabilidade que a terceira carta é de naipe espada de ponto de vista de Pedro? E de ponto de vista de Maria? As probabilidade dependem das informações disponíveis Para a segunda abordagem, vamos primeiro estudar umas outras questões: 1. João embaralha um baralho com 52 cartas. Em seguida, ele descarta as primeiras duas cartas. Qual é a probabilidade que a terceira carta é de naipe espada? 2. Pedro embaralha um baralho com 52 cartas. Em seguida, ele coloca todas as cartas, fechada, numa fileira. Pedro pode ver as primeiras duas cartas, mas Maria, não. Qual é a probabilidade que a terceira carta é de naipe espada de ponto de vista de Pedro? E de ponto de vista de Maria? As probabilidade dependem das informações disponíveis 3. Pedro embaralha um baralho com 52 cartas. Em seguida, ele coloca todas as cartas, fechada, numa fileira. Pedro pode ver as últimas duas cartas, mas Maria, não. Qual é a probabilidade que a terceira carta é de naipe espada de ponto de vista de Pedro? E de ponto de vista de Maria? 4. João embaralha um baralho com 52 cartas. Em seguida, ele coloca todas as cartas, fechada, numa fileira. Qual é a probabilidade que uma carta qualquer é de naipe espada? As probabilidade dependem das informações disponíveis 3. Pedro embaralha um baralho com 52 cartas. Em seguida, ele coloca todas as cartas, fechada, numa fileira. Pedro pode ver as últimas duas cartas, mas Maria, não. Qual é a probabilidade que a terceira carta é de naipe espada de ponto de vista de Pedro? E de ponto de vista de Maria? 4. João embaralha um baralho com 52 cartas. Em seguida, ele coloca todas as cartas, fechada, numa fileira. Qual é a probabilidade que uma carta qualquer é de naipe espada? As probabilidade dependem das informações disponíveis Uma urna tem 13 bolas brancas e 39 pretas. Alice seleciona k bolas sem olhar. Qual é a probabilidade que a próxima bola que ela seleciona é preta? Não é relevante que k bolas foram descartadas, já que não obtivemos informações sobre elas. Então Pr[3a bola branca] = 13 52 = 1 4 CONCLUSÂO ▶ As probabilidades não são propriedades intrínsecas das cartas (dos objetos), mas dependem das informações que as partes detêm sobre os eventos. ▶ Probabilidades são subjetivas nesse sentido. Mas qualquer pessoa racional, com as mesmas informações, chegaria à mesma probabilidade. Probabilidade e raciocínio lógico 5 PROBABILIDADE E RACIOCÍNIO LÓGICO Falácia da afirmação da conclusão (1) Se o aluno fizer todos os exercícios, ele passa na disciplina (2) Alícia passou na prova ⇒ Logo, Alícia fez todos os exercícios Falácia da afirmação da conclusão (1) A =⇒ B (2) B ⇒ Logo A ▶ errado pelas leis da lógica formal Falácia da afirmação da conclusão (1) A =⇒ B (2) B ⇒ Logo, A se torna mais plausível ▶ segue as leis de probabilidade ▶ conforme bom senso Silogismo do policial ▶ Um policial, andando na rua à noite, está vendo uma pessoa mascarada saindo da vitrina quebrada de uma jouaileira, carregando uma bolsa pesada. ▶ O policial não hesita mas prende o homem, deduzendo que ele é um ladrão. ▶ Qual é a regra lógica que levou o policial a esta conclusão? ▶ Nenhuma das regras de inferência que estudamos na ILC (modus ponens, silogismo hipotético, ..) pode ser aplicada. ▶ Existe até uma possível explicação: o homem é o dono da jouaileira que, voltando de uma festa mascarada, viu que alguém quebrou a vitrina da sua loja, e está protegendo seus bens. Silogismo do policial ▶ Um policial, andando na rua à noite, está vendo uma pessoa mascarada saindo da vitrina quebrada de uma jouaileira, carregando uma bolsa pesada. ▶ O policial não hesita mas prende o homem, deduzendo que ele é um ladrão. ▶ Qual é a regra lógica que levou o policial a esta conclusão? ▶ Nenhuma das regras de inferência que estudamos na ILC (modus ponens, silogismo hipotético, ..) pode ser aplicada. ▶ Existe até uma possível explicação: o homem é o dono da jouaileira que, voltando de uma festa mascarada, viu que alguém quebrou a vitrina da sua loja, e está protegendo seus bens. Silogismo do policial (A): X é um ladrão (B): X se comporta de forma suspeita (as evidências) (C): A experiência do policial (informações prévias) Pela lógica formal, alguém se comportando de forma suspeita não prova que é um ladrão. Mas aumenta a probabilidade sim. Ou seja, (1) Se A é V , então B se torna mais plausível (2) B é V ⇒ Logo, A se torna mais plausível Silogismo do policial (A): X é um ladrão (B): X se comporta de forma suspeita (as evidências) (C): A experiência do policial (informações prévias) Probabilidades condicionais mostre que quão menos plausível é B|C, mais força de evidência tem observar A: ▶ ‘Se A é V , então B se torna mais plausível’ corresponde a P(B|AC) > p(B|C) ▶ Mas sabemos que p(B|AC) p(B|C) = p(A ∩ B|C) = p(A|BC) p(A|C) ▶ Logo p(A|BC) > p(A|C). ▶ Se p(B|C), a probabilidade de comportamento suspeita, é muito baixa, aumenta p(A|BC), a probabilidade de X ser ladrão. Silogismo da chuve (A) ‘Vai chuver em 10 minutos’ (B) ‘Nuvens cinzas estão se formando.’ (C) ‘Bom senso’ (informações prévias) Temos agora: (1) Se A é V , então B se torna mais plausível (2) B é V ⇒ Logo, A se torna mais plausível ▶ Observe que chuve implica, necessáriamente, a presença de nuvens; está é uma implicação lógica. ▶ Mas não é verdade que a chuva causa as núvens. Ao contrário, as núvens são a causa física da chuva. Inferência Bayesiana ▶ É possível deduzir as leis da probabilidade a partir de três princípios/desiderata. ▶ A inferência Bayesiana nos dá respostas onde a lógica e a abordagem clássica falha ▶ O ‘bom senso’ do cerebro humano funciona dessa maneira ▶ Redes bayesianas, subárea da Inteligência Artificial ▶ Atribuir ligações e probabilidades a priori ▶ Raciocinar com dezenas, centenas de afirmações Teoria de probabilidade como extensão da lógica Exprima graus de plausibilidade ▶ "Não acho que vai chuver hoje’ ’ ▶ "Tenho certeza que vai chuver, já que há nuvens cinzas no ceu.’ ’ ▶ Exprima subjetividade. ▶ É o que um ser vivo usa para sobreviver. Probabilidade é uma forma de exprimir graus de convicção Probabilidades podem ser interpretadas de duas maneiras ▶ A interpretação frequentista vê probabilidades como o resultados de (um número infinito de) experimentos probabilísticos. Essa é a abordagem usada pela maioria dos matemáticos e livros ▶ A interpretação Bayesiana (ou interpretação de graus de convicçaõ ou interpretação subjetiva) vê as probabilidades como o grau em que alguém acredita no valor de verdade das proposições que dependem de variáveis aleatórias. ▶ Qual é a probabilidade que Sr. Da Silva matou sua esposa, dadas as evidências; ▶ Qual é a probabilidade de chuva amanhã? A segunda maneira dá resultados onde a primeira cala, então pode ser considerada mais produtiva. Algoritmos probabilísticos 6 ALGORITMOS PROBABILÍSTICOS Definição algoritmo probabilístico Definição Um algoritmo descreve com exatidão um procedimento para, a partir de uma dada entrada, se calcular um resultado. Definição Um algoritmo determinístico é um algoritmo que, em cada momento da sua execução, sabe-se exatamente qual será o próximo passo. Definição Um algoritmo probabilístico é um algoritmo que, em algum momento da sua execução, usa aleatoriedade externa para decidir sobre o próximo passo. Aviso Um algoritmo probabilístico não é um algoritmo determinístico, mas o termo algoritmo não determinístico tem um outro significado e pode causar confusão. É melhor evitar. Definição algoritmo probabilístico Definição Um algoritmo descreve com exatidão um procedimento para, a partir de uma dada entrada, se calcular um resultado. Definição Um algoritmo determinístico é um algoritmo que, em cada momento da sua execução, sabe-se exatamente qual será o próximo passo. Definição Um algoritmo probabilístico é um algoritmo que, em algum momento da sua execução, usa aleatoriedade externa para decidir sobre o próximo passo. Aviso Um algoritmo probabilístico não é um algoritmo determinístico, mas o termo algoritmo não determinístico tem um outro significado e pode causar confusão. É melhor evitar. Definição algoritmo probabilístico Definição Um algoritmo descreve com exatidão um procedimento para, a partir de uma dada entrada, se calcular um resultado. Definição Um algoritmo determinístico é um algoritmo que, em cada momento da sua execução, sabe-se exatamente qual será o próximo passo. Definição Um algoritmo probabilístico é um algoritmo que, em algum momento da sua execução, usa aleatoriedade externa para decidir sobre o próximo passo. Aviso Um algoritmo probabilístico não é um algoritmo determinístico, mas o termo algoritmo não determinístico tem um outro significado e pode causar confusão. É melhor evitar. Pattern matching – clássico ▶ voce precisa procurar a palavra u0 . . . u11 =’universidade’ ▶ num string s0s1s2 . . . sn, onde n pode ser (muito) grande ▶ estatégia: ▶ comparar se sj = u0 ▶ comparar se sj+1 = u1 ▶ . . . ▶ comparar se sj+11 = u11 Pattern matching – probabilístico Abordagem com fingerprint ▶ interpretar os caracteres u0, . . . , u11 como inteiros ▶ calcular o fingerprint de ‘universidade’: f = u0 + . . . + u11 (mod 256) ▶ calcular g0 = s0 + . . . + s11 ▶ agora, se g0 ̸= f , temos certeza que os padrões são diferentes ▶ se g0 = f faremos a comparação de cada par de caracteres Pattern matching ▶ calcular g1 a partir de g0 é eficiente já que −s0 + g0 + s12 = −s0 + (s0 + s1 + . . . + s11) + s12 = s1 + . . . + s12 = g1 ▶ ao invés de somar módulo 256, é melhor somar módulo um número primo ▶ mesmo assim, poderia existir um pior caso. ▶ para evitar isto, é melhor que esse primo seja escolhido aleatoriamente Probabilismo para quê? 1. Para melhorar o desempenho 1.1 Comparar duas listas 1.2 Pattern matching 1.3 QuickSort 1.4 . . . 2. Por que não existe algoritmo determinístico 2.1 Escolher leader numa rede 2.2 Calcular raíz quadrado modulo um primo Tipos de erros Algoritmos probabilísticos são usados para ▶ melhorar o tempo de execução sem introduzir um erro (pattern matching, quick sort, hashing) ▶ permitindo algum tipo de erro: ▶ a resposta está sempre certa, mas o algoritmo nem sempre termina ▶ two-sided error: o algoritmo dá uma resposta errada com prob = 2−t. ▶ one-sided error: o algoritmo acerta quando afirma que n não é primo, mas pode errar com prob = 2−t quando afirma que n é primo. Ampliar a probabilidade de sucesso Um algoritmo probabilístico que acerta apenas em 1% dos casos é, na verdade, muito poderoso: ▶ falha 99% dos casos ▶ Depois de k = 100 tentativas, a probabilidade de ter nenhum sucesso é de p = 0.99100 = 0.366. ▶ (Curiosidade: (1 − 1 n)n = e−1 = 1 e ≈ 0.367879.) ▶ Depois de k = 1000 tentativas, p = 0.991000 = 4.3171 · 10−5. Algoritmos probabilísticos – resumo ▶ aleatoriedade é um recurso muito importante na ciência da computação ▶ na prática, os algoritmos probabilísticos caracterizam melhor o que se pode calcular que os algoritmos determinísticos