3
$\begingroup$

Obtain $M\in\{-1,+1\}^{n\times n}$ by unbiased coin flipping.

What is known about the distribution of permanent $\mathsf{Perm}(M)$? It seems to be bimodal.

Given a function $g(n)$ what is the function $f(m)$ (at least approximately) such that probability $$\mathsf{Prob}\big(|\mathsf{Perm}(M)|\in\big(\mathsf{E}[|\mathsf{Perm}(M)|]-g(n),\mathsf{E}[|\mathsf{Perm}(M)|]+g(n)\big)\big)\geq f(n)$$ holds for some $a>0$ where $\mathsf{E}[|\mathsf{Perm}(M)|]$ is expected absolute value permanent over ${M\in\{-1,+1\}^{n\times n}}$?

Can $g=O\big(n^{-c\log n}\big)$ and $f=\Omega\big(n^{-d\log n}\big)$ simultaneously hold for some $c,d>0$?

That is if we seek then the fraction of matrices with permanent close to mean the fraction should be lower bounded generously as well reasonably which should mean concentration is large.

I think this is false and for $\{0,1\}^{n\times n}$ case as the comments suggest it seems false as well.

The closest reference I found was here https://arxiv.org/pdf/0804.2362v3.pdf which looks insufficient.

Is there a lower bound on probability that $\mathsf{Perm}(M)\in(-n^{c\log n},n^{c\log n})$ is valid?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin P. Costello
    Commented Oct 21, 2016 at 0:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – usul
    Commented Oct 21, 2016 at 0:59
  • $\begingroup$ @KevinP.Costello "(overly) tight concentration for the determinant" makes it sound what I seek is impossible. Is it your judgement? $\endgroup$
    – user94040
    Commented Oct 21, 2016 at 6:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin P. Costello
    Commented Oct 21, 2016 at 19:06
  • $\begingroup$ @KevinP.Costello I wrongly guessed expected value (may be now there is an analogy with determinants). $\endgroup$
    – user94040
    Commented Oct 21, 2016 at 19:20

0

Reset to default

You must log in to answer this question.