Skip to main content
1 of 2
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

(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$ 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
  • 108.9k
  • 9
  • 264
  • 459