Mathematik
Refine
Year of publication
Document Type
- Article (84)
- Preprint (47)
- Doctoral Thesis (46)
- Report (16)
- Conference Proceeding (9)
- diplomthesis (6)
- Book (3)
- Part of a Book (2)
- Bachelor Thesis (1)
- Diploma Thesis (1)
- Master's Thesis (1)
Language
- English (216) (remove)
Has Fulltext
- yes (216) (remove)
Is part of the Bibliography
- no (216)
Keywords
- Kongress (6)
- Kryptologie (5)
- Online-Publikation (4)
- LLL-reduction (3)
- Moran model (3)
- computational complexity (3)
- contraction method (3)
- Algebraische Geometrie (2)
- Brownian motion (2)
- Commitment Scheme (2)
Institute
- Mathematik (216)
- Informatik (50)
- Medizin (2)
- Frankfurt Institute for Advanced Studies (FIAS) (1)
- MPI für Hirnforschung (1)
- MPI für empirische Ästhetik (1)
- Physik (1)
In the model of randomly perturbed graphs we consider the union of a deterministic graph G with minimum degree αn and the binomial random graph G(n, p). This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac’s theorem and the results by Pósa and Korshunov on the threshold in G(n, p). In this note we extend this result in G ∪G(n, p) to sparser graphs with α = o(1). More precisely, for any ε > 0 and α: N ↦→ (0, 1) we show that a.a.s. G ∪ G(n, β/n) is Hamiltonian, where β = −(6 + ε) log(α). If α > 0 is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if α = O(1/n) the random part G(n, p) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into G(n, p).
For a class of Cannings models we prove Haldane’s formula, π(sN)∼2sNρ2, for the fixation probability of a single beneficial mutant in the limit of large population size N and in the regime of moderately strong selection, i.e. for sN∼N−b and 0<b<1/2. Here, sN is the selective advantage of an individual carrying the beneficial type, and ρ2 is the (asymptotic) offspring variance. Our assumptions on the reproduction mechanism allow for a coupling of the beneficial allele’s frequency process with slightly supercritical Galton–Watson processes in the early phase of fixation.
The problem of unconstrained or constrained optimization occurs in many branches of mathematics and various fields of application. It is, however, an NP-hard problem in general. In this thesis, we examine an approximation approach based on the class of SAGE exponentials, which are nonnegative exponential sums. We examine this SAGE-cone, its geometry, and generalizations. The thesis consists of three main parts:
1. In the first part, we focus purely on the cone of sums of globally nonnegative exponential sums with at most one negative term, the SAGE-cone. We ex- amine the duality theory, extreme rays of the cone, and provide two efficient optimization approaches over the SAGE-cone and its dual.
2. In the second part, we introduce and study the so-called S-cone, which pro- vides a uniform framework for SAGE exponentials and SONC polynomials. In particular, we focus on second-order representations of the S-cone and its dual using extremality results from the first part.
3. In the third and last part of this thesis, we turn towards examining the con- ditional SAGE-cone. We develop a notion of sublinear circuits leading to new duality results and a partial characterization of extremality. In the case of poly- hedral constraint sets, this examination is simplified and allows us to classify sublinear circuits and extremality for some cases completely. For constraint sets with certain conditions such as sets with symmetries, conic, or polyhedral sets, various optimization and representation results from the unconstrained setting can be applied to the constrained case.
The aim of this bachelor thesis is to compare and empirically test the use of classification to improve the topic models Latent Dirichlet Allocation (LDA) and Author Topic Modeling
(ATM) in the context of the social media platform Twitter. For this purpose, a corpus was classified with the Dewey Decimal Classification (DDC) and then used to train the topic models. A second dataset, the unclassified corpus, was used for comparison. The assumption that the use of classification could improve the topic models did not prove true for the LDA topic model. Here, a sufficiently good improvement of the models could not be achieved. The ATM model, on the other hand, could be improved by using the classification. In general, the ATM model performed significantly better than the LDA model. In the context of the social media platform Twitter, it can thus be seen that the ATM model is superior to the LDA model and can additionally be improved by classifying the data.
We provide extensions of the dual variational method for the nonlinear Helmholtz equation from Evéquoz and Weth. In particular we prove the existence of dual ground state solutions in the Sobolev critical case, extend the dual method beyond the standard Stein Tomas and Kenig Ruiz Sogge range and generalize the method for sign changing nonlinearities.
We study continuous dually epi-translation invariant valuations on certain cones of convex functions containing the space of finite-valued convex functions. Using the homogeneous decomposition of this space, we associate a certain distribution to any homogeneous valuation similar to the Goodey-Weil embedding for translation invariant valuations on convex bodies. The support of these distributions induces a corresponding notion of support for the underlying valuations, which imposes certain restrictions on these functionals, and we study the relation between the support of a valuation and its domain. This gives a partial answer to the question which dually epi-translation invariant valuations on finite-valued convex functions can be extended to larger cones of convex functions.
We also study topological properties of spaces of valuations with support contained in a fixed compact set. As an application of these results, we introduce the class of smooth valuations on convex functions and show that the subspace of smooth dually epi-translation invariant valuations is dense in the space of continuous dually epi-translation invariant valuation on finite-valued convex functions. These smooth valuations are given by integrating certain smooth differential forms over the graph of the differential of a convex function. We use this construction to give a characterization of a dense subspace of all continuous valuations on finite-valued convex functions that are rotation invariant as well as dually epi-translation invariant.
Using results from Alesker's theory of smooth valuations on convex bodies, we also show that any smooth valuation can be written as a convergent sum of mixed Hessian valuations. In particular, mixed Hessian valuations span a dense subspace, which is a version of McMullen’s conjecture for valuations on convex functions.
In this paper we deal with an implementation as well as numerical experiments for the coupling of interior and exterior problems of the elastodynamic wave equation with transparent boundary conditions in 3D as described in a previous paper by this author. In more detail, the FEM‐BEM‐coupling as well as the time discretization by using leapfrog and convolution quadrature is considered. Our aim is to provide an insight into the necessary steps of the implementation. Based on this, we present numerical experiments for a non‐convex domain and analyze the errors.
We contribute to the foundations of tropical geometry with a view toward formulating tropical moduli problems, and with the moduli space of curves as our main example. We propose a moduli functor for the moduli space of curves and show that it is representable by a geometric stack over the category of rational polyhedral cones. In this framework, the natural forgetful morphisms between moduli spaces of curves with marked points function as universal curves.
Our approach to tropical geometry permits tropical moduli problems—moduli of curves or otherwise—to be extended to logarithmic schemes. We use this to construct a smooth tropicalization morphism from the moduli space of algebraic curves to the moduli space of tropical curves, and we show that this morphism commutes with all of the tautological morphisms.
The specific temporal evolution of bacterial and phage population sizes, in particular bacterial depletion and the emergence of a resistant bacterial population, can be seen as a kinetic fingerprint that depends on the manifold interactions of the specific phage–host pair during the course of infection. We have elaborated such a kinetic fingerprint for a human urinary tract Klebsiella pneumoniae isolate and its phage vB_KpnP_Lessing by a modeling approach based on data from in vitro co-culture. We found a faster depletion of the initially sensitive bacterial population than expected from simple mass action kinetics. A possible explanation for the rapid decline of the bacterial population is a synergistic interaction of phages which can be a favorable feature for phage therapies. In addition to this interaction characteristic, analysis of the kinetic fingerprint of this bacteria and phage combination revealed several relevant aspects of their population dynamics: A reduction of the bacterial concentration can be achieved only at high multiplicity of infection whereas bacterial extinction is hardly accomplished. Furthermore the binding affinity of the phage to bacteria is identified as one of the most crucial parameters for the reduction of the bacterial population size. Thus, kinetic fingerprinting can be used to infer phage–host interactions and to explore emergent dynamics which facilitates a rational design of phage therapies.
In vivo functional diversity of midbrain dopamine neurons within identified axonal projections
(2019)
Functional diversity of midbrain dopamine (DA) neurons ranges across multiple scales, from differences in intrinsic properties and connectivity to selective task engagement in behaving animals. Distinct in vitro biophysical features of DA neurons have been associated with different axonal projection targets. However, it is unknown how this translates to different firing patterns of projection-defined DA subpopulations in the intact brain. We combined retrograde tracing with single-unit recording and labelling in mouse brain to create an in vivo functional topography of the midbrain DA system. We identified differences in burst firing among DA neurons projecting to dorsolateral striatum. Bursting also differentiated DA neurons in the medial substantia nigra (SN) projecting either to dorsal or ventral striatum. We found differences in mean firing rates and pause durations among ventral tegmental area (VTA) DA neurons projecting to lateral or medial shell of nucleus accumbens. Our data establishes a high-resolution functional in vivo landscape of midbrain DA neurons.
We study empirically and analytically growth and fluctuation of firm size distribution. An empirical analysis is carried out on a US data set on firm size, with emphasis on one-time distribution as well as growth-rate probability distribution. Both Pareto's law and Gibrat's law are often used to study firm size distribution. Their theoretical relationship is discussed, and it is shown how they are complementable with a bimodal distribution of firm size. We introduce economic mechanisms that suggest a bimodal distribution of firm size in the long run. The mechanisms we study have been known in the economic literature since long. Yet, they have not been studied in the context of a dynamic decision problem of the firm. Allowing for these mechanism thus will give rise to heterogeneity of firms with respect to certain characteristics. We then present different types of tests on US data on firm size which indicate a bimodal distribution of firm size.
Strong convergence rates for numerical approximations of stochastic partial differential equations
(2018)
In this thesis and in the research articles which this thesis consists of, respectively, we focus on strong convergence rates for numerical approximations of stochastic partial differential equations (SPDEs). In Part I of this thesis, i.e., Chapter 2 and Chapter 3, we study higher order numerical schemes for SPDEs with multiplicative trace class noise based on suitable Taylor expansions of the Lipschitz continuous coefficients of the SPDEs under consideration. More precisely, Chapter 2 proves strong convergence rates for a linear implicit Euler-Milstein scheme for SPDEs and is based on an unpublished manuscript written by the author of this thesis. This chapter extends an earlier result1 by slightly lowering the assumptions posed on the diffusion coefficient and a different approximation of the semigroup. In Chapter 3 we introduce an exponential Wagner-Platen type numerical scheme for SPDEs and prove that this numerical approximation method converges in the strong sense with oder up to 3/2−. Moreover, we illustrate how the (mixed) iterated stochastic-deterministic integrals, that are part of our numerical scheme, can be simulated exactly under suitable assumptions.
The second part of this thesis, i.e. Chapter 4 and Chapter 5, is devoted to strong convergence rates for numerical approximations of SPDEs with superlinearly growing nonlinearities driven by additive space-time white noise. More specifically, in Chapter 4, we prove strong convergence with rate in the time variable for a class of nonlinearity-truncated numerical approximation schemes for SPDEs and provide examples that fit into our abstract setting like stochastic Allen-Cahn equations. Finally, in Chapter 5, we extend this result with spatial approximations and establish strong convergence rates for a class of full-discrete nonlinearity truncated numerical approximation schemes for SPDEs. Moreover, we apply our strong convergence result to stochastic Allen-Cahn equations and provide lower and upper bounds which show that our strong convergence result can, in general, not essentially be improved.
To crack the neural code and read out the information neural spikes convey, it is essential to understand how the information is coded and how much of it is available for decoding. To this end, it is indispensable to derive from first principles a minimal set of spike features containing the complete information content of a neuron. Here we present such a complete set of coding features. We show that temporal pairwise spike correlations fully determine the information conveyed by a single spiking neuron with finite temporal memory and stationary spike statistics. We reveal that interspike interval temporal correlations, which are often neglected, can significantly change the total information. Our findings provide a conceptual link between numerous disparate observations and recommend shifting the focus of future studies from addressing firing rates to addressing pairwise spike correlation functions as the primary determinants of neural information.
In 1957, Craig Mooney published a set of human face stimuli to study perceptual closure: the formation of a coherent percept on the basis of minimal visual information. Images of this type, now known as “Mooney faces”, are widely used in cognitive psychology and neuroscience because they offer a means of inducing variable perception with constant visuo-spatial characteristics (they are often not perceived as faces if viewed upside down). Mooney’s original set of 40 stimuli has been employed in several studies. However, it is often necessary to use a much larger stimulus set. We created a new set of over 500 Mooney faces and tested them on a cohort of human observers. We present the results of our tests here, and make the stimuli freely available via the internet. Our test results can be used to select subsets of the stimuli that are most suited for a given experimental purpose.
Motivation: The topic of this paper is the estimation of alignments and mutation rates based on stochastic sequence-evolution models that allow insertions and deletions of subsequences ("fragments") and not just single bases. The model we propose is a variant of a model introduced by Thorne, Kishino, and Felsenstein (1992). The computational tractability of the model depends on certain restrictions in the insertion/deletion process; possible effects we discuss.
Results: The process of fragment insertion and deletion in the sequence-evolution model induces a hidden Markov structure at the level of alignments and thus makes possible efficient statistical alignment algorithms. As an example we apply a sampling procedure to assess the variability in alignment and mutation parameter estimates for HVR1 sequences of human and orangutan, improving results of previous work. Simulation studies give evidence that estimation methods based on the proposed model also give satisfactory results when applied to data for which the restrictions in the insertion/deletion process do not hold.
Availability: The source code of the software for sampling alignments and mutation rates for a pair of DNA sequences according to the fragment insertion and deletion model is freely available from www.math.uni-frankfurt.de/~stoch/software/mcmcsalut under the terms of the GNU public license (GPL, 2000).
Viewing of ambiguous stimuli can lead to bistable perception alternating between the possible percepts. During continuous presentation of ambiguous stimuli, percept changes occur as single events, whereas during intermittent presentation of ambiguous stimuli, percept changes occur at more or less regular intervals either as single events or bursts. Response patterns can be highly variable and have been reported to show systematic differences between patients with schizophrenia and healthy controls. Existing models of bistable perception often use detailed assumptions and large parameter sets which make parameter estimation challenging. Here we propose a parsimonious stochastic model that provides a link between empirical data analysis of the observed response patterns and detailed models of underlying neuronal processes. Firstly, we use a Hidden Markov Model (HMM) for the times between percept changes, which assumes one single state in continuous presentation and a stable and an unstable state in intermittent presentation. The HMM captures the observed differences between patients with schizophrenia and healthy controls, but remains descriptive. Therefore, we secondly propose a hierarchical Brownian model (HBM), which produces similar response patterns but also provides a relation to potential underlying mechanisms. The main idea is that neuronal activity is described as an activity difference between two competing neuronal populations reflected in Brownian motions with drift. This differential activity generates switching between the two conflicting percepts and between stable and unstable states with similar mechanisms on different neuronal levels. With only a small number of parameters, the HBM can be fitted closely to a high variety of response patterns and captures group differences between healthy controls and patients with schizophrenia. At the same time, it provides a link to mechanistic models of bistable perception, linking the group differences to potential underlying mechanisms.
Thought structures of modelling task solutions and their connection to the level of difficulty
(2015)
Although efforts have been made to integrate the concept of mathematical modelling in school, among others PISA and TIMSS revealed weaknesses of not only German students in the field of mathematical modelling. There may be various reasons starting from educational policy via curricular issues to practical instructional concerns. Studies show that mathematical modelling has not been arrived yet in everyday school class (Blum &BorromeoFerri, 2009, p. 47). Thus, the proportion of mathematical modelling in everyday school classes is low (Jordan et al., 2006). When focusing on the teachers’ point of view there are difficulties which may contribute to avoid modelling tasks in class. The development of reasonable modelling tasks, estimating the task space, valuating the task difficulty and assessing the student solutions are difficulties which occur to an increasing degree compared to ordinary mathematics tasks.The project MokiMaS (transl.: modeling competency in math classes of secondary education) aims at providing inter-year modelling tasks, whose task space and level of difficulty is known, together with an evaluation scheme. In particular a theory based method has been developed to determine the level of difficulty of modelling tasks on the basis of thought structures, representing the cognitive load of solution approaches. The current question is whether this method leads to a realistic rating. To go further into that question an evaluation scheme has been developed which is guided by the daily assessment work of teachers, to investigate the relation of task difficulty and student performance.
Bipartite graphs occur in many parts of mathematics, and their embeddings into orientable compact surfaces are an old subject. A new interest comes from the fact that these embeddings give dessins d’enfants providing the surface with a unique structure as a Riemann surface and algebraic curve. In this paper, we study the (surprisingly many different) dessins coming from the graphs of finite cyclic projective planes. It turns out that all reasonable questions about these dessins — uniformity, regularity, automorphism groups, cartographic groups, defining equations of the algebraic curves, their fields of definition, Galois actions — depend on cyclic orderings of difference sets for the projective planes. We explain the interplay between number theoretic problems concerning these cyclic ordered difference sets and topological properties of the dessin like e.g. the Wada property that every vertex lies on the border of every cell.
The purpose of the present paper is to explain the fake projective plane constructed by J. H. Keum from the point of view of arithmetic ball quotients. Beside the ball quotient associated with the fake projective plane, we also analize two further naturally related ball quotients whose minimal desingularizations lead to two elliptic surfaces, one already considered by J. H. Keum as well as the one constructed by M. N. Ishida in terms of p-adic uniformization.
2000 Mathematics Subject Classification: 11F23,14J25,14J27
Can variances of latent variables be scaled in such a way that they correspond to eigenvalues?
(2017)
The paper reports an investigation of whether sums of squared factor loadings obtained in confirmatory factor analysis correspond to eigenvalues of exploratory factor analysis. The sum of squared factor loadings reflects the variance of the corresponding latent variable if the variance parameter of the confirmatory factor model is set equal to one. Hence, the computation of the sum implies a specific type of scaling of the variance. While the investigation of the theoretical foundations suggested the expected correspondence between sums of squared factor loadings and eigenvalues, the necessity of procedural specifications in the application, as for example the estimation method, revealed external influences on the outcome. A simulation study was conducted that demonstrated the possibility of exact correspondence if the same estimation method was applied. However, in the majority of realized specifications the estimates showed similar sizes but no correspondence.
In this paper, a translation of the visual description technique HyCharts to Hybrid Data-Flow Graphs (HDFG) is given. While HyCharts combine a data-flow and a control-flow oriented formalism for the specification of the architecture and the behavior of hybrid systems, HDFG allow the efficient and homogeneous internal representation of hybrid systems in computers and their automatic manipulation. HDFG represent a system as a data-flow network built from a set of fundamental functions.
The translation permits to combine the advantages of the different description techniques: The use of HyCharts for specification supports the abstract and formal interactive specification of hybrid systems, while HDFG permit the tool based optimization of hybrid systems and the synthesis of mixed-signal prototypes.
We study exchangeable coalescent trees and the evolving genealogical trees in models for neutral haploid populations.
We show that every exchangeable infinite coalescent tree can be obtained as the genealogical tree of iid samples from a random marked metric measure space when the marks are added to the metric distances. We apply this representation to generalize the tree-valued Fleming-Viot process to include the case with dust in which the genealogical trees have isolated leaves.
Using the Donnelly-Kurtz lookdown approach, we describe all individuals ever alive in the population model by a random complete and separable metric space, the lookdown space, which we endow with a family of sampling measures. This yields a pathwise construction of tree-valued Fleming-Viot processes. In the case of coming down from infinity, we also read off a process whose state space is endowed with the Gromov-Hausdorff-Prohorov topology. This process has additional jumps at the extinction times of parts of the population.
In the case with only binary reproduction events, we construct the lookdown space also from the Aldous continuum random tree by removing the root and the highest leaf, and by deforming the metric in a way that corresponds to the time change that relates the Fleming-Viot process with a Dawson-Watanabe process. The sampling measures on the lookdown space are then image measures of the normalized local time measures.
We also show invariance principles for Markov chains that describe the evolving genealogy in Cannings models. For such Markov chains with values in the space of distance matrix distributions, we show convergence to tree-valued Fleming-Viot processes under the conditions of Möhle and Sagitov for the convergence of the genealogy at a fixed time to a coalescent with simultaneous multiple mergers. For the convergence of Markov chains with values in the space of marked metric measure spaces, an additional assumption is needed in the case with dust.
Random constraint satisfaction problems have been on the agenda of various sciences such as discrete mathematics, computer science, statistical physics and a whole series of additional areas of application since the 1990s at least. The objective is to find a state of a system, for instance an assignment of a set of variables, satisfying a bunch of constraints. To understand the computational hardness as well as the underlying random discrete structures of these problems analytically and to develop efficient algorithms that find optimal solutions has triggered a huge amount of work on random constraint satisfaction problems up to this day. Referring to this context in this thesis we present three results for two random constraint satisfaction problems. ...
Based on a non-rigorous formalism called the “cavity method”, physicists have made intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random k-SAT or random graph k-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called condensation [Krzakala et al., PNAS 2007]. The existence of this phase transition seems to be intimately related to the difficulty of proving precise results on, e. g., the k-colorability threshold as well as to the performance of message passing algorithms. In random graph k-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture, provided that k exceeds a certain constant k0.
The condensation phase transition and the number of solutions in random graph and hypergraph models
(2016)
This PhD thesis deals with two different types of questions on random graph and random hypergraph structures.
One part is about the proof of the existence and the determination of the location of the condensation phase transition. This transition will be investigated for large values of $k$ in the problem of $k$-colouring random graphs and in the problem of 2-colouring random $k$-uniform hypergraphs, where in the latter case we investigate a more general model with finite inverse temperature.
The other part deals with establishing the limiting distribution of the number of solutions in these structures in density regimes below the condensation threshold.
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.
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.
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.
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.
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.
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.
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.
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).
Sensitivity of output of a linear operator to its input can be quantified in various ways. In Control Theory, the input is usually interpreted as disturbance and the output is to be minimized in some sense. In stochastic worst-case design settings, the disturbance is considered random with imprecisely known probability distribution. The prior set of probability measures can be chosen so as to quantify how far the disturbance deviates from the white-noise hypothesis of Linear Quadratic Gaussian control. Such deviation can be measured by the minimal Kullback-Leibler informational divergence from the Gaussian distributions with zero mean and scalar covariance matrices. The resulting anisotropy functional is defined for finite power random vectors. Originally, anisotropy was introduced for directionally generic random vectors as the relative entropy of the normalized vector with respect to the uniform distribution on the unit sphere. The associated a-anisotropic norm of a matrix is then its maximum root mean square or average energy gain with respect to finite power or directionally generic inputs whose anisotropy is bounded above by a >= 0. We give a systematic comparison of the anisotropy functionals and the associated norms. These are considered for unboundedly growing fragments of homogeneous Gaussian random fields on multidimensional integer lattice to yield mean anisotropy. Correspondingly, the anisotropic norms of finite matrices are extended to bounded linear translation invariant operators over such fields.
Statistical analysis on various stocks reveals long range dependence behavior of the stock prices that is not consistent with the classical Black and Scholes model. This memory or nondeterministic trend behavior is often seen as a reflection of market sentiments and causes that the historical volatility estimator becomes unreliable in practice. We propose an extension of the Black and Scholes model by adding a term to the original Wiener term involving a smoother process which accounts for these effects. The problem of arbitrage will be discussed. Using a generalized stochastic integration theory [8], we show that it is possible to construct a self financing replicating portfolio for a European option without any further knowledge of the extension and that, as a consequence, the classical concept of volatility needs to be re-interpreted.
AMS subject classifications: 60H05, 60H10, 90A09.
Integral equations for the mean-square estimate are obtained for the linear filtering problem, in which the noise generating the signal is a fractional Brownian motion with Hurst index h∈(3/4,1) and the noise in the observation process includes a fractional Brownian motion as well as a Wiener process. AMS subject classifications: 93E11, 60G20, 60G35.
Within the last twenty years, the contraction method has turned out to be a fruitful approach to distributional convergence of sequences of random variables which obey additive recurrences. It was mainly invented for applications in the real-valued framework; however, in recent years, more complex state spaces such as Hilbert spaces have been under consideration. Based upon the family of Zolotarev metrics which were introduced in the late seventies, we develop the method in the context of Banach spaces and work it out in detail in the case of continuous resp. cadlag functions on the unit interval. We formulate sufficient conditions for both the sequence under consideration and its possible limit which satisfies a stochastic fixed-point equation, that allow to deduce functional limit theorems in applications. As a first application we present a new and considerably short proof of the classical invariance principle due to Donsker. It is based on a recursive decomposition. Moreover, we apply the method in the analysis of the complexity of partial match queries in two-dimensional search trees such as quadtrees and 2-d trees. These important data structures have been under heavy investigation since their invention in the seventies. Our results give answers to problems that have been left open in the pioneering work of Flajolet et al. in the eighties and nineties. We expect that the functional contraction method will significantly contribute to solutions for similar problems involving additive recursions in the following years.
We provide a mathematical framework to model continuous time trading in limit order markets of a small investor whose transactions have no impact on order book dynamics. The investor can continuously place market and limit orders. A market order is executed immediately at the best currently available price, whereas a limit order is stored until it is executed at its limit price or canceled. The limit orders can be chosen from a continuum of limit prices.
In this framework we show how elementary strategies (hold limit orders with only finitely many different limit prices and rebalance at most finitely often) can be extended in a suitable
way to general continuous time strategies containing orders with infinitely many different limit prices. The general limit buy order strategies are predictable processes with values in the set of nonincreasing demand functions (not necessarily left- or right-continuous in the price variable). It turns out that this family of strategies is closed and any element can be approximated by a sequence of elementary strategies.
Furthermore, we study Merton’s portfolio optimization problem in a specific instance of this framework. Assuming that the risky asset evolves according to a geometric Brownian
motion, a proportional bid-ask spread, and Poisson execution times for the limit orders of the small investor, we show that the optimal strategy consists in using market orders to keep the
proportion of wealth invested in the risky asset within certain boundaries, similar to the result for proportional transaction costs, while within these boundaries limit orders are used to profit from the bid-ask spread.
In recent years using symmetry has proven to be a very useful tool to simplify computations in semidefinite programming. This dissertation examines the possibilities of exploiting discrete symmetries in three contexts: In SDP-based relaxations for polynomial optimization, in testing positivity of symmetric polynomials, and combinatorial optimization. In these contexts the thesis provides new ways for exploiting symmetries and thus deeper insight in the paradigms behind the techniques and studies a concrete combinatorial optimization question.
Poster presentation from Twentieth Annual Computational Neuroscience Meeting: CNS*2011 Stockholm, Sweden. 23-28 July 2011. In statistical spike train analysis, stochastic point process models usually assume stationarity, in particular that the underlying spike train shows a constant firing rate (e.g. [1]). However, such models can lead to misinterpretation of the associated tests if the assumption of rate stationarity is not met (e.g. [2]). Therefore, the analysis of nonstationary data requires that rate changes can be located as precisely as possible. However, present statistical methods focus on rejecting the null hypothesis of stationarity without explicitly locating the change point(s) (e.g. [3]). We propose a test for stationarity of a given spike train that can also be used to estimate the change points in the firing rate. Assuming a Poisson process with piecewise constant firing rate, we propose a Step-Filter-Test (SFT) which can work simultaneously in different time scales, accounting for the high variety of firing patterns in experimental spike trains. Formally, we compare the numbers N1=N1(t,h) and N2=N2(t,h) of spikes in the time intervals (t-h,t] and (h,t+h]. By varying t within a fine time lattice and simultaneously varying the interval length h, we obtain a multivariate statistic D(h,t):=(N1-N2)/V(N1+N2), for which we prove asymptotic multivariate normality under homogeneity. From this a practical, graphical device to spot changes of the firing rate is constructed. Our graphical representation of D(h,t) (Figure 1A) visualizes the changes in the firing rate. For the statistical test, a threshold K is chosen such that under homogeneity, |D(h,t)|<K holds for all investigated h and t with probability 0.95. This threshold can indicate potential change points in order to estimate the inhomogeneous rate profile (Figure 1B). The SFT is applied to a sample data set of spontaneous single unit activity recorded from the substantia nigra of anesthetized mice. In this data set, multiple rate changes are identified which agree closely with visual inspection. In contrast to approaches choosing one fixed kernel width [4], our method has advantages in the flexibility of h.
In der folgenden Arbeit werden Eigenschaften von Verzweigungsprozessen in zufälliger Umgebung (engl. branching processes in random environment, kurz BPREs) untersucht. Das Modell geht auf Smith (1969) und Athreya (1971) zurück. Ein BPRE ist ein einfaches mathematisches Modell für die Entwicklung einer Population von apomiktischen (d.h. sich ungeschlechtlich fortpflanzenden) Individuen in diskreter Zeit, wobei die Umgebungsbedingungen einen Einfluß auf den Fortpflanzungserfolg der Individuen haben. Dabei wird angenommen, dass die Umgebungsbedingungen in den einzelnen Generationen zufällig sind, und zwar unabhängig und identisch verteilt von Generation zu Generation. Man denke z.B. an eine Population von Pflanzen mit einem einjährigen Zyklus, die in jedem Jahr anderen Witterungsbedingungen ausgesetzt sind, wobei angenommen wird, dass diese sich unabhängig und identisch verteilt ändern. In Kapitel 1 wird eines der wichtigsten Hilfsmittel zur Beschreibung von BPREs, die sogenannte zugehörige Irrfahrt, eingeführt und die Klassifizierung von BPREs beschrieben. In Kapitel 2 werden bekannte Resultate, insbesondere zu kritischen, schwach subkritischen und stark subkritischen Verzweigungsprozessen, wiederholt. In Kapitel 3 wird der sogenannte intermediär subkritische Fall behandelt. Mithilfe von funktionalen Grenzwertsätzen für bedingte Irrfahrten wird die genaue Asymptotik der Überlebenswahrscheinlichkeit des Prozesses, die bereits in Vatutin (2004) bewiesen wurde, unter etwas allgemeineren Voraussetzungen gezeigt. Anschließend wird untersucht, wie häufig der Prozess, bedingt auf Überleben, nur noch aus einem Individuum besteht. Im letzten Teil des Kapitels wird ein funktionaler Grenzwertsatz für die zugehörige Irrfahrt, bedingt aufs Überleben des Prozesses, gezeigt. Diese konvergiert, richtig skaliert, gegen einen Levy-Prozess, der darauf bedingt ist, sein Minimum am Ende anzunehmen. In Kapitel 4 werden große Abweichungen von BPREs untersucht. Die Ratenfunktion des BPRE wird sowohl für den Fall mindestens geometrisch schnell abfallender Tails, als auch für den Fall von Nachkommenverteilungen mit schweren Tails bestimmt. Wie sich herausstellt, hängt die Ratenfunktion von der Ratenfunktion der zugehörigen Irrfahrt, der exponentiellen Abfallrate der Überlebenswahrscheinlichkeit sowie, bei Nachkommenverteilungen mit schweren Tails, auch von den Tails derselben ab. In der Ratenfunktion spiegeln sich die wahrscheinlichsten Wege, um Ereignisse der großen Abweichungen zu realisieren, wider, was in Kapitel 4.3 beschrieben wird. In Kapitel 4.4 wird im speziellen Fall von Nachkommenverteilungen mit gebrochen-linearer Erzeugendenfunktion die Ratenfunktion für Ereignisse bestimmt, bei denen ein superkritischer BPRE überlebt, aber klein im Vergleich zum Erwartungswert bleibt. In Kapitel 4.5 werden die großen Abweichungen, bedingt auf die Umgebung untersucht (engl. quenched). In diesem Fall können unwahrscheinliche Ereignisse nur über den Verzweigungsmechanismus und nicht mehr über eine außergewöhnliche Umgebung realisiert werden. Zum Abschluss der Dissertation werden Verzweigungsprozesse in zufälliger Umgebung, bedingt auf Überle-ben, simuliert. Dazu wird eine Konstruktion nach Geiger (1999) angewendet. Diese erlaubt es, Galton-Watson Bäume in variierender Umgebung, bedingt auf Überleben, entlang einer Ahnenlinie zu konstruieren. Der Fall geometrischer Nachkommenverteilungen, auf den wir uns in Kapitel 5 beschränken, erlaubt die explizite Berechnung der benötigten Verteilungen. Als Anwendung des Grenzwertsatzes aus Kapitel 3.1 können nun intermediär subkritische Verzweigungsprozesse, bedingt auf Überleben, wie folgt simuliert werden: Zunächst wird die Umgebung zufällig bestimmt, und zwar als Irrfahrt, bedingt darauf ihr Minimum am Ende anzunehmen. Anschließend wird, der Geiger-Konstruktion folgend, ein Verzweigungsprozess in dieser Umgebung, bedingt auf Überleben, simuliert. Zum Abschluss wird in einem kurzen Ausblick auf aktuelle Forschung verwiesen. Im Anhang befinden sich einige technische Resultate.
The Benchmark Dose (BMD) approach, which was suggested firstly in 1984 by K. Crump [CRUMP (1984)], is a widely used instrument in risk assessment of substances in the environment and in food. In this context, the BMD approach determines a reference point (RfP) on the statistically estimated dose-response curve, for which the risk can be determined with adequate certainty and confidence. In the next step of risk characterization a threshold is calculated, based on this RfP and toxicological considerations. The BMD approach bases upon the fit of a dose-response model on the data. For this fit a stochastic distribution of the response endpoint is taken as a basis. Ultimately, the BMD reflects the dose for which a pre-specified increase in an adverse health effect (the benchmark response) can be expected. Until now, the BMD approach has been specified only for quantal and continuous endpoints. But in risk assessment of carcinogens especially so called time-to-event data are of high interest since they contain more information on the tumor development than quantal incidence data. The goal of this diploma thesis was to extend the BMD approach to such time-to-event data.
Dessins d'enfants (children's drawings) may be defined as hypermaps, i.e. as bipartite graphs embedded in compact Riemann surfaces. They are very important objects in order to describe the surface of the embedding as an algebraic curve. Knowing the combinatorial properties of the dessin may, in fact, help us determining defining equations or the field of definition of the surface. This task is easier if the automorphism group of the dessin is "large". In this thesis we consider a special type of dessins, so-called Wada dessins, for which the underlying graph illustrates the incidence structure of points and of hyperplanes of projective spaces. We determine under which conditions they have a large orientation-preserving automorphism group. We show that applying algebraic operations called "mock" Wilson operations to the underlying graph we may obtain new dessins. We study the automorphism group of the new dessins and we show that the dessins we started with are coverings of the new ones.
New conditions of solvability based on a general theorem on the calculation of the index at infinity for vector fields that have degenerate principal linear part as well as degenerate ... next order ... terms are obtained for the 2 Pi-periodic problem for the scalar equation x'' +n2x=g(|x|)+f(t,x)+b(t) with bounded g(u) and f(t,x) -> 0 as |x| -> 0. The result is also applied to the solvability of a two-point boundary value problem and to resonant problems for equations arising in control theory.
AMS subject classifications: 47Hll, 47H30.
Linear-implicit versions of strong Taylor numerical schemes for finite dimensional Itô stochastic differential equations (SDEs) are shown to have the same order as the original scheme. The combined truncation and global discretization error of an gamma strong linear-implicit Taylor scheme with time-step delta applied to the N dimensional Itô-Galerkin SDE for a class of parabolic stochastic partial differential equation (SPDE) with a strongly monotone linear operator with eigenvalues lambda 1 <= lambda 2 <= ... in its drift term is then estimated by K(lambda N -½ + 1 + delta gamma) where the constant K depends on the initial value, bounds on the other coefficients in the SPDE and the length of the time interval under consideration.
AMS subject classifications: 35R60, 60H15, 65M15, 65U05.
We presented a proof for the classical stable limit laws under use of contraction method in combination with the Zolotarev metric. Furthermore, a stable limit law was proved for scaled sums of growing into sequences. This limit law was alternatively formulated for sequences of random variables defined by a simple degenerate recursion.
We present a new self-contained and rigorous proof of the smoothness of invariant fiber bundles for dynamic equations on measure chains or time scales. Here, an invariant fiber bundle is the generalization of an invariant manifold to the nonautonomous case. Our main result generalizes the “Hadamard-Perron theorem” to the time-dependent, infinite-dimensional, noninvertible, and parameter-dependent case, where the linear part is not necessarily hyperbolic with variable growth rates. As a key feature, our proof works without using complicated technical tools.
Dynamical systems driven by Gaussian noises have been considered extensively in modeling, simulation, and theory. However, complex systems in engineering and science are often subject to non-Gaussian fluctuations or uncertainties. A coupled dynamical system under a class of Lévy noises is considered. After discussing cocycle property, stationary orbits, and random attractors, a synchronization phenomenon is shown to occur, when the drift terms of the coupled system satisfy certain dissipativity and integrability conditions. The synchronization result implies that coupled dynamical systems share a dynamical feature in some asymptotic sense.
This work connects Markov chain imbedding technique (MCIT) introduced by M.V. Koutras and J.C. Fu with distributions concerning the cycle structure of permutations. As a final result program code is given that uses MCIT to deliver proper numerical values for these. The discrete distributions of interest are the one of the cycle structure, the one of the number of cycles, the one of the rth longest and shortest cycle and finally the length of a random chosen cycle. These are analyzed for equiprobable permutations as well as for biased ones. Analytical solutions and limit distributions are also considered to put the results on a safe, theoretical base.
Condensing phenomena for systems biology, ecology and sociology present in real life different complex behaviors. Based on local interaction between agents, we present another result of the Energy-based model presented by [20]. We involve an additional condition providing the total condensing (also called consensus) of a discrete positive measure. Key words: Condensing; consensus; random move; self-organizing groups; collective intelligence; stochastic modeling. AMS Subject Classifications: 81T80; 93A30; 37M05; 68U20
Tropical geometry is the geometry of the tropical semiring \[\mathbb{T}:=(\mathbb{R}\cup\{\infty\},\min,+).\] Classical algebraic structures correspond to tropical structures. If $I\lhd K[x_1,\ldots,x_n]$ is an ideal in a polynomial ring over a field $K$ with valuation $v$, then the classical algebraic variety correspond to the tropical variety $T(I)$. It is the set of all points $w$, such that the minimum $\min\{v(c_\alpha)+w\cdot\alpha\}$ is achieved twice for all $f=\sum_\alpha c_\alpha x^\alpha\in I$. So tropical geometry relates algebraic geometric problems with discrete geometric problems. In this thesis we obtain a tropical version of the Eisenbud-Evans Theorem which states that every algebraic variety in $\mathbb{R}^n$ is the intersection of $n$ hypersurfaces. We find out that in the tropical setting every tropical variety $T(I)$ can be written as an intersection of only $(n+1)$ tropical hypersurfaces. So we get a finite generating system of $I$ such that the corresponding tropical hypersurfaces intersect to the tropical variety, a so-called tropical basis. Let $I \lhd K[x_1,\ldots,x_n]$ be a prime ideal generated by the polynomials $f_1, \ldots, f_r$. Then there exist $g_0,\ldots,g_{n} \in I$ such that \[ T(I) \ = \ \bigcap_{i=0}^{n}T(g_i)\] and thus $\mathcal{G} := \{f_1, \ldots, f_r, g_0, \ldots, g_{n}\}$ is a tropical basis for $I$ of cardinality $r+n+1$. Tropical bases are discussed by Bogart, Jensen, Speyer, Sturmfels and Thomas where it is shown that tropical bases of linear polynomials of a linear ideal have to be very large. We do not restrict the tropical basis to consist of linear polynomials and therefore we get a shorter tropical basis. But the degrees of our polynomials can be very large. The main ingredient to get a short tropical basis is the use of projections, in particular geometrically regular projections. Together with the fact that preimages of projections of tropical varieties are themselves tropical varieties of a certain elimination ideal we get the desired result. Let $I \lhd K[x_1, \ldots, x_n]$ be an $m$-dimensional prime ideal and $\pi : \mathbb{R}^n \to \mathbb{R}^{m+1}$ be a rational projection. Then $\pi^{-1}(\pi(T(I)))$ is a tropical variety, namely \[ \pi^{-1}(\pi(T(I))) \ = \ T(J \cap K[x_1, \ldots, x_n]) \,\] Here $J$ is an ideal in $K[x_1,\ldots,x_n,\lambda_1,\ldots,\lambda_{n-m-1}]$ derived from the ideal $I$. We show that this elimination ideal is a principal ideal which yields a polynomial in our tropical basis. The advantage of our method is that we find our polynomials by projections and therefore we can use the results of Gelfand, Kapranov and Zelevinsky , of Esterov and Khovanskii , and of Sturmfels, Tevelev and Yu. With mixed fiber polytopes we get the structure and combinatorics of the image of a tropical variety and therefore the structure of the polynomials in our tropical basis. Let $I=\lhd K[x_1,\ldots,x_n]$ an $m$-dimensional ideal, generated by generic polynomials $f_1,\ldots, f_{n-m}$, $\pi:\mathbb{R}^n\to\mathbb{R}^{m+1}$ a projection and $\psi$ a projection presented by a matrix with a rowspace equal to the kernel of $\pi$. Then up to affine isomorphisms, the cells of the dual subdivision of $\pi^{-1} \pi T(I)$ are of the form \[ \sum_{i=1}^p \Sigma_{\psi} (C_{i1}^{\vee}, \ldots, C_{i{k}}^{\vee}) \] for some $p\in\mathbb{N}$ and faces $F_1, \ldots, F_p$ of $T(f_1)\cap\ldots\cap T(f_k)$ and the dual cell of $F_i\subseteq U = T(f_1)\cup\ldots\cup T(f_k)$ is given by $F_i^\vee=C_{i1}^{\vee}+ \ldots+ C_{ik}^{\vee}$ with faces $C_{i1}, \ldots, C_{i k}$ of $T(f_1), \ldots, T(f_{k})$. In case that we project a tropical curve we want to find the number of $(n-1)$-cells of the above form with $p>1$, i.e. the cells which are dual to vertices of $\pi(T(I))$ which are the intersection of the images of two non-adjacent $1$-cells of $T(I)$. Vertices of this type are called selfintersection points. We show that there exist a tropcal line $L_n\subset\mathbb{R}^n$ and a projection $\pi:\mathbb{R}^n\to\mathbb{R}^2$, such that $L_n$ has $\sum_{i=1}^{n-2}i$ selfintersection points. Furthermore we find tropical curves $\mathcal{C}\subset\mathbb{R}^n$, which are transversal intersections of $n-1$ tropical hypersurfaces of degrees $d_1,\ldots,d_{n-1}$ and a projection $\pi:\mathbb{R}^n\to\mathbb{R}^2$, such that $\mathcal{C}$ has at least $(d_1\cdot\ldots\cdot d_{n-1})^2\cdot \sum_{i=1}^{n-2}i) $ selfintersection points. A caterpillar is a certain simple type of a tropical line and for this type we show that it can have at most $\sum_{i=1}^{n-2}i$ selfintersection points.
Mixed volumes, mixed Ehrhart theory and applications to tropical geometry and linkage configurations
(2009)
The aim of this thesis is the discussion of mixed volumes, their interplay with algebraic geometry, discrete geometry and tropical geometry and their use in applications such as linkage configuration problems. Namely we present new technical tools for mixed volume computation, a novel approach to Ehrhart theory that links mixed volumes with counting integer points in Minkowski sums, new expressions in terms of mixed volumes of combinatorial quantities in tropical geometry and furthermore we employ mixed volume techniques to obtain bounds in certain graph embedding problems.
Local interactions between particles of a collection causes all particles to reorganize in new positions. The purpose of this paper is to construct an energy-based model of self-organizing subgroups, which describes the behavior of singular local moves of a particle. The present paper extends the Hegselmann-Krause model on consensus dynamics, where agents simultaneously move to the barycenter of all agents in an epsilon neighborhood. The Energy-based model presented here is analyzed and simulated on finite metric space. AMS Subject Classifications:81T80; 93A30; 37M05; 68U20
Deformation quantization on symplectic stacks and applications to the moduli of flat connections
(2008)
It is a common problem in mathematical physics to describe and quantize the Poisson algebra on a symplectic quotient [...] given in terms of some moment map [...] on a symplectic manifold [...] with a hamiltonian action by a Lie group G. Among others, problems may arise in two parts of the process: c might be a singular value of the moment map and the quotient might not be well-behaving; in the interesting cases the quotient often is singular. By the famous result of Sjamaar and Lerman ([102]) X is a symplectic stratified space. We are interested in cases for which we can give a deformation quantization of the possibly singular Poisson algebra of X. To that purpose we introduce a Poisson algebra on the associated stack [...] for special cases and consider its deformations and their classification. We dedicate ourselves to use the rather geometric methods introduced by Fedosov for symplectic manifolds in [37]. That leads to the question how to perform differential geometry on a smooth stack. The Lie groupoid atlas of a smooth stack is a nice model for the same space (Tu, Xu and Laurent-Gengoux in [107] and Behrend and Xu in [16]), but both have different topoi. We give a morphism (P,R) that compares the topologies of a smooth stack and its atlas. This yields a method to transport sheaves and their sections between a smooth stack and its Lie groupoid atlas. A symplectic stack is a smooth separated Deligne-Mumford stack with a 2-form which is closed and non-degenerate in an atlas. Via (P,R) a deformation quantization on a symplectic stack can be performed in terms of an atlas. We also give a classification functor for the quantizations in the spirit of Deligne ([35]) based on the geometric interpretation given by Gutt and Rawnsely in [49]. As an application we give a deformation quantization for the moduli stack of flat connections in particular configurations. We use Darboux charts provided by Huebschmann (e.g. in [54]) to construct the corresponding Lie groupoid. This captures the symplectic form arising in the reduction process and differs from other approaches using gerbes of bundles (e.g. Teleman [105]).
In this work, we extend the Hegselmann and Krause (HK) model, presented in [16] to an arbitrary metric space. We also present some theoretical analysis and some numerical results of the condensing of particles in finite and continuous metric spaces. For simulations in a finite metric space, we introduce the notion "random metric" using the split metrics studies by Dress and al. [2, 11, 12].
Das libor Markt Modell (LMM) ist seit seiner Entwicklung in den Veröffentlichungen von Brace, Gatarek, Musiela (1997), einerseits, und unabhängig von diesen von Miltersen, Sandmann, Sondermann (1997), andererseits, zu dem anerkanntesten Instrument zur Modellierung der Zinsstruktur und der damit verbundenen Preisfindung für relevante Finanzderivate geworden. libor steht dabei für London Inter-Bank Offered Rate, ein täglich in London fixierter Referenz-Zins für kurzfristige Anlagen. Drei- oder sechsmonatige Laufzeiten sind in Verbindung mit dem LMM üblich. Die Forschung zur Verbesserung dieses Modells hat in den letzten Jahren an Zuwachs gewonnen. Beim Versuch den Fehler der Anpassung an die täglich beobachteten Preise von Zinsoptionen wie Caps und Swaptions zu verringern, erhält man in der Folge auch genauere Bewertungen für andere, exotischere, Derivate. Die zugrunde liegende und zentrale Idee des LMM besteht darin, die Forward (Termin) Zinsen direkt als primären (Vektor) Prozess mehrerer libor Sätze zu betrachten und diese simultan zu modellieren, anstatt sie nur herzuleiten aus einem übergeordneten, unendlich dimensionalen Forward Zinsprozess, wie im zeitlich früher entwickelten Heath-Jarrow-Morton Modell. Das überzeugendste Argument für diese Diskretisierung ist, dass die libor Sätze direkt im Markt beobachtbar sind und ihre Volatilitäten auf eine natürliche Weise in Beziehung gebracht werden können zu bereits liquide gehandelten Produkten, eben jenen Caps und Swaptions. Dennoch beinhaltet das Modell eine gravierende Insuffizienz, indem es keine Krümmung der Volatilitätsoberfläche, im Hinblick auf Optionen mit verschiedenen Basiszinsen, abbildet. Wie im einfachen eindimensionalen Black-Scholes Modell prägen sich auch hier die Ungenauigkeiten der Verteilung in fehlenden heavy tails deutlich aus. Smile und Skew Effekte sind erkennbar. Im klassischen liborMarkt Modell wird in Richtung der Basiszinsdimension nur eine affine Struktur erzeugt, welche bestenfalls als Approximation für die erwünschte Oberfläche dienen kann. Die beobachteten Verzerrungen führen naturgemäss zu einer ungenauen Abbildung der Realität und fehlerhaften Reproduktion der Preise in Regionen, die ein wenig entfernt vom Bereich am Geld liegen. Derartig ungewollte Dissonanzen in Gewinn und Verlustzahlen führten z.B. in 1998 zu gravierenden Verlusten im Zinsderivateportfolio der heutigen Royal Bank of Scotland. ...
This thesis exhibits skeins based on the Homfly polynomial and their relations to Schur functions. The closures of skein-theoretic idempotents of the Hecke algebra are shown to be specializations of Schur functions. This result is applied to the calculation of the Homfly polynomial of the decorated Hopf link. A closed formula for these Homfly polynomials is given. Furthermore, the specialization of the variables to roots of unity is considered. The techniques are skein theory on the one side, and the theory of symmetric functions in the formulation of Schur functions on the other side. Many previously known results have been proved here by only using skein theory and without using knowledge about quantum groups.
Epstein and Penner constructed in [EP88] the Euclidean decomposition of a non-compact hyperbolic n-manifold of finite volume for a choice of cusps, n >= 2. The manifold is cut along geodesic hyperplanes into hyperbolic ideal convex polyhedra. The intersection of the cusps with the Euclidean decomposition determined by them turns out to be rather simple as stated in Theorem 2.2. A dual decomposition resulting from the expansion of the cusps was already mentioned in [EP88]. These two dual hyperbolic decompositions of the manifold induce two dual decompositions in the Euclidean structure of the cusp sections. This observation leads in Theorems 5.1 and 5.2 to easily computable, necessary conditions for an arbitrary ideal polyhedral decomposition of the manifold to be a Euclidean decomposition.
Die vorliegende Arbeit beschäftigt sich mit der BFV-Reduktion von Hamiltonschen Systemen mit erstklassigen Zwangsbedingungen im Rahmen der klassischen Hamiltonschen Mechanik und im Rahmen der Deformationsquantisierung. Besondere Aufmerksamkeit wird dabei Zwangsbedingungen zuteil, die als Nullfaser singulärer äquivarianter Impulsabbildungen entstehen. Es ist schon länger bekannt, daß für Nullfasern regulärer äquivarianter Impulsabbildungen die in der theoretischen Physik gebräuchliche Methode der BFV-Reduktion zur Phasenraumreduktion nach Marsden/Weinstein äquivalent ist. In [24] konnte gezeigt werden, daß in dieser Situation die BFV-Reduktion sich auch im Rahmen der Deformationsquantisierung natürlich formulieren läßt und erfolgreich zur Konstruktion von Sternprodukten auf Marsden/Weinstein-Quotienten verwendet werden kann. Ein Hauptergebnis der vorliegenden Arbeit besteht in der Verallgemeinerung der Ergebnisse aus [24] auf den Fall singulärer Impulsabbildungen, deren Komponenten 1.) das Verschwindungsideal der Zwangsfläche erzeugen und 2.) einen vollständigen Durchschnitt bilden. Die Argumentation von [24] wird durch Gebrauch der Störungslemmata aus dem Anhang A.1 systematisiert und vereinfacht. Zum Existenzbeweis von stetigen Homotopien und stetiger Fortsetzungsabbildung für die Koszulauflösung werden der Zerfällungssatz und der Fortsetzungssatz von Bierstone und Schwarz [20] benutzt. Außerdem wird ein ’Jacobisches Kriterium’ für die Überprüfung von Bedingung 2.) angegeben. Basierend auf diesem Kriterium und Techniken aus [3] werden die Bedingungen 1.) und 2.) an einer Reihe von Beispielen getestet. Als Korollar erhält man den Beweis dafür, daß es symplektisch stratifizierte Räume gibt, die keine Orbifaltigkeiten sind und dennoch eine stetige Deformationsquantisierung zulassen. Ferner wird (ähnlich zu [92]) eine konzeptionielle Erklärung dafür gegeben, warum im Fall vollständiger Durchschnitte das Problem der Quantisierung der BRST-Ladung eine so einfache Lösung hat. Bildet die Impulsabbildung eine erstklassige Zwangsbedingung, ist aber kein vollständiger Durchschnitt, dann ist es im allgemeinen nicht bekannt, wie entsprechende Quantenreduktionsresultate zu erzielen sind. Ein Hauptaugenmerk der Untersuchung wird es deshalb sein, in dieser Situation die klassische BFV-Reduktion besser zu verstehen – natürlich in der Hoffnung, Grundlagen für eine etwaige (Deformations-)Quantisierung zu liefern. Wir werden feststellen, daß es zwei Gründe gibt, die Tate-Erzeuger (alias: Antigeister höheren Niveaus) notwendig machen: die Topologie der Zwangsfläche und die Singularitätentheorie der Impulsabbildung. Die Zahl der Tate-Erzeuger kann durch Übergang zu projektiven Tate-Erzeugern, also Vektorbündeln, verringert werden. Allerdings sorgt Halperins Starrheitssatz [57] dafür, daß im wesentlichen alle Fälle, für die die Zwangsfläche kein lokal vollständiger Durchschnitt ist, zu unendlich vielen Tate-Erzeugern führen. Erzeugen die Komponenten einer Impulsabbildung einer linearen symplektischen Gruppenwirkung das Verschwindungsideal der Zwangsfläche, so kann man eine lokal endliche Tate-Auflösung finden. Diese besitzt nach dem Fortsetzungssatz und dem Zerfällungssatz von Bierstone und Schwarz stetige, kontrahierende Homotopien. Ausgehend von einer solchen Tate-Auflösung konstruieren wir, die klassische BFV-Konstruktion für vollständige Durchschnitte verallgemeinernd, eine graduierte superkommutative Algebra. Wir können zeigen, daß diese graduierte Algebra auch im Vektorbündelfall eine graduierte Poissonklammer besitzt, die sogenannte Rothstein-Poissonklammer. Die Existenz einer solchen Poissonklammer war bereits von Rothstein [87] für die einfachere Situation einer symplektischen Supermannigfaltigkeit bewiesen worden. Darüberhinaus werden wir sehen, daß es auch im Vektorbündelfall eine BRST-Ladung gibt. Diese sieht im Fall von Impulsabbildungen etwas einfacher aus als für allgemeine erstklassige Zwangsbedingungen. Insgesamt wird also die klassische BFV-Konstruktion [95] auf den Fall projektiver Tate-Erzeuger verallgemeinert, und als eine Homotopieäquivalenz in der additiven Kategorie der Fréchet-Räume interpretiert.
Concentration of multivariate random recursive sequences arising in the analysis of algorithms
(2006)
Stochastic analysis of algorithms can be motivated by the analysis of randomized algorithms or by postulating on the sets of inputs of the same length some probability distributions. In both cases implied random quantities are analyzed. Here, the running time is of great concern. Characteristics like expectation, variance, limit law, rates of convergence and tail bounds are studied. For the running time, beside the expectation, upper bounds on the right tail are particularly important, since one wants to know large values of the running time not taking place with possibly high probability. In the first chapter game trees are analyzed. The worst case runnig time of Snir's randomized algorithm is specified and its expectation, asymptotic behavior of the variance, a limit law with uniquely characterized limit and tail bounds are identified. Furthermore, a limit law for the value of the game tree under Pearl's probabilistic modell is proved. In the second chapter upper and lower bounds for the Wiener Index of random binary search trees are identified. In the third chapter tail bounds for the generation size of multitype Galton-Watson processes (with immigration) are derived, depending on their offspring distribution. Therefore, the method used to prove the tail bounds in the first chapter is generalized.
Approximating Perpetuities
(2006)
A perpetuity is a real valued random variable which is characterised by a distributional fixed-point equation of the form X=AX+b, where (A,b) is a vector of random variables independent of X, whereas dependencies between A and b are allowed. Conditions for existence and uniqueness of solutions of such fixed-point equations are known, as is the tail behaviour for most cases. In this work, we look at the central area and develop an algorithm to approximate the distribution function and possibly density of a large class of such perpetuities. For one specific example from the probabilistic analysis of algorithms, the algorithm is implemented and explicit error bounds for this approximation are given. At last, we look at some examples, where the densities or at least some properties are known to compare the theoretical error bounds to the actual error of the approximation. The algorithm used here is based on a method which was developed for another class of fixed-point equations. While adapting to this case, a considerable improvement was found, which can be translated to the original method.
It is commonly agreed that cortical information processing is based on the electric discharges (spikes') of nerve cells. Evidence is accumulating which suggests that the temporal interaction among a large number of neurons can take place with high precision, indicating that the efficiency of cortical processing may depend crucially on the precise spike timing of many cells. This work focuses on two temporal properties of parallel spike trains that attracted growing interest in the recent years: In the first place, specific delays (phase offsets') between the firing times of two spike trains are investigated. In particular, it is studied whether small phase offsets can be identified with confidence between two spike trains that have the tendency to fire almost simultaneously. Second, the temporal relations between multiple spike trains are investigated on the basis of such small offsets between pairs of processes. Since the analysis of all delays among the firing activity of n neurons is extremely complex, a method is required with which this highly dimensional information can be collapsed in a straightforward manner such that the temporal interaction among a large number of neurons can be represented consistently in a single temporal map. Finally, a stochastic model is presented that provides a framework to integrate and explain the observed temporal relations that result from the previous analyses.
The existence of a mean-square continuous strong solution is established for vector-valued Itö stochastic differential equations with a discontinuous drift coefficient, which is an increasing function, and with a Lipschitz continuous diffusion coefficient. A scalar stochastic differential equation with the Heaviside function as its drift coefficient is considered as an example. Upper and lower solutions are used in the proof.
The synchronization of neuronal firing activity is considered an important mechanism in cortical information processing. The tendency of multiple neurons to synchronize their joint firing activity can be investigated with the 'unitary event' analysis (Grün, 1996). This method is based on the nullhypothesis of independent Bernoulli processes and can therefore not tell whether coincidences observed between more than two processes can be considered "genuine" higher- order coincidences or whether they might be caused by coincidences of lower order that coincide by chance ("chance coincidences"). In order to distinguish between genuine and chance coincidences, a parametric model of independent interaction processes (MIIP) is presented. In the framework of this model, Maximum-Likelihood estimates are derived for the firing rates of n single processes and for the rates with which genuine higher order correlations occur. The asymptotic normality of these estimates is used to derive their asymptotic variance and in order to investigate whether higher order coincidences can be considered genuine or whether they can be explained by chance coincidences. The empirical test power of this procedure for n=2 and n=3 processes and for finite analysis windows is derived with simulations and compared to the asymptotic values. Finally, the model is extended in order to allow for the analysis of correlations that are caused by jittered coincidences.
Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25
We study the approximability of the following NP-complete (in their feasibility recognition forms) number theoretic optimization problems: 1. Given n numbers a1 ; : : : ; an 2 Z, find a minimum gcd set for a1 ; : : : ; an , i.e., a subset S fa1 ; : : : ; ang with minimum cardinality satisfying gcd(S) = gcd(a1 ; : : : ; an ). 2. Given n numbers a1 ; : : : ; an 2 Z, find a 1-minimum gcd multiplier for a1 ; : : : ; an , i.e., a vector x 2 Z n with minimum max 1in jx i j satisfying P n...
Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications
(1999)
Pseudorandom function tribe ensembles are pseudorandom function ensembles that have an additional collision resistance property: almost all functions have disjoint ranges. We present an alternative to the construction of pseudorandom function tribe ensembles based on oneway permutations given by Canetti, Micciancio and Reingold [CMR98]. Our approach yields two different but related solutions: One construction is somewhat theoretic, but conceptually simple and therefore gives an easier proof that one-way permutations suffice to construct pseudorandom function tribe ensembles. The other, slightly more complicated solution provides a practical construction; it starts with an arbitrary pseudorandom function ensemble and assimilates the one-way permutation to this ensemble. Therefore, the second solution inherits important characteristics of the underlying pseudorandom function ensemble: it is almost as effcient and if the starting pseudorandom function ensemble is efficiently invertible (given the secret key) then so is the derived tribe ensemble. We also show that the latter solution yields so-called committing private-key encryption schemes. i.e., where each ciphertext corresponds to exactly one plaintext independently of the choice of the secret key or the random bits used in the encryption process.
We introduce the relationship between incremental cryptography and memory checkers. We present an incremental message authentication scheme based on the XOR MACs which supports insertion, deletion and other single block operations. Our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller authentication codes than the tree scheme presented in [BGG95]. Furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. From this scheme we derive memory checkers for data structures based on lists. Conversely, we use a lower bound for memory checkers to show that so-called message substitution detecting schemes produce signatures or authentication codes with size proportional to the message length.
A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.