The IMA Volumes in Mathematics and its Applications Volume 147 Series Editors DouglasN. Arnold Arnd Scheel Institute for Mathematics and its Applications (IMA) The Institute for Mathematics and its Applications was established by a grant from the National Science Foundation to the University of Minnesota in 1982. The primary mission of the IMA is to foster research of a truly inter- disciplinary nature, establishing links between mathematics of the highest caliber and important scientific and technological problems from other dis- ciplines and industries. To this end, the IMA organizes a wide variety of pro- grams, ranging from short intense workshops in areas of exceptional interest and opportunity to extensive thematic programs lasting a year. IMA Volumes are used to communicate results of these programs that we believe are of particular value to the broader scientific community. The full list of IMA books can be found at the Web site of the Institute for Mathematics and its Applications: http://www.ima.umn.edu/springer/volumes.html Presentation materials from the IMA talks are available at http://www.ima.umn.edu/talks/ Douglas N. Arnold, Director of the IMA * * * * * * * * * * IMA ANNUAL PROGRAMS 1982–1983 Statistical and Continuum Approaches to Phase Transition 1983–1984 Mathematical Models for the Economics of Decentralized Resource Allocation 1984–1985 Continuum Physics and Partial Differential Equations 1985–1986 Stochastic Differential Equations and Their Applications 1986–1987 Scientifi c Computation 1987–1988 Applied Combinatorics 1988–1989 Nonlinear Waves 1989–1990 Dynamical Systems and Their Applications 1990–1991 Phase Transitions and Free Boundaries 1991–1992 Applied Linear Algebra 1992–1993 Control Theory and its Applications 1993–1994 Emerging Applications of Probability 1994–1995 Waves and Scattering 1995–1996 Mathematical Methods in Material Science 1996–1997 Mathematics of High Performance Computing (Continued at the back) Grzegorz A. Rempała Jacek Wesołowski Authors Symmetric Functionals on Random Matrices and Random Matchings Problems 123 GrzegorzA. Rempał a JacekWesoło wski DepartmentofMathematics WydzialMatematykiiNauk UniversityofLouisville,KY,USA Informacyjnych Louisville40292 PolitechnikaWarszawska,Warszawa, http://www.louisville.edu/∼garemp01 1Pl.Politechniki Warszawa00-661 Poland ISBN:978-0-387-75145-0 e-ISBN:970-0-387-75146-7 MathematicsSubjectClassification(2000):60F05,60F17,62G20,62G10,05A16 LibraryofCongressControlNumber:2007938212 (cid:1)c 2008SpringerScience+BusinessMedia,LLC Allrights reserved.Thisworkmaynotbetranslated orcopiedinwholeorinpartwithoutthewritten permissionofthepublisher(SpringerScience+BusinessMedia,LLC,233SpringStreet,NewYork,NY 10013,USA),exceptforbriefexcerptsinconnectionwithreviewsorscholarlyanalysis.Useinconnection withanyformofinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilar ordissimilarmethodologynowknownorhereafterdevelopedisforbidden. Theuseinthispublicationoftradenames,trademarks,servicemarks,andsimilarterms,eveniftheyare notidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyaresubject toproprietaryrights. Printedonacid-freepaper. 9 8 7 6 5 4 3 2 1 springer.com Moim Rodzicom, Helenie oraz Jasiowi i Antosiowi (Grzegorz Rempa(cid:1)la) Moim Rodzicom (Jacek Weso(cid:1)lowski) Foreword This IMA Volume in Mathematics and its Applications SYMMETRIC FUNCTIONALS ON RANDOM MATRICES AND RANDOM MATCHINGS PROBLEMS During the academic year 2003–2004, the Institute for Mathematics and its Applications (IMA) held a thematic program on Probability and Statis- tics in Complex Systems. The program focused on large complex systems in which stochasticity plays a significant role. Such systems are very diverse, and the IMA program emphasized systems as varied as the human genome, the internet, andworldfinancialmarkets.Although quite different,these sys- tems have features in common, such as multitudes of interconnecting parts and the availability of large amounts of high-dimensional noisy data. The programemphasizedthe developmentandapplicationofcommonmathemat- icalandcomputationaltechniquestomodelandanalyzesuchsystems.About 1,000 mathematicians, statisticians, scientists, and engineers participated in the IMA thematic program, including about 50 who were in residence at the IMA during much or all of the year. The present volume was born during the 2003–2004thematic program at the IMA.The twoauthorswerevisitorstothe IMA duringthe programyear, withthefirstauthorresidentfortheentiretenmonths.Thisvolumeisaresult ofthe authors’interactionsatthe IMA, and,especially their discussionswith the many other program participants in the program and their involvement inthenumeroustutorials,workshops,andseminarsheldduringtheyear.The booktreatsrecentprogressinrandommatrixpermanents,randommatchings and their asymptotic behavior, an area of stochastic modeling and analysis which has applications to a variety of complex systems and problems of high dimensional data analysis. Like many outcomes of IMA thematic programs,the seed for this volume wasplantedatthe IMA, butittook time to growandflourish.Thefinalfruit VIII Foreword is realizedwell after the programends. While all credit and responsibility for thecontentsofthebookresidewiththeauthors,theIMAisdelightedtohave supplied the fertile ground for this work to take place. WetakethisopportunitytothanktheNationalScienceFoundationforits support of the IMA. Series Editors Douglas N. Arnold, Director of the IMA Arnd Scheel, Deputy Director of the IMA Preface The idea of writing this monograph came about through discussions which we held as participants in the activities of an annual program “Probability and Statistics in Complex Systems” of the Institute for Mathematics and Its Applications at the University of Minnesota (IMA) which was hosted there duringthe2003/04academicyear.InthecourseofinteractionswiththeInsti- tute’s visitors and guests, we came to a realization that many of the ideas and techniques developed recently for analyzing asymptotic behavior of ran- dom matchings are relatively unknown and could be of interest to a broader community of researchers interested in the theory of random matrices and statistical methods for high dimensional inference. In our IMA discussions it also transpired that many of the tools developed for the analysis of asymp- toticbehaviorofrandompermanentsandthelikesmaybealsousefulinmore general context of problems emerging in the area of complex stochastic sys- tems.Insuchsystems,ofteninthecontextofmodeling,statisticalhypothesis testing or estimation of the relevant quantities, the distributional properties of the functionals on the entries of random matrices are of concern. From this viewpoint, the interest in the laws of various random matrix functionals usefulin statisticalanalysiscontrastswiththe interestofa classicaltheory of randommatriceswhichisprimarilyconcernedwithasymptoticdistributional laws of eigenvalues and eigenvectors. Thetext’scontentisdrawnfromtherecentliteratureonquestionsrelated toasymptoticsforrandompermanentsandrandommatchings.Thatmaterial has been augmented with a sizable amount of preliminary material in order tomakethetextsomewhatself-contained.Withthissupplementarymaterial, the text should be accessible to any mathematics, statistics or engineering graduate student who has taken basic introductory courses in probability theory and mathematical statistics. The presentation is organized in seven chapters. Chapter 1 gives a gen- eral introduction to the topics covered in the text while also providing the reader with some examples of their applications to problems in stochastic complex systems formulatedin terms of randommatchings.This preliminary X Preface chapter makes a connectionbetween randommatchings, randompermanents and U-statistics. Also a concept of a P- statistic, which connects the three concepts is introduced there. Chapter 2 builds upon these connections and contains a number of results for a general class of random matchings which, likeforinstancethevarianceformulaforaP-statistic,arefundamentaltothe developments further in the text. Taken together the material of Chapters 1 and2shouldgivethe readerthenecessarybackgroundtoapproachthetopics covered later in the text. Chapters3and4dealwithrandompermanentsandaproblemofdescrib- ing asymptotic distributions for a “classical” count of perfect matchings in random bipartite graphs. Chapter 3 details a relatively straightforward but computationally tedious approach leading to central limit theorems and laws of large numbers for random permanents. Chapter 4 presents a more gen- eraltreatmentofthe subjectby meansoffunctionallimit theoremsandweak convergence of iterative stochastic integrals. The basic facts of the theory of stochastic integration are outlined in the first sections of Chapter 4 as necessary. In Chapter 5 the results on asymptotics of random permanents are extendedtoP-statistics,atthesametime coveringalargeclassofmatchings. The limiting laws are expressed with the help of multiple Wiener-Itˆo inte- grals. The basic properties of a multiple Wiener-Itoˆ integral are summarized in the first part of the chapter. Several applications of the asymptotic results to particular counting problems introduced in earlier chapters are presented in detail. Chapter 6 makes a connection between P-statistics andmatchings on one side and the “incomplete” U-statistics on the other. The incomplete perma- nent design is analyzed first. An overview of the analysis of both asymptotic and finite sample properties of P-statistics in terms of their variance effi- ciencyascomparedwiththecorresponding“complete”statisticsispresented. Inthesecondpartminimumrectangulardesigns(muchlighterthatpermanent designs)areintroducedandtheirefficiencyisanalyzed.Alsotheirrelationsto the concept of mutual orthogonal Latin squares of classical statistical design theory is discussed there. Chapter 7 covers some of the recent results on the asymptotic lognor- mality of sequences of products of increasing sums of independent identi- cally distributed random variables and their U-statistics counterparts. The developments of the chapter lead eventually to a limit theorem for random determinants for Wishart matrices. Here again, similarly as in some of the earlier-discussed limit theorems for random permanents, the lognormal law appears in the limit. We would like to express our thanks to several individuals and institu- tionswhohelpedusincompletingthisproject.We wouldliketoacknowledge the IMA director, Doug Arnold who constantly encouraged our efforts, as wellasourmany othercolleagues,especially Andr´eK´ezdy,Ofer Zeitouniand Shmuel Friedland, who lookedat and commentedon the variousfinished and Preface XI not-so-finishedportionsofthe text.WewouldalsoliketothankEwaKubicka andGrzegorzKubickifortheirhelpwithdrawingsomeofthegraphspresented in the book. Whereas the idea of writing the current monographwas born at theIMA,theopportunitytodosowasalsopartiallyprovidedbyotherinstitu- tions. In particular, the Statistical and Applied Mathematical Sciences Insti- tuteinDurham,NCheldduring2005/6academicyearaprogramon“Random Matrices and High Dimensional Inference” and kindly invited the first of the authors to participate in its activities as a long term visitor.The project was alsosupportedbylocalgrantsfromthe FacultyofMathematicsandInforma- tion Science of the Warsaw University of Technology, Warszawa, Poland and from the Department of Mathematics at the University of Louisville. Louisville, KY and Warszawa (Poland) Grzegorz A. Rempal(cid:1)a July 2007 Jacek Weso(cid:1)lowski