Extreme value limit theorems in discrete mathematics

Abstract

The present thesis deals with limit theorems for the numbers of inversions and descents, as well as for related combinatorial objects. This subject combines two different areas of mathematics: extreme value theory and statistical algebra. Permutation statistics have been studied and investigated for a long time, while also generating recent interest. Many of them can be generalized from symmetric groups to finite Coxeter groups, as symmetric groups are a subclass of these. When we treat the underlying Coxeter group as a proba- bility space, commonly equipped with the uniform distribution, the numbers of inversions and descents become random variables, which we call Xinv and Xdes. The study of their probabilistic and asymptotic properties, such as the central limit theorem (CLT), is part of statistical algebra. The validity of the CLT of Xinv and Xdes was recently classified on all finite Coxeter groups, which serves as a motivation to subsequently investigate the extreme value be- haviors of these statistics. Hence, in this thesis, we initiate the study of extreme values of permutation statistics. By this, we understand the maximum of a permutation stati- stic within a collection of independent samples. To get meaningful asymptotic statements, we need to construct a triangular array that encompasses an infinite sequence (Wn)n∈N of finite Coxeter groups of increasing ranks and contains kn i.i.d. samples Xn1, . . . , Xnkn drawn from Wn. So far, there is little understanding and classification for extreme values of triangular arrays, which is why we aim to find new ways to tackle these extreme values. Due to the asymptotic normality of inversions and descents, the Gumbel distribution is a natural candidate for the extreme value limit distribution in a triangular array built from Xinv or Xdes. However, the choice of the number of samples kn plays a crucial role. On one hand, kn must diverge to infinity, but on the other hand, it must not be too large to avoid degeneracy of extreme values. One novel contribution is a universal bound on kn which is yielded by the Berry-Esseen bound. However, we are clearly interested in methods and results that make use of the underlying permutation statistics and its specific properties. We find such methods that can yield significantly stronger bounds on kn, which are ideally subexponential, and this turns out to be successful for both the number of inversions and the number of descents. This is highlighted as the first main result of this thesis. In addition, we provide asymptotic theory for the joint distribution (Xinv, Xdes)⊤, which is less understood than the individual statistics Xinv and Xdes. Up to date, (Xinv, Xdes)⊤ is only known to be asymptotically normal on symmetric groups. The primary challenge here is the dependency structure between Xinv and Xdes, so the joint distribution needs to be handled with more elaborate methods. To tackle the dependency, we use the Hájek projection ˆXinv of Xinv, giving an m-dependent approximation ( ˆXinv, Xdes)⊤ for which we can obtain a suitable quantitative Gaussian approximation. This leads to several no- vel contributions, namely, the extension of the CLT for (Xinv, Xdes)⊤ beyond symme- tric groups, and the max-attraction of (Xinv, Xdes)⊤ to a bivariate Gumbel distribution. The latter is highlighted as the second main result of this thesis. We further argue that this result can be obtained for other permutation statistics with certain properties as well. Finally, we extensively analyze the applicability of these methods to generalized inversions and descents, which are an interesting combinatorial extension of common inversions and descents. These generalized statistics are indexed by a parameter d whose magnitude is significant for asymptotic considerations, so we determine its impact on the CLT and the extreme value limit theorems. This thesis is organized as follows. Chapter 1 introduces the basics and different facets of extreme value theory in both univariate and multivariate scenarios, and outlines the research history of extremes of triangular arrays. Chapter 2 gives preliminaries on inversions and descents first on symmetric groups, then in the more general framework of finite Coxeter groups. Here, we also outline the research history of the CLT for the random number of inversions and descents. In Chapter 3, we prove the max-attraction to the Gumbel distribution of inversions and descents for a large class of finite Coxeter groups, based on generating functions and their decomposition into independent but not identically distributed parts. For this scenario, we employ large deviations theory to obtain tail equivalence to the standard normal dis- tribution, which leads to extreme value limit theorems. We also discuss the asymptotic upper bound on the number of samples kn in each row of the triangular array. For Xdes, we find an even better bound on kn than for Xinv. Moreover, we show that a weak but universal extreme value limit theorem applies to a very large class of random variables, including other permutation statistics. Chapter 4 is extensively devoted to the asymptotics of the joint distribution (Xinv, Xdes)⊤. We first introduce the Hájek projection ˆXinv and a high-dimensional Gaussian approxi- mation for m-dependent random vectors. With these tools, we first extend the CLT for (Xinv, Xdes)⊤ from symmetric groups to the signed and even-signed permutation groups, on which we also propose a biased random choice of signs. More importantly though, we show that (Xinv, Xdes)⊤ is in the maximum domain of attraction of the two-dimensional Gumbel distribution with independent marginals. In the concluding Chapter 5, we determine the univariate and bivariate extreme value asymptotics of generalized inversions and descents with the previously developed methods.

Die vorliegende Dissertation beschäftigt sich mit Grenzwertsätzen für die Anzahlen von Inversions und Descents sowie für ähnliche kombinatorische Objekte. Dieses Thema ver- bindet zwei verschiedene Gebiete der Mathematik: Extremwerttheorie und statistische Algebra. Permutationsstatistiken werden seit Langem erforscht und sind auch in jüng- ster Zeit von Interesse. Viele können von symmetrischen Gruppen auf allgemeine endliche Coxeter-Gruppen übertragen werden, da symmetrische Gruppen eine Teilfamilie der letzte- ren bilden. Wir können die zugrundeliegende Coxetergruppe als Wahrscheinlichkeitsraum auffassen, üblicherweise mit der Gleichverteilung. Die Anzahl der Inversions bzw. Descents ist dann eine Zufallsvariable, die wir mit Xinv bzw. Xdes benennen. Die Erforschung der stochastischen und asymptotischen Eigenschaften solcher Zufallsvariablen, etwa des zen- tralen Grenzwertsatzes (ZGWS), gehört zum Gebiet der statistischen Algebra. Die Gültigkeit des ZGWS für Xinv und Xdes wurde erst kürzlich für alle endlichen Coxe- tergruppen charakterisiert. Dies ist für uns eine Motivation, auch die Extremwerte dieser Statistiken zu untersuchen. Diese Dissertationsarbeit initiiert somit das Studium der Ex- tremwerte von Permutationsstatistiken. Darunter verstehen wir den größten Wert einer Permutationsstatistik innerhalb von unabhängigen Stichproben. Um sinnvolle asympto- tische Aussagen erhalten zu können, müssen wir ein Dreiecksschema konstruieren, das eine unendliche Folge (Wn)n∈N von immer größer werdenden endlichen Coxeter-Gruppen umfasst. Auf der n-ten Gruppe Wn ziehen wir dann kn unabhängige Stichproben der in- teressierenden Permutationsstatistik. Allerdings sind Extremwerte von Dreiecksschemata nur unzureichend verstanden bzw. klassifiziert, weshalb wir nach neuen Wegen suchen, um mit ihnen umzugehen. Angesichts des ZGWS ist die Gumbel-Verteilung ein natürlicher Kandidat für die Ex- tremwertverteilung eines Dreiecksschemas aus Xinv oder Xdes. Allerdings spielen die Zei- lenlängen kn des Dreiecksschemas eine entscheidende Rolle. Einerseits muss kn bestimmt divergieren, andererseits darf es nicht zu groß sein, damit das Extremwertverhalten nicht entartet. Eine neue Erkenntnis ist die Einführung einer universellen Schranke für kn, die aus der Berry-Esseen-Fehlerabschätzung resultiert. Wir interessieren uns jedoch beson- ders für Methoden und Erkenntnisse, welche die zugrundeliegende Permutationsstatistik berücksichtigen und ihre Eigenschaften ausnutzen. Wir entwickeln solche Methoden, die zu einer viel besseren, idealerweise subexponentiellen kn-Schranke führen, sowohl für die An- zahl der Inversions als auch für die Anzahl der Descents. Dies ist das erste Hauptresultat dieser Arbeit. Es ist auch interessant, die gemeinsame Verteilung (Xinv, Xdes)⊤, die bislang weniger ver- standen ist als ihre individuellen Komponenten Xinv und Xdes, auf ihre asymptotischen Eigenschaften zu untersuchen. Nach heutigem Stand ist für sie nur der ZGWS auf sym- metrischen Gruppen bekannt. Die wesentliche Herausforderung ist hier die Abhängigkeit zwischen Xinv und Xdes, weshalb hier aufwändigere Methoden erforderlich sind. Um das Problem der Abhängigkeit zu lösen, benutzen wir die Hájek-Projektion ˆXinv von Xinv zwecks einer m-abhängigen Approximation ( ˆXinv, Xdes)⊤, für die wiederum eine geeignete Gauß-Approximation genutzt werden kann. Dies führt zu mehreren neuen Ergebnissen, nämlich die Verallgemeinerung des ZGWS auf andere endliche Coxeter-Gruppen sowie die Max-Anziehung von (Xinv, Xdes)⊤ zu einer zweidimensionalen Gumbel-Verteilung. Letzte- res ist das zweite Hauptresultat dieser Arbeit. Es zeigt sich außerdem, dass dieses Resultat auch für andere Permutationsstatistiken mit bestimmten Eigenschaften gültig ist. Abschließend analysieren wir in aller Ausführlichkeit die Anwendbarkeit dieser Methoden auf die sog. verallgemeinerten Inversions und Descents, die eine interessante kombinatori- sche Erweiterung der herkömmlichen Inversions und Descents darstellen. Diese erweiterten Statistiken werden durch einen Parameter d indiziert, dessen asymptotische Größenord- nung entscheidend ist. Somit bestimmen wir seinen Einfluss auf die Gültigkeit des ZGWS und auf das Extremwertverhalten. Diese Arbeit ist wie folgt strukturiert: Kapitel 1 führt in die Grundlagen und verschiedenen Richtungen der Extremwerttheorie im Ein- wie im Mehrdimensionalen ein und rekapitu- liert die Forschungsgeschichte von Extremwerten auf Dreiecksschemata. Kapitel 2 liefert die Grundlagen für Inversions und Descents zunächst auf symmetrischen, dann allgemeiner auf endlichen Coxeter-Gruppen. Dabei besprechen wir auch die bislang bekannten zentralen Grenzwertsätze für die zufällige Anzahl von Inversions oder Descents. In Kapitel 3 beweisen wir die Max-Anziehung von Inversions und Descents zur Gumbel- Verteilung für eine große Klasse endlicher Coxeter-Gruppen. Dabei nutzen wir Zerlegungen ihrer erzeugenden Funktionen in unabhängige aber nicht identisch verteilte Summanden und verwenden die sog. Large Deviations Theory, um Tail-Äquivalenz zur Standardnor- malverteilung zu erhalten. Wir diskutieren dabei auch die asymptotische Schranke für die Längen kn der Zeilen im Dreiecksschema. Für Xdes ergibt sich dabei sogar eine bessere Schranke als für Xinv. Zudem zeigen wir, dass ein schwächerer Extremwertsatz mit einer strengen Schranke für kn für eine sehr allgemeine Klasse von Zufallsvariablen gilt, die auch andere Permutationsstatistiken beinhaltet. Kapitel 4 ist ausführlich der Asymptotik der gemeinsamen Verteilung (Xinv, Xdes)⊤ ge- widmet. Wir führen zunächst die Hájek-Projektion ˆXinv und die hochdimensionale Gauß- Approximation m-abhängiger Zufallsvektoren ein. Mit diesen Hilfsmitteln erhalten wir den ZGWS für (Xinv, Xdes)⊤ auch auf den sog. (even-)signed permutation groups, für die wir auch eine verzerrte Auswahl der Vorzeichen diskutieren. Noch wichtiger ist jedoch der Beweis, dass (Xinv, Xdes)⊤ im Max-Anziehungsbereich der zweidimensionalen Gumbel- Verteilung mit unabhängigen Rändern liegt. Im abschließenden Kapitel 5 betrachten wir die verallgemeinerten Inversions und Descents, und bestimmen mit den zuvor entwickelten Techniken auch für diese Klasse von Permu- tationsstatistiken die uni- und bivariate Extremwert-Asymptotik.