With the advance in nanotechnology, we are more interested in the "smaller worlds". One of the practical applications of this is to measure a very small displacement or the mass of a nano-mechanical object. To measure such properties, one needs a very sensitive detector. A quantum point contact (QPC) is one of the most sensitive detectors. In a QPC, electrons tunnel one by one through a tunnel junction (a "hole"). The tunnel junction in a QPC consists of a narrow constriction (nm-wide) between two conductors. To measure the properties of a nano-mechanical object (which acts as a harmonic oscillator), we couple it to a QPC. This coupling effects the electrons tunneling through the QPC junction. By measuring the transport properties of the tunneling electrons, we can infer the properties of the oscillator (i.e. the nano-mechanical object). However, this coupling introduces noise, which reduces the measurement precision. Thus, it is very important to understand this source of noise and to study how it effects the measurement process. We theoretically study the transport properties of electrons through a QPC junction, weakly coupled to a vibration mode of a nano-mechanical oscillator via both the position and the momentum of the oscillator. %We study both the position and momentum based coupling. The transport properties that we study consist of the average flow of current through the junction, given by the one-time correlation of the electron tunneling event, and the current noise given by the two-time correlation of the average current, i.e, the variance. The first comprehensive experimental study of the noise spectrum of a detector coupled to a QPC was performed by the group of Stettenheim et al. Their observed spectral features had two pronounced peaks which depict the noise produced due to the coupling of the QPC with the oscillator and in turn provide evidence of the induced feedback loop (back-action). Benatov and Blencowe theoretically studied these spectral features using the Born approximation and the Markovian approximation. In this case the Born approximation refers to second order perturbation of the interaction Hamiltonian. In this approximation, the electrons tunnel independently, i.e., one by one only, and co-tunneling is disregarded. The Markovian approximation does not take into account the past behavior of the system under time evolution. These two approximations also enable one to study the system analytically, and the noise is calculated using the MacDonald formula. Our main aim for this thesis is to find a suitable theoretical model that would replicate the experimental plots from the work of Stettenheim et al. Our work does not use the Markovian approximation. However, we do use the Born approximation. This is justified as long as the coupling between the oscillator and QPC is weak. We first obtain the non-Markovian unconditional master equation for the reduced density matrix of the system. Non-Markovian dynamics enables us to study, in principle, the full memory effects of the system. From the master equation, we then derive analytical results for the current and the current noise. Due to the non-Markovian nature of our system, the electron tunneling parameters are time-dependent. Therefore, we cannot study the system analytically. We thus numerically solve the current noise expression to obtain the noise spectrum. We then compare our noise spectrum with the experimental noise spectrum. We show that our spectral noise results agree better with the experimental evidence compared to the results obtained using the Markovian approximation. We thus conclude that one needs non-Markovian dynamics to understand the experimental noise spectrum of a QPC coupled to a nano-mechanical oscillator. / Physics

Policy based network management is a promising approach for provisioning and management of quality of service in mobile ad hoc networks. In this thesis, we focus on performance evaluation of this approach in context of the amount of service received by certain nodes called policy execution points (PEPs) or policy clients from certain specialized nodes called the policy decision points (PDPs) or policy servers. We develop analytical models for the study of the system behavior under two scenarios; a simple Markovian scenario where we assume that the random variables associated with system processes follow an exponential distribution and a more complex non-Markovian scenario where we model the system processes according to general distribution functions as observed through simulation. We illustrate that the simplified Markovian model provides a reasonable indication of the trend of the service availability seen by policy clients and highlight the need for an exact analysis of the system without relying on Poisson assumptions for system processes. In the case of the more exact non-Markovian analysis, we show that our model gives a close approximation to the values obtained via empirical methods. Stochastic Petri Nets are used as performance evaluation tools in development and analysis of these system models. / Master of Science

The complexity of modern computer and software systems still seems to grow exponentially, while the human user is widely left without explanations on how to understand these systems. One of the central tasks of current computer science therefore lies in the development of methods and tools to build such an understanding. A similar task is addressed by formal verification which gives various verifiable justifications for the functionality of a system. As these still only give knowledge that a system functions properly they only address a portion of the task to make systems easier to comprehend. It is widely believed that cause-effect reasoning plays an important role in forming human understanding of complex relations. Thus, there are already many accounts on causality in modern computer science. However, most of them are focusing on a form of backward looking actual causality. This variant of causality is concerned with actual events after their occurrence and tries to reason about causes mostly in a counterfactual manner. In this thesis we address a probabilistic form of causality which is forward looking by nature. As such, we define and discuss novel notions of probabilistic causes in discrete time Markov chains and Markov decision processes. For this we rely on two central principles of probabilistic causality. On one hand, the probability-raising principle states that a cause should raise the probability of its effect. On the other hand, temporal priority requires that a cause must occur before its effect. We build the mathematical and algorithmic foundations of our so called probability-raising causes. For this we work in a state-based setting where causes and effects are reachability properties of sets of states. In order to measure the predictive power of states we define quality-measures for which we interpret causes as binary classifiers. With these tools we address the algorithmic questions of checking cause-effect relations if both a cause candidate and an effect are given and finding quality-optimal causes if only the effect is given. We discuss possible extensions of this basic state-based framework to more general formulations of causes and effects as ω-regular properties.:Abstract 3 1 Introduction 7 1.1 Contributions and Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Preliminaries 21 2.1 Markov Decision Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.1 Graph of an MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.2 Schedulers and Probability Measure . . . . . . . . . . . . . . . . . . . . . 23 2.1.3 Maximal and Minimal Probabilities . . . . . . . . . . . . . . . . . . . . . . 25 2.1.4 Frequencies and Balance Equations . . . . . . . . . . . . . . . . . . . . . 26 2.1.5 MR Scheduler in MDPs without ECs . . . . . . . . . . . . . . . . . . . . . . 26 2.1.6 MEC-Quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Automata and ω-Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Probability-Raising Causality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 Probability-Raising Causality in Markov Decision Processes 33 3.1 Setting and Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1.1 Related Work revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2.1 Conceptual Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2.2 Racetrack MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3 Quality Measures for Probability-Raising Causes . . . . . . . . . . . . . . . . . . 52 3.3.1 PR Causes as Binary Classifiers in MDPs . . . . . . . . . . . . . . . . . . . 53 3.3.2 Quality Measures for a given PR Cause . . . . . . . . . . . . . . . . . . . . 54 4 Algorithmic Considerations 59 4.1 Checking the Probability-Raising Conditions . . . . . . . . . . . . . . . . . . . . . 60 4.1.1 Canonical MDP for given Cause Set . . . . . . . . . . . . . . . . . . . . . . 61 4.1.2 Checking the SPR Condition and the Existence of PR Causes . . . . . . . 72 4.1.3 Checking the GPR Condition . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2 Computing the Quality of a PR Cause . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.2.1 Max/Min Ratios for Disjoint Sets of Terminal States . . . . . . . . . . . . 92 4.3 Quality-Optimal Probability-Raising Causes . . . . . . . . . . . . . . . . . . . . . . 97 4.3.1 Quality-Optimal SPR Causes . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.3.2 Quality-Optimal GPR Causes . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5 Variants of Probability-Raising Causality in MDPs 115 5.1 Probability-Raising Scheduler and Potential PR Causes . . . . . . . . . . . . . . . 116 5.1.1 Checking for SPR Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.1.2 Checking for GPR Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.2 ω-Regular Effects - Reachability Causes . . . . . . . . . . . . . . . . . . . . . . . . 127 5.2.1 Checking Reachability Probability-Raising Causes . . . . . . . . . . . . . . 128 5.2.2 Quality and Optimality of Reachability PR Causes . . . . . . . . . . . . . . 133 5.3 ω-Regular Co-Safety Causes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 5.3.1 Checking Co-Safety PR causes . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.3.2 Quality and Optimality of Co-Safety PR Causes . . . . . . . . . . . . . . . 142 6 Conclusion 147

To address the shortcomings in existing Markov model implementations in handling large amount of metagenomic data with comparable or better accuracy in classification, we developed a new algorithm based on pseudo-count supplemented standard Markov model (SMM), which leverages the power of higher order models to more robustly classify reads at different taxonomic levels. Assessment on simulated metagenomic datasets demonstrated that overall SMM was more accurate in classifying reads to their respective taxa at all ranks compared to the interpolated methods. Higher order SMMs (9th order or greater) also outperformed BLAST alignments in assigning taxonomic labels to metagenomic reads at different taxonomic ranks (genus and higher) on tests that masked the read originating species (genome models) in the database. Similar results were obtained by masking at other taxonomic ranks in order to simulate the plausible scenarios of non-representation of the source of a read at different taxonomic levels in the genome database. The performance gap became more pronounced with higher taxonomic levels. To eliminate contaminations in datasets and to further improve our alignment-free approach, we developed a new framework based on a genome segmentation and clustering algorithm. This framework allowed removal of adapter sequences and contaminant DNA, as well as generation of clusters of similar segments, which were then used to sample representative read fragments to constitute training datasets. The parameters of a logistic regression model were learnt from these training datasets using a Bayesian optimization procedure. This allowed us to establish thresholds for classifying metagenomic reads by SMM. This led to the development of a Python-based frontend that combines our SMM algorithm with the logistic regression optimization, named POSMM (Python Optimized Standard Markov Model). POSMM provides a much-needed alternative to metagenome profiling programs. Our algorithm that builds the genome models on the fly, and thus obviates the need to build a database, complements alignment-based classification and can thus be used in concert with alignment-based classifiers to raise the bar in metagenome profiling.

This dissertation defends the so-called 'agency-approach' to causation, which attempts to ground the causal relation in the cause's role of being a means to bring about its effect. The defence is confined to a conceptual interpretation of this theory, pertaining to the concept of causation as it appears in a causal judgement. However, causal judgements are not seen as limited to specific domains, and they are not exclusively attributed to human agents alone. As a methodological framework to describe the different perspectives of causal judgments, a method taken from the philosophy of information is made use of - the so-called 'method of abstraction'. According to this method, levels of abstraction are devised for the subjective perspective of the acting agent, for the agent as observer during the observation of other agents' actions, and for the agent that judges efficient causation. As a further piece of propaedeutic work, a class of similar (yet not agency-centred) approaches to causation is considered, and their modelling paradigms - Bayesian networks and interventions objectively construed - will be criticised. The dissertation then proceeds to the defence of the agency-approach, the first part of which is a defence against the objection of conceptual circularity, which holds that agency analyses causation in causal terms. While the circularity-objection is rebutted, I rely at that stage on a set of subjective concepts, i.e. concepts that are eligible to the description of the agent's own experience while performing actions. In order to give a further, positive corroboration of the agency-approach, an investigation into the natural origins and constraints of the concept of agency is made in the central chapter six of the dissertation. The thermodynamic account developed in that part affords a third-person perspective on actions, which has as its core element a cybernetic feedback cycle. At that point, the stage is set to analyse the relation between the first- and the third-person perspectives on actions previously assumed. A dual-aspect interpretation of the cybernetic-thermodynamic picture developed in chapter six will be directly applied to the levels of abstraction proposed earlier. The level of abstraction that underpins judgments of efficient causation, the kind of causation seemingly devoid of agency, will appear as a derived scheme produced by and dependent on the concept of agency. This account of efficient causation, the 'objectification of agency', affords the rebuttal of a second objection against the agency-approach, which claims that the approach is inappropriately anthropomorphic. The dissertation concludes with an account of single-case, or token level, causation, and with an examination of the impact of the causal concept on the validity of causal models.

Neste trabalho foi estudado um problema de controle de sistemas lineares com saltos Markovianos sem observação da variável de salto, que pode ser escrito como um problema de otimização de considerável complexidade. As contribuições para a área estão divididas em três aspectos. Um dos avanços foi a elaboração de um contraexemplo para a conjectura de que há somente um mínimo local isolado para o problema. Além disso, foi estudado o problema de otimização intermediário, que consiste em fixar todas as variáveis do problema exceto duas matrizes de ganhos, e os resultados indicam que, com uma pequena alteração na formulação, este é um problema biquadrático. Por fim, novos algoritmos foram elaborados a partir de um método disponível na literatura, chamado de método Variacional, adaptando-o para atualizar os ganhos aos pares, levando a problemas intermediários biquadráticos. Três métodos foram implementados para a resolução destes problemas: dois métodos clássicos de descida, Newton e Gradiente, e uma adaptação do próprio método Variacional. Para a análise dos resultados foram utilizados exemplos gerados aleatoriamente a partir do Gerador de SLSM, que pode ser encontrado na literatura, e o método Variacional como referência para comparação com os métodos propostos / This work addresses a control problem arising in linear systems with Markov jumps without observation of the jump variable and advances in three different aspects. First, it is presented a counterexample to the conjecture that states about the uniqueness of local minimum. Second, the intermediary optimization problem, which sets all the variables of the problem except two arrays of gains, was studied and the results suggested that a slight modification in the formulation makes the intermediary problem a biquadratic one. Finally, new algorithms were developed based on a method available in the literature, which is frequently referred to as the Variational method, adapting it to update the gains in pairs, leading to biquadratic intermediary problems. Three methods were implemented to solve these intermediary problems: two classical descent methods, Newton and Gradient, and an adaptation of the Variational method. To evaluate the performance of the proposed methods, randomly generated examples were used and the Variational method was set as reference for comparing the results

Este trabalho trata do controle Markoviano aplicado a um robô manipulador visando obter um sistema tolerante a falhas. Os controladores H2, H&#8734, e H2/H&#8734 Markovianos são calculados e aplicados ao robô em diversas situações de operação. Os controladores obtidos mantiveram a estabilidade do sistema tanto em situações de operação normal, quanto em situações de falhas sucessivas. / This work deals with Markovian control applied to a robot manipulator, in an effort to obtain a fault tolerant system. The H2, H&#8734, and H2/H&#8734 controllers were calculated and applied to the robot in different operation situations. The obtained controllers guaranteed the stability of the system in both situations: normal operation, and successive faults operation.

Neste trabalho foi estudado um problema de controle de sistemas lineares com saltos Markovianos sem observação da variável de salto, que pode ser escrito como um problema de otimização de considerável complexidade. As contribuições para a área estão divididas em três aspectos. Um dos avanços foi a elaboração de um contraexemplo para a conjectura de que há somente um mínimo local isolado para o problema. Além disso, foi estudado o problema de otimização intermediário, que consiste em fixar todas as variáveis do problema exceto duas matrizes de ganhos, e os resultados indicam que, com uma pequena alteração na formulação, este é um problema biquadrático. Por fim, novos algoritmos foram elaborados a partir de um método disponível na literatura, chamado de método Variacional, adaptando-o para atualizar os ganhos aos pares, levando a problemas intermediários biquadráticos. Três métodos foram implementados para a resolução destes problemas: dois métodos clássicos de descida, Newton e Gradiente, e uma adaptação do próprio método Variacional. Para a análise dos resultados foram utilizados exemplos gerados aleatoriamente a partir do Gerador de SLSM, que pode ser encontrado na literatura, e o método Variacional como referência para comparação com os métodos propostos / This work addresses a control problem arising in linear systems with Markov jumps without observation of the jump variable and advances in three different aspects. First, it is presented a counterexample to the conjecture that states about the uniqueness of local minimum. Second, the intermediary optimization problem, which sets all the variables of the problem except two arrays of gains, was studied and the results suggested that a slight modification in the formulation makes the intermediary problem a biquadratic one. Finally, new algorithms were developed based on a method available in the literature, which is frequently referred to as the Variational method, adapting it to update the gains in pairs, leading to biquadratic intermediary problems. Three methods were implemented to solve these intermediary problems: two classical descent methods, Newton and Gradient, and an adaptation of the Variational method. To evaluate the performance of the proposed methods, randomly generated examples were used and the Variational method was set as reference for comparing the results

Cette thèse cherche à quantifier le temps de premier passage (FPT) d'un marcheur non-markovien sur une cible. La première partie est consacrée au calcul du temps moyen de premier passage (MFPT) pour différents processus non-markoviens confinés, pour lesquels les variables cachées sont connues. Notre méthode, qui adapte un formalisme existant, repose sur la détermination de la distribution des variables cachées au moment du FPT. Nous étendons ensuite ces idées à processus non-markoviens confinés généraux, sans introduire les variables cachées - en général inconnues. Nous montrons que le MFPT est entièrement déterminé par la position du marcheur dans le futur du FPT. Pour des processus gaussiens à incréments stationnaires, cette position est très proche d'une processus gaussien, hypothèse qui permet de déterminer ce processus de manière auto-cohérente, et donc de calculer le MFPT. Nous appliquons cette théorie à différents exemples en dimension variée, obtenant des résultats très précis quantitativement. Nous montrons également que notre théorie est exacte perturbativement autour d'une marche markovienne. Dans une troisième partie, nous explorons l'influence du vieillissement sur le FPT en confinement, et prédisons la dépendance en les paramètres géométriques de la distribution de ce FPT, prédictions vérifiées sur maints exemples. Nous montrons en particulier qu'une non-linéarité du MFPT avec le volume confinant est une caractéristique d'un processus vieillissant. Enfin, nous étudions les liens entre les problèmes avec et sans confinement. Notre travail permet entre autre de d'estimer l'exposant de persistance associé à des processus gaussiens non-markoviens vieillissant. / The aim of this thesis is the evaluation of the first-passage time (FPT) of a non-markovian walker over a target. The first part is devoted to the computation of the mean first-passage time (MFPT) for different non-markovien confined processes, for which hidden variables are explicitly known. Our methodology, which adapts an existing formalism, relies on the determination of the distribution of the hidden variables at the instant of FPT. Then, we extend these ideas to the case of general non-markovian confined processes, without introducing the -often unkown- hidden variables. We show that the MFPT is entirely determined by the position of the walker in the future of the FPT. For gaussian walks with stationary increments, this position can be accurately described by a gaussian process, which enable to determine it self-consistently, and thus to find the MFPT. We apply this theory on many examples, in various dimensions. We show moreover that this theory is exact perturbatively around markovian processes. In the third part, we explore the influence of aging properties on the the FPT in confinement, and we predict the dependence of its statistic on geometric parameters. We verify these predictions on many examples. We show in particular that the non-linearity of the MFPT with the confinement is a hallmark of aging. Finally, we study some links between confined and unconfined problems. Our work suggests a promising way to evaluate the persistence exponent of non-markovian gaussian aging processes.

All fields of physics - be it nuclear, atomic and molecular, solid state, or optical - offer examples of systems which are strongly influenced by the environment of the actual system under investigation. The scope of what is called "the environment" may vary, i.e., how far from the system of interest an interaction between the two does persist. Typically, however, it is much larger than the open system itself. Hence, a fully quantum mechanical treatment of the combined system without approximations and without limitations of the type of system is currently out of reach. With the single assumption of the environment to consist of an internally thermalized set of infinitely many harmonic oscillators, the seminal work of Stockburger and Grabert [Chem. Phys., 268:249-256, 2001] introduced an open system description that captures the environmental influence by means of a stochastic driving of the reduced system. The resulting stochastic Liouville-von Neumann equation describes the full non-Markovian dynamics without explicit memory but instead accounts for it implicitly through the correlations of the complex-valued noise forces. The present thesis provides a first application of the Stockburger-Grabert stochastic Liouville-von Neumann equation to the computation of the dynamics of anharmonic, continuous open systems. In particular, it is demonstrated that trajectory based propagators allow for the construction of a numerically stable propagation scheme. With this approach it becomes possible to achieve the tremendous increase of the noise sample count necessary to stochastically converge the results when investigating such systems with continuous variables. After a test against available analytic results for the dissipative harmonic oscillator, the approach is subsequently applied to the analysis of two different realistic, physical systems. As a first example, the dynamics of a dissipative molecular oscillator is investigated. Long time propagation - until thermalization is reached - is shown to be possible with the presented approach. The properties of the thermalized density are determined and they are ascertained to be independent of the system's initial state. Furthermore, the dependence on the bath's temperature and coupling strength is analyzed and it is demonstrated how a change of the bath parameters can be used to tune the system from the dissociative to the bound regime. A second investigation is conducted for a dissipative tunneling scenario in which a wave packet impinges on a barrier. The dependence of the transmission probability on the initial state's kinetic energy as well as the bath's temperature and coupling strength is computed. For both systems, a comparison with the high-temperature Markovian quantum Brownian limit is performed. The importance of a full non-Markovian treatment is demonstrated as deviations are shown to exist between the two descriptions both in the low temperature cases where they are expected and in some of the high temperature cases where their appearance might not be anticipated as easily.