Probabilidades para um bit

Inicialmente todos os bits estão a zero

Designando o bit na posição i por bi …

Qual a probabilidade do bit 𝑏𝑖 = 1 depois de aplicar a primeira função de dispersão na inserção de um elemento?

Assumindo que a função de dispersão seleciona cada uma das posições do vetor com igual probabilidade …

A probabilidade é simplesmente

• P[bi = 1] = 1 / n