Problem $3(4$ points$)$ Let $x$ and $Y$ be finite sets and let $Y^x$ denote the set of all

functions from $x$ to $Y.$ We call every subset $Hsube{Y}^x$ a family of hash functions and

each function of $H$ a hash function. A family of hash functions $Hsube{Y}^x$ is said to

be strongly $2-$universal if the following property holds, with hinH picked uniformly at

random:

AAx,$x^{\text{'}}$inxAAy,$y^{\text{'}}$inY$(x{x}^{\text{'}}=>P{r}_h[h(x)=y^{{?}^{?}}h(x^{\text{'}})=y^{\text{'}}]=\frac{1}{|Y{|}^2}).$

Let $Hsube{Y}^x$ be a strongly $2-$universal hash family with $|Y|=c{M}^2$ for some constant

$c>0.$ Suppose we use a random function hinH to hash a multi$-$set $($a multi$-$set can

contain the same element multiple times$)$ of elements of $x,$ and suppose that $$ contains

at most $M$ distinct elements. Prove that the probability of a collision $($i$.$e$.,$ the event

that two distinct elements of $$ are hashed to the same value$)$ is at most $\frac{1}{2c}.$

Hint: You can first compute the expected number of collisions and then use Markov's

inequality.