Setup: Given $a,b\in\mathbb{N}$, and $b\geq a$ such that $b/a\in\mathbb{N}$, I generate (i.e., uniformly sample amongst all possible matrices) a random constrained matrices $\mathbf{A}\in\{0,1\}^{a,b}$, where $a$ is the number of rows and $b$ is the number of columns, such that each column of $\mathbf{A}$ contains exactly one element 1 (i.e., weight of one), and each row of $\mathbf{A}$ contains exactly $b/a$ elements 1 (i.e., weight of $b/a$). This implies that any individual column is uniformly distributed among all length-$a$ columns of weight one (in total there are only $a$ such columns).
Question: Looking at just two columns, given that I know one column in $\mathbf{A}$, I know intuitively that the probability that my second column has 1 in the same row as the first is less than $1/a$ because the first column tells me that the row budget (of the row where it has a 1 in) is less than the row budget of other rows. How do I show this rigorously?
Best Answer
The required probability is $\dfrac{b/a-1}{b-1}$. There are many ways to see this, here is a particularly long winded one.
Call the two columns $S$ and $T$. Call the row of the $1$ in column $S$ as $R$.
The number of matrices that satisfy the given conditions that have a $1$ in the position $(R,S)$ (intersection of $R$ and $S$) is
$${b-1\choose b/a-1}{b-b/a\choose b/a}\cdots{b-(a-1)b/a\choose b/a} ------ (1)$$
because the # of ways to choose 1's in the row $R$ is the first term and the ways of choosing $1$'s in the rest of the rows are the subsequent terms (order of rows doesn't matter)
Similarly the number of matrices that satisfy the given conditions that have a $1$ in the position $(R,S)$ and a $1$ in position $(R,T)$ is
$${b-2\choose b/a-2}{b-b/a\choose b/a}\cdots{b-(a-1)b/a\choose b/a}------ (2)$$
Divide $(2)$ by $(1)$ to get the required probability $=\dfrac{b/a-1}{b-1}$
To see that this is less than or equal to $1/a$, suppose $\dfrac{b/a-1}{b-1} \geq \dfrac{1}{a}$. Then $\dfrac{b-a}{b-1} \geq 1$ which is only possible if $a = 1$ in which case equality holds. If $a>1$ then $\dfrac{b/a-1}{b-1} < \dfrac{1}{a}$.