Concentration of permanent estimators for certain large matrices

2004/07/08 by Shmuel Friedland, Brian Rider, Ofer Zeitouni · 2 citations
Mathematics · #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Random Matrices and Applications #math.PR #msc:15A52

paper · pdf · doi:10.1214/105051604000000396

published as Annals of Probability 2004, Vol. 14, No. 3, 1559-1576

arxiv created 2004/07/08 · openalex publication_date 2004/07/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let A_n=(a_ij)_i,j=1ⁿ be an n×n positive matrix with entries in [a,b], 0<a≤b. Let X_n=(√a_ijx_ij)_i,j=1ⁿ be a random matrix, where \x_ij\ are i.i.d. N(0,1) random variables. We show that for large n, det (X_n^TX_n) concentrates sharply at the permanent of A_n, in the sense that n^-1log (det(X_n^TX_n)/\operatorname perA_n)→_n→∞0 in probability.

Cited by

• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
• Generalized Friedland-Tverberg inequality: applications and extensions

Related

• Law of Large Numbers for Permanents of Random Constrained Matrices
• A simple observation on random matrices with continuous diagonal entries
• Concentration of the Spectral Measure for Large Random Matrices with Stable Entries
• A Concentration of Measure and Random Matrix Approach to Large\n Dimensional Robust Statistics
• Concentration of Measure and Large Random Matrices with an application to Sample Covariance Matrices