7
$\begingroup$

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?

$\endgroup$
2
  • 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 $1-p$? $\endgroup$ Feb 16, 2017 at 4:55
  • $\begingroup$ Perhaps see: mathoverflow.net/questions/45822/… $\endgroup$ Feb 16, 2017 at 12:42

3 Answers 3

6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ You mean, close to $(\mathbb{E} P)^2$. $\endgroup$ Feb 16, 2017 at 12:53
  • 1
    $\begingroup$ Is it possible to explicitly compute the probability of P=0? $\endgroup$ Feb 16, 2017 at 13:51
  • $\begingroup$ @FedorPetrov how did you go from sum over $\tau$ to sum over $i$? $\endgroup$
    – Turbo
    Feb 17, 2017 at 5:39
  • $\begingroup$ for fixed $\pi$, we vary $\sigma$, and $\tau:=\pi^{-1}\sigma$ runs over all permutations $\endgroup$ Feb 17, 2017 at 6:46
  • 1
    $\begingroup$ @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., terrytao.files.wordpress.com/2008/04/permanent.pdf among many others.) $\endgroup$
    – Pat Devlin
    Feb 17, 2017 at 17:55
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.