7

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?

Jairo Bochi
  • 2,411
Turbo
  • 13,684
  • 1
    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 $1-p$? – Robert Israel Feb 16 '17 at 04:55
  • Perhaps see: http://mathoverflow.net/questions/45822/anti-concentration-bound-for-permanents-of-gaussian-matrices – Ryan O'Donnell Feb 16 '17 at 12:42

3 Answers3

6

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

Pat Devlin
  • 2,660
4

(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.

Fedor Petrov
  • 102,548
  • You mean, close to $(\mathbb{E} P)^2$. – Jairo Bochi Feb 16 '17 at 12:53
  • 1
    Is it possible to explicitly compute the probability of P=0? – Jairo Bochi Feb 16 '17 at 13:51
  • @FedorPetrov how did you go from sum over $\tau$ to sum over $i$? – Turbo Feb 17 '17 at 05:39
  • for fixed $\pi$, we vary $\sigma$, and $\tau:=\pi^{-1}\sigma$ runs over all permutations – Fedor Petrov Feb 17 '17 at 06:46
  • 1
    @JairoBochi : Computing the probability that $P=0$ is a long-standing 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., https://terrytao.files.wordpress.com/2008/04/permanent.pdf among many others.) – Pat Devlin Feb 17 '17 at 17:55
1

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.

ofer zeitouni
  • 7,434