I have a 163x163 binary Matrix (contains only 1s and 0s). Each row has exactly 4 ones and 159 zeros(assume random). I want mainly to find the probability of the first row to share (exactly or at least, it does not matter) two ones in the same column with other row.

To give an example: a success is found if both the first and eleventh row contain a 1 in their 47th and 100th column.

If I am not clear I apologize, just let me know and I'll try to explain better. Using this, I will later attempt to find the expected value of the total number of columns that have another column that shares (exactly or at least) two ones with it.

Thank you very much!


Let $p$ be the probability that Row $1$ and Row $i\ne 1$ do not share at least two $1$'s. Then the probability none of the $162$ rows below the first share at least two $1$'s with the first row is $p^{162}$. So the probability at least one row does share two or more $1$'s with the first row is $1-p^{162}$. Thus once we find $p$ we will be finished.

Imagine that the $1$'s for Row $1$ have been picked, and are fixed from now on.

There are $\binom{163}{4}$ equally likely ways to place four $1$'s in Row $i$. There are $\binom{159}{4}$ ways to choose the locations of these $1$'s so that they are all in columns distinct from the columns in which Row $1$ has a $1$.

Now we count the number of ways there is an overlap in exactly one column. The column where the overlap occurs can be chosen in $\binom{4}{1}$ ways, and the $3$ non-overlap columns can be chosen in $\binom{159}{3}$ ways, for a total of $\binom{4}{1}\binom{159}{3}$. It follows that $$p=\frac{\binom{159}{4}+\binom{4}{1}\binom{159}{3}}{\binom{163}{4}},$$ and now we have all the information we need.

  • $\begingroup$ Thanks a lot, if I could give you more upvotes I would!!! Perfectly explained. $\endgroup$ – Gaspa79 Apr 21 '15 at 22:23
  • $\begingroup$ You are welcome. The setting is different from the usual ones, but the tools are standard. The further question that you referred to can be tackled using indicator random variables. $\endgroup$ – André Nicolas Apr 21 '15 at 22:41

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.