1
$\begingroup$

Let there be a matrix $\alpha=(a_{i,j})_{i\in [m], j\in [n]}$, where $a_{i,j}\in\{0,1\}$ And every row has exactly $r\le n$ ones.

We independently with probability $p$ choose some columns from this matrix and mark everything in these columns.

What is a probability $P$ that we have marked every ones from at least one row?

I would like to see in answer a connection to properties of matrix $\alpha$, such as rank or determinant

For example if we take: $$\alpha=\left[\begin{array}{ccc}1&1&1&0&0&0\\0&0&0&1&1&1\\\end{array}\right]$$

Then probability looks like $P=2p^3-p^6$

So i suspect that in general we have $P=1-(1-p^{r})^{rank(\alpha)}$

But i may be wrong

Regards

$\endgroup$
1
  • $\begingroup$ The answer clearly depends on the matrix itself. Had your matrix two identical rows (or two overlapping by two common columns): the answer would be different. $\endgroup$ May 4, 2020 at 8:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.