I'm trying to understand the complete proof of the May-Wigner theorem. We have a real random $n\times n$ matrix $B$ with its non-zero elements $B_{ij}$ are chosen independiently from a fixed distribution of mean 0 and variance $\alpha^2$. The porcentage of non-zero elements in $B$ is $C$, $0<C<1$. We consider a directed graph $G$ with $n$ vertices and one directed edge from vertex j to vertex I for each non-zero entry $B_{ij}$. Moreover, $B^N$ is the product of $N$ times the matrix B ($n<<N<<n\log n$) and its elements $B_{ij}^N$ are sums of non-zero N-fold products of entries of $B$: $B_{ij_1}B_{j_1j_2}...B_{j_{N-1}j}$ where subcrits may be repeated. Those products may be interpreted as a path of length $N$, with possible overlaps, from vertex $j$ to vertex $i$ in the graph $G$. Let $b$ be one non-zero summand of $B_{ij}^N$ and $nC>1$. We shall call a second such summand $b'$ a matcking summand for $b$ if their product involves only even exponents when written as a product of powers of distinct entries of $B$ (and in this case we know that $bb'$ is non-zero, because all odd moments are zero of the distribution of the hypothesis). We can obtain matching summands for $b$ in this way: first, the path in $G$ associated with $b$ may contain several subpaths from a vertex $s$ to a vertex $r$. We allow but do not require $r=s$. If there are t such subpaths ($t\le N$). All distinct, then $t\!$ matching summands for $b$ may be obtained by permuting these subpaths (no repetitions). If some of these subpaths are repeated, then there are less than $t\!$ such matching summands (because of the combination with repetition formule). We obtain an upper bound on the expected number of such summands (of $B_{ij}^2$, this is the objective of this section) by first fixing $r$ and $s$ (there are $n^2$ such pairs of species) and then maximizing the product $B$ of the probability of obtaining $t$ such subpaths by $t!$. An assymptotic counting argument yields: $B\sim(\frac{N}{tn})^{2t}t^t$. I'm trying to understand this last conclusion, if $B$ refers to the probability of obtaining $t$ subpaths multiplied by $t!$, then the $t^t$ on the right would be explained by the Stirling's approximation: $t\!\sim t^t$ for large $t$. But I don't know how to conclude the rest. The proof continues by the maximization of this conclusion by $t\sim\sqrt\log n$...

  • 3
    $\begingroup$ Paragraph breaks are your friend... $\endgroup$ – YuiTo Cheng Apr 2 '19 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.