- / -

Στην παρούσα εργασία θα αναφερθούμε στο κατωφλικό φαινόμενο που εμφανίζεται στο k-SAT. Κύρια προσφορά της διπλωματικής είναι μια νέα απόδειξη του κάτω φράγματος στην περίπτωση του προβλήματος 2-SAT, όπου εκμεταλλευόμενοι γνωστά θεωρήματα από τη θεωρία τυχαίων γραφημάτων επιτυγχάνουμε μια ευκολότερη απόδειξη. Ξεκινάμε κάνοντας μια γενική παρουσίαση του προβλήματος της ικανοποιησιμότητας. Στο επόμενο κεφάλαιο παρουσιάζουμε κάποιους βασικούς ορισμούς και κάνουμε μια σύντομη αναδρομή στα αποτελέσματα που έχουν προκύψει. Αντικείμενο του τρίτου και τέταρτου κεφαλαίου είναι το 2-SAT όπου παρουσιάζονται αντιστοίχως η απόδειξη που δόθηκε από τον Goerdt[24] και μια νέα απόδειξη για το κάτω φράγμα με χρήση resolution. Στο τελευταίο κεφάλαιο στρέφουμε το ενδιαφέρον μας στην περίπτωση του 3-SAT και εξετάζουμε τις αποδείξεις ενός άνω και ενός κάτω κατωφλίου. / -

This thesis uses two datasets: NCDS (National Child Development Study) and Bartholomew's Digital road map to investigate the relationship between road traffic pollution and asthma amongst children. A pollution exposure model is developed to provide an indicator of road traffic pollution. Also, a spatially driven logistic regression model of the risk of asthma occurrence is developed. The relationship between asthma and pollution is tested using this model. The power of the test has been studied. Because of the uncertainty of exact spatial location of subjects, given a post-code, we have considered error-in-variable model, otherwise known as measurement error model. A general foundation is presented. Inference is attempted in three approaches. Compared with models without measurement error, no improvement on log-likelihood is made. We suggest the error can be omitted. We also take a Bayesian approach to analyse the relationship. A discretized MCMC (Markov Chain Monte Carlo) is developed so that it can be used to estimate parameters and to do inference on a very complex posterior density function. It extends the simulated tempering method to 'multi-dimension temperature' situation. We use this method to implement MCMC on our models. The improvement in speed is remarkable. A significant effect of road traffic pollution on asthma is not found. But the methodology (spatially driven logistic regression and discretized MCMC) can be applied on other data.

In this thesis, we investigate joint models of longitudinal and time-to-event data. We extend the current literature by developing a model that assigns subject-specific variance to the longitudinal process and links this variance to the survival outcome. During development we provide the theoretical definition of the model and its properties, and explore the practical implications for estimating the parameters. We use Markov Chain Monte Carlo (MCMC) methods, and compare the different samplers used in similar models in the literature with our custom MCMC algorithm, written in C++. We use the Deviance Information Criterion to perform model comparisons, and we formalise suggestions from the literature to use posterior predictive model checking to construct a goodness-of-fit test for our model. We use the model on two real-world datasets to investigate claims relating to the importance of blood pressure volatility on stroke risk, and examine the consequences of ignoring measurement error. We amend our model to accommodate competing risk, time-dependent baseline hazard rates, and bivariate longitudinal processes - at which point we update our MCMC samplers and identify the issues. Finally, we use our code in a separate, but related, collaboration with other researchers to analyse repeated counts data.

This thesis is in two parts. Part I concerns simulation of random fields using the circulant embedding method, and Part II studies the numerical solution of stochastic differential equations (SDEs).

No description available.

Two well-known methods of improving the reliability of a system are (i) provision of redundant units, and (ii) repair maintenance. In a redundant system more units made available for performing the system function when fewer are required actually. There are two major types of redundancy - parallel and standby. In this dissertation we are concerned with both these types. Some of the typical assumptions made in the analysis of redundant systems are (i) the repair facility can take up a failed unit for repair at any time, if no other unit is undergoing repair (ii) the system under consideration is needed all the time However, we frequently come accross systems where one or more assumptions have to be relaxed. This is the motivation for the detailed study of the models presented in this dissertation. In this dissertation we present models of redundant systems relaxing one or more of these assumptions simultaneously. More specifically it is a study of stochastic models of redundant systems with 'vacation period' for the repair facility (both standby and parallel systems), and intermittently used systems. The dissertation contains five chapters. Chapter 1 is introductory in nature and contains a brief description of the mathematical techniques used in the analysis of redundant systems. In Chapter 2 assumption (i) is relaxed while studying a model of cold standby redundant system with 'vacation period' for the repair facility. In this model the repair facility is not available for a random time immediately after each repair completion. Integral equations for the reliability and availability functions of the system are derived under suitable assumptions. In Chapter 3, once again assumption (i) is relaxed while studying a model of parallel redundant systems with the same 'vacation period' for the repair facility, explained in the above paragraph. In Chapter 4, the detailed review of intermittently used systems have been studied. In Chapter 5, assumption (ii) is relaxed. This chapter is devoted to the study of an intermittently used 2-unit cold standby system with a single repair facility. This study was carried out using the 'correlated alternating renewal process' and the joint forward recurrence times. All the above models have been studied, when some of the underlying distributions have a non-Markovian nature. They have been analysed using a regeneration point technique. / Mathematical Sciences / M. Sc. (Statistics)

Quantum Markov processes are widely used models of the dynamics open quantum systems, a fundamental topic in theoretical and mathematical physics with important applications in experimental realisations of quantum systems such as ultracold atomic gases and new quantum information technologies such as quantum metrology and quantum control. In this thesis we present a mathematical framework which effectively characterises dynamical phase transitions in quantum Markov processes, using the theory of large deviations, by combining insights developed in non-equilibrium dynamics with techniques from quantum information and probability. We provide a natural decomposition for quantum Markov chains into phases, paving the way for the rigorous treatment of critical features of such systems such as phase transitions and phase purification. A full characterisation of dynamical phase transitions beyond properties of the steady state is described in terms of a dynamical perspective through critical behaviour of the quantum jump trajectories. We extend a fundamental result from large deviations for classical Markov chains, the Sanov theorem, to a quantum setting; we prove this Sanov theorem for the output of quantum Markov chains, a result which could be extended to a quantum Donsker-Varadhan theory. We perform an in-depth analysis of the atom maser, an infinite-dimensional quantum Markov process exhibiting various types of critical behaviour: for certain parameters it exhibits strong intermittency in the atom detection counts, and has a bistable stationary state. We show that the atom detection counts satisfy a large deviations principle, and therefore we deal with a phase cross-over rather than a genuine phase transition, although the latter occurs in the limit of infinite pumping rate. As a corollary, we obtain the Central Limit Theorem for the counting process.

Molecular dynamics (MD) computations aim to simulate materials at the atomic level by approximating molecular interactions classically, relying on the Born-Oppenheimer approximation and semi-empirical potential energy functions as an alternative to solving the difficult time-dependent Schrodinger equation. An approximate solution is obtained by discretization in time, with an appropriate algorithm used to advance the state of the system between successive timesteps. Modern MD simulations simulate complex systems with as many as a trillion individual atoms in three spatial dimensions. Many applications use MD to compute ensemble averages of molecular systems at constant temperature. Langevin dynamics approximates the effects of weakly coupling an external energy reservoir to a system of interest, by adding the stochastic Ornstein-Uhlenbeck process to the system momenta, where the resulting trajectories are ergodic with respect to the canonical (Boltzmann-Gibbs) distribution. By solving the resulting stochastic differential equations (SDEs), we can compute trajectories that sample the accessible states of a system at a constant temperature by evolving the dynamics in time. The complexity of the classical potential energy function requires the use of efficient discretization schemes to evolve the dynamics. In this thesis we provide a systematic evaluation of splitting-based methods for the integration of Langevin dynamics. We focus on the weak properties of methods for confiurational sampling in MD, given as the accuracy of averages computed via numerical discretization. Our emphasis is on the application of discretization algorithms to high performance computing (HPC) simulations of a wide variety of phenomena, where configurational sampling is the goal. Our first contribution is to give a framework for the analysis of stochastic splitting methods in the spirit of backward error analysis, which provides, in certain cases, explicit formulae required to correct the errors in observed averages. A second contribution of this thesis is the investigation of the performance of schemes in the overdamped limit of Langevin dynamics (Brownian or Smoluchowski dynamics), showing the inconsistency of some numerical schemes in this limit. A new method is given that is second-order accurate (in law) but requires only one force evaluation per timestep. Finally we compare the performance of our derived schemes against those in common use in MD codes, by comparing the observed errors introduced by each algorithm when sampling a solvated alanine dipeptide molecule, based on our implementation of the schemes in state-of-the-art molecular simulation software. One scheme is found to give exceptional results for the computed averages of functions purely of position.

This thesis consists of two parts. The first part (Chapters 2-4) focuses on the problem of inverting the signature of a path of bounded variation, and we present three results here. First, we give an explicit inversion formula for any axis path in terms of its signature. Second, we show that for relatively smooth paths, the derivative at the end point can be approximated arbitrarily closely by its signature sequence, and we provide explicit error estimates. As an application, we give an effective inversion procedure for piecewise linear paths. Finally, we prove a uniform estimate for the signatures of paths of bounded variations, and obtain a reconstruction theorem via that uniform estimate. Although this general reconstruction theorem is not computationally efficient, the techniques involved in deriving the uniform estimate are useful in other situations, and we also give an application in the case of expected signatures for Brownian motion. The second part (Chapter 5) deals with rough paths. After introducing proper backgrounds, we extend the uniform estimate above to the context of rough paths, and show how it can lead to simple proofs of distance bounds for Gaussian iterated integrals.