Probability of intersection of sparse vectors

Question

Pick two $k$-sparse $\{0,1\}^n$ vectors $u,v$ uniformly ($k$-sparse implies we vectors have exactly $k$ coordinates $1$s). What is the probability that they intersect at exactly $i\in\{1,\dots,k\}$ coordinates which are $1$ and what is the probability they do not intersect?

Answer 1

There are $\binom{n}{k}$ different $k$-sparse vectors of length $n$.

Since each is equally likely, it suffices to consider the reference vector $(1,\ldots, 1, 0,\ldots,0)$ with the first $k$-entries equal to $1$, and the remaining equal to $0$, and to ask what is the probability that a uniformly selected $k$-sparse vector intersects this this reference vector at $i$ coordinates.

For this to happen, the new vector must have exactly $i$ of the first $k$ entries equal to $1$, and $(k-i)$ of the remaining $(n-k)$ entries equal to $1$. There are exactly

$$\binom{k}{i} \binom{n-k}{k-i}$$

such vectors. Therefore the probability of intersecting at $i$ sites is

$$P(i) = \frac{ \binom{k}{i} \binom{n-k}{k-i} } { \binom{n}{k} }.$$

Note that if $k - (n-k) = 2k - n =j > 0$ then the vectors will always intersect in at least $j$ entries, and hence we must correct for $$P(i) = 0, \qquad \text{if i < j.}$$