Timeline for On the precise concentration of permanent of $\pm1$ matrices
Current License: CC BY-SA 3.0
34 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 27, 2016 at 23:15 | history | edited | user94040 | CC BY-SA 3.0 |
added 24 characters in body
|
| Oct 25, 2016 at 8:09 | history | undeleted | user94040 | ||
| Oct 25, 2016 at 0:22 | history | deleted | user94040 | via Vote | |
| Oct 25, 2016 at 0:22 | history | undeleted | user94040 | ||
| Oct 25, 2016 at 0:04 | history | deleted | user94040 | via Vote | |
| Oct 24, 2016 at 23:04 | history | edited | user94040 | CC BY-SA 3.0 |
[Edit removed during grace period]
|
| Oct 24, 2016 at 22:56 | history | edited | user94040 | CC BY-SA 3.0 |
added 138 characters in body
|
| Oct 24, 2016 at 22:53 | comment | added | user94040 | @KevinP.Costello without $|\cdot|$ (absolute value) what probability does $\mathsf{Perm}(M)\in(-f(n),f(n))$ hold for some fixed function $f(n):\Bbb N\rightarrow\Bbb N$? | |
| Oct 23, 2016 at 23:22 | history | edited | user94040 | CC BY-SA 3.0 |
deleted 9 characters in body
|
| Oct 23, 2016 at 23:16 | comment | added | user94040 | @user36212 ok great comment I will remove $\{0,1\}$ case. Please feel free to expand your comment as answer. Could you also post your references for fact that concentration cannot be tight? An expanded answer would help understand greatly | |
| Oct 23, 2016 at 23:16 | history | edited | user94040 | CC BY-SA 3.0 |
added 165 characters in body; edited title
|
| Oct 23, 2016 at 23:01 | history | edited | user94040 | CC BY-SA 3.0 |
deleted 122 characters in body; edited title
|
| Oct 23, 2016 at 23:00 | comment | added | user36212 | At least for 0/1 matrices, it is false. The expected permanent for a p-biased choice of 0/1 is $n!p^n$; if you increase $p$ by a factor $1+1/n$ you multiply the result by $e$. If you believe the permanent is close to expectation for $p=1/2$, why not for all constant $p$..? But the standard deviation in the number of $1$s in your matrix is about $n$, so you expect that reasonably often your matrix will look like a $p(1+1/n)$-random matrix. | |
| Oct 23, 2016 at 22:53 | comment | added | user94040 | @user36212 so you think the anti-concentration I seek is false? | |
| Oct 23, 2016 at 22:52 | history | edited | user94040 | CC BY-SA 3.0 |
added 68 characters in body
|
| Oct 23, 2016 at 22:49 | comment | added | user36212 | I think Janson has some papers proving log-normality of matching counts, though as far as I know they focus on the sparse case (i.e. only a few 1s and mainly 0s). | |
| Oct 23, 2016 at 22:47 | comment | added | user36212 | @KevinP.Costello In fact I would be fairly confident that the permanent is log-normally distributed in the limit. For a lazy heuristic why this should be true (but it's enough to show that better than log-normal concentration is definitely false, and get quite close to log-normal): observe that the permanent of a uniform random 0/1 nxn matrix is the number of matchings in a uniform random bipartite graph, whose logarithm (by the solutions of the van der Waerden / Bregman conjectures) we know is basically controlled by the number of edges; and that's normally distributed in the limit by CLT. | |
| Oct 23, 2016 at 21:14 | history | edited | user94040 | CC BY-SA 3.0 |
added 60 characters in body; edited title
|
| Oct 23, 2016 at 0:26 | comment | added | Nick Cook | @usul -- Aaronson actually asked about this on MO here: mathoverflow.net/questions/45822/… (which also shows up to the right of this page as the most related question, for me at least). | |
| Oct 21, 2016 at 19:24 | history | edited | user94040 | CC BY-SA 3.0 |
added 228 characters in body
|
| Oct 21, 2016 at 19:20 | comment | added | user94040 | @KevinP.Costello I wrongly guessed expected value (may be now there is an analogy with determinants). | |
| Oct 21, 2016 at 19:18 | history | edited | user94040 | CC BY-SA 3.0 |
added 228 characters in body
|
| Oct 21, 2016 at 19:06 | comment | added | Kevin P. Costello | Not "impossible" so much as "very hard to prove", even if it's true. For an $n \times n \pm 1$ matrix $A$, with asymptotically positive probability we have $$|\det(A)|>\sqrt{(n-1)!} e^{\sqrt{\log n} },$$ and with asymptotically positive probability we have $$|\det(A)| < \sqrt{(n-1)!} e^{-\sqrt{\log n}}.$$ So for the determinant, there's no bound of the sort you're asking for. And the ways I know of for getting a handle on random permanents (e.g. expansion by minors, as in the Tao-Vu paper) would give identical bounds if you replaced "permanent" by "determinant" everywhere. | |
| Oct 21, 2016 at 13:49 | history | edited | user94040 | CC BY-SA 3.0 |
deleted 36 characters in body
|
| Oct 21, 2016 at 6:53 | history | edited | user94040 | CC BY-SA 3.0 |
edited tags
|
| Oct 21, 2016 at 6:51 | comment | added | user94040 | @KevinP.Costello "(overly) tight concentration for the determinant" makes it sound what I seek is impossible. Is it your judgement? | |
| Oct 21, 2016 at 6:37 | history | edited | user94040 | CC BY-SA 3.0 |
added 14 characters in body
|
| Oct 21, 2016 at 0:59 | comment | added | usul | Vaguely related -- in his recent talk at Avi Wigderson's birthday, at 38:10 (I suggest starting at 37:00), Scott Aaronson mentioned it as an open problem to understand the distribution of the permananent of matrices with i.i.d. Gaussian entries. (We might expect the answer to be similar to those with your distribution...) He said that experiments show it to be lognormal as with the determinant. | |
| Oct 21, 2016 at 0:21 | comment | added | Kevin P. Costello | If you replace permanent by determinant, the limiting distribution is fairly well understood: $\log\left(| Det(A) |\right)$ is asymptotically normal with mean $\frac{1}{2} \log( (n-1)! )$ and variance $\sqrt{0.5 \log n}$ (see, for example, arxiv.org/pdf/1112.0752.pdf ). The concentration is of the logarithm instead of the determinant itself. I find it hard to imagine any argument that could give the tight concentration you want for the permanent without giving a similarly (overly) tight concentration for the determinant. | |
| Oct 20, 2016 at 23:04 | history | edited | user94040 | CC BY-SA 3.0 |
edited title
|
| Oct 20, 2016 at 23:02 | history | undeleted | user94040 | ||
| Oct 20, 2016 at 23:02 | history | deleted | user94040 | via Vote | |
| Oct 20, 2016 at 22:58 | history | edited | user94040 | CC BY-SA 3.0 |
added 64 characters in body; edited title
|
| Oct 20, 2016 at 22:03 | history | asked | user94040 | CC BY-SA 3.0 |