6
$\begingroup$

Given a matrix $W_{n,m}$ whose each entry $w_{ij}$ is 1 or -1 or 0 with probability $p$, $p$ and $1-2p$ respectively, $0<p<0.45$

Let $R_i$ be the sum of $i^{th}$ row and $C_{j}$ is the sum of $j^{th}$ column.

What is the probability that row sums are greater than 0 and column sums are greater than 0, i.e

$$P(R_1>0,R_2>0,...,R_n>0,C_1>0,C_2>0,...,C_m>0)$$

Finding all possible combinations such that row sums and column sums are greater than 0 is not easy. Please help me on how can I proceed, either to find exact probability or upper bound it.

$\endgroup$
5
  • $\begingroup$ It is not less than the product of probabilities $P(R_1>0)^n P(C_1>0)^m$, which is close to $2^{-n-m}$ (though slightly less cause of strict inequality) by monotone events correlation inequality (a variant of Kleitman lemma). $\endgroup$ Commented Jan 18, 2019 at 21:20
  • 3
    $\begingroup$ This is an interesting and difficult problem, so I don't know why someone would vote to close it. $\endgroup$ Commented Jan 19, 2019 at 1:54
  • $\begingroup$ @BrendanMcKay somebody does not consider it to be of research level. Good to have so high level users here! $\endgroup$ Commented Jan 19, 2019 at 8:31
  • $\begingroup$ @FedorPetrov - Since $P(R_1>0)$ and $P(R_1<0)$ are same, $P(R_1>0)$ should be upper bounded by $0.5$. Hence using independent assumption $2^{-n-m}$ should be the upper bound. Please correct me if I am wrong $\endgroup$ Commented Jan 19, 2019 at 21:19
  • $\begingroup$ @user2490585 it is a lower bound, not upper. And it is not sharp, see the answer by Brendan McKay below. $\endgroup$ Commented Jan 19, 2019 at 21:24

1 Answer 1

6
$\begingroup$

To the best of my knowledge, there is no known result that applies to this case immediately. I'll mention some articles which demonstrate techniques that could be used.

Riordan and Selby (2000) found the exponential part of the probability that a random graph $G_{n,p}$ has all degrees greater than a given value close to the mean. Interesting, they showed that if $P_n(p)$ is this probability, then $P_n(p)^{1/n}\to C$ for $n\to\infty$ with fixed $p$, where $C\approx 0.61023$ is independent of $p$.

McKay, Wanless and Wormald (2002) found the precise probability for the same problem, but only when $p$ is close to $\frac12$.

Ordentlich, Parvaresh, and Roth (2012) found a very good approximation of the probability that a random $n\times n$ binary matrix has all row and column sums at least $\frac12 n$.

You will see that the calculations are quite laborious even if only an approximation is needed. From the second one you can also see that the asymptotically exact answer can be complicated too.

In all these cases, the effect of non-independence is very strong. For example, in the third case, although one might guess a probability in the order of $2^{-2n}$, the actual probability is close to $2^{-1.46n}$. The row sums are independent, and the column sums are also independent, but the column sums conditional on the row sums being large are very different from the unconditional column sums.

$\endgroup$
3
  • $\begingroup$ I may be confused, but... To clarify, one is talking 0/1 entries in (3), so the probability of at least $n/2$ ones in each row and column seems to be the same (taking $n$ odd for convenience) as the probability that the OP's sums are all positive, except it applies to the case $p=1/2$? Since his symbols are $0-$biased, $2^{-1.46n}$ is an upper bound to his requested probability. $\endgroup$
    – kodlu
    Commented Jan 19, 2019 at 5:12
  • $\begingroup$ @kodlu Yes, the third example matches the OP's problem for $p=\frac12$. But can you give a rigorous proof that the probably is less for smaller $p$? I don't find it obvious. Also see what I'm about to add to the first example. $\endgroup$ Commented Jan 19, 2019 at 7:14
  • $\begingroup$ @BrendanMcKay - Thanks a lot for your insights. As part of deriving an upper bound for my research problem, this probability is a component of the upper bound (This probability needs to be calculated such that m and n vary over a range). Actually I am more interested in calculating $P(R_1>0,..R_n>0|C_1>0,..,C_m>0)$. Initially I started with the assumption that $R_i|\{C_j\}_{j=1}^{m}$ are independent. However this is a very lose bound for small values of p, resulting in an incorrect upper bound. Thus non independence between rows is very strong for small values of p. I will go through reference $\endgroup$ Commented Jan 19, 2019 at 21:48

Your Answer

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

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