# Symmetric choice problem

Given a $n \times n$ zero matrix, one can randomly choose $k$ distinct cells in the upper triangle (excluding the diagonal, thus $\frac{n^2-n}{2}$ possible cells to choose from, each cell has the same probability to be chosen). When the cell are chosen, their value are flipped as $1$, and the corresponding cells in the lower triangle are also flipped to keep the matrix symmetric.

What is the probability of the $i$th row getting $c$ $1$s, $i= 1,...,n$?

My guess is the probability of $c$ ones for each row is the same, thus it could be $\frac{{\left( {\begin{array}{*{20}{c}} {n - 1} \\ c \end{array}} \right)\left( {\begin{array}{*{20}{c}} {\frac{{{n^2} - n}}{2} - (n - 1)} \\ {k - c} \end{array}} \right)}}{{\left( {\begin{array}{*{20}{c}} {\frac{{{n^2} - n}}{2}} \\ k \end{array}} \right)}}$, which is the probability of $c$ $1$s in the first row.

Need help to prove the number of $1$s in every row has the same probability distribution.

• @user202729 No. Sorry for not being clear. I have edited the question. – Tony Jan 13 '18 at 4:14
• @user202729 Yes. That is right. Thanks! – Tony Jan 13 '18 at 4:17
• @quasi Yes. Thanks! – Tony Jan 13 '18 at 4:21

The total number of possible ways is $\frac{n^2-n}2 \choose k$. So the denominator is right.

The $i$th row has $n-1$ non diagonal entries... There are ${n-1} \choose c$ ways to get $c$ ones, for each of the $\frac{n^2-n}2 -(n-1)\choose {k-c}$ ways of filling out the rest of it... Note : if $c\gt k$, we get $0$...

Looks right. ..

Note that, in the $i^{th}$ row, the number of $1$'s among $a_{ij}, j<i$ is same as the number of $1$'s among $a_{ji},j<i$, of the $i^{th}$ column.Suppose we want to know if there are $c$ $1$'s in the $i^{th}$ row. It is equivalent to checking the numbers $a_{ij}$ for $j>i$, $a_{ji}$ for $j<i$.

Then the $(n-1)$ cells ($a_{ij}$ for $j>i$, $a_{ji}$ for $j<i$) among the the $\frac{n^2-n}2$ upper triangular cells contains $c$ $1$'s.

I am pretty sure you can work out the rest.

• $a_{ii}$ is always $0$, by the construction of the matrix. – user202729 Jan 13 '18 at 4:23
• oh I didnt notice. I edited the answer. – QED Jan 13 '18 at 4:35