La función hash, $ H (k)=lfloor km \ rfloor $ es un simple uniforme para reales $ k $ de forma independiente, distribuida uniformemente en el rango de $ 0 \ leq k <1 $

Question

Estaba pasando por el texto Introducción a los algoritmos de Cormen ET. Alabama. donde encontré la siguiente declaración:

Si se sabe que las claves son números reales aleatorios $ k $ distribuidos de forma independiente y uniformemente en el rango $ 0 \ leq k <1 $ , la función hash

$$ h (k)=lfloor km \ rfloor $$ Satisface la condición de simple hashing uniforme.

Ahora, lo que puedo entender que probablemente están considerando una perturbación uniforme en el sentido "continuo" y no en el sentido discreto. Si hubiera estado en el sentido discreto, supongamos que para $ n $ teclas La función de la masa de probabilidad (PMF) será constante e igual a $ 1 / n $ y por lo tanto, será igualmente probable que cada llave se use en el hashing por allí, por el resultado del resultado deseado.

Pero nos parecemos en problemas si la distribución a la que se hace referencia es continua (me siento por la línea: "distribuida uniformemente en el rango $ 0 \ leq k <1 $ ")

Permitir $ f (x) $ ser la función de densidad de probabilidad asociada (PDF) y de la información dada que tenemos $ f (x)= 1 $ , (que se encuentra con bastante facilidad, integrando $ f (x) $ en el rango $ 0 $ a $ 1 $ y equiparlo con $ 1 $ y señalando que En la distribución uniforme, el PDF es una constante).

Ahora, aunque el P.D.F es una constante, pero p.D.F no es la probabilidad. Más bien, la probabilidad en un punto de espectro es $ 0 $ . Ahora cómo usar este resultado para llegar a la reclamación de los autores.

¿O estoy enteramente por culpa, considerando que la distribución sea continua?

(hay una respuesta aquí , pero no entra en este detalle como la pregunta que hay diferente después de todo).

Answer 1

$ h \ in [m] ^ u $ satisface el simple supuesto de hashing uniforme si cuando $ x \ en u$ se elige uniformemente al azar, luego $ h (x) $ se distribuye uniformemente sobre $ [m]$ , o equivalentemente $ \ forall i \ in [m]: \ pr \ limits_ {x \ in u} [h (x)= i]=frac {1} {m} $ .En nuestro caso tenemos:

$ \ pr [h (x)= i]=pr \ big [\ lfloor mx \ rfloor= i \ big]=pr [i \ le mx .

Utilizamos el hecho de que si $ x $ se distribuye uniformemente sobre $ [0,1] $ Luego $ \ PR [A \ le x \ le b]= ba $ (la igualdad tiene con las cuatro combinaciones de $ \ le $ y $ <$ ).