Spelling suggestions: "subject:"markov process"" "subject:"darkov process""
101 |
Contributions aux méthodes de branchement multi-niveaux pour les évènements rares, et applications au trafic aérien / Contributions to multilevel splitting for rare events, and applications to air trafficJacquemart, Damien 08 December 2014 (has links)
La thèse porte sur la conception et l'analyse mathématique de méthodes de Monte Carlo fiables et précises pour l'estimation de la (très petite) probabilité qu'un processus de Markov atteigne une région critique de l'espace d'état avant un instant final déterministe. L'idée sous-jacente aux méthodes de branchement multi-niveaux étudiées ici est de mettre en place une suite emboitée de régions intermédiaires de plus en plus critiques, de telle sorte qu'atteindre une région intermédiaire donnée sachant que la région intermédiaire précédente a déjà été atteinte, n'est pas si rare. En pratique, les trajectoires sont propagées, sélectionnées et répliquées dès que la région intermédiaire suivante est atteinte, et il est facile d'estimer avec précision la probabilité de transition entre deux régions intermédiaires successives. Le biais dû à la discrétisation temporelle des trajectoires du processus de Markov est corrigé en utilisant des régions intermédiaires perturbées, comme proposé par Gobet et Menozzi. Une version adaptative consiste à définir automatiquement les régions intermédiaires, à l’aide de quantiles empiriques. Néanmoins, une fois que le seuil a été fixé, il est souvent difficile voire impossible de se rappeler où (dans quel état) et quand (à quel instant) les trajectoires ont dépassé ce seuil pour la première fois, le cas échéant. La contribution de la thèse consiste à utiliser une première population de trajectoires pilotes pour définir le prochain seuil, à utiliser une deuxième population de trajectoires pour estimer la probabilité de dépassement du seuil ainsi fixé, et à itérer ces deux étapes (définition du prochain seuil, et évaluation de la probabilité de transition) jusqu'à ce que la région critique soit finalement atteinte. La convergence de cet algorithme adaptatif à deux étapes est analysée dans le cadre asymptotique d'un grand nombre de trajectoires. Idéalement, les régions intermédiaires doivent êtres définies en terme des variables spatiale et temporelle conjointement (par exemple, comme l'ensemble des états et des temps pour lesquels une fonction scalaire de l’état dépasse un niveau intermédiaire dépendant du temps). Le point de vue alternatif proposé dans la thèse est de conserver des régions intermédiaires simples, définies en terme de la variable spatiale seulement, et de faire en sorte que les trajectoires qui dépassent un seuil précocement sont davantage répliquées que les trajectoires qui dépassent ce même seuil plus tardivement. L'algorithme résultant combine les points de vue de l'échantillonnage pondéré et du branchement multi-niveaux. Sa performance est évaluée dans le cadre asymptotique d'un grand nombre de trajectoires, et en particulier un théorème central limite est obtenu pour l'erreur d'approximation relative. / The thesis deals with the design and mathematical analysis of reliable and accurate Monte Carlo methods in order to estimate the (very small) probability that a Markov process reaches a critical region of the state space before a deterministic final time. The underlying idea behind the multilevel splitting methods studied here is to design an embedded sequence of intermediate more and more critical regions, in such a way that reaching an intermediate region, given that the previous intermediate region has already been reached, is not so rare. In practice, trajectories are propagated, selected and replicated as soon as the next intermediate region is reached, and it is easy to accurately estimate the transition probability between two successive intermediate regions. The bias due to time discretization of the Markov process trajectories is corrected using perturbed intermediate regions as proposed by Gobet and Menozzi. An adaptive version would consist in the automatic design of the intermediate regions, using empirical quantiles. However, it is often difficult if not impossible to remember where (in which state) and when (at which time instant) did each successful trajectory reach the empirically defined intermediate region. The contribution of the thesis consists in using a first population of pilot trajectories to define the next threshold, in using a second population of trajectories to estimate the probability of exceeding this empirically defined threshold, and in iterating these two steps (definition of the next threshold, and evaluation of the transition probability) until the critical region is reached. The convergence of this adaptive two-step algorithm is studied in the asymptotic framework of a large number of trajectories. Ideally, the intermediate regions should be defined in terms of the spatial and temporal variables jointly (for example, as the set of states and times for which a scalar function of the state exceeds a time-dependent threshold). The alternate point of view proposed in the thesis is to keep intermediate regions as simple as possible, defined in terms of the spatial variable only, and to make sure that trajectories that manage to exceed a threshold at an early time instant are more replicated than trajectories that exceed the same threshold at a later time instant. The resulting algorithm combines importance sampling and multilevel splitting. Its preformance is evaluated in the asymptotic framework of a large number of trajectories, and in particular a central limit theorem is obtained for the relative approximation error.
|
102 |
Étude d’algorithmes de simulation par chaînes de Markov non réversiblesHuguet, Guillaume 10 1900 (has links)
Les méthodes de Monte Carlo par chaînes de Markov (MCMC) utilisent généralement des
chaînes de Markov réversibles. Jusqu’à récemment, une grande partie de la recherche théorique
sur les chaînes de Markov concernait ce type de chaînes, notamment les théorèmes de
Peskun (1973) et de Tierney (1998) qui permettent d’ordonner les variances asymptotiques
de deux estimateurs issus de chaînes réversibles différentes.
Dans ce mémoire nous analysons des algorithmes simulants des chaînes qui ne respectent
pas cette condition. Nous parlons alors de chaînes non réversibles. Expérimentalement, ces
chaînes produisent souvent des estimateurs avec une variance asymptotique plus faible et/ou
une convergence plus rapide. Nous présentons deux algorithmes, soit l’algorithme de marche
aléatoire guidée (GRW) par Gustafson (1998) et l’algorithme de discrete bouncy particle
sampler (DBPS) par Sherlock et Thiery (2017). Pour ces deux algorithmes, nous comparons
expérimentalement la variance asymptotique d’un estimateur avec la variance asymptotique
en utilisant l’algorithme de Metropolis-Hastings.
Récemment, un cadre théorique a été introduit par Andrieu et Livingstone (2019) pour
ordonner les variances asymptotiques d’une certaine classe de chaînes non réversibles. Nous
présentons leur analyse de GRW. De plus, nous montrons que le DBPS est inclus dans
ce cadre théorique. Nous démontrons que la variance asymptotique d’un estimateur peut
théoriquement diminuer en ajoutant des propositions à cet algorithme. Finalement, nous
proposons deux modifications au DBPS.
Tout au long du mémoire, nous serons intéressés par des chaînes issues de propositions
déterministes. Nous montrons comment construire l’algorithme du delayed rejection avec
des fonctions déterministes et son équivalent dans le cadre de Andrieu et Livingstone (2019). / Markov chain Monte Carlo (MCMC) methods commonly use chains that respect the detailed
balance condition. These chains are called reversible. Most of the theory developed for
MCMC evolves around those particular chains. Peskun (1973) and Tierney (1998) provided
useful theorems on the ordering of the asymptotic variances for two estimators produced by
two different reversible chains.
In this thesis, we are interested in non-reversible chains, which are chains that don’t
respect the detailed balance condition. We present algorithms that simulate non-reversible
chains, mainly the Guided Random Walk (GRW) by Gustafson (1998) and the Discrete
Bouncy Particle Sampler (DBPS) by Sherlock and Thiery (2017). For both algorithms, we
compare the asymptotic variance of estimators with the ones produced by the Metropolis-
Hastings algorithm.
We present a recent theoretical framework introduced by Andrieu and Livingstone (2019)
and their analysis of the GRW. We then show that the DBPS is part of this framework
and present an analysis on the asymptotic variance of estimators. Their main theorem
can provide an ordering of the asymptotic variances of two estimators resulting from nonreversible
chains. We show that an estimator could have a lower asymptotic variance by
adding propositions to the DBPS. We then present empirical results of a modified DBPS.
Through the thesis we will mostly be interested in chains that are produced by deterministic
proposals. We show a general construction of the delayed rejection algorithm using
deterministic proposals and one possible equivalent for non-reversible chains.
|
103 |
Simulátor provozu stanic s kmitočtovým skákáním a vyhýbáním se kolizí / Simulator of stations with frequency hopping and collision avoidanceAkkizová, Dinara January 2011 (has links)
The master's thesis aims to introduce and study the issue of frequency hopping with collsion avoidance (FH/CA). On this basis, design a computer program for simulating the operation of a radio systém FHCA, who works in the band used by other systems FH/CA . This simulation programm using MATLAB software to implement verify the correctness of programs. Use simulator to obtain date about the intensity of interference systems FH/CA for the chosen scenario. This work consists of five parts: the first part consists of describing the queuing system, the second part of the description of the radio frequency system with collision avoidence FH / CA, the third part of the description of the simulation model. The fourth part includes verification of the model in the fifth and last section inspects results are shown.
|
104 |
Spolehlivost technických systémů / Reliability of Technical SystemsErtl, Jakub January 2009 (has links)
The diploma project is focused on investigating the reliability of multi-state technical systems. A summary of the basic conception of renewal theory and stochastic processes is given in this paper. The possibility of solving multi-state systems reliability by using Markov models or simulation is shown. The software Reliab. S. M. S. O. 1.0 was created for solving non-homogeneous series, parallel, series-parallel and parallel-series systems. Outputs of this software are described in chapter 10. This work also contains $\beta$-factor method and theory of common-cause failures. The diploma project was supported by project from MSMT of the Czech Republic no. 1M06047 "Centre for Quality and Reliability of Production" and by grant from Grant Agency of the Czech Republic (Czech Science Foundation) reg. no. 103/08/1658 "Advanced optimum design of composed concrete structures".
|
105 |
Acceleration Strategies of Markov Chain Monte Carlo for Bayesian Computation / Stratégies d'accélération des algorithmes de Monte Carlo par chaîne de Markov pour le calcul BayésienWu, Chang-Ye 04 October 2018 (has links)
Les algorithmes MCMC sont difficiles à mettre à l'échelle, car ils doivent balayer l'ensemble des données à chaque itération, ce qui interdit leurs applications dans de grands paramètres de données. En gros, tous les algorithmes MCMC évolutifs peuvent être divisés en deux catégories: les méthodes de partage et de conquête et les méthodes de sous-échantillonnage. Le but de ce projet est de réduire le temps de calcul induit par des fonctions complexes ou à grande efficacité. / MCMC algorithms are difficult to scale, since they need to sweep over the whole data set at each iteration, which prohibits their applications in big data settings. Roughly speaking, all scalable MCMC algorithms can be divided into two categories: divide-and-conquer methods and subsampling methods. The aim of this project is to reduce the computing time induced by complex or largelikelihood functions.
|
106 |
The Symbol of a Markov SemimartingaleSchnurr, Alexander 27 April 2009 (has links)
We prove that every (nice) Feller process is an It^o process in the sense of Cinlar, Jacod, Protter and Sharpe (1980). Next we generalize the notion of the symbol and define it for this larger class of processes. As examples the solutions of stochastic differential equations are considered. The symbol is then used to derive a quick approach to the semimartingale characteristics as well as the generator of the process under consideration. Finally we give some examples of how our methods work for processes used in mathematical finance. / Wir haben gezeigt, dass jeder (nette) Feller Prozess ein It^o Prozess im Sinne von Cinlar, Jacod, Protter und Sharpe (1980) ist. Es stellt sich heraus, dass man den Begriff des Symbols, der für Feller Prozesse bekannt ist, auf diese größere Klasse verallgemeinern kann. Dieses Symbol haben wir für die Lösungen verschiedener stochastischer Differentialgleichungen berechnet. Außerdem haben wir gezeigt, dass das Symbol einen schnellen Zugang zur Berechnung der Semimartingal-Charakteristiken und des Erzeugers eines It^o Prozesses liefert. Zuletzt wurden die Ergebnisse auf Prozesse angewendet, die in der Finanzmathematik gebräuchlich sind. - (Die Dissertation ist veröffentlicht im Shaker Verlag GmbH, Postfach 101818, 52018 Aachen, Deutschland, http://www.shaker.de, ISBN: 978-3-8322-8244-8)
|
107 |
Probability Based Path Planning of Unmanned Ground Vehicles for Autonomous Surveillance : Through World Decomposition and Modelling of Target DistributionLiljeström, Per January 2022 (has links)
The interest in autonomous surveillance has increased due to advances in autonomous systems and sensor theory. This thesis is a preliminary study of the cooperation between UGVs and stationary sensors when monitoring a dedicated area. The primary focus is the path planning of a UGV for different initial intrusion alarms. Cell decomposition, i.e., spatial partitioning, of the area of surveillance was utilized, and the objective function is based on the probability of a present intruder in each cell. These probabilities were modeled through two different methods: ExpPlanner, utilizing an exponential decay function. Markov planner, utilizing a Markov chain to propagate the probabilities. The performance of both methods improves when a confident alarm system is utilized. By prioritizing the direction of the planned paths, the performances improved further. The Markov planner outperforms the ExpPlanner in finding a randomly walking intruder. The ExpPlanner is suitable for passive surveillance, and the Markov planner is suitable for ”aggressive target hunting”.
|
108 |
Passeios aleatórios em redes finitas e infinitas de filas / Random walks in finite and infinite queueing networksGannon, Mark Andrew 27 April 2017 (has links)
Um conjunto de modelos compostos de redes de filas em grades finitas servindo como ambientes aleatorios para um ou mais passeios aleatorios, que por sua vez podem afetar o comportamento das filas, e desenvolvido. Duas formas de interacao entre os passeios aleatorios sao consideradas. Para cada modelo, e provado que o processo Markoviano correspondente e recorrente positivo e reversivel. As equacoes de balanceamento detalhado sao analisadas para obter a forma funcional da medida invariante de cada modelo. Em todos os modelos analisados neste trabalho, a medida invariante em uma grade finita tem forma produto. Modelos de redes de filas como ambientes para multiplos passeios aleatorios sao estendidos a grades infinitas. Para cada modelo estendido, sao especificadas as condicoes para a existencia do processo estocastico na grade infinita. Alem disso, e provado que existe uma unica medida invariante na rede infinita cuja projecao em uma subgrade finita e dada pela medida correspondente de uma rede finita. Finalmente, e provado que essa medida invariante na rede infinita e reversivel. / A set of models composed of queueing networks serving as random environments for one or more random walks, which themselves can affect the behavior of the queues, is developed. Two forms of interaction between the random walkers are considered. For each model, it is proved that the corresponding Markov process is positive recurrent and reversible. The detailed balance equa- tions are analyzed to obtain the functional form of the invariant measure of each model. In all the models analyzed in the present work, the invariant measure on a finite lattice has product form. Models of queueing networks as environments for multiple random walks are extended to infinite lattices. For each model extended, the conditions for the existence of the stochastic process on the infinite lattice are specified. In addition, it is proved that there exists a unique invariant measure on the infinite network whose projection on a finite sublattice is given by the corresponding finite- network measure. Finally, it is proved that that invariant measure on the infinite lattice is reversible.
|
109 |
Passeios aleatórios em redes finitas e infinitas de filas / Random walks in finite and infinite queueing networksMark Andrew Gannon 27 April 2017 (has links)
Um conjunto de modelos compostos de redes de filas em grades finitas servindo como ambientes aleatorios para um ou mais passeios aleatorios, que por sua vez podem afetar o comportamento das filas, e desenvolvido. Duas formas de interacao entre os passeios aleatorios sao consideradas. Para cada modelo, e provado que o processo Markoviano correspondente e recorrente positivo e reversivel. As equacoes de balanceamento detalhado sao analisadas para obter a forma funcional da medida invariante de cada modelo. Em todos os modelos analisados neste trabalho, a medida invariante em uma grade finita tem forma produto. Modelos de redes de filas como ambientes para multiplos passeios aleatorios sao estendidos a grades infinitas. Para cada modelo estendido, sao especificadas as condicoes para a existencia do processo estocastico na grade infinita. Alem disso, e provado que existe uma unica medida invariante na rede infinita cuja projecao em uma subgrade finita e dada pela medida correspondente de uma rede finita. Finalmente, e provado que essa medida invariante na rede infinita e reversivel. / A set of models composed of queueing networks serving as random environments for one or more random walks, which themselves can affect the behavior of the queues, is developed. Two forms of interaction between the random walkers are considered. For each model, it is proved that the corresponding Markov process is positive recurrent and reversible. The detailed balance equa- tions are analyzed to obtain the functional form of the invariant measure of each model. In all the models analyzed in the present work, the invariant measure on a finite lattice has product form. Models of queueing networks as environments for multiple random walks are extended to infinite lattices. For each model extended, the conditions for the existence of the stochastic process on the infinite lattice are specified. In addition, it is proved that there exists a unique invariant measure on the infinite network whose projection on a finite sublattice is given by the corresponding finite- network measure. Finally, it is proved that that invariant measure on the infinite lattice is reversible.
|
110 |
Hodnocení zdravotní technologie (HTA): léčba karcinomu prsu, případová studie ČR / Health technology assessment: case study on breast carcinoma treatment in the Czech RepublicŠlegerová, Lenka January 2019 (has links)
Health technology assessment: case study on breast carcinoma treatment in the Czech Republic Bc. Lenka Šlegerová January 4, 2019 Abstract This thesis proposes an original method for assessing total costs of med- ical treatment. It defines the semi-Markov model with four states that are associated with specific costs of the treatment, and not with patients' health statuses. This method is applied to individuals' treatment data drawn from the Czech clinical practice in the treatment of the metastatic HER2+ breast cancer. The aim is to assess the cost-effectiveness of adding medication per- tuzumab to the combination of trastuzumab+docetaxel within first-line therapy and to examine whether using individual data on Czech patients and the economic conditions leads to different results from foreign stud- ies. Furthermore, employing censored data from the clinical practice in the thesis complicates the estimation of patients' overall survival in compari- son to clinical-trials data that form random samples. Therefore, survival functions were not only estimated by the Kaplan-Meier estimator but also using the Cox proportional hazard model and the Accelerated failure time model that both control for the effects of included covariates. The addition of pertuzumab does not result in significantly longer pa- tients'...
|
Page generated in 0.045 seconds