probability - If k-universal hash family then (k-1)-universal hash family

218 Views Asked by At

Regarding this question: If k-universal hash family then (k-1)-universal hash family

It's been answered and I dont understand the answer:

\begin{align} Pr[h(x_1) = i_1 &\land \cdots \land h(x_{k-1}) = i_{k-1}] \\&= Pr[h(x_1)=i_1 \land \cdots \land h(x_{k-1})=i_{k-1}\land h(x_k)=1] \\&+ Pr[h(x_1)=i_1 \land \cdots \land h(x_{k-1})=i_{k-1}\land h(x_k)=2]+\ldots \\&+Pr[ h(x_1)=i_1 \land \cdots \land h(x_{k-1})=i_{k-1}\land h(x_k)=m] \\&= \frac{1}{m^k}+\frac{1}{m^k}+\ldots +\frac{1}{m^k}=\frac{m}{m^k}=\frac{1}{m^{k-1}} \end{align}

Why is the first equality correct?

1

There are 1 best solutions below

1
On BEST ANSWER

By definition, $h$ takes one of the values $1$ through $m$. Thus the event that it takes certain values at $x_1$ through $x_{k-1}$ is the disjoint union over $1\le j\le m$ of the events that it takes those values and also the value $j$ at $x_k$. The probability of the disjoint union of events is the sum of the probabilities of those events.