Probabilidade em Computa¸cao

Probabilidade em Algoritmos

Jair Donadelli

2008

“Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a ”correct”algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.” Abelson & Sussman

Sumário

1 Espaços de probabilidade discretos
1.1 Identidade polinomial
2 Probabilidade condicional e Independência
2.1 Espaço produto
2.2 Identidade polinomial revisitada
2.3 Igualdade do produto de matrizes
3 Teorema de Bayes
3.1 Sigilo perfeito
3.2 Mensagens eletrônicas indesejáveis (Spam)
4 Variáveis aleatórias discretas
4.1 Distribuições de Bernoulli, binomial, geométrica e uniforme
4.2 MAX 3-SAT
4.3 Gerador de prováveis primos
4.4 Quicksort
4.5 Skip lists
5 Leis de Desvio
5.1 Markov e Chebyshev
5.2 Tabelas de espalhamento (Hashing)
  5.2.1 Hashing universal.
5.3 Desigualdades de Chernoff–Hoeffding.
5.4 Treaps
6 Modelos de Computação
6.1 Máquinas de Turing
  6.1.1 Máquina de Acesso Aleatório — RAM
  6.1.2 Algoritmos.
6.2 Algoritmos aleatorizados
  6.2.1 Máquina de Turing probabilística off-line.
  6.2.2 Máquina de Turing não-determinística.
6.3 Circuitos booleanos
7 Classes de complexidade
  7.0.1 Complexidade de máquinas de Turing.
  7.0.2 Complexidade de programas RAM.
  7.0.3 Complexidade de circuitos.
7.1 Classes probabilísticas
  7.1.1 Definição alternativa de BPP.
7.2 BPP ⊆ P/poly
7.3 BPP está na Hierarquia Polinomial
8 Cadeias de Markov homogêneas
8.1 2-SAT
8.2 Distribuição estacionária de uma cadeia de Markov
  8.2.1 O Teorema Fundamental das Cadeias de Markov
9 Passeios aleatórios em grafos
9.1 s - t conexidade em grafos
9.2 Passeio aleatório em grafos regulares
10 Passeios aleatórios em grafos expansores
  10.0.1 Expander mixing lemma
11 Passeio aleatório na WEB: o Google PageRank
12 Desaleatorização de BPP
12.1 Geradores pseudoaleatórios
  12.1.1 Existência de geradores pseudoaleatórios condicionada a existência de problemas difíceis.
12.2 Construções de sequências k-a-k independentes
  12.2.1 Sequências com distribuição uniforme e independência 2-a-2.
  12.2.2 Sequências com distribuição uniforme e independência k-a-k.
12.3 Hash Universal
12.4 Desaleatorização com grafos expansores

1 Espaços de probabilidade discretos

Neste texto consideraremos triplas (Ω,,P) que definem um espaço de probabilidade discreto, ou seja,

Ω é um conjunto enumerável, chamado espaço amostral;
= 2^Ω é a σ-álgebra de eventos,
P: → ℝ é tal que
1. 0 ≤P(E) ≤ 1 para todo evento E ∈;
2. P(Ω) = 1;
3. para qualquer seqüência enumerável E_i_i≥1 de eventos disjuntos vale
  $( ) ⋃ ∑ P ( Ei) = P(Ei). i≥1 i≥1$ (1)

O lado esquerdo da equação (1) não depende de uma enumeração particular dos conjuntos e um teorema do cálculo garante o mesmo para o lado direito: se uma série de termos não-negativos converge então qualquer rearranjo dos termos resulta numa série que converge para o mesmo valor (veja Bartle, 1976). Como = 2^Ω = {E: E ⊆ Ω} está fixo escrevemos somente (Ω,P). No caso de espaços discretos a função de probabilidade P fica definida pelos valores de P({ω}) para todo ω ∈ Ω pois decorre de (1) que

∑ P(E) = P({a}) a∈E

para todo evento E ⊆ Ω. Com isso, podemos tomar P: Ω → [0,1] e como consequência escrevemos P(ω) ao inves de P ({ω}) omitindo as chaves nos eventos unitários.

Exemplo 1. Quando nos referimos ao lançamento de uma moeda equilibrada, estamos considerando o espaço amostral {cara,coroa} com a função de probabilidade P({cara}) = P({coroa}) = 1∕2, portanto, P(∅) = 0 e P({cara,coroa}) = 1. Agora, suponha que uma moeda equilibrada é lançada até sair cara. Então, o espaço amostral que modela esse experimento é o conjunto das seqüencias ω_n = (c₁,c₂,…,c_n) tal que para cada n ≥ 1 temos c_n = cara e para 1 ≤ i < n temos c_i = coroa, logo Ω = {ω_n: n ≥ 1}. Esse conjunto é claramente enumerável. Ainda, se definimos

( 1)n P(ωn ) = 2

então temos um espaço de probabilidade pois 0 < P(ω_n) < 1 para todo ω_n e

∑ ∑ -i P (ω ) = 2 = 1. ω∈Ω i≥1

(2)

Seja a descrição de um evento P ⊆ Ω. Denotamos por

P [ P ]

a propbabilidade do evento P, isto é, P [ P ] = P(P) e para evidenciar o espaço amostral escrevemos

PΩ [ P ] ou P ω∈RΩ [ P ].

Por exemplo, quando consideramos a probabilidade de um algoritmo aleatorizado A com entrada x responder errado, escrevemos

P m [ A (x, ω) est´a errado ] ω∈R{0,1}

para denotar a probabilidade das seqüências ω de m bits que fazem com que o algoritmo responda errado, ou em outras palavras, a probabilidade que uma escolha aleatória ω ∈_R{0,1}^m faça o algoritmo responder errado.

Nos algoritmos, nós vamos assumir a possibilidade de se fazer escolhas aleatórias, ou seja, assumir que os algoritmos dispõem de uma fonte de bits aleatórios e escrevemos a instrução

a ←R {0, 1}

para denotar o fato de que a é uma variável do algoritmo e que após a execução da atribuição ← _R o valor da variável a é um elemento qualquer de {0,1} com 1∕2. De um modo geral, se (Ω,P) é um espaço de probabilidade finito, então escrevemos a instrução

a ←R Ω

chamada de escolha aleatória uniforme em Ω.

Observação 2. Para a análise de complexidade dos algoritmos, assumimos que a instrução a ← _R{0,1} tem custo constante. No caso geral, a ← _RΩ, é feito em tempo O(log |Ω|).

Exercício 3. Prove que P(E₁ ∪ E₂) = P(E₁) + P(E₂) - P(E₁ ∩ E₂), para quaisquer eventos E₁ e E₂ num espaço de probabilidade discreto.

Exercício 4. Prove que para qualquer seqüência enumerável (E_i)_i≥1 de eventos num espaço discreto vale

( ⋃ ) ∑ P ( Ei) ≤ P(Ei). i≥1 i>1

1.1 Identidade polinomial

Consideremos o problema de decidir se f = 0, onde f ∈ ℝ[x] é um polinômio não-nulo de grau no máximo d > 0. Esse problema e sua variante multivariáveis tem importância central em complexidade computacional e voltaremos a estudá-lo na seção 2.2 e veremos sua importância na seção 12. Por ora, limitamo-nos a descrição do caso mais simples para ilustrar as definições apresentadas até agora.

Dado f ∈ ℝ[x] de grau no máximo d, escolhemos aleatoriamente e uniformemente a ∈{1,2,…,3d}. Se f(a) = 0, então respondemos sim, f = 0, senão respondemos não, f≠0. Notemos que se f = 0 então a resposta sim está correta entretanto se f≠0, então pode ocorrer f(a) = 0 caso a escolha aleatória a seja uma raiz de f; nesse caso a resposta sim está errada. Uma resposta não está sempre correta, ou seja, de fato f≠0.

__________________________________________________________________

  Dados $d ∈ ℕ$ e $f ∈ ℝ [x]$ de grau no máximo $d$
  Devolve não se $f ⁄= 0$ ou sim, $f = 0$ com
  probabilidade de erro no máximo $1∕3$ .

  1 $a ←R {1, 2, . .. , 3d}$ ;
  2 se $f(a) = 0$ então devolva(sim);