I read this sentence on mit.ocw and don't understand why this completely random function would need $|U|\log n$ bits to be described?

Unfortunately, if we choose a hash function h that happens to be a completely random function from U to [n], we would actually need $|U|\log n$ bits to describe it.


The word random is misplaced here, the question is how many bits are required to describe a function from $U$ to $\{1,...,n\}$. The connection to randomness here is simply the fact that you need to deal with an arbitrary function (since you pick one uniformly at random). Thus, you cannot rely on any structure of the function, which could allow a more compact description (e.g. a constant function would require only $\log n$ bits to describe).

One way to look at it, is saying that you need to specify the output for every possible input. Since there are $|U|$ possible inputs, and specifying an element in the range requires $\log n$ bits, this results in a $|U|\log n$ length description. You can also use the fact that there are $n^{|U|}$ different functions from $U$ to $[n]$, so you need $\log n^{|U|}=|U|\log n$ bits to index an element in this set.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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