Mathematik
Refine
Year of publication
Document Type
- Article (110)
- Doctoral Thesis (76)
- Preprint (44)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (370)
Is part of the Bibliography
- no (370)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
Institute
- Mathematik (370)
- Informatik (55)
- Präsidium (22)
- Physik (6)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
Algorithms for the Maximum Cardinality Matching Problem which greedily add edges to the solution enjoy great popularity. We systematically study strengths and limitations of such algorithms, in particular of those which consider node degree information to select the next edge. Concentrating on nodes of small degree is a promising approach: it was shown, experimentally and analytically, that very good approximate solutions are obtained for restricted classes of random graphs. Results achieved under these idealized conditions, however, remained unsupported by statements which depend on less optimistic assumptions.
The KarpSipser algorithm and 1-2-Greedy, which is a simplified variant of the well-known MinGreedy algorithm, proceed as follows. In each step, if a node of degree one (resp. at most two) exists, then an edge incident with a minimum degree node is picked, otherwise an arbitrary edge is added to the solution.
We analyze the approximation ratio of both algorithms on graphs of degree at most D. Families of graphs are known for which the expected approximation ratio converges to 1/2 as D grows to infinity, even if randomization against the worst case is used. If randomization is not allowed, then we show the following convergence to 1/2: the 1-2-Greedy algorithm achieves approximation ratio (D-1)/(2D-3); if the graph is bipartite, then the more restricted KarpSipser algorithm achieves the even stronger factor D/(2D-2). These guarantees set both algorithms apart from other famous matching heuristics like e.g. Greedy or MRG: these algorithms depend on randomization to break the 1/2-barrier even for paths with D=2. Moreover, for any D our guarantees are strictly larger than the best known bounds on the expected performance of the randomized variants of Greedy and MRG.
To investigate whether KarpSipser or 1-2-Greedy can be refined to achieve better performance, or be simplified without loss of approximation quality, we systematically study entire classes of deterministic greedy-like algorithms for matching. Therefore we employ the adaptive priority algorithm framework by Borodin, Nielsen, and Rackoff: in each round, an adaptive priority algorithm requests one or more edges by formulating their properties---like e.g. "is incident with a node of minimum degree"---and adds the received edges to the solution. No constraints on time and space usage are imposed, hence an adaptive priority algorithm is restricted only by its nature of picking edges in a greedy-like fashion. If an adaptive priority algorithm requests edges by processing degree information, then we show that it does not surpass the performance of KarpSipser: our D/(2D-2)-guarantee for bipartite graphs is tight and KarpSipser is optimal among all such "degree-sensitive" algorithms even though it uses degree information merely to detect degree-1 nodes. Moreover, we show that if degrees of both nodes of an edge may be processed, like e.g. the Double-MinGreedy algorithm does, then the performance of KarpSipser can only be increased marginally, if at all. Of special interest is the capability of requesting edges not only by specifying the degree of a node but additionally its set of neighbors. This enables an adaptive priority algorithm to "traverse" the input graph. We show that on general degree-bounded graphs no such algorithm can beat factor (D-1)/(2D-3). Hence our bound for 1-2-Greedy is tight and this algorithm performs optimally even though it ignores neighbor information. Furthermore, we show that an adaptive priority algorithm deteriorates to approximation ratio exactly 1/2 if it does not request small degree nodes. This tremendous decline of approximation quality happens for graphs on which 1-2-Greedy and KarpSipser perform optimally, namely paths with D=2. Consequently, requesting small degree nodes is vital to beat factor 1/2.
Summarizing, our results show that 1-2-Greedy and KarpSipser stand out from known and hypothetical algorithms as an intriguing combination of both approximation quality and conceptual simplicity.
Die letzten Jahrzehnte brachten einen enormen Zuwachs des Wissens und Verständnisses über die molekularen Prozesse des Lebens.Möglich wurde dieser Zuwachs durch die Entwicklung diverser Methoden, mit denen beispielsweise gezielt die Konzentration einzelner Stoffe gemessen werden kann oder gar alle anwesenden Metaboliten eines biologischen Systems erfasst werden können. Die großflächige Anwendung dieser Methoden führte zur Ansammlung vieler unterschiedlicher -om-Daten, wie zum Beispiel Metabolom-, Proteom- oder Transkriptoms-Datensätzen. Die Systembiologie greift auf solche Daten zurück, um mathematische Modelle biologischer Systeme zu erstellen, und ermöglicht so ein Studium biologischer Systeme auch außerhalb des Labors.
Für größere biologische Systeme stehen jedoch meistens nicht alle Informationen über Stoffkonzentrationen oder Reaktionsgeschwindigkeiten zur Verfügung, um eine quantitative Modellierung, also die Beschreibung von Änderungsraten kontinuierlicher Variablen, durchführen zu können. In einem solchen Fall wird auf Methoden der qualitativen Modellierung zurückgegriffen. Eine dieser Methoden sind die Petrinetze (PN), welche in den 1960er Jahren von Carl Adam Petri entwickelt wurden, um nebenläufige Prozesse im technischen Umfeld zu beschreiben. Seit Anfang der 1990er Jahre finden PN auch Anwendung in der Systembiologie, um zum Beispiel metabolische Systeme oder Signaltransduktionswege zu modellieren. Einer der Vorteile dieser Methode ist zudem, dass Modelle als qualitative Beschreibung des Systems begonnen werden können und im Laufe der Zeit um quantitative Beschreibungen ergänzt werden können.
Zur Modellierung und Analyse von PN existieren bereits viele Anwendungen. Da das Konzept der PN jedoch ursprünglich nicht für die Systembiologie entwickelt wurde und meist im technischen Bereich verwendet wird, existierten kaum Anwendungen, die für den Einsatz in der Systembiologie entwickelt wurden. Daher ist auch die Durchführung der für die Systembiologie entwickelten Analysemethoden für PN nicht mit diesen Anwendungen möglich. Die Motivation des ersten Teiles dieser Arbeit war daher, eine Anwendung zu schaffen, die speziell für die PN-Modellierung und Analyse in der Systembiologie gedacht ist, also in ihren Analysemethoden und ihrer Terminologie sich an den Bedürfnissen der Systembiologie orientiert. Zudem sollte die Anwendung den Anwender bei der Auswertung der Resultate der Analysemethoden visuell unterstützen, indem diese direkt visuell im Kontext des PN gesetzt werden. Da bei komplexeren PN die Resultate der Analysemethoden in ihrer Zahl drastisch anwachsen, wird eine solche Auswertung dieser notwendig. Aus dieser Motivation heraus entstand die Anwendung MonaLisa, dessen Implementierung und Funktionen im ersten Teil der vorliegenden Arbeit beschrieben werden. Neben den klassischen Analysemethoden für PN, wie den Transitions- und Platz-Invarianten, mit denen grundlegende funktionale Module innerhalb eines PN gefunden werden können, wurden weitere, meist durch die Systembiologie entwickelte, Analysemethoden implementiert. Dazu zählen zum Beispiel die Minimal Cut Sets, die Maximal Common Transitions Sets oder Knock-out-Analysen. Mit MonaLisa ist aber auch die Simulation des dynamischen Verhaltens des modellierten biologischen Systems möglich. Hierzu stehen sowohl deterministische als auch stochastische Verfahren, beispielsweise der Algorithmus von Gillespie zur Simulation chemischer Systeme, zur Verfügung. Für alle zur Verfügung gestellten Analysemethoden wird ebenfalls eine visuelle Repräsentation ihrer Resultate bereitgestellt. Im Falle der Invarianten werden deren Elemente beispielsweise in der Visualisierung des PN eingefärbt. Die Resultate der Simulationen oder der topologischen Analyse können durch verschiedene Graphen ausgewertet werden. Um eine Schnittstelle zu anderen Anwendungen zu schaffen, wurde für MonaLisa eine Unterstützung einiger gängiger Dateiformate der Systembiologie geschaffen, so z.B. für SBML und KGML.
Der zweite Teil der Arbeit beschäftigt sich mit der topologischen Analyse eines Datensatzes von 2641 Gesamtgenom Modellen aus der path2models-Datenbank. Diese Modelle wurden automatisiert aus dem vorhandenen Wissen der KEGG- und der MetaCyc-Datenbank erstellt. Die Analyse der topologischen Eigenschaften eines Graphen ermöglicht es, grundlegende Aussagen über die globalen Eigenschaften des modellierten Systems und dessen Entstehungsprozesses zu treffen. Daher ist eine solche Analyse oft der erste Schritt für das Verständnis eines komplexen biologischen Systems. Für die Analyse der Knotengrade aller Reaktionen und Metaboliten dieser Modelle wurden sie in einem ersten Schritt in PN transformiert. Die topologischen Eigenschaften von metabolischen Systemen werden in der Literatur schon sehr gut beschrieben, wobei die Untersuchungen meist auf einem Netzwerk der Metaboliten oder der Reaktionen basieren. Durch die Verwendung von PN wird es möglich, die topologischen Eigenschaften von Metaboliten und Reaktionen in einem gemeinsamen Netzwerk zu untersuchen. Die Motivation hinter diesen Untersuchungen war, zu überprüfen, ob die schon beschriebenen Eigenschaften auch für eine Darstellung als PN zutreffen und welche neuen Eigenschaften gefunden werden können. Untersucht wurden der Knotengrad und der Clusterkoeffizient der Modelle. Es wird gezeigt, dass einige wenige Metaboliten mit sehr hohem Knotengrad für eine ganze Reihe von Effekten verantwortlich sind, wie beispielsweise dass die Verteilung des Knotengrades und des Clusterkoeffizienten, im Bezug auf Metaboliten, skalenfrei sind und dass sie für die Vernetzung der Nachbarschaft von Reaktionen verantwortlich sind. Weiter wird gezeigt, dass die Größe eines Modelles Einfluss auf dessen topologische Eigenschaften hat. So steigt die Vernetzung der Nachbarschaft eines Metaboliten, je mehr Metaboliten in einem biologischen System vorhanden sind, gleiches gilt für den durchschnittlichen Knotengrad der Metaboliten.
Given an Abelian semi-group (A, +), an A-valued curvature measure is a valuation with values in A-valued measures. If A = R, complete classifications of Hausdorff-continuous translation-invariant SO(n)-invariant valuations and curvature measures were obtained by Hadwiger and Schneider, respectively. More recently, characterisation results have been achieved for curvature measures with values in A = Sym^p R^n and A = Sym^2 Λ^q R^n for p, q ≥ 1 with varying assumptions as for their invariance properties.
In the present work, we classify all smooth translation-invariant SO(n)-covariant curvature measures with values in any SO(n)-representation in terms of certain differential forms on the sphere bundle S R^n and describe their behaviour under the globalisation map. The latter result also yields a similar classification of all continuous SO(n)-module-valued SO(n)-covariant valuations. Furthermore, a decomposition of the space of smooth translation-
invariant scalar-valued curvature measures as an SO(n)-module is obtained. As a corollary, we construct explicit bases of continuous translation-invariant scalar-valued valuations and smooth translation-invariant scalar-valued curvature measures.
Die Populationsgenetik beschäftigt sich mit dem Einfluss von zufälliger Reproduktion, Rekombination, Migration, Mutation und Selektion auf die genetische Struktur einer Population.
In dieser Arbeit mit dem englischen Titel "Ancestral lines under mutation and selection" wird das Zusammenspiel von zufälliger Reproduktion, gerichteter Selektion und Zweiwegmutation untersucht.
Dazu betrachten wir eine haploide Population in der jedes Individuum zu jedem Zeitpunkt genau einen von zwei Typen aus S:={0,1} trägt. Dabei sei 1 der neutrale und 0 der selektiv bevorzugte Typ. Im Diffusionslimes sehr großer Populationen modellieren wir den Prozess der Frequenz der Typ-0-Individuen durch eine Wright-Fisher-Diffusion X:=(X_t) mit Mutation und gerichteter Selektion.
Zu jedem Zeitpunkt s gibt es genau ein Individuum, dessen Nachkommen ab einem bestimmten zukünftigen Zeitpunkt t>s die gesamte Population ausmachen werden. Wir nennen dieses Individuum den gemeinsamen Vorfahren zum Zeitpunkt s, da alle Individuen zu allen Zeitpunkten r>t von ihm abstammen. Sei R_{s} dessen Typ zum Zeitpunkt s. Wir nehmen an, dass der Prozess X zum Zeitpunkt 0 im Gleichgewicht ist und definieren die Wahrscheinlichkeit, dass der gemeinsame Vorfahre zum Zeitpunkt 0 Typ 0 hat, durch h(x):= P(R_{0}=0|X_{0}=x). Eine Darstellung von h(x) wurde bereits von Fearnhead (2002) und Taylor (2007) gefunden und dort mit vorwiegend analytischen Methoden bewiesen. In dieser Arbeit entwickeln wir in Kapitel 3 ein neues Teilchenbild, den pruned lookdown ancestral selection graph (pruned LD-ASG), der für sich selbst genommen interessant ist und eine neue probabilistische Interpretation der Darstellung von h(x) liefert.
Durch Erweiterung des Teilchenbildes auf Nachkommenverteilungen mit schweren Tails und mit Hilfe einer Siegmund Dualität gelingt es uns in Kapitel 4 das Resultat für h(x) von klassischen Wright-Fisher-Diffusionen auf Lambda-Wright-Fisher-Diffuison zu erweitern.
Eine Verbindung zwischen Ideen von Taylor (2007), der den gemeinsamen Prozess (X,R) untersucht hat, und einem von Fearnhead (2002) betrachteten Prozess (R,V), der die Entwicklung des Typs R des gemeinsamen Vorfahren in einer Umgebung von V sogenannten virtuellen Linien beschreibt, stellen wir in Kapitel 6 her. Wir bestimmen die gemeinsame Dynamik des Tripels (X,R,V). In Kapitel 7 betrachten wir ein diskretes Bild mit endlicher Populationsgröße N und schlagen dort eine Brücke zu Resultaten von Kluth, Hustedt und Baake (2013).
Des Weiteren entwickeln wir in Kapitel 5 dieser Arbeit einen Algorithmus zur Simulation der Typen einer Stichprobe von m Individuen, die aus einer Wright-Fisher-Population mit Mutation und Selektion im Gleichgewicht gezogen wird. Mittels dieses Algorithmus illustrieren wir die Typenverteilung für verschiedene Parameterwerte und Stichprobengrößen.
Das Vertrauen vieler Menschen in ihre mathematischen und musikalischen Fähigkeiten ist oftmals sehr niedrig ausgeprägt oder wenig ausdifferenziert. Sie glauben, dass sie in dem einen oder anderen Fach (oder beiden) nicht gut seien. Hinzukommt, dass die Aussage „Ich kann nicht singen“ oder „Mathematik habe ich noch nie verstanden“ durchaus gesellschaftsfähig ist und sie nicht daran hindern muss, eine erfolgreiche Karriere zu durchlaufen, noch wird es die Meinung anderer über sie ändern.
Das Projekt „European Music Portfolio – Sounding Ways into Mathematics“ (EMP-Maths) möchte dieses Verständnis ändern. Jeder kann singen und Musik machen und jeder kann Mathematik treiben. Beide Themen sind integraler Bestandteil unseres Lebens und unserer Gesellschaft. Was geändert werden muss, ist das Bild von diesen beiden Fächern und die Fähigkeit von Lehrpersonen, Lernenden die Gelegenheit zu geben, dieses zu verändern und die beiden Fächer als bereichernd für die Lebensgestaltung einzustufen.
Beispielhaft wird im Arbeitsbuch eine Aktivität vorgestellt, in welcher Mathematik und Musik in einer Unterrichtssequenz miteinander verbunden werden. Weitere Aktivitäten, die in der Schule genutzt werden können, finden sich im Handbuch für Lehrerinnen und Lehrer. Viele weitere Beispiele und Vorschläge sind bereits vorhanden (siehe Web-Seite des Projekts) und wir möchten jeden ermutigen, sie zu nutzen. Die Auswahl im Handbuch deckt einige zentralen Felder der Mathematik und der Musik ab: Singen, Tanzen, Hören, Probleme lösen, Zahlen, Messen, Raum und Form. Mit diesem Ansatz wollen wir das Projekt an die Kerncurricula der beteiligten Länder anbinden: Deutschland, Griechenland, Rumänien, Slowakei, Spanien, Schweiz und Großbritannien. Die Dokumentation der Beispiele erfolgt in einer Art von Didaktischen Design Patterns, deren Struktur an die Anforderungen des Projekts angepasst wurde.
Das Projekt „Sounding Ways into Mathematics“ stellt Aktivitäten mit unterschiedlichen mathematischen und musikalischen Inhalten vor, um Lehrpersonen ein möglichst breites Spektrum an Hilfsmitteln, Ideen und Beispielen anbieten zu können. Diese Aktivitäten sind so aufgebaut, dass sie erweiter- und anpassbar an unterschiedliche Kontexte sowie auf die Bedürfnisse einer jeden Lehrperson und deren Schülerinnen und Schülern sind. Ferner wurden diese Aktivitäten nicht nur entwickelt, um von der Lehrperson instruktiv ausgeführt zu werden, sondern, um sie gemeinsam mit der Lerngruppe zu nutzen und eventuell sogar gemeinsam zu verändern und weiter zu entwickeln.
Das Projekt „Sounding Ways into Mathematics“ steht in Verbindung zum EMP-Sprachen Projekt „A creative Way into Languages“ (http://emportfolio.eu/emp/).
European Music Portfolio (EMP) – Maths: 'Sounding ways into mathematics' : teacher’s handbook
(2016)
Music and mathematics share an odd character: many people believe that they are not good at one or the other (or both). However, ‘I cannot sing’ or ‘I never understood mathematics’ will probably not keep them from having successful careers, and nor will it change the opinions others have about them.
The project ‘European Music Portfolio – Sounding Ways into Mathematics’ (EMP-Maths) aims towards a different understanding with regards to this character. Everyone can sing and make music, and everyone can do mathematics. Both topics are integral parts of our life and society. What needs to be improved is our ability to give students opportunities to like them.
This teacher’s handbook presents activities with different mathematical and musical content in order to offer teachers resources, ideas and examples. These activities are designed to be expandable, adaptable to different contexts, and adjustable to the needs of each teacher and their students. Furthermore, these activities are not just planned to be carried out individually; a teaching unit could be used to make sense of them, or they could even be developed in connection with each other.
Apart from this teacher’s handbook, the project provides a continuing professional development (CPD) course, a webpage (http://maths.emportfolio.eu) from which all materials can be downloaded, and an online collaboration platform. A general overview of related literature and research is available in separate documents. Additional teacher booklets provide related materials and a brief overview of the theoretical background, and are the basis for the CPD courses. The project ‘Sounding Ways into Mathematics’ is related to the EMP-Languages project ‘A Creative Way into Languages’ (http://emportfolio.eu/emp/).
The behaviour of electronic circuits is influenced by ageing effects. Modelling the behaviour of circuits is a standard approach for the design of faster, smaller, more reliable and more robust systems. In this thesis, we propose a formalization of robustness that is derived from a failure model, which is based purely on the behavioural specification of a system. For a given specification, simulation can reveal if a system does not comply with a specification, and thus provide a failure model. Ageing usually works against the specified properties, and ageing models can be incorporated to quantify the impact on specification violations, failures and robustness. We study ageing effects in the context of analogue circuits. Here, models must factor in infinitely many circuit states. Ageing effects have a cause and an impact that require models. On both these ends, the circuit state is highly relevant, an must be factored in. For example, static empirical models for ageing effects are not valid in many cases, because the assumed operating states do not agree with the circuit simulation results. This thesis identifies essential properties of ageing effects and we argue that they need to be taken into account for modelling the interrelation of cause and impact. These properties include frequency dependence, monotonicity, memory and relaxation mechanisms as well as control by arbitrary shaped stress levels. Starting from decay processes, we define a class of ageing models that fits these requirements well while remaining arithmetically accessible by means of a simple structure.
Modeling ageing effects in semiconductor circuits becomes more relevant with higher integration and smaller structure sizes. With respect to miniaturization, digital systems are ahead of analogue systems, and similarly ageing models predominantly focus on digital applications. In the digital domain, the signal levels are either on or off or switching in between. Given an ageing model as a physical effect bound to signal levels, ageing models for components and whole systems can be inferred by means of average operation modes and cycle counts. Functional and faithful ageing effect models for analogue components often require a more fine-grained characterization for physical processes. Here, signal levels can take arbitrary values, to begin with. Such fine-grained, physically inspired ageing models do not scale for larger applications and are hard to simulate in reasonable time. To close the gap between physical processes and system level ageing simulation, we propose a data based modelling strategy, according to which measurement data is turned into ageing models for analogue applications. Ageing data is a set of pairs of stress patterns and the corresponding parameter deviations. Assuming additional properties, such as monotonicity or frequency independence, learning algorithm can find a complete model that is consistent with the data set. These ageing effect models decompose into a controlling stress level, an ageing process, and a parameter that depends on the state of this process. Using this representation, we are able to embed a wide range of ageing effects into behavioural models for circuit components. Based on the developed modelling techniques, we introduce a novel model for the BTI effect, an ageing effect that permits relaxation. In the following, a transistor level ageing model for BTI that targets analogue circuits is proposed. Similarly, we demonstrate how ageing data from analogue transistor level circuit models lift to purely behavioural block models. With this, we are the first to present a data based hierarchical ageing modeling scheme. An ageing simulator for circuits or system level models computes long term transients, solutions of a differential equation. Long term transients are often close to quasi-periodic, in some sense repetitive. If the evaluation of ageing models under quasi-periodic conditions can be done efficiently, long term simulation becomes practical. We describe an adaptive two-time simulation algorithm that basically skips periods during simulation, advancing faster on a second time axis. The bottleneck of two-time simulation is the extrapolation through skipped frames. This involves both the evaluation of the ageing models and the consistency of the boundary conditions. We propose a simulator that computes long term transients exploiting the structure of the proposed ageing models. These models permit extrapolation of the ageing state by means of a locally equivalent stress, a sort of average stress level. This level can be computed efficiently and also gives rise to a dynamic step control mechanism. Ageing simulation has a wide range of applications. This thesis vastly improves the applicability of ageing simulation for analogue circuits in terms of modelling and efficiency. An ageing effect model that is a part of a circuit component model accounts for parametric drift that is directly related to the operation mode. For example asymmetric load on a comparator or power-stage may lead to offset drift, which is not an empiric effect. Monitor circuits can report such effects during operation, when they become significant. Simulating the behaviour of these monitors is important during their development. Ageing effects can be compensated using redundant parts, and annealing can revert broken components to functional. We show that such mechanisms can be simulated in place using our models and algorithms. The aim of automatized circuit synthesis is to create a circuit that implements a specification for a certain use case. Ageing simulation can identify candidates that are more reliable. Efficient ageing simulation allows to factor in various operation modes and helps refining the selection. Using long term ageing simulation, we have analysed the fitness of a set of synthesized operational amplifiers with similar properties concerning various use cases. This procedure enables the selection of the most ageing resilient implementation automatically.
From Brownian motion with a local time drift to Feller's branching diffusion with logistic growth
(2011)
We give a new proof for a Ray-Knight representation of Feller's branching diffusion with logistic growth in terms of the local times of a reflected Brownian motion H with a drift that is affine linear in the local time accumulated by H
at its current level. In Le et al. (2011) such a representation was obtained by an approximation through Harris paths that code the genealogies of particle systems. The present proof is purely in terms of stochastic analysis, and is inspired by previous work of Norris, Rogers and Williams (1988).
Random ordinary differential equations (RODEs) are ordinary differential equations (ODEs) which have a stochastic process in their vector field functions. RODEs have been used in a wide range of applications such as biology, medicine, population dynamics and engineering and play an important role in the theory of random dynamical systems, however, they have been long overshadowed by stochastic differential equations.
Typically, the driving stochastic process has at most Hoelder continuous sample paths and the resulting vector field is, thus, at most Hoelder continuous in time, no matter how smooth the vector function is in its original variables, so the sample paths of the solution are certainly continuously differentiable, but their derivatives are at most Hoelder continuous in time. Consequently, although the classical numerical schemes for ODEs can be applied pathwise to RODEs, they do not achieve their traditional orders.
Recently, Gruene and Kloeden derived the explicit averaged Euler scheme by taking the average of the noise within the vector field. In addition, new forms of higher order Taylor-like schemes for RODEs are derived systematically by Jentzen and Kloeden.
However, it is still important to build higher order numerical schemes and computationally less expensive schemes as well as numerically stable schemes and this is the motivation of this thesis. The schemes by Gruene and Kloeden and Jentzen and Kloeden are very general, so RODEs with special structure, i.e., RODEs with Ito noise and RODEs with affine structure, are focused and numerical schemes which exploit these special structures are investigated.
The developed numerical schemes are applied to several mathematical models in biology and medicine. In order to see the performance of the numerical schemes, trajectories of solutions are illustrated. In addition, the error vs. step sizes as well as the computational costs are compared among newly developed schemes and the schemes in literature.
In the qualitative analysis of solutions of partial differential equations, many interesting questions are related to the shape of solutions. In particular, the symmetries of a given solution are of interest. One of the first more general results in this direction was given in 1979 by Gidas, Ni and Nirenberg... The main tool in proving this symmetry and monotonicity result is the moving plane method. This method, which goes back to Alexandrov’s work on constant mean curvature surfaces in 1962, was introduced in 1971 by Serrin in the context of partial differential equations to analyze an overdetermined problem...
Triangles of groups have been introduced by Gersten and Stallings. They are, roughly speaking, a generalization of the amalgamated free product of two groups and occur in the framework of Corson diagrams. First, we prove an intersection theorem for Corson diagrams. Then, we focus on triangles of groups. It has been shown by Howie and Kopteva that the colimit of a hyperbolic triangle of groups contains a non-abelian free subgroup. We give two natural conditions, each of which ensures that the colimit of a non-spherical triangle of groups either contains a non-abelian free subgroup or is virtually solvable.
This work proposes to employ the (bursty) GLO model from Bingmer et. al (2011) to model the occurrence of tropical cyclones. We develop a Bayesian framework to estimate the parameters of the model and, particularly, employ a Markov chain Monte Carlo algorithm. This also allows us to develop a forecasting framework for future events.
Moreover, we assess the default probability of an insurance company that is exposed to claims that occur according to a GLO process and show that the model is able to substantially improve actuarial risk management if events occur in oscillatory bursts.
Optimierung von Phasen- und Ratenparametern in einem stochastischen Modell neuronaler Feueraktivität
(2014)
In unserem Gehirn wird Information von Neuronen durch die Emission von Spikes repräsentiert. Als wichtige Signalkomponenten werden hierbei die Rate (Anzahl Spikes), die Phase (zeitliche Verschiebung der Spikes) und synchrone Oszillationen (rhythmische Entladungen der Neuronen am selben Zyklus) diskutiert.
In dieser Arbeit wird untersucht, wie Rate und Phase für eine optimale Detektion miteinander kombiniert werden und abhängig vom gewählten Parameterbereich wird der Beitrag der Phase quantifiziert.
Dies wird anhand eines stochastischen Spiketrain-Modell untersucht, das hohe Ähnlichkeiten zu empirischen Spiketrains zeigt und die drei genannten Signalkomponenten beinhaltet. Das ELO-Modell („exponential lockig to a free oscillator“) ist in zwei Prozessstufen unterteilt: Im Hintergrund steht ein globaler Oszillationsprozess, der unabhängige und normal-verteilte Intervallabschnitte hervorbringt (Oszillation). An den Intervallgrenzen starten unabhängig, inhomogene Poisson-Prozesse (Synchronizität) mit exponentiell abnehmender Feuerrate, die durch eine stimulusspezifische Rate und Phase festgelegt ist.
Neben einer analytischen Bestimmung der optimalen Parameter im Falle reiner Raten- bzw. Phasencodierung, wird die gemeinsame Codierung anhand von Simulationsstudien analysiert.
Containment problems belong to the classical problems of (convex) geometry. In the proper sense, a containment problem is the task to decide the set-theoretic inclusion of two given sets, which is hard from both the theoretical and the practical perspective. In a broader sense, this includes, e.g., radii or packing problems, which are even harder. For some classes of convex sets there has been strong interest in containment problems. This includes containment problems of polyhedra and balls, and containment of polyhedra, which have been studied in the late 20th century because of their inherent relevance in linear programming and combinatorics.
Since then, there has only been limited progress in understanding containment problems of that type. In recent years, containment problems for spectrahedra, which naturally generalize the class of polyhedra, have seen great interest. This interest is particularly driven by the intrinsic relevance of spectrahedra and their projections in polynomial optimization and convex algebraic geometry. Except for the treatment of special classes or situations, there has been no overall treatment of that kind of problems, though.
In this thesis, we provide a comprehensive treatment of containment problems concerning polyhedra, spectrahedra, and their projections from the viewpoint of low-degree semialgebraic problems and study algebraic certificates for containment. This leads to a new and systematic access to studying containment problems of (projections of) polyhedra and spectrahedra, and provides several new and partially unexpected results.
The main idea - which is meanwhile common in polynomial optimization, but whose understanding of the particular potential on low-degree geometric problems is still a major challenge - can be explained as follows. One point of view towards linear programming is as an application of Farkas' Lemma which characterizes the (non-)solvability of a system of linear inequalities. The affine form of Farkas' Lemma characterizes linear polynomials which are nonnegative on a given polyhedron. By omitting the linearity condition, one gets a polynomial nonnegativity question on a semialgebraic set, leading to so-called Positivstellensaetze (or, more precisely Nichtnegativstellensaetze). A Positivstellensatz provides a certificate for the positivity of a polynomial function in terms of a polynomial identity. As in the linear case, these Positivstellensaetze are the foundation of polynomial optimization and relaxation methods. The transition from positivity to nonnegativity is still a major challenge in real algebraic geometry and polynomial optimization.
With this in mind, several principal questions arise in the context of containment problems: Can the particular containment problem be formulated as a polynomial nonnegativity (or, feasibility) problem in a sophisticated way? If so, how are positivity and nonnegativity related to the containment question in the sense of their geometric meaning? Is there a sophisticated Positivstellensatz for the particular situation, yielding certificates for containment? Concerning the degree of the semialgebraic certificates, which degree is necessary, which degree is sufficient to decide containment?
Indeed, (almost) all containment problems studied in this thesis can be formulated as polynomial nonnegativity problems allowing the application of semialgebraic relaxations. Other than this general result, the answer to all the other questions (highly) depends on the specific containment problem, particularly with regard to its underlying geometry. An important point is whether the hierarchies coming from increasing the degree in the polynomial relaxations always decide containment in finitely many steps.
We focus on the containment problem of an H-polytope in a V-polytope and of a spectrahedron in a spectrahedron. Moreover, we address containment problems concerning projections of H-polyhedra and spectrahedra. This selection is justified by the fact that the mentioned containment problems are computationally hard and their geometry is not well understood.
This thesis covers the analysis of radix sort, radix select and the path length of digital trees under a stochastic input assumption known as the Markov model.
The main results are asymptotic expansions of mean and variance as well as a central limit theorem for the complexity of radix sort and the path length of tries, PATRICIA tries and digital search trees.
Concerning radix select, a variety of different models for ranks are discussed including a law of large numbers for the worst case behavior, a limit theorem for the grand averages model and the first order asymptotic of the average complexity in the quantile model.
Some of the results are achieved by moment transfer techniques, the limit laws are based on a novel use of the contraction method suited for systems of stochastic recurrences.
This work is concerned with two topics at the intersection of convex algebraic geometry and optimization.
We develop a new method for the optimization of polynomials over polytopes. From the point of view of convex algebraic geometry the most common method for the approximation of polynomial optimization problems is to solve semidefinite programming relaxations coming from the application of Positivstellensätze. In optimization, non-linear programming problems are often solved using branch and bound methods. We propose a fused method that uses Positivstellensatz-relaxations as lower bounding methods in a branch and bound scheme. By deriving a new error bound for Handelman's Positivstellensatz, we show convergence of the resulting branch and bound method. Through the application of Positivstellensätze, semidefinite programming has gained importance in polynomial optimization in recent years. While it arises to be a powerful tool, the underlying geometry of the feasibility regions (spectrahedra) is not yet well understood. In this work, we study polyhedral and spectrahedral containment problems, in particular we classify their complexity and introduce sufficient criteria to certify the containment of one spectrahedron in another one.
In der Arbeit wird ein Testverfahren zum Prüfen der Varianzhomogenität der Lebenszeiten eines Erneuerungsprozesses entwickelt. Das Verfahren basiert auf der "Filtered-Derivative"-Methode. Zur Herleitung des Annahmebereichs werden zunächst Bootstrap-Permutationen genutzt, bevor zu einer asymptotischen Methode übergangen wird. Ein entsprechender funktionaler Grenzwertsatz wird skizziert. Aufbauend auf dem Test wird ein Multiple-Filter-Algorithmus zur genauen Detektion der Varianz-Change-Points besprochen. Schließlich folgt die Inklusion von vorher detektierten Ratenänderungen in das Verfahren. Der Test und der Algorithmus werden in Simulationsstudien evaluiert. Abschließend erfolgt eine Anwendung auf EEG-Daten.
The cones of nonnegative polynomials and sums of squares arise as central objects in convex algebraic geometry and have their origin in the seminal work of Hilbert ([Hil88]). Depending on the number of variables n and the degree d of the polynomials, Hilbert famously characterizes all cases of equality between the cone of nonnegative polynomials and the cone of sums of squares. This equality precisely holds for bivariate forms, quadratic forms and ternary quartics ([Hil88]). Since then, a lot of work has been done in understanding the difference between these two cones, which has major consequences for many practical applications such as for polynomial optimization problems. Roughly speaking, minimizing polynomial functions (constrained as well as unconstrained) can be done efficiently whenever certain nonnegative polynomials can be written as sums of squares (see Section 2.3 for the precise relationship). The underlying reason is the fundamental difference that checking nonnegativity of polynomials is an NP-hard problem whenever the degree is greater or equal than four ([BCSS98]), whereas checking whether a polynomial can be written as a sum of squares is a semidefinite feasibility problem (see Section 2.2). Although the complexity status of the semidefinite feasibility problem is still an open problem, it is polynomial for fixed number of variables. Hence, understanding the difference between nonnegative polynomials and sums of squares is highly desirable both from a theoretical and a practical viewpoint.
In dieser Arbeit wurde deutlich, dass die Multilevel Monte Carlo Methode eine signifikante Verbesserung gegenüber der Monte Carlo Methode darstellt. Sie schafft es den Rechenaufwand zu verringern und in fast allen Fällen die gewollte Genauigkeit zu erreichen. Die Erweiterung durch Richardson Extrapolation brachte immer eine Verringerung des Rechenaufwands oder zumindest keine Verschlechterung, auch wenn nicht in allen Fällen die schwache Konvergenzordnung verdoppelt wurde.
Im Falle der Optionssensitivitäten ist eine Anwendung des MLMC-Algorithmus problematisch. Das Funktional, das auf den Aktienkurs angewendet wird, darf keine Unstetigkeitsstelle besitzen, bzw. im Falle des Gammas muss es stetig differenzierbar sein. Die Anwendung der MLMC Methode macht dann vor allem Sinn, wenn sich die Sensitivität als Funktion des Aktienkurses umformen lässt, so dass nur der Pfad der Aktie simuliert werden muss. Nur wenn dies nicht möglich ist, wäre es sinnvoll, die in Kapitel 6.5 am Beispiel des Deltas vorgestellte Methode zu benutzen, in der man einen zweiten Pfad für das Delta simuliert.
Weitere Verbesserungsmöglichkeiten könnten in der Wahl von anderen varianzreduzierenden Methoden liegen oder durch Verwendung von Diskretisierungsverfahren mit höherer starker Ordnung als das Euler-Verfahren (vgl. [7], Verwendung des Milstein-Verfahrens). In diesem Fall ist theoretisch ein Rechenaufwand der Größenordnung O(ϵexp-2) möglich, da die Anzahl der zu erstellenden Samples nicht mehr mit steigendem L erhöht wird. Somit könnte das L so groß gewählt werden, dass der Bias verschwindet und der MSE ausschließlich von der Varianz des Schätzers abhängt. Um diese auf eine Größenordnung von O(ϵexp2) zu bringen, ist es nötig, O(ϵexp2) Pfade zu erstellen (siehe Gleichung (3.6)), was den Rechenaufwand begründet.
Quasi-Monte-Carlo-Verfahren zur Bewertung von Finanzderivaten, BacDas Gebiet der Optionsbewertung ist durch die Entwicklungen zu neuen und immer komplexer werdenden Optionstypen und durch Verbesserungen im Bereich der Aktienkurs-Modelle geprägt. Diese Entwicklung und die gestiegene Leistungsfähigkeit der Parallelrechner haben das Interesse an den flexiblen Quasi-Monte-Carlo-Verfahren neu geweckt.
Die experimentellen Untersuchungen bestätigen die Überlegenheit des Quasi-Monte-Carlo-Verfahren gegenüber den klassische Monte-Carlo-Verfahren in Bezug auf niedrigdimensionale Optionstypen. Dieser Überlegenheit nimmt aber mit zunehmender Dimension ab, was eine Nachteil für das Quasi-Monte-Carlo Verfahren darstellt. Zur Verbesserung des Verfahrens gibt das Dimensions-Reduktions-Prinzip (effective dimension) und weitere Niederdiskrepanz-Folgen, wie Niederreiter-Folgen, Lattice-Regeln, usw. Weitere Verbesserungsmöglichkeiten könnten auch durch Wahl von anderen Diskretisierungsverfahren mit höherer starker Ordnung, wie z.B dem Milstein-Verfahren, erreicht werden. Mit dem Quasi-Monte-Carlo-Verfahren lässen sich auch komplizierte Optionen bewerten,
wie z.B. Bermuda-Optionen, Barrier-Optionen, Cap-Optionen, Shout-Optionen, Lokkback-Optionen, Multi-Asset-Optionen, Outperformance-Optionen, und auch mit weiteren Bewertungs-Modellen kombinieren, wie z.B. dem Black-Scholes-Modell mit variabler Verzinsung, Black-Scholes-Modell mit zeitabhängiger Volatilität, Heston-Modell für stochastische Volatilität, Merton-Sprung-Diffusion-Modell und dem Libor-Markt Modell für Zinsderivate, auf die ich in dieser Bachelorarbeit nicht mehr eingehen werde, mit denen ich mich jedoch in der Masterarbeit genauer beschäftigen werde.
Finanzderivate sind Produkte, die eine Möglichkeit bieten sich gegen künftige Preisschwankungen abzusichern oder auf eine zukünftige Preisentwicklung zu spekulieren. Die wichtigsten Arten von Finanzderivaten sind Optionen, Futures, Forwards und Swaps. Gegenstand vorliegender Bachelorarbeit werden ausschließlich Optionen sein. Auf den internationalen Finanzmärkten werden verschiedene Typen von Optionen gehandelt, weshalb sich die Frage des "fairen Preises" eines solchen Produktes stellt. Für viele gehandelte Optionen gibt es keine geschlossene Lösung zur Bestimmung des Preises, deshalb werden für diese numerische Verfahren zur Berechnung angewandt. Dabei muss beachtet werden, dass der Optionswert möglichst genau ist, jedoch sollte der Aufwand dabei ziemlich gering sein.
Ziel dieser Arbeit ist die Bestimmung eines numerischen Verfahrens, mit dem man europäische und amerikanische Multiasset-Optionen bewerten kann. Dieses Verfahren soll eine Erweiterung des bekannten Binomialverfahrens sein. Im Fokus steht dabei das Binomialverfahren, da es durch die Einschränkung auf zwei Entwicklungsmöglichkeiten in der Anwendung einfacher ist als das Black-Scholes-Modell. Dieses Verfahren ist nur für europäische und amerikanische Standard-Optionen definiert. Bei der Erweiterung muss beachtet werden, dass Multiasset-Optionen von mehreren Wertpapieren abhängen. In der Arbeit wird ein Produktbinomialverfahren entwickelt, das die Anzahl der Wertpapiere in der Dimension der entstehenden Bäume berücksichtigt. Dieses Verfahren konvergiert gegen das mehrdimensionale Black-Scholes-Modell und ist zu dessen graphischer Darstellung geeignet. Es wird jedoch auch gezeigt, dass dieses dem Fluch der Dimension unterliegt und somit der Aufwand für einen möglichst genauen Optionswert ziemlich hoch ist. Die Erweiterung dieses Verfahrens durch Dünne Gitter erzielt eine Optimierung der Laufzeit. Da der Fokus dieser Bachelorarbeit jedoch auf dem Produktbinomialverfahren liegt, wird im Folgenden auf diese Erweiterung nicht eingegangen.
We consider a class of nonautonomous nonlinear competitive parabolic systems on bounded radial domains under Neumann or Dirichlet boundary conditions. We show that, if the initial profiles satisfy a reflection inequality with respect to a hyperplane, then bounded positive solutions are asymptotically (in time) foliated Schwarz symmetric with respect to antipodal points. Additionally, a related result for (positive and sign changing solutions) of scalar equations with Neumann or Dirichlet boundary conditions is given. The asymptotic shape of solutions to cooperative systems is also discussed.
A multiple filter test for the detection of rate changes in renewal processes with varying variance
(2014)
The thesis provides novel procedures in the statistical field of change point detection in time series.
Motivated by a variety of neuronal spike train patterns, a broad stochastic point process model is introduced. This model features points in time (change points), where the associated event rate changes. For purposes of change point detection, filtered derivative processes (MOSUM) are studied. Functional limit theorems for the filtered derivative processes are derived. These results are used to support novel procedures for change point detection; in particular, multiple filters (bandwidths) are applied simultaneously in oder to detect change points in different time scales.
Wie können Optionen bewertet werden, zu denen keine geschlossenen Lösungen existieren? Die Antwort lautet: Numerische Verfahren. In Hinblick auf diese Frage wurden in der Vergangenheit meist Baumverfahren, Finite-Differenzen- oder Monte-Carlo-Methoden herangezogen. Im Gegensatz dazu behandelt diese Bachelorarbeit den Einsatz von Quadraturverfahren (QUAD) bei der Bewertung von exotischen Optionen, also Optionen, die kompliziertere Auszahlungsstrukturen besitzen wie einfache Standard-Optionen. Die Grundidee besteht darin, den Optionswert als mehrdimensionales Integral in eindimensionale Integrale zu zerlegen, die daraufhin durch Quadraturformeln approximiert werden...Die Genauigkeit des Verfahrens wird erhöht, indem die Schrittweite der Quadraturformel h verkleinert wird. Dies hat allerdings zur Folge, dass sich der Rechenaufwand erhöht. QUAD jedoch schafft es, durch Reduzierung der Dimension und Ausnutzung der herausragenden Konvergenzeigenschaften von Quadraturformeln eine hohe Genauigkeit bei gleichzeitig geringen Rechenkosten zu erreichen.
Die Methode ist allgemein anwendbar und zeigt insbesondere beim Preisen von pfadabhängigen Optionen mit diskreten Zeitpunkten ihre Stärken. Als Anwendungsbeispiele betrachten wir deshalb folgende Optionstypen: Digitale-, Barrier-, Zusammengesetzte-, Bermuda- und Lookback Optionen. Ferner existieren entsprechende Verfahren für Asiatische- oder Amerikanische Optionen, für die jedoch mehr Vorarbeit notwendig ist.
Der große Vorteil von QUAD gegenüber anderen numerischen Verfahren liegt in der Vermeidung eines (bedeutsamen) Verteilungsfehlers und in der Tatsache, dass keine Bedingungen an die Auszahlungsfunktion gestellt werden müssen. Baum- oder Finite-Differenzen-Verfahren reduzieren zwar durch Gitterverfeinerung den Verteilungsfehler, allerdings geht dies Hand in Hand mit deutlich höheren Rechenzeiten. Zum Beispiel benötigt ein Baumverfahren für die doppelte Exaktheit einen vierfachen Rechenaufwand, während die QUAD Methode bei einem vierfachen Rechenaufwand die Exaktheit mit Faktor 16 erhöht (bei Extrapolation steigt dieser Faktor bis 256).
QUAD kann als "der perfekte Baum" angesehen werden, da es ähnlich zu Multinomialbäumen auf Rückwärtsverfahren zurückgreift, andererseits aber die hohe Flexibilität besitzt, Knoten frei und in großer Anzahl zu wählen. Des Weiteren gehen nur die den Optionspreis bestimmenden Zeitpunkte in die Bewertung mit ein, sodass auf zwischenzeitliche Zeitschritte gänzlich verzichtet werden kann.
Die eigentliche Arbeit gliedert sich in sechs Abschnitte. Zunächst erfolgt eine Einführung in allgemeine Quadraturverfahren, exotische Optionen und das Black-Scholes-Modell, was im Anschluss den Übergang zum Lösungsansatz liefert. Dieser Abschnitt schließt mit einer geschlossenen Integrallösung für Optionen, die der Black-Scholes-Differentialgleichung folgen, ab. In Abschnitt 4 wird die genaue Untersuchung der QUAD Methode vorgenommen. Unter Verwendung des in Abschnitt 5 vorgestellten Algorithmus wird anschließend in Abschnitt 6 die QUAD Methode auf die zuvor genannten Optionsklassen angewandt. Die entsprechenden Resultate werden am Ende dieses Teils in Tabellen und Graphiken präsentiert. Den Abschluss bildet das Fazit und die Zusammenfassung der Ergebnisse.
Sprung-Diffusions-Modelle zur Bewertung Europäischer Optionen, BacIn dieser Arbeit wurden die Europäische Optionen in den Sprung-Diffusions-Modellen von Merton und dem Modell von Kou bewertet. So stellen die geschlossenen Lösungen für das Merton-Modell als Anwendung der Black-Scholes-Formel eine einfache Möglichkeit zur Berechnung eines Optionspreises dar. Die Verwendung einer analytischen Lösung für Merton ist allerdings nur eingeschränkt, d.h. für zwei spezielle Sprungverteilungsfunktionen (Plötzlicher Ruin und die Lognormalverteilung) möglich. Das Kou-Modell hingegen, hat eine geschlossene Lösung für Doppel-Exponentialverteilte Sprünge. Eine flexible Lösungsmöglichkeit zur Bestimmung eines Optionspreises ist die Verwendung des Monte-Carlo-Verfahrens für die Simulation der Kursbewegung mit zugrunde liegendem Sprung-Diffusions-Modell. In diesem Fall ist das Monte-Carlo-Verfahren zur Ermittlung des Optionspreises nur einmal anzuwenden. Dieses Verfahren konvergiert mit einer Konvergenzrate von 1/2.
Wie alle anderen Modelle, die auf Lévy Prozessen basieren, lässt das Kou-Modell eine empirische Beobachtung vermissen, nämlich die mögliche Abhängigkeit zwischen Renditen der Underlyings (der sogenannte "volatility clustering affect"), weil das Modell unabhängige Inkremente unterstellt. Eine Möglichkeit die Abhängigkeit mit einzubeziehen, wäre die Nutzung anderer Punktprozesse Ñ(t) mit abhängigen Inkrementen anstelle des Poisson-Prozesses N(t). Es muss natürlich die Unabhängikeit zwischen der Brownschen Bewegung, den Sprunghöhen und ~N(t) beibehalten werden. Das so modifizierte Modell hat keine unabhängigen Inkremente mehr, ist aber einfach die geschlossene Lösungsformel für Call- und Put-Optionen zu erhalten. Andererseits scheint es schwer analytische Lösungen für Pfadabhängige Optionen durch Nutzung von Ñ(t) anstelle von N(t) zu erhalten.
The work presented in this thesis is devoted to two classes of mathematical population genetics models, namely the Kingman-coalescent and the Beta-coalescents. Chapters 2, 3 and 4 of the thesis include results concerned with the first model, whereas Chapter 5 presents contributions to the second class of models.
The objective of this paper is the study of the equilibrium behavior of a population on the hierarchical group ΩN consisting of families of individuals undergoing critical branching random walk and in addition these families also develop according to a critical branching process. Strong transience of the random walk guarantees existence of an equilibrium for this two-level branching system. In the limit N→∞ (called the hierarchical mean field limit), the equilibrium aggregated populations in a nested sequence of balls B(N)ℓ of hierarchical radius ℓ converge to a backward Markov chain on R+. This limiting Markov chain can be explicitly represented in terms of a cascade of subordinators which in turn makes possible a description of the genealogy of the population.
We determine that the continuous-state branching processes for which the genealogy, suitably time-changed, can be described by an autonomous Markov process are precisely those arising from $\alpha$-stable branching mechanisms. The random ancestral partition is then a time-changed $\Lambda$-coalescent, where $\Lambda$ is the Beta-distribution with parameters $2-\alpha$ and $\alpha$, and the time change is given by $Z^{1-\alpha}$, where $Z$ is the total population size. For $\alpha = 2$ (Feller's branching diffusion) and $\Lambda = \delta_0$ (Kingman's coalescent), this is in the spirit of (a non-spatial version of) Perkins' Disintegration Theorem. For $\alpha =1$ and $\Lambda$ the uniform distribution on $[0,1]$, this is the duality discovered by Bertoin & Le Gall (2000) between the norming of Neveu's continuous state branching process and the Bolthausen-Sznitman coalescent.
We present two approaches: one, exploiting the `modified lookdown construction', draws heavily on Donnelly & Kurtz (1999); the other is based on direct calculations with generators.
In this paper we prove asymptotic normality of the total length of external branches in Kingman's coalescent. The proof uses an embedded Markov chain, which can be described as follows: Take an urn with n black balls. Empty it in n steps according to the rule: In each step remove a randomly chosen pair of balls and replace it by one red ball. Finally remove the last remaining ball. Then the numbers Uk, 0 < k < n, of red balls after k steps exhibit an unexpected property: (U0, ... ,Un) and (Un, ... ;U0) are equal in distribution.
The random split tree introduced by Devroye (1999) is considered. We derive a second order expansion for the mean of its internal path length and furthermore obtain a limit law by the contraction method. As an assumption we need the splitter having a Lebesgue density and mass in every neighborhood of 1. We use properly stopped homogeneous Markov chains, for which limit results in total variation distance as well as renewal theory are used. Furthermore, we extend this method to obtain the corresponding results for the Wiener index.
ranching Processes in Random Environment (BPREs) $(Z_n:n\geq0)$ are the generalization of Galton-Watson processes where \lq in each generation' the reproduction law is picked randomly in an i.i.d. manner. The associated random walk of the environment has increments distributed like the logarithmic mean of the offspring distributions. This random walk plays a key role in the asymptotic behavior. In this paper, we study the upper large deviations of the BPRE $Z$ when the reproduction law may have heavy tails. More precisely, we obtain an expression for the limit of $-\log \mathbb{P}(Z_n\geq \exp(\theta n))/n$ when $n\rightarrow \infty$. It depends on the rate function of the associated random walk of the environment, the logarithmic cost of survival $\gamma:=-\lim_{n\rightarrow\infty} \log \mathbb{P}(Z_n>0)/n$ and the polynomial rate of decay $\beta$ of the tail distribution of $Z_1$. This rate function can be interpreted as the optimal way to reach a given "large" value. We then compute the rate function when the reproduction law does not have heavy tails. Our results generalize the results of B\"oinghoff $\&$ Kersting (2009) and Bansaye $\&$ Berestycki (2008) for upper large deviations. Finally, we derive the upper large deviations for the Galton-Watson processes with heavy tails.
In this article, we illustrate the flexibility of the algebraic integration formalism introduced in M. Gubinelli (2004), Controlling Rough Paths, J. Funct. Anal. 216, 86-140, by establishing an existence and uniqueness result for delay equations driven by rough paths. We then apply our results to the case where the driving path is a fractional Brownian motion with Hurst parameter H > 1/3.
We consider catalytic branching random walk (the reactant) where the state space is a countable Abelean group. The branching is critical binary and the local branching rate is given by a catalytic medium. Here the medium is itself an autonomous (ordinary) branching random walk (the catalyst) - maybe with a different motion law. For persistent catalyst (transient motion) the reactant shows the usual dichotomy of persistence versus extinction depending on transience or recurrence of its motion. If the catalyst goes to local extinction it turns out that the longtime behaviour of the reactant ranges (depending on its motion) from local extinction to free random walk with either deterministic or random global intensity of particles.
It is possible to represent each of a number of Markov chains as an evolving sequence of connected subsets of a directed acyclic graph that grow in the following way: initially, all vertices of the graph are unoccupied, particles are fed in one-by-one at a distinguished source vertex, successive particles proceed along directed edges according to an appropriate stochastic mechanism, and each particle comes to rest once it encounters an unoccupied vertex. Examples include the binary and digital search tree processes, the random recursive tree process and generalizations of it arising from nested instances of Pitman's two-parameter Chinese restaurant process, tree-growth models associated with Mallows' ϕ model of random permutations and with Schützenberger's non-commutative q-binomial theorem, and a construction due to Luczak and Winkler that grows uniform random binary trees in a Markovian manner. We introduce a framework that encompasses such Markov chains, and we characterize their asymptotic behavior by analyzing in detail their Doob-Martin compactifications, Poisson boundaries and tail σ-fields.
We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to c⋅nα are chosen, where 0<α≤12, c>0 and n is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as n→∞, which depends on α. The proof relies on a contraction argument for probability distributions on càdlàg functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties.
We study the price-setting problem of market makers under perfect competition in continuous time. Thereby we follow the classic Glosten-Milgrom model that defines bid and ask prices as the expectation of a true value of the asset given the market makers partial information that includes the customers trading decisions. The true value is modeled as a Markov process that can be observed by the customers with some noise at Poisson times.
We analyze the price-setting problem by solving a non-standard filtering problem with an endogenous filtration that depends on the bid and ask price process quoted by the market maker. Under some conditions we show existence and uniqueness of the price processes. In a different setting we construct a counterexample to uniqueness. Further, we discuss the behavior of the spread by a convergence result and simulations.
In this thesis, the asymptotic behaviour of Pólya urn models is analyzed, using an approach based on the contraction method. For this, a combinatorial discrete time embedding of the evolution of the composition of the urn into random rooted trees is used. The recursive structure of the trees is used to study the asymptotic behavior using ideas from the contraction method.
The approach is applied to a couple of concrete Pólya urns that lead to limit laws with normal distributions, with non-normal limit distributions, or with asymptotic periodic distributional behavior.
Finally, an approach more in the spirit of earlier applications of the contraction method is discussed for one of the examples. A general transfer theorem of the contraction method is extended to cover this example, leading to conditions on the coefficients of the recursion that are not only weaker but also in general easier to check.
Im Rahmen dieser Arbeit wird der aktuelle Stand auf dem Gebiet des Lokalen Lovász Lemmas (LLL) beschrieben und ein Überblick über die Arbeiten zu konstruktiven Beweisen und Anwendungen gegeben. Ausgehend von Jószef Becks Arbeit zu einer algorithmischen Herangehensweise, haben sich in den letzten Jahren im Umfeld von Moser und Tardos und ihren Arbeiten zu einem konstruktiven Beweis des LLL eine erneute starke Beschäftigung mit dem Thema und eine Fülle von Verbesserungen entwickelt.
In Kapitel 1 wird als Motivation eine kurze Einführung in die probabilistische Methode gegeben. Mit der First- und Second Moment Method werden zwei einfache Vorgehensweisen vorgestellt, die die Grundidee dieses Beweisprinzips klar werden lassen. Von Paul Erdős eröffnet, beschreibt es Wege, Existenzbeweise in nicht-stochastischen Teilgebieten der Mathematik mithilfe stochastischer Überlegungen zu führen. Das Lokale Lemma als eine solche Überlegung entstammt dieser Idee.
In Kapitel 2 werden verschiedene Formen des LLL vorgestellt und bewiesen, außerdem wird anhand einiger Anwendungsbeispiele die Vorgehensweise bei der Verwendung des LLL veranschaulicht.
In Kapitel 3 werden algorithmische Herangehensweisen beschrieben, die geeignet sind, von der (mithilfe des LLL gezeigten) Existenz gewisser Objekte zur tatsächlichen Konstruktion derselben zu gelangen.
In Kapitel 4 wird anhand von Beispielen aus dem reichen Schatz neuerer Veröffentlichungen gezeigt, welche Bewegung nach der Arbeit von Moser und Tardos entstanden ist. Dabei beleuchtet die Arbeit nicht nur einen anwendungsorientierten Beitrag von Haeupler, Saha und Srinivasan, sondern auch einen Beitrag Terence Taos, der die Beweistechnik Mosers aus einem anderen Blickwinkel beleuchtet.
The relation between the complexity of a time-switched dynamics and the complexity of its control sequence depends critically on the concept of a non-autonomous pullback attractor. For instance, the switched dynamics associated with scalar dissipative affine maps has a pullback attractor consisting of singleton component sets. This entails that the complexity of the control sequence and switched dynamics, as quantified by the topological entropy, coincide. In this paper we extend the previous framework to pullback attractors with nontrivial components sets in order to gain further insights in that relation. This calls, in particular, for distinguishing two distinct contributions to the complexity of the switched dynamics. One proceeds from trajectory segments connecting different component sets of the attractor; the other contribution proceeds from trajectory segments within the component sets. We call them “macroscopic” and “microscopic” complexity, respectively, because only the first one can be measured by our analytical tools. As a result of this picture, we obtain sufficient conditions for a switching system to be more complex than its unswitched subsystems, i.e., a complexity analogue of Parrondo’s paradox.
Neuronal activity in the brain is often investigated in the presence of stimuli, termed externally driven activity. This stimulus-response-perspective has long been focussed on in order to find out how the nervous system responds to different stimuli. The neuronal response consists of baseline activity, so called spontaneous activity1, and activity which is caused by the stimulus. The baseline activity is often considered as constant over time which allows the identification of the stimulus-evoked part of the neuronal response by averaging over a set of trials.
However, during the last years it has been recognized that own dynamics of the nervous system plays an important role in information processing. As a consequence, spontaneous activity is no longer regarded only as background ’noise’ and its role in cortical processing is reconsidered. Therefore, the study of spontaneous firing pattern gains more importance as these patterns may shape neuronal responses to a larger extent as previously thought. For example, recent findings suggest that prestimulus activity can predict a person’s visual perception performance on a single trial basis (Hanslmayr et al., 2007). In this context, Ringach (2009) remarks that one can learn much about even the quiescent state of the brain which “underlies the importance of understanding cortical responses as the fusion of ongoing activity and sensory input”.
Taking into account that spontaneous activity reflects anything else but noise, new challenges arise when analysing neuronal data. In this thesis one of these problems related to the analysis of neuronal activity will be adressed, namely the nonstationarity of firing rates.
The present work consists of four chapters. First of all the introduction gives neurophysiological background information to get an idea of neuronal information processing. Afterwords the theory of point processes is provided which forms the basis for modeling neuronal spiking data. In the last section of the introduction a statement of the problem is given. Chapter 2 proposes an easily applicable statistical method for the detection of nonstationarity. It is applied to simulations and to real data in order to show its capabilities. Thereafter, four other approaches are presented which provide useful illustrations concerning the nonstationarity of the firing rate but share the problem that one cannot make objective statements on the basis of their results. They were developed in the course of establishing a suitable method. In chapter 4 the results are discussed and suggestions for further study are given.
A stochastic model for the joint evaluation of burstiness and regularity in oscillatory spike trains
(2013)
The thesis provides a stochastic model to quantify and classify neuronal firing patterns of oscillatory spike trains. A spike train is a finite sequence of time points at which a neuron has an electric discharge (spike) which is recorded over a finite time interval. In this work, these spike times are analyzed regarding special firing patterns like the presence or absence of oscillatory activity and clusters (so called bursts). These bursts do not have a clear and unique definition in the literature. They are often fired in response to behaviorally relevant stimuli, e.g., an unexpected reward or a novel stimulus, but may also appear spontaneously. Oscillatory activity has been found to be related to complex information processing such as feature binding or figure ground segregation in the visual cortex. Thus, in the context of neurophysiology, it is important to quantify and classify these firing patterns and their change under certain experimental conditions like pharmacological treatment or genetical manipulation. In neuroscientific practice, the classification is often done by visual inspection criteria without giving reproducible results. Furthermore, descriptive methods are used for the quantification of spike trains without relating the extracted measures to properties of the underlying processes.
For that reason, a doubly stochastic point process model is proposed and termed 'Gaussian Locking to a free Oscillator' - GLO. The model has been developed on the basis of empirical observations in dopaminergic neurons and in cooperation with neurophysiologists. The GLO model uses as a first stage an unobservable oscillatory background rhythm which is represented by a stationary random walk whose increments are normally distributed. Two different model types are used to describe single spike firing or clusters of spikes. For both model types, the distribution of the random number of spikes per beat has different probability distributions (Bernoulli in the single spike case or Poisson in the cluster case). In the second stage, the random spike times are placed around their birth beat according to a normal distribution. These spike times represent the observed point process which has five easily interpretable parameters to describe the regularity and the burstiness of the firing patterns.
It turns out that the point process is stationary, simple and ergodic. It can be characterized as a cluster process and for the bursty firing mode as a Cox process. Furthermore, the distribution of the waiting times between spikes can be derived for some parameter combination. The conditional intensity function of the point process is derived which is also called autocorrelation function (ACF) in the neuroscience literature. This function arises by conditioning on a spike at time zero and measures the intensity of spikes x time units later. The autocorrelation histogram (ACH) is an estimate for the ACF. The parameters of the GLO are estimated by fitting the ACF to the ACH with a nonlinear least squares algorithm. This is a common procedure in neuroscientific practice and has the advantage that the GLO ACF can be computed for all parameter combinations and that its properties are closely related to the burstiness and regularity of the process. The precision of estimation is investigated for different scenarios using Monte-Carlo simulations and bootstrap methods.
The GLO provides the neuroscientist with objective and reproducible classification rules for the firing patterns on the basis of the model ACF. These rules are inspired by visual inspection criteria often used in neuroscientific practice and thus support and complement usual analysis of empirical spike trains. When applied to a sample data set, the model is able to detect significant changes in the regularity and burst behavior of the cells and provides confidence intervals for the parameter estimates.
We investigate multivariate Laurent polynomials f \in \C[\mathbf{z}^{\pm 1}] = \C[z_1^{\pm 1},\ldots,z_n^{\pm 1}] with varieties \mathcal{V}(f) restricted to the algebraic torus (\C^*)^n = (\C \setminus \{0\})^n. For such Laurent polynomials f one defines the amoeba \mathcal{A}(f) of f as the image of the variety \mathcal{V}(f) under the \Log-map \Log : (\C^*)^n \to \R^n, (z_1,\ldots,z_n) \mapsto (\log|z_1|, \ldots, \log|z_n|). I.e., the amoeba \mathcal{A}(f) is the projection of the variety \mathcal{V}(f) on its (componentwise logarithmized) absolute values. Amoebas were first defined in 1994 by Gelfand, Kapranov and Zelevinksy. Amoeba theory has been strongly developed since the beginning of the new century. It is related to various mathematical subjects, e.g., complex analysis or real algebraic curves. In particular, amoeba theory can be understood as a natural connection between algebraic and tropical geometry.
In this thesis we investigate the geometry, topology and methods for the approximation of amoebas.
Let \C^A denote the space of all Laurent polynomials with a given, finite support set A \subset \Z^n and coefficients in \C^*. It is well known that, in general, the existence of specific complement components of the amoebas \mathcal{A}(f) for f \in \C^A depends on the choice of coefficients of f. One prominent key problem is to provide bounds on the coefficients in order to guarantee the existence of certain complement components. A second key problem is the question whether the set U_\alpha^A \subseteq \C^A of all polynomials whose amoeba has a complement component of order \alpha \in \conv(A) \cap \Z^n is always connected.
We prove such (upper and lower) bounds for multivariate Laurent polynomials supported on a circuit. If the support set A \subset \Z^n satisfies some additional barycentric condition, we can even give an exact description of the particular sets U_\alpha^A and, especially, prove that they are path-connected.
For the univariate case of polynomials supported on a circuit, i.e., trinomials f = z^{s+t} + p z^t + q (with p,q \in \C^*), we show that a couple of classical questions from the late 19th / early 20th century regarding the connection between the coefficients and the roots of trinomials can be traced back to questions in amoeba theory. This yields nice geometrical and topological counterparts for classical algebraic results. We show for example that a trinomial has a root of a certain, given modulus if and only if the coefficient p is located on a particular hypotrochoid curve. Furthermore, there exist two roots with the same modulus if and only if the coefficient p is located on a particular 1-fan. This local description of the configuration space \C^A yields in particular that all sets U_\alpha^A for \alpha \in \{0,1,\ldots,s+t\} \setminus \{t\} are connected but not simply connected.
We show that for a given lattice polytope P the set of all configuration spaces \C^A of amoebas with \conv(A) = P is a boolean lattice with respect to some order relation \sqsubseteq induced by the set theoretic order relation \subseteq. This boolean lattice turns out to have some nice structural properties and gives in particular an independent motivation for Passare's and Rullgard's conjecture about solidness of amoebas of maximally sparse polynomials. We prove this conjecture for special instances of support sets.
A further key problem in the theory of amoebas is the description of their boundaries. Obviously, every boundary point \mathbf{w} \in \partial \mathcal{A}(f) is the image of a critical point under the \Log-map (where \mathcal{V}(f) is supposed to be non-singular here). Mikhalkin showed that this is equivalent to the fact that there exists a point in the intersection of the variety \mathcal{V}(f) and the fiber \F_{\mathbf{w}} of \mathbf{w} (w.r.t. the \Log-map), which has a (projective) real image under the logarithmic Gauss map. We strengthen this result by showing that a point \mathbf{w} may only be contained in the boundary of \mathcal{A}(f), if every point in the intersection of \mathcal{V}(f) and \F_{\mathbf{w}} has a (projective) real image under the logarithmic Gauss map.
With respect to the approximation of amoebas one is in particular interested in deciding membership, i.e., whether a given point \mathbf{w} \in \R^n is contained in a given amoeba \mathcal{A}(f). We show that this problem can be traced back to a semidefinite optimization problem (SDP), basically via usage of the Real Nullstellensatz. This SDP can be implemented and solved with standard software (we use SOSTools and SeDuMi here). As main theoretic result we show that, from the complexity point of view, our approach is at least as good as Purbhoo's approximation process (which is state of the art).