Supposed we have a function $h:U\to [m_1]$. Given this hash function, can we generate without using randomization or a universal hash collection another hash $h':U \to [m_2]$, which depends on $h$ and the values of $h'(x)$ are uniform? i.e., for every value $y\in [m_2]$ we have $\Pr_{x} (h'(x)=y|h(x)=t)=1/m_2$ ($x$ is chosen at random).

I know that if $U=[2^t]$, $m_1=2^{n_1}$, $m_2=2^{n_2}$, $t>n_1+n_2$ and $h(x)$ is the first $n_1$ bits of $x$ this problem is easy: we can select $h'(x)$ to be the bits $n_1+1$ till $n_2$ of $x$. My question is how to generalized this approche.


1 Answer 1


From what I have understand from your question, I think you are looking for a way to transform a probability distribution to another probability distribution. For example, if your first hash function distributes your data into a gaussian/normal form into the buckets, then you need a function that takes the index of this bucket as input and gives you another bucket which must be chosen uniformally. This post may be helpful if I ve understand correctly what you are trying to achieve: https://stats.stackexchange.com/questions/223317/how-to-transform-one-pdf-into-another-graphically My personal opinion is that a successful transformation depends a lot in your data. A hash function tries to distribute the data uniformally in the first place. But, even if you have a function G that distributes your data in a "weird" way then you can make a transformation T: G -> F so that F is whatever distribution you like.

[EDIT] I don't think that this is achievable without using randomization. For example, if you have a hash function that maps all your data into one bin (for example the bin 0) then this function is constant. So, you are trying to create a function that takes a constant value and maps it uniformally, which cannot be done if you don't use any randomness or internal memory. By internal memory, I mean that your function "should remember" what kind of inputs has already "seen", and map them in a different value each time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.