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.

  • $\begingroup$ @user202729 No. Sorry for not being clear. I have edited the question. $\endgroup$ – Tony Jan 13 '18 at 4:14
  • $\begingroup$ @user202729 Yes. That is right. Thanks! $\endgroup$ – Tony Jan 13 '18 at 4:17
  • $\begingroup$ @quasi Yes. Thanks! $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.