<p>This dissertation establishes limit theory for topological functionals of geometric complexes from a stochastic process viewpoint. Standard filtrations of geometric complexes, such as the Čech and Vietoris-Rips complexes, have a natural parameter <i>r </i>which governs the formation of simplices: this is the basis for persistent homology. However, the parameter <i>r</i> may also be considered the time parameter of an appropriate stochastic process which summarizes the evolution of the filtration.</p><p>Here we examine the stochastic behavior of two of the foremost classes of topological functionals of such filtrations: the Betti numbers and the Euler characteristic. There are also two distinct setups in which the points underlying the complexes are generated, where the points are distributed randomly in <i>R^d</i> according to a general density (the traditional setup) and where the points lie in the tail of a heavy-tailed or exponentially-decaying “noise” distribution (the extreme-value theory (EVT) setup).<br></p><p>These results constitute some of the first results combining topological data analysis (TDA) and stochastic process theory. The first collection of results establishes stochastic process limits for Betti numbers of Čech complexes of Poisson and binomial point processes for two specific regimes in the traditional setup: the sparse regime—when the parameter <i>r </i>governing the formation of simplices causes the Betti numbers to concentrate on components of the lowest order; and the critical regime—when the parameter <i>r</i> is of the order <i>n^-1/d</i> and the geometric complex becomes highly connected with topological holes of every dimension. The second collection of results establishes a functional strong law of large numbers and a functional central limit theorem for the Euler characteristic of a random geometric complex for the critical regime in the traditional setup. The final collection of results establishes functional strong laws of large numbers for geometric complexes in the EVT setup for the two classes of “noise” densities mentioned above.<br></p>

The aim of this paper is to investigate the known nonuniform version of Esseen''s inequality in the Lp-metric, to get a numerical bound for the appearing constant L. For a long time the results given by several authors constate the impossibility of a nonuniform estimation in the most interesting case δ=1, because the effect L=L(δ)=O(1/(1-δ)), δ->1-0, was observed, where 2+δ, 0<δ<1, is the order of the assumed moments of the considered independent random variables X_k, k=1,2,...,n. Again making use of the method of conjugated distributions, we improve the well-known technique to show in the most interesting case δ=1 the finiteness of the absolute constant L and to prove L=L(1)=<127,74*7,31^(1/p), p>1. In the case 0<δ<1 we only give the analytical structure of L but omit numerical calculations. Finally an example on normal approximation of sums of l_2-valued random elements demonstrates the application of the nonuniform mean central limit bounds obtained here.:1. Introduction S. 3 2. The nonuniform version of ESSEEN''s Inequality in the Lp-metrie S. 4 3. The partition of the domain of integration S. 5 4. The domain of moderate x S. 8 5. An error bound for large values of L2+δ,n S. 12 6. The proof of the inequality (2.1) S. 13 7. An application to normalapproximation of sums of l2-valued random elements S. 14 References S. 18 / Das Anliegen dieses Artikels besteht in der Untersuchung einer bekannten Variante der Esseen''schen Ungleichung in Form einer ungleichmäßigen Fehlerabschätzung in der Lp-Metrik mit dem Ziel, eine numerische Abschätzung für die auftretende absolute Konstante L zu erhalten. Längere Zeit erweckten die Ergebnisse, die von verschiedenen Autoren angegeben wurden, den Eindruck, dass die ungleichmäßige Fehlerabschätzung im interessantesten Fall δ=1 nicht möglich wäre, weil auf Grund der geführten Beweisschritte der Einfluss von δ auf L in der Form L=L(δ)=O(1/(1-δ)), δ->1-0, beobachtet wurde, wobei 2+δ, 0<δ<1, die Ordnung der vorausgesetzten Momente der betrachteten unabhängigen Zufallsgrößen X_k, k=1,2,...,n, angibt. Erneut wird die Methode der konjugierten Verteilungen angewendet und die gut bekannte Beweistechnik verbessert, um im interessantesten Fall δ=1 die Endlichkeit der absoluten Konstanten L nachzuweisen und um zu zeigen, dass L=L(1)=<127,74*7,31^(1/p), p>1, gilt. Im Fall 0<δ<1 wird nur die analytische Struktur von L herausgearbeitet, jedoch ohne numerische Berechnungen. Schließlich wird mit einem Beispiel zur Normalapproximation von Summen l_2-wertigen Zufallselementen die Anwendung der gewichteten Fehlerabschätzung im globalen zentralen Grenzwertsatz demonstriert.:1. Introduction S. 3 2. The nonuniform version of ESSEEN''s Inequality in the Lp-metrie S. 4 3. The partition of the domain of integration S. 5 4. The domain of moderate x S. 8 5. An error bound for large values of L2+δ,n S. 12 6. The proof of the inequality (2.1) S. 13 7. An application to normalapproximation of sums of l2-valued random elements S. 14 References S. 18

No description available.

No description available.

[pt] Nessa dissertação vamos introduzir, elaborar e combinar ideias da Teoria de martingais, a Teoria de grafos aleatórios e o Teorema Central do Limite. Em particular, veremos como martingais podem ser usados para representar desvios de contagem de subgrafos. Usando esta representação e o Teorema Central do Limite para martingais, conseguiremos demonstrar um Teorema Central do Limite para a contagem de subgrafos livres de triângulos no grafo aleatório Erdos-Rényi G(n,m) . Além disso, nossa demonstração também nos trará informação sobre a taxa de convergência, mostrando que a distribuição dos desvios converge rapidamente para a distribuição normal. / [en] In this dissertation we shall introduce, elaborate and combine ideas from martingale Theory, random graph Theory and the Central Limit Theorem. In particular, we will see how martingales can be used to represent deviations of subgraph counts. Using this representation and the Central Limit Theorem for martingales, we will be able to demonstrate a Central Limit Theorem for the triangle-free subgraph count in the Erdos-Rényi G(n,m) random graph. Furthermore, our proof also gives us information about the rate of convergence, showing that the distribution of deviations converges rapidly to the normal distribution.

No description available.

L’objectif en arrière-plan est de montrer que plusieurs modèles de marches aléatoires en milieux aléatoires (MAMA) sont reliés à un modèle-jouet appelé le modèle de piège de Bouchaud. Le domaine des MAMA est très vaste, mais nous nous intéressons particulièrement à une classe de modèle où la marche est réversible et directionnellement transiente. En particulier, nous verrons pourquoi on pense que ces modèles se ressemblent et quel genre de similarités on s’attend à obtenir, une fois qu’on aura présenté le modèle de Bouchaud. Nous verrons aussi quelques techniques de base utilisés de ce domaine, telles que les temps de régénérations. Comme contribution, nous allons démontrer un théorème central limite pour la marche aléatoire β-biaisée sur un arbre de Galton-Watson. / This Master thesis is part of a larger project of linking the behaviours of a certain type of random walks in random environments (RWRE) with those of a toy model called the Bouchaud’s trap model. The domain of RWRE is very wide but our interest will be on a particular kind of models which are reversible and directionally transient. More specifically, we will see why those models have similar behaviours and what kind of results we could expect once we have reviewed the Bouchaud’s trap model. We will also present some basic technic used in this field, such as regeneration times. As a contribution, we will demonstrate a central limit theorem for the β-biased random walk on a Galton-Watson tree.

Le sujet principal de ce mémoire est l'étude de la distribution asymptotique de la fonction f_m qui compte le nombre de diviseurs premiers distincts parmi les nombres premiers $p_1,...,p_m$. Au premier chapitre, nous présentons les sept résultats qui seront démontrés au chapitre 4. Parmi ceux-ci figurent l'analogue du théorème d'Erdos-Kac et un résultat sur les grandes déviations. Au second chapitre, nous définissons les espaces de probabilités qui serviront à calculer les probabilités asymptotiques des événements considérés, et éventuellement à calculer les densités qui leur correspondent. Le troisième chapitre est la partie centrale du mémoire. On y définit la promenade aléatoire qui, une fois normalisée, convergera vers le mouvement brownien. De là, découleront les résultats qui formeront la base des démonstrations de ceux chapitre 1. / The main topic of this masters thesis is the study of the asymptotic distribution of the fonction f_m which counts the number of distinct prime divisors among the first $m$ prime numbers, i.e. $p_1,...,p_m$. The first chapter provides the seven main results which will later on be proved in chapter 4. Among these we find the analogue of the Erdos-Kac central limit theorem and a result on large deviations. In the following chapter, we define several probability spaces on which we will calculate asymptotic probabilities of specific events. These will become necessary for calculating their corresponding densities. The third chapter is the main part of this masters thesis. In it, we introduce a random walk which, when suitably normalized, will converge to the Brownian motion. We will then obtain results which will form the basis of the proofs of those of chapiter 1.

Im ersten Teil der Dissertation wird ein diskretes stochastisches zustandsabhängiges Modell eines zweiseitigen Limit Orderbuchs als bestehend aus den Zustandsgrößen bester Bidpreis (Geldkurs), bester Askpreis (Briefkurs) und vorhandener Kauf- bzw. Verkaufsdichte definiert. Für eine einfache Skalierung mit zwei Zeitskalen wird ein Grenzwertsatz bewiesen. Die Veränderungen der besten Bid- und Askpreise werden im Sinne des Gesetzes der großen Zahlen skaliert und dies entspricht der langsameren Zeitskala. Das Platzieren bzw. Stornieren der Limitorder findet auf der schnelleren Zeitskala statt. Der Grenzwertsatz besagt, dass die fundamentalen Zustandsgrößen, gegeben Regularitätsbedingungen der einkommenden Order, fast sicher zu einem stetigen Limesmodell konvergieren. Im Limesmodell sind der beste Bidpreis und der beste Askpreis die eindeutigen Lösungen von zwei gekoppelten gewöhnlichen DGLen. Die Kauf- und Verkaufsdichten sind jeweils als eindeutige Lösungen von linearen hyperbolischen PDGLen, die anhand der Erwartungswerte der einkommenden Orderparameter festgelegt sind, gegeben. Die Lösungen sind in geschlossener Form erhältlich. Im zweiten Teil wird ein funktionaler zentraler Grenzwertsatz d.h. ein Invarianzprinzip für ein vereinfachtes Modell eines Limitorderbuches bewiesen. Unter einer natürlichen Skalierung konvergiert der zweidimensionale Preisprozess (Bid- und Askpreis) in Verteilung zu einer Semimartingal reflektierten Brownschen Bewegung in der zugelassenen Preismenge. Gleichzeitig konvergieren die Kauf- und Verkaufsdichten im schwachen Sinn zum Betrag einer zweiparametrischen Brownschen Bewegung. Es wird weiterhin anhand eines Beispiels gezeigt, wie man für das Modell im ersten Teil eine stochastiche PDGL, unter einer starken Stationaritätsannahme für die Orderplatzierungen und -stornierungen, herleiten kann. Im dritten Teil wird ein Mittelungs- bzw. ein Invarianzprinzip für diskrete Banach- bzw. Hilbertraumwertige stochastische Prozesse bewiesen. / In the first part of the thesis, we define a random state-dependent discrete model of a two-sided limit order book in terms of its key quantities best bid [ask] price and the standing buy [sell] volume density. For a simple scaling that introduces a slow time scaling, that is equivalent to the classical law of large numbers, for the bid/ask prices and a faster time scale for the limit volume placements/cancelations, that keeps the expected volume rate over the considered price interval invariant, we prove a limit theorem. The limit theorem states that, given regularity conditions on the random order flow, the key quantities converge in the sense of a strong law of large numbers to a tractable continuous limiting model. The limiting model is such that the best bid and ask price dynamics can be described in terms of two coupled ODE:s, while the dynamics of the relative buy and sell volume density functions are given as the unique solutions of two linear first-order hyperbolic PDE:s with variable coefficients, specified by the expectation of the order flow parameters. In the second part, we prove a functional central limit theorem i.e. an invariance principle for an order book model with block shaped volume densities close to the spread. The weak limit of the two-dimensional price process (best bid and ask price) is given by a semi-martingale reflecting Brownian motion in the set of admissible prices. Simultaneously, the relative buy and sell volume densities close to the spread converge weakly to the modulus of a two-parameter Brownian motion. We also demonstrate an example how to easily derive an SPDE for the relative volume densities in a simple case, when a strong stationarity assumption is made on the limit order placements and cancelations for the model suggested in the first part. In the third and final part of the thesis, we prove an averaging and an invariance principle for discrete processes taking values in Banach and Hilbert spaces, respectively.

We study certain questions related to the performance of the Karp-Sipser algorithm on the sparse Erdös-Rényi random graph. The Karp-Sipser algorithm, introduced by Karp and Sipser [34] is a greedy algorithm which aims to obtain a near-maximum matching on a given graph. The algorithm evolves through a sequence of steps. In each step, it picks an edge according to a certain rule, adds it to the matching and removes it from the remaining graph. The algorithm stops when the remining graph is empty. In [34], the performance of the Karp-Sipser algorithm on the Erdös-Rényi random graphs G(n,M = [^cn/₂]) and G(n, p = ^c/_n), c &GT; 0 is studied. It is proved there that the algorithm behaves near-optimally, in the sense that the difference between the size of a matching obtained by the algorithm and a maximum matching is at most o(n), with high probability as n → ∞. The main result of [34] is a law of large numbers for the size of a maximum matching in G(n,M = ^cn/₂) and G(n, p = ^c/_n), c &GT; 0. Aronson, Frieze and Pittel [2] further refine these results. In particular, they prove that for c &LT; e, the Karp-Sipser algorithm obtains a maximum matching, with high probability as n → ∞; for c &GT; e, the difference between the size of a matching obtained by the algorithm and the size of a maximum matching of G(n,M = ^cn/₂) is of order Θ_{log n}(n^1/5), with high probability as n → ∞. They further conjecture a central limit theorem for the size of a maximum matching of G(n,M = ^cn/₂) and G(n, p = ^c/_n) for all c &GT; 0. As noted in [2], the central limit theorem for c &LT; 1 is a consequence of the result of Pittel [45]. In this thesis, we prove a central limit theorem for the size of a maximum matching of both G(n,M = ^cn/₂) and G(n, p = ^c/_n) for c &GT; e. (We do not analyse the case 1 ≤ c ≤ e). Our approach is based on the further analysis of the Karp-Sipser algorithm. We use the results from [2] and refine them. For c &GT; e, the difference between the size of a matching obtained by the algorithm and the size of a maximum matching is of order Θ_{log n}(n^1/5), with high probability as n → ∞, and the study [2] suggests that this difference is accumulated at the very end of the process. The question how the Karp-Sipser algorithm evolves in its final stages for c > e, motivated us to consider the following problem in this thesis. We study a model for the destruction of a random network by fire. Let us assume that we have a multigraph with minimum degree at least 2 with real-valued edge-lengths. We first choose a uniform random point from along the length and set it alight. The edges burn at speed 1. If the fire reaches a node of degree 2, it is passed on to the neighbouring edge. On the other hand, a node of degree at least 3 passes the fire either to all its neighbours or none, each with probability 1/2. If the fire extinguishes before the graph is burnt, we again pick a uniform point and set it alight. We study this model in the setting of a random multigraph with N nodes of degree 3 and α(N) nodes of degree 4, where α(N)/N → 0 as N → ∞. We assume the edges to have i.i.d. standard exponential lengths. We are interested in the asymptotic behaviour of the number of fires we must set alight in order to burn the whole graph, and the number of points which are burnt from two different directions. Depending on whether α(N) » √N or not, we prove that after the suitable rescaling these quantities converge jointly in distribution to either a pair of constants or to (complicated) functionals of Brownian motion. Our analysis supports the conjecture that the difference between the size of a matching obtained by the Karp-Sipser algorithm and the size of a maximum matching of the Erdös-Rényi random graph G(n,M = ^cn/₂) for c > e, rescaled by n^1/5, converges in distribution.