La funzione hash, $ h (k)=lfloor km \ rfloor $ è semplice uniforme per $ k $ $ in modo indipendente, distribuito in modo uniforme nella gamma $ 0 \ Leq K <1 $

Question

Stavo attraversando l'introduzione del testo agli algoritmi di Cormen et. al. dove ho trovato la seguente dichiarazione:

.

Se i tasti sono noti per essere numeri reali casuali $ k $ distribuito in modo indipendente e uniformemente nella gamma $ 0 \ Leq k <1 $ , la funzione hash

$$ h (k)=lfloor km \ rfloor $$ Soddisfa la condizione di semplice hashing uniforme.

Ora quello che posso capire che probabilmente stanno prendendo in considerazione di disturbi uniformi nel senso "continuo" e non nel senso discreto. Era stato nel senso discreto, supponiamo quindi per $ N $ tasti la funzione di massa probabilità (PMF) deve essere costante e uguale a $ 1 / N $ E quindi sarà ugualmente probabile che ogni tasto venga utilizzato nel hashing lì - Yeilding il risultato desiderato.

Ma sembriamo un problema nei guai se la distribuzione si fa riferimento è continua (mi sento a causa della linea: "distribuita uniformemente in la gamma $ 0 \ Leq K <1 $ ")

Let $ f (x) $ Sii la funzione di densità di probabilità associata (PDF) e dalle informazioni fornite che abbiamo $ f (x)= 1 $ , (che è abbastanza facilmente trovato, integrando $ f (x) $ nella gamma $ 0 $ a $ 1 $ ed equiparandolo con $ 1 $ e notandolo Nella distribuzione uniforme, il PDF è una costante).

Ora anche se P.D.F è un costante ma P.D.F non è la probabilità. Piuttosto la probabilità in un punto di spettro è $ 0 $ . Ora come usare questo risultato per arrivare alla richiesta degli autori.

o sono interamente in errore considerando la distribuzione per essere continua?

(c'è una risposta qui , ma non va in questo dettaglio come la domanda che è diversa Dopo tutto).

Answer 1

$ h \ in [m] ^ u $ soddisfa la semplice capacità di hashing uniforme se quando $ x \ in u$ è scelto uniformemente a caso, quindi $ h (x) $ è distribuito uniformemente su $ [m]$ o equivalentemente $ \ forall I \ in [m]: \ PR \ Limits_ {x \ in u} [h (x)= i]=frac {1} {m} $ .Nel nostro caso abbiamo:

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

Abbiamo usato il fatto che se $ x $ è uniformemente distribuito su $ [0,1] $ Allora $ \ PR [A \ Le x \ le b]= BA $ (l'uguaglianza detiene con tutte e quattro le combinazioni di $ \ le $ e $ <$ ).