Concentration Bound of $0/1$ permanent

Question

If I pick a random $0/1$ $n\times n$ matrix with $0$ occuring with probability $p$ then what does the distribution of the permanent look like?

Answer 1

Let $X_n$ denote the permanent of your random 0/1 $n\times n$ matrix. Then after normalizing, $X_n$ converges to a log-normal distribution [as does the determinant of the matrix]. That is, $\log(|X_n|)$ has a central limit theorem.

For references, see:

https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/div-classtitlethe-numbers-of-spanning-trees-hamilton-cycles-and-perfect-matchings-in-a-random-graphdiv/09FDBF0DCE75F834AEBD831B156753D5

or

https://mini.pw.edu.pl/~wesolo/publikacje/2002RemWesJTP.pdf

Or see the following recent paper that obtains a more nuanced result (as well as concentration results and bounds on moments).

https://arxiv.org/abs/1605.07570

Answer 2

(Something to start with.)

Denote the permanent by $P$. We have ${\mathbb E}(P)=(1-p)^nn!$. Now look at ${\mathbb E}(P^2)$. This is a sum over all pairs of permutations $\pi,\sigma$ of $(1-p)^{2n-fix(\pi^{-1}\sigma)}$, where $fix(\tau)$ denotes the number of fixed points of a permutation $\tau$. Thus $${\mathbb E}(P^2)=n!(1-p)^{2n}\sum_{\tau\in S_n} (1-p)^{-fix(\tau)}=n!^2(1-p)^{2n}\sum_{i=0}^n\frac1{i!}\left(\frac{p}{1-p}\right)^i,$$ see here, for example. For small $p$ this is close to $({\mathbb E} P)^2$ and thus we have a sort of concentration. When $p$ grows, the ratio ${\mathbb E}(P^2)/({\mathbb E}(P))^2$ grows, so we lose concentration.

Answer 3

I am not sure how precise you want to be about "distribution", but the concentration in the title hints that maybe you did not mean distribution in a precise sense (like limit law). If so, one could argues as follows:

First, the permanent is close (in the sense of concentration) to the square of the determinant of a matrix $Q$ with $Q_{i,j}=P_{i,j} \times N_{i,j}$ where $N_{i,j}$ are iid standard Gaussians. Indeed, This is the Gudsil-Gutman estimator, and Barvinok had shown that you get at most an exponential error. In fact, concentration is better - see the paper https://arxiv.org/pdf/1301.6268.pdf.

Now you need to ask, for a random Wigner matrix with entries product of Bernoulli and Gaussian, how does the determinant concentrate. A lot is known on that too - see e.g. https://terrytao.files.wordpress.com/2008/03/determinant.pdf and papers by Tao-Vu and Costello-Vu.