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
Last updated