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?

1$\begingroup$ Equivalently, what is the distribution of the number of perfect matchings in a random bipartite graph with $n$ vertices in each part and each possible edge having probability $1p$? $\endgroup$ – Robert Israel Feb 16 '17 at 4:55

$\begingroup$ Perhaps see: mathoverflow.net/questions/45822/… $\endgroup$ – Ryan O'Donnell Feb 16 '17 at 12:42
Let $X_n$ denote the permanent of your random 0/1 $n\times n$ matrix. Then after normalizing, $X_n$ converges to a lognormal distribution [as does the determinant of the matrix]. That is, $\log(X_n)$ has a central limit theorem.
For references, see:
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).
(Something to start with.)
Denote the permanent by $P$. We have ${\mathbb E}(P)=(1p)^nn!$. Now look at ${\mathbb E}(P^2)$. This is a sum over all pairs of permutations $\pi,\sigma$ of $(1p)^{2nfix(\pi^{1}\sigma)}$, where $fix(\tau)$ denotes the number of fixed points of a permutation $\tau$. Thus $${\mathbb E}(P^2)=n!(1p)^{2n}\sum_{\tau\in S_n} (1p)^{fix(\tau)}=n!^2(1p)^{2n}\sum_{i=0}^n\frac1{i!}\left(\frac{p}{1p}\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.


1$\begingroup$ Is it possible to explicitly compute the probability of P=0? $\endgroup$ – Jairo Bochi Feb 16 '17 at 13:51

$\begingroup$ @FedorPetrov how did you go from sum over $\tau$ to sum over $i$? $\endgroup$ – 1.. Feb 17 '17 at 5:39

$\begingroup$ for fixed $\pi$, we vary $\sigma$, and $\tau:=\pi^{1}\sigma$ runs over all permutations $\endgroup$ – Fedor Petrov Feb 17 '17 at 6:46

1$\begingroup$ @JairoBochi : Computing the probability that $P=0$ is a longstanding open problem with lots of intermediate progress and literature on the subject. Do a google search for the very related question asking "what's the probability that a random matrix is singular" [the answer there is conjectured to be roughly equal to the probability that two rows or columns are linearly independent]. In fact, it was hard even to show that $P=0$ is unlikely! (See, e.g., terrytao.files.wordpress.com/2008/04/permanent.pdf among many others.) $\endgroup$ – Pat Devlin Feb 17 '17 at 17:55
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 GudsilGutman 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 TaoVu and CostelloVu.