Q$\mathrm{.}5.$ Locality sensitive hashing $($LSH$)$ focuses on pairs of signatures likely to be from similar

documents. It partitions the signature matrix $M$ into $b$ bands of $r$ rows each. Suppose $M$ has $100$

rows and $100000$ columns and $b=20$ bands and the goal is to find pairs of documents that are

at least $80\%$ similar. Answer the following: $2**2\mathrm{.}5=5M$

a$.$ If column $1$ and $3$ in $M$ are $85\%$ similar, then what is the probability that we may miss

this pair as a candidate pair? $[10$M$]$

b$.$ If columns $1$ and $6$ in $M$ are $60\%$ similar, then what is the probability that they end up as

a candidate pair?