Rare events play a crucial role in our society and a great effort has been dedicated to numerically study them in different contexts. This thesis proposes a numerical methodology based on Monte Carlo Metropolis-Hastings algorithm to efficiently sample rare events in chaotic systems. It starts by reviewing the relevance of rare events in chaotic systems, focusing in two types of rare events: states in closed systems with rare chaoticities, characterised by a finite-time Lyapunov exponent on a tail of its distribution, and states in transiently chaotic systems, characterised by a escape time on the tail of its distribution. This thesis argues that these two problems can be interpreted as a traditional problem of statistical physics: sampling exponentially rare states in the phase-space - states in the tail of the density of states - with an increasing parameter - the system size. This is used as the starting point to review Metropolis-Hastings algorithm, a traditional and flexible methodology of importance sampling in statistical physics. By an analytical argument, it is shown that the chaoticity of the system hinders direct application of Metropolis-Hastings techniques to efficiently sample these states because the acceptance is low. It is argued that a crucial step to overcome low acceptance rate is to construct a proposal distribution that uses information about the system to bound the acceptance rate. Using generic properties of chaotic systems, such as exponential divergence of initial conditions and fractals embedded in their phase-spaces, a proposal distribution that guarantees a bounded acceptance rate is derived for each type of rare events. This proposal is numerically tested in simple chaotic systems, and the efficiency of the resulting algorithm is measured in numerous examples in both types of rare events. The results confirm the dramatic improvement of using Monte Carlo importance sampling with the derived proposals against traditional methodologies: the number of samples required to sample an exponentially rare state increases polynomially, as opposed to an exponential increase observed in uniform sampling. This thesis then analyses the sub-optimal (polynomial) efficiency of this algorithm in a simple system and shows analytically how the correlations induced by the proposal distribution can be detrimental to the efficiency of the algorithm. This thesis also analyses the effect of high-dimensional chaos in the proposal distribution and concludes that an anisotropic proposal that takes advantage of the different rates of expansion along the different unstable directions, is able to efficiently find rare states. The applicability of this methodology is also discussed to sample rare states in non-hyperbolic systems, with focus on three systems: the logistic map, the Pomeau-Manneville map, and the standard map. Here, it is argued that the different origins of non-hyperbolicity require different proposal distributions. Overall, the results show that by incorporating specific information about the system in the proposal distribution of Metropolis-Hastings algorithm, it is possible to efficiently find and sample rare events of chaotic systems. This improved methodology should be useful to a large class of problems where the numerical characterisation of rare events is important.

The concept of pseudo-differential operators allows one to study stochastic processes through their symbol. This approach has generated many new insights in recent years. However, most results are based on the assumption of bounded coefficients. In this thesis, we study Levy-type processes with unbounded coefficients and, especially, affine processes. In particular, we establish a connection between pseudo-differential operators and affine processes which are well-known from mathematical finance. Affine processes are an interesting example in this field since they have linearly growing and hence unbounded coefficients. New techniques and tools are developed to handle the affine case and then expanded to general Levy-type processes. In this way, the convergence of a simulation scheme based on a Markov chain approximation, results on path properties, and necessary conditions for the symmetry of operators were proven.

Gegenstand der Arbeit sind zufällige Mengen $Xi$ aus dem erweiterten Konvexring und zugehörige markierte Punktprozesse $Psi$ in $mathbb{R}^d$ mit Marken aus dem System der konvexen Körper. Es wird gezeigt, unter welchen Voraussetzungen an $Psi$ die zweite Produktdichte $varrho_S^{(2)}$ des durch $Xi$ induzierten zufälligen Oberflächenmaßes $S_{Xi}$ existiert und eine klassische Beziehung zwischen der Intensitätsfunktion von $S_{Xi}$ und der Ableitung der sphärischen Kontaktverteilungsfunktion von $Xi$ bei Null auf entsprechende Größen zweiter Ordnung übertragen werden kann. Mit Hilfe des so erhaltenen Zugangs wird $varrho_S^{(2)}$ für einige Beispiele bestimmt. Desweiteren werden spezielle markierte Punktprozesse $Psi$ betrachtet, die durch Verdünnung gemäß einer Methode nach Matérn aus einem markierten Poisson-Prozess hervorgehen. Als praktische Anwendung wird für zwei Proben eines Feuerbetons mit kugelförmigen Einschlüssen untersucht, welche Modelle für zufällige Systeme harter Kugeln zur Beschreibung geeignet sind.

Natural language is a remarkable example of a complex dynamical system which combines variation and universal structure emerging from the interaction of millions of individuals. Understanding statistical properties of texts is not only crucial in applications of information retrieval and natural language processing, e.g. search engines, but also allow deeper insights into the organization of knowledge in the form of written text. In this thesis, we investigate the statistical and dynamical processes underlying the co-existence of universality and variability in word statistics. We combine a careful statistical analysis of large empirical databases on language usage with analytical and numerical studies of stochastic models. We find that the fat-tailed distribution of word frequencies is best described by a generalized Zipf’s law characterized by two scaling regimes, in which the values of the parameters are extremely robust with respect to time as well as the type and the size of the database under consideration depending only on the particular language. We provide an interpretation of the two regimes in terms of a distinction of words into a finite core vocabulary and a (virtually) infinite noncore vocabulary. Proposing a simple generative process of language usage, we can establish the connection to the problem of the vocabulary growth, i.e. how the number of different words scale with the database size, from which we obtain a unified perspective on different universal scaling laws simultaneously appearing in the statistics of natural language. On the one hand, our stochastic model accurately predicts the expected number of different items as measured in empirical data spanning hundreds of years and 9 orders of magnitude in size showing that the supposed vocabulary growth over time is mainly driven by database size and not by a change in vocabulary richness. On the other hand, analysis of the variation around the expected size of the vocabulary shows anomalous fluctuation scaling, i.e. the vocabulary is a nonself-averaging quantity, and therefore, fluctuations are much larger than expected. We derive how this results from topical variations in a collection of texts coming from different authors, disciplines, or times manifest in the form of correlations of frequencies of different words due to their semantic relation. We explore the consequences of topical variation in applications to language change and topic models emphasizing the difficulties (and presenting possible solutions) due to the fact that the statistics of word frequencies are characterized by a fat-tailed distribution. First, we propose an information-theoretic measure based on the Shannon-Gibbs entropy and suitable generalizations quantifying the similarity between different texts which allows us to determine how fast the vocabulary of a language changes over time. Second, we combine topic models from machine learning with concepts from community detection in complex networks in order to infer large-scale (mesoscopic) structures in a collection of texts. Finally, we study language change of individual words on historical time scales, i.e. how a linguistic innovation spreads through a community of speakers, providing a framework to quantitatively combine microscopic models of language change with empirical data that is only available on a macroscopic level (i.e. averaged over the population of speakers).

Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p ∈ ]0,1] and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far. In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with nonnegative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in pseudo-polynomial time.

Kollektive Migration und Schwarmverhalten sind Beispiele für Selbstorganisation und können in verschiedenen biologischen Systemen beobachtet werden, beispielsweise in Vogel-und Fischschwärmen oder Bakterienpopulationen. Im Zentrum dieser Arbeit steht ein räumlich diskretes und zeitlich stetiges Model, welches das kollektive Migrieren von Individuen mittels eines stochastischen Vielteilchensystems (VTS) beschreibt und analysierbar macht. Das konstruierte Modell ist in keiner Klasse gut untersuchter Vielteilchensysteme enthalten, sodass der größte Teil der Arbeit der Entwicklung von Methoden zur Untersuchung des Langzeitverhaltens bestimmter VTS gewidmet ist. Eine entscheidende Rolle spielen hier Gibbs-Maße, die zu zeitlich invarianten Maßen in Beziehung gesetzt werden. Durch eine Simulationsstudie und die Analyse des Einflusses der Parameter Migrationsgeschwindigkeit, Sensitivität der Individuen und (räumliche) Dichte der Anfangsverteilung können Eigenschaften kollektiver Migration erklärt und Hypothesen für weitere Analysen aufgestellt werden. / Collective migration and swarming behavior are examples of self-organization and can be observed in various biological systems, such as in flocks of birds, schools of fish or populations of bacteria. In the center of this thesis lies a stochastic interacting particle system (IPS), which is a spatially discrete model with a continuous time scale that describes collective migration and which can be treated using analytical methods. The constructed model is not contained in any class of well-understood IPS’s. The largest part of this work is used to develop methods that can be used to study the long-term behavior of certain IPS’s. Thereby Gibbs-Measures play an important role and are related to temporally invariant measures. One can explain the properties of collective migration and propose a hypothesis for further analyses by a simulation study and by analysing the parameters migration velocity, sensitivity of individuals and (spatial) density of the initial distribution.

Viele Resultate über MR- und OR-Verfahren zur Lösung linearer Gleichungssysteme bleiben (in leicht modifizierter Form) gültig, wenn der betrachtete Operator nicht invertierbar ist. Neben dem für reguläre Probleme charakteristischen Abbruchverhalten, kann bei einem singulären Gleichungssystem auch ein so genannter singulärer Zusammenbruch auftreten. Für beide Fälle werden verschiedene Charakterisierungen angegeben. Die Unterrauminverse, eine spezielle verallgemeinerte Inverse, beschreibt die Näherungen eines MR-Unterraumkorrektur-Verfahrens. Für Krylov-Unterräume spielt die Drazin-Inverse eine Schlüsselrolle. Bei Krylov-Unterraum-Verfahren kann a-priori entschieden werden, ob ein regulärer oder ein singulärer Abbruch auftritt. Wir können zeigen, dass ein Krylov-Verfahren genau dann für beliebige Startwerte eine Lösung des linearen Gleichungssystems liefert, wenn der Index der Matrix nicht größer als eins und das Gleichungssystem konsistent ist. Die Berechnung stationärer Zustandsverteilungen zeitstetiger Markov-Ketten mit endlichem Zustandsraum stellt eine praktische Aufgabe dar, welche die Lösung eines singulären linearen Gleichungssystems erfordert. Die Eigenschaften der Übergangs-Halbgruppe folgen aus einfachen Annahmen auf rein analytischem und matrixalgebrischen Wege. Insbesondere ist die erzeugende Matrix eine singuläre M-Matrix mit Index 1. Ist die Markov-Kette irreduzibel, so ist die stationäre Zustandsverteilung eindeutig bestimmt.

The discretization of the stationary diffusion equation with random parameters by the Stochastic Finite Element Method requires the solution of a highly structured but very large linear system of equations. Depending on the stochastic properties of the diffusion coefficient together with the stochastic discretization we consider three solver cases. If the diffusion coefficient is given by a stochastically linear expansion, e.g. a truncated Karhunen-Loeve expansion, and tensor product polynomial stochastic shape functions are employed, the Galerkin matrix can be transformed to a block-diagonal matrix. For the solution of the resulting sequence of linear systems we study Krylov subspace recycling methods whose success depends on the ordering and grouping of the linear systems as well as the preconditioner. If we use complete polynomials for the stochastic discretization instead, we show that decoupling of the Galerkin matrix with respect to the stochastic degrees of freedom is impossible. For a stochastically nonlinear diffusion coefficient, e.g. a lognormal random field, together with complete polynomials serving as stochastic shape functions, we introduce and test the performance of a new Kronecker product preconditioner, which is not exclusively based on the mean value of the diffusion coefficient.

In this thesis the Lyapunov exponents of random dynamical systems are presented and investigated. The main results are: 1. In the space of all unbounded linear cocycles satisfying a certain integrability condition, we construct an open set of linear cocycles have simple Lyapunov spectrum and no exponential separation. Thus, unlike the bounded case, the exponential separation property is nongeneric in the space of unbounded cocycles. 2. The multiplicative ergodic theorem is established for random difference equations as well as random differential equations with random delay. 3. We provide a computational method for computing an invariant measure for infinite iterated functions systems as well as the Lyapunov exponents of products of random matrices. / In den vorliegenden Arbeit werden Lyapunov-Exponented für zufällige dynamische Systeme untersucht. Die Hauptresultate sind: 1. Im Raum aller unbeschränkten linearen Kozyklen, die eine gewisse Integrabilitätsbedingung erfüllen, konstruieren wir eine offene Menge linearer Kyzyklen, die einfaches Lyapunov-Spektrum besitzen und nicht exponentiell separiert sind. Im Gegensatz zum beschränkten Fall ist die Eingenschaft der exponentiellen Separiertheit nicht generisch in Raum der unbeschränkten Kozyklen. 2. Sowohl für zufällige Differenzengleichungen, als auch für zufällige Differentialgleichungen, mit zufälligem Delay wird ein multiplikatives Ergodentheorem bewiesen. 3.Eine algorithmisch implementierbare Methode wird entwickelt zur Berechnung von invarianten Maßen für unendliche iterierte Funktionensysteme und zur Berechnung von Lyapunov-Exponenten für Produkte von zufälligen Matrizen.

In Natural Language Processing (NLP), speech and text are parsed and generated with language models and parser models, and translated with translation models. Each model contains a set of numerical parameters which are found by applying a suitable training algorithm to a set of training data. Many such training algorithms are instances of the Expectation-Maximization (EM) algorithm. In [BSV15], a generic EM algorithm for NLP is described. This work presents a particular speech model, the Hidden Markov model, and its standard training algorithm, the Baum-Welch algorithm. It is then shown that the Baum-Welch algorithm is an instance of the generic EM algorithm introduced by [BSV15], from which follows that all statements about the generic EM algorithm also apply to the Baum-Welch algorithm, especially its correctness and convergence properties.