Função de hash, $ h (k)=lFloor km \ rfloor $ é uniforme simples para $ k $ de forma independente, uniformemente distribuído no intervalo $ 0 \ leq k <1 $

Question

Eu estava passando pela introdução de texto para algoritmos por Cormen ET. al. onde me deparei com a seguinte declaração:

.

Se as chaves são conhecidas por serem aleatórias reais $ k $ de forma independente e uniformemente distribuída na gama $ 0 \ leq k <1 $ , a função hash

$$ h (k)=lFloor km \ rfloor $$ satisfaz a condição de hashing uniforme simples.

Agora o que posso entender que eles provavelmente estão considerando a violação uniforme no sentido "contínuo" e não no sentido discreto. Se estivesse no sentido discreto, em seguida, supor para $ n $ chaves A função de massa de probabidade (PMF) deve ser constante e igual a $ 1 / N $ e por isso deve ser igualmente provável para cada chave a ser usada no hash, yeilding o resultado desejado.

Mas parecemos meio em apuros se a distribuição ser chamada é contínua (sinto-me por causa da linha: "Uniformemente distribuída em a gama $ 0 \ LEQ K <1 $ ")

Deixe $ f (x) $ A função de densidade de probabilidade associada (PDF) e da informação dada que temos $ f (x)= 1 $ , (que é facilmente encontrado, integrando $ f (x) $ na matemática do intervalo $ 0 $ para $ 1 $ e equacionando com $ 1 $ e observando que Na distribuição uniforme, o PDF é uma constante).

Agora, embora o P.D.F seja uma constante, mas P.D.F não é a probabilidade. Em vez disso, a probabilidade em um ponto de espectro é $ 0 $ . Agora como usar esse resultado para chegar à reivindicação dos autores.

ou sou inteiramente a culpa, considerando a distribuição para ser contínua?

(há uma resposta aqui , mas não entra nesse detalhe como a pergunta existe diferente Afinal de contas).

Answer 1

$ h \ in [m] ^ u $ satisfaz a simples suposição de hash uniforme se quando $ x \ em u$ é escolhido uniformemente ao aleatório, então $ h (x) $ é distribuído uniformemente sobre $ [m]$ , ou equivalentemente $ \ forall i \ in [M]: \ pr \ limites_ {x \ in u} [h (x)= i]=frac {1} {m} $ .No nosso caso, temos:

$ \ pr [H (x)= i]=pr \ big [\ lFlor mx \ rfloor= i \ big]=pr [i \ le mx .

.

Nós usamos o fato de que, se $ x $ é uniformemente distribuído sobre $ [0,1] $ então $ \ pr [a \ le x \ le b]= BA $ (a igualdade segura com todas as quatro combinações de $ \ le $ e $ <$ ).