Probability of two strings being equal

Question

Given a matrix $A\in F_2^{n\times m}$, (let $m< n$ and $A$ has full column rank) what is the probability under the distribution ( $y,y'$ uniformly random in $\{0,1\}^m$), such that $Ay=y'$? I am not sure if it should be $1/2^m$ or $1/2^n$.

Answer 1

You didn't specify a distribution; I'll assume uniform distributions throughout.

$y'$ may or may not be in the image of $A$. If it is, then since $A$ has full column rank, there's exactly one $y\in\mathbb F_2^m$ such that $Ay=y'$, so the probability is $2^{-m}$. If it isn't, then the probability is $0$.

If instead $y'$ is picked randomly, the probability of it being $Ay$ is $2^{-n}$; so this is also the probability for $Ay=y'$ if both $y$ and $y'$ are picked randomly.

Answer 2

The answer is $1/2^m$ or $0$, depending on whether $y'$ is in the range of $A$ or not. Try the case $m=1$ to get a feel for this.