L'objectif de ce travail est de proposer de nouveaux estimateurs de quantiles extrêmes dans le cadre conditionnel c'est-à-dire dans la situation où la variable d'intérêt Y, supposée aléatoire et réelle, est mesurée simultanément avec une covariable X. Pour ce faire, nous nous intéressons à l'étude des valeurs extrêmes d'un échantillon d'observations indépendantes dont la loi conditionnelle de Y en un point x de la covariable X est à " queue lourde ". Selon la nature de la covariable, nous considérons deux situations. Primo, lorsque la covariable est déterministe et de dimension finie ou infinie (i.e covariable fonctionnelle), nous proposons d'estimer les quantiles extrêmes par la méthode dite de la " fenêtre mobile ". La loi limite des estimateurs ainsi construits est ensuite donnée en fonction de la vitesse de convergence de l'ordre du quantile vers un. Secundo, lorsque la covariable est aléatoire et de dimension finie, nous montrons que sous certaines conditions, il est possible d'estimer les quantiles extrêmes conditionnels au moyen d'un estimateur à " noyau " de la fonction de survie conditionnelle. Ce résultat nous permet d'introduire deux versions lisses de l'estimateur de l'indice de queue conditionnel indispensable lorsque l'on veut extrapoler. Nous établissons la loi asymptotique de ces estimateurs. Par ailleurs, nous considérons le cas sans covariable (non conditionnel) lorsque la fonction de répartition est à " queue lourde ". Nous proposons et étudions un nouvel estimateur des quantiles extrêmes. Afin d'apprécier le comportement de nos nouveaux outils statistiques, des résultats sur simulation ainsi que sur des données réelles sont présentés.

In this dissertation, we consider a complex biological system known as cortical microtubule (CMT) system, where stochastic dynamics of the components (i.e., the CMTs) are defined in both space and time. CMTs have an inherent spatial dimension of their own, as their length changes over time in addition to their location. As a result of their dynamics in a confined space, they run into and interact with each other according to simple stochastic rules. Over time, CMTs acquire an ordered structure that is achieved without any centralized control beginning with a completely disorganized system. It is also observed that this organization might be distorted, when parameters of dynamicity and interactions change due to genetic mutation or environmental conditions. The main question of interest is to explore the characteristics of this system and the drivers of its self-organization, which is not feasible relying solely on biological experiments. For this, we replicate the system dynamics and interactions using computer simulations. As the simulations successfully mimic the organization seen in plant cells, we conduct an extensive analysis to discover the effects of dynamics and interactions on system characteristics by experimenting with different input parameters. To compare simulation results, we characterize system properties and quantify organization level using metrics based on entropy, average length and number of CMTs in the system. Based on our findings and conjectures from simulations, we develop analytical models for more generalized conclusions and efficient computation of system metrics. As a fist step, we formulate a mean-field model, which we use to derive sufficient conditions for organization to occur in terms of input parameters. Next, considering the parameter ranges that satisfy these conditions, we develop predictive methodologies for estimation of expected average length and number of CMTs over time, using a fluid model, transient analysis, and approximation algorithms tailored to our problem. Overall, we build a comprehensive framework for analysis and control of microtubule organization in plant cells using a wide range of models and methodologies in conjunction. This research also has broader impacts related to the fields of bio-energy, healthcare, and nanotechnology; in addition to its methodological contribution to stochastic modeling of systems with high-level spatial and temporal complexity.

The increasing usage of information technology in military affairs raises the need for robust high capacity radio networks. The network will be used to provide several different types of services, for example group calls and situation awareness services. All services have specific demands on packet delays and packet losses in order to be fully functional, and therefore there is a need for a Quality of Service (QoS) mechanism in the network. In this master thesis we examine the possibility to provide a QoS mechanism in Ad Hoc networks by using priority queues. The study includes two different queuing schemes, namely fixed priority queuing and weighted fair queuing. The performance of the two queuing schemes are evaluated and compared with respect to the ability to provide differentiation in network delay, i.e., provide high priority traffic with lower delays than low priority traffic. The study is mainly done by simulations, but for fixed priority queuing we also derive a analytical approximation of the network delay. Our simulations show that fixed priority queuing provides a sharp delay differentiation between service classes, while weighted fair queuing gives the ability to control the delay differentiation. One of those queuing schemes alone might not be the best solution for providing QoS, instead we suggest that a combination of them is used.

We provide contributions to two classical areas of queueing. The first part of this thesis focuses on finding new conditions for a Markov chain on a general state space to be Harris recurrent, positive Harris recurrent or geometrically ergodic. Most of our results show that establishing each property listed above is equivalent to finding a good enough feasible solution to a particular optimal stopping problem, and they provide a more complete understanding of the role Foster's criterion plays in the theory of Markov chains. The second and third parts of the thesis involve analyzing queues from a transient, or time-dependent perspective. In part two, we are interested in looking at a queueing system from the perspective of a customer that arrives at a fixed time t. Doing this requires us to use tools from Palm theory. From an intuitive standpoint, Palm probabilities provide us with a way of computing probabilities of events, while conditioning on sets of measure zero. Many studies exist in the literature that deal with Palm probabilities for stationary systems, but very few treat the non-stationary case. As an application of our main results, we show that many classical results from queueing (in particular ASTA and Little's law) can be generalized to a time-dependent setting. In part three, we establish a continuity result for what we refer to as jump processes. From a queueing perspective, we basically show that if the primitives and the initial conditions of a sequence of queueing processes converge weakly, then the corresponding queue-length processes converge weakly as well in some sense. Here the notion of convergence used depends on properties of the limiting process, therefore our results generalize classical continuity results that exist in the literature. The way our results can be used to approximate queueing systems is analogous to the way phase-type random variables can be used to approximate other types of random variables.

Stochastic fluctuations can have profound impacts on engineered systems. Nonetheless, we can achieve significant benefits such as cost reduction based upon expanding our fundamental knowledge of stochastic systems. The primary goal of this thesis is to contribute to our understanding by developing and analyzing stochastic models for specific types of engineered systems. The knowledge gained can help management to optimize decision making under uncertainty. This thesis has three parts. In Part I, we study many-server queues that model large-scale service systems such as call centers. We focus on the positive recurrence of piecewise Ornstein-Uhlenbeck (OU) processes and the validity of using these processes to predict the steady-state performance of the corresponding many-server queues. In Part II, we investigate diffusion processes constrained to the positive orthant under infinitesimal changes in the drift. This sensitivity analysis on the drift helps us understand how changes in service capacities at individual stations in a stochastic network would affect the steady-state queue-length distributions. In Part III, we study the trading mechanism known as limit order book. We are motivated by a desire to better understand the interplay among order flow rates, liquidity fluctuation, and optimal executions. The goal is to characterize the temporal evolution of order book shape on the “macroscopic” time scale.

In this paper we will show how recent advances in the combinatorics of lattice paths can be applied to solve interesting and nontrivial problems in the theory of queues. The problems we discuss range from classical ones like M^a/M^b/1 systems to open tandem systems with and without global blocking and to queueing models that are related to random walks in a quarter plane like the Flatto-Hahn model or systems with preemptive priorities. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics

The purpose of the research presented here is twofold. The first component explores the probabilistic interpretation of Stein’s method, as introduced in Barbour (1988). This is done in the setting of random variable approximations. This probabilistic method, where the Stein equation is interpreted in terms of the generator of an underlying birth and death process having equilibrium distribution equal to that of the approximant, provides a natural explanation of why Stein’s method works. An open problem has been to use this generator approach to obtain bounds on the differences of the solution to the Stein equation. Uniform bounds on these differences produce Stein “magic” factors, which control the bounds. With the choice of unit per capita death rate for the birth and death process, we are able to produce a result giving a new Stein factor bound, which applies to a selection of distributions. The proof is via a probabilistic approach, and we also include a probabilistic proof of a Stein factor bound from Barbour, Holst and Janson (1992). These results generalise the work of Xia (1999), which applies to the Poisson distribution with unit per capita death rate. (For complete abstract open document)

Parallel processing is prevalent in many manufacturing and service systems. Many manufactured products are built and assembled from several components fabricated in parallel lines. An example of this manufacturing system configuration is observed at a manufacturing facility equipped to assemble and test web servers. Characteristics of a typical web server assembly line are: multiple products, job circulation, and paralleling processing. The primary objective of this research was to develop analytical approximations to predict performance measures of manufacturing systems with job failures and parallel processing. The analytical formulations extend previous queueing models used in assembly manufacturing systems in that they can handle serial and different configurations of paralleling processing with multiple product classes, and job circulation due to random part failures. In addition, appropriate correction terms via regression analysis were added to the approximations in order to minimize the gap in the error between the analytical approximation and the simulation models. Markovian and general type manufacturing systems, with multiple product classes, job circulation due to failures, and fork and join systems to model parallel processing were studied. In the Markovian and general case, the approximations without correction terms performed quite well for one and two product problem instances. However, it was observed that the flow time error increased as the number of products and net traffic intensity increased. Therefore, correction terms for single and fork-join stations were developed via regression analysis to deal with more than two products. The numerical comparisons showed that the approximations perform remarkably well when the corrections factors were used in the approximations. In general, the average flow time error was reduced from 38.19% to 5.59% in the Markovian case, and from 26.39% to 7.23% in the general case. All the equations stated in the analytical formulations were implemented as a set of Matlab scripts. By using this set, operations managers of web server assembly lines, manufacturing or other service systems with similar characteristics can estimate different system performance measures, and make judicious decisions - especially setting delivery due dates, capacity planning, and bottleneck mitigation, among others.

No description available.

Cette thèse porte sur l'efficacité des algorithmes distribués de partage des ressources et des algorithmes de découvert de chemin en ligne. Dans la première partie de la thèse, nous analysons un jeu dans lequel les utilisateurs paient pour utiliser une ressource partagée. La ressource allouée à un utilisateur est directement proportionnel à son paiement. Chaque utilisateur veut minimiser son paiement en assurant une certaine qualité de service. Ce problème est modélisé comme un jeu non-coopératif de partage des ressources. A cause du manque des expressions analytiques de la discipline de file d'attente sous-jacente, nous pouvons résoudre le jeu que sous certaines hypothèses. Pour le cas général, nous développons une approximation basée sur un résultat fort trafic et nous validons la précision de l'approximation numériquement.Dans la deuxième partie, nous étudions l'efficacité des jeux de balance de charge, c'est à dire, nous comparons la perte de performance de routage non coopératif décentralisé avec un routage centralisé. Nous montrons que le PoA est une mesure très pessimiste car il est atteint que dans des cas pathologiques. Dans la plupart des scénarios, les implémentations distribués de balance de charge effectuent presque aussi bien que la mise en œuvre centralisée optimale.Dans la dernière partie de la thèse, nous analysons problème de découverte chemin optimal dans les graphes complets. En ce problème, les valeurs des arêtes sont inconnues, mais peuvent être interrogés. Pour une fonction donnée qui est appliquée à des chemins, l'objectif est de trouver un meilleur chemin de valeur à partir d'une source vers une destination donnée interrogation le plus petit nombre de bords. Nous vous proposons le rapport de requête en tant que mesure de l'efficacité des algorithmes qui permettent de résoudre ce problème. Nous prouvons une limite inférieure pour ne importe quel algorithme qui résout ce problème et nous avons proposé un algorithme avec un rapport de requête strictement inférieure à 2. / This thesis deals with the efficiency of distributed resource sharing algorithms and of online path discovery algorithms. In the first part of the thesis, we analyse a game in which users pay for using a shared resource. The allocated resource to a user is directly proportional to its payment. Each user wants to minimize its payment while ensuring a certain quality of service. This problem is modelled as a non-cooperative resource-sharing game. Due to lack of analytical expressions for the underlying queuing discipline, we are able to give the solution of the game only under some assumptions. For the general case, we develop an approximation based on a heavy-traffic result and we validate the accuracy of the approximation numerically. In the second part, we study the efficiency of load balancing games, i.e., we compare the loss in performance of noncooperative decentralized routing with a centralized routing. We show that the PoA is very pessimistic measure since it is achieved in only pathological cases. In most scenarios, distributed implementations of load-balancing perform nearly as well as the optimal centralized implementation. In the last part of the thesis, we analyse the optimal path discovery problem in complete graphs. In this problem, the values of the edges are unknown but can be queried. For a given function that is applied to paths, the goal is to find a best value path from a source to a given destination querying the least number of edges. We propose the query ratio as efficiency measure of algorithms that solve this problem. We prove a lower-bound for any algorithm that solves this problem and we proposed an algorithm with query ratio strictly less than 2.