Suppose $L_1$ and $L_2$ are the lists of random uniform elements with sizes $m$. The elements are from $\{0,1\}^{n}$, e.g. the binary vector in $F_2^n$. What is the probability that $x_1 \in L_1$ and $x_2 \in L_2$ such that $x_1 = x_2$ ?
I need a formal proof for it. My idea is as followed: Let $X=a$($Y=b$) be the random variable that take element $a$(b) from the list, then $P(X=a, Y=b)=\frac{1}{m^{2}}$. We need to calculate the probability $P(X=Y)$. We use $P(X=Y) = \sum_{a \in L_1, b\in L_2} P(a==b|X=a,Y=b) P(X=a, Y=b)$. The $P(a=b|X=a, Y=b)$ means the probability that $a$ is equal to $b$ under the condition that we take element $a(b)$ from $L_1(L_2)$, then what is this probability? Or what is the alternative proof?
No, $P(X=Y)=\frac 1{2^n}$ because there is only one value from each list being considered. You would sum over the possible values of $X$ and $Y$ if you want the expected number of matches between the two lists and get $\frac {m^2}{2^n}$ for that answer.