Choosing an independent hash function, given hash function value

Question

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.

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.