Timeline for Probability two products are equal
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 15, 2016 at 9:09 | vote | accept | Simd | ||
| Jan 15, 2016 at 9:08 | history | bounty ended | Simd | ||
| Jan 14, 2016 at 10:56 | comment | added | Simd | Yes exactly. What do "atypical" matrices, that is those whose probability is much larger than $2^{-n}$, look like? For matrices whose row rank is full (or are even orthogonal) it is tempting to believe that we need roughly the same number of $1$s and $-1$s in each row to get a probability like $2^{-n}$ but I suspect that is not sufficient. | |
| Jan 14, 2016 at 9:20 | comment | added | Dierk Bormann | So what you're saying is that a particular large matrix might be "atypical" in that sense, and you want a simple test for checking whether it is, am I right? | |
| Jan 14, 2016 at 9:14 | comment | added | Dierk Bormann | Now I understand. Well, with my argument I can only show that the fraction of such matrices whose probability is anything different from $2^{-n}$ must be exceedingly small for large $n$. | |
| Jan 13, 2016 at 22:24 | comment | added | Simd | My follow up question was slightly against the spirit of your answer. Let me put it another way. Say you have a particular large matrix $M$ with approx. $10n/\ln{n}$ rows and $n$ columns with rank $10n/\ln{n}$, say. Is there some property of the matrix that one can test from which one could work out if the probability will be approximately $2^{-n}$ or from which one could give some upper bound? I was originally hoping that orthogonality might be sufficient to get small probability but I think kodlu argued that that wouldn't be enough. | |
| Jan 13, 2016 at 21:04 | comment | added | kodlu | nice answer. it seems one can't go far without relaxing the fixed matrix assumption. | |
| Jan 13, 2016 at 20:55 | comment | added | Dierk Bormann | On the other hand, the majority of matrices with $m'/n < \ln{4}/\ln(\pi n/4)$ have a probability of the approximate form $P(M's=0) \approx \left(\pi n/4\right)^{- m'/2} = c^{-n}$, with $c = \left(\pi n/4\right)^{m'/2n}$ so that $1<c<2$. Of course this $c$ is not a constant, but at least it varies more slowly than exponentially with $n$. | |
| Jan 13, 2016 at 20:46 | comment | added | Dierk Bormann | Thanks a lot for your appreciation! I am not sure whether I fully understand your comment, but I believe the rank of $M$ might be such a property. Assume $m<n$ and let $m'$ be the rank of $M$. We can select $m'$ linearly independent rows of $M$ and form a new $m'\times n$-matrix $M'$. Then $M's=0$ is equivalent to $Ms=0$, i.e. in particular the probabilities are equal. My result above applied to $M'$ tells us that, for large $n$, among the matrices with $m'/n > \ln{4}/\ln(\pi n/4)$ only a negligibe fraction has a probability $P(M's=0)$ larger than $2^{-n}$. | |
| Jan 13, 2016 at 18:50 | comment | added | Simd | This is a wonderful answer. Thank you! Take the case where $q > \ln{4}/\ln(\pi n/4)$. I find it very interesting if there is no easily or efficiently identifiable property of $M$ which will determine if the probability is approximately of the form $2^{-n}$ (or indeed $c^{-n}$ for any constant $c>1$). Do you think that is the case? | |
| Jan 13, 2016 at 17:06 | history | answered | Dierk Bormann | CC BY-SA 3.0 |