The Exercise

A random variable $X$ takes values in a finite set $A$ with probability distribution $p$. A function $g$ from $A$ to the set $B$ of strings of $m$ bits is drawn uniformly at random from a family $\mathcal G$, and $X$ is replaced by its hashed value $G(X)$, where $G$ stands for the random choice. The family is universal when any two distinct inputs $x \neq x'$ collide, $g(x) = g(x')$, for at most a fraction $1/|B|$ of its members. The uncertainty left in the hashed value for someone who knows which function was drawn is measured by the conditional Shannon entropy $H(G(X)\mid G)$ and the conditional collision entropy $H_c(G(X)\mid G)$. For a universal family, Theorem 12.16 bounds both from below by the collision entropy $H_c(X) = -\log_2 \sum_x p(x)^2$ of the input: $$H(G(X)\mid G) \;\ge\; H_c(G(X)\mid G) \;\ge\; m - 2^{\,m - H_c(X)}.$$(1)

Entropies of a Hashed Variable

The law $\mu_Y$ of a random variable $Y$ on a finite sample space $\Omega$ under weights $\mu$ is the function on the values of $Y$ that gives each value $y$ the total weight of the outcomes at which $Y$ takes it, $$\mu_Y(y) = \sum_{\omega:\,Y(\omega) = y} \mu(\omega).$$(2)^✦ For a probability distribution $\mu$, the law $\mu_Y$ is the distribution of $Y$. Under $p$, the law $p_g$ of a hash function $g$ is the distribution of the hashed value $g(X)$ on $B$.

The collision probability of a distribution $q$ on a finite set is $P_c(q) = \sum_i q_i^2$.^✦ For a probability distribution, $P_c(q)$ is the probability that two independent draws from $q$ agree. For the hashed value, the average collision probability $P_c(G(X)\mid G)$ is the mean of $P_c(p_g)$ over the family, $$P_c(G(X)\mid G) = \frac{1}{|\mathcal G|} \sum_{g \in \mathcal G} P_c(p_g).$$(3)^✦ The conditional collision entropy $H_c(G(X)\mid G)$ of the hashed value given the choice of function is the negative logarithm in base two of $P_c(G(X)\mid G)$: $$H_c(G(X)\mid G) = -\log_2 P_c(G(X)\mid G).$$(4)^✦

The conditional Shannon entropy $H(G(X)\mid G)$ of the hashed value given the choice of function is the mean over the family of the Shannon entropy in bits of the hashed value, $$H(G(X)\mid G) = \frac{1}{|\mathcal G|} \sum_{g \in \mathcal G} H(p_g), \qquad H(q) = -\sum_{y} q(y) \log_2 q(y).$$(5)^✦

The Claim

What Is Checked

The claims are stated over the conditional entropies (4) and (5) of the hashed value, together with the collision probability $P_c(p)$ of the input distribution.

These are inequalities (6) and (7), and the existence claim (8).