A Markov process is defined by its transition matrix. A skip-free Markov process is a stochastic system defined by a level that can only change by one unit either upwards or downwards. A regular perturbation is defined as a modification of one or more parameters that is small enough not to change qualitatively the model.<p>This thesis focuses on a category of methods, called matrix analytic methods, that has gained much interest because of good computational properties for the analysis of a large family of stochastic processes. Those methods are used in this work in order i) to analyze the effect of regular perturbations of the transition matrix on the stationary distribution of skip-free Markov processes; ii) to determine transient distributions of skip-free Markov processes by performing regular perturbations.<p>In the class of skip-free Markov processes, we focus in particular on quasi-birth-and-death (QBD) processes and Markov modulated fluid models.<p><p>We first determine the first order derivative of the stationary distribution - a key vector in Markov models - of a QBD for which we slightly perturb the transition matrix. This leads us to the study of Poisson equations that we analyze for finite and infinite QBDs. The infinite case has to be treated with more caution therefore, we first analyze it using probabilistic arguments based on a decomposition through first passage times to lower levels. Then, we use general algebraic arguments and use the repetitive block structure of the transition matrix to obtain all the solutions of the equation. The solutions of the Poisson equation need a generalized inverse called the deviation matrix. We develop a recursive formula for the computation of this matrix for the finite case and we derive an explicit expression for the elements of this matrix for the infinite case.<p><p>Then, we analyze the first order derivative of the stationary distribution of a Markov modulated fluid model. This leads to the analysis of the matrix of first return times to the initial level, a charactersitic matrix of Markov modulated fluid models.<p><p>Finally, we study the cumulative distribution function of the level in finite time and joint distribution functions (such as the level at a given finite time and the maximum level reached over a finite time interval). We show that our technique gives good approximations and allow to compute efficiently those distribution functions.<p><p><p>----------<p><p><p><p><p><p>Un processus markovien est défini par sa matrice de transition. Un processus markovien sans sauts est un processus stochastique de Markov défini par un niveau qui ne peut changer que d'une unité à la fois, soit vers le haut, soit vers le bas. Une perturbation régulière est une modification suffisamment petite d'un ou plusieurs paramètres qui ne modifie pas qualitativement le modèle.<p><p>Dans ce travail, nous utilisons des méthodes matricielles pour i) analyser l'effet de perturbations régulières de la matrice de transition sur le processus markoviens sans sauts; ii) déterminer des lois de probabilités en temps fini de processus markoviens sans sauts en réalisant des perturbations régulières. <p>Dans la famille des processus markoviens sans sauts, nous nous concentrons en particulier sur les processus quasi-birth-and-death (QBD) et sur les files fluides markoviennes. <p><p><p><p>Nous nous intéressons d'abord à la dérivée de premier ordre de la distribution stationnaire – vecteur clé des modèles markoviens – d'un QBD dont on modifie légèrement la matrice de transition. Celle-ci nous amène à devoir résoudre les équations de Poisson, que nous étudions pour les processus QBD finis et infinis. Le cas infini étant plus délicat, nous l'analysons en premier lieu par des arguments probabilistes en nous basant sur une décomposition par des temps de premier passage. En second lieu, nous faisons appel à un théorème général d'algèbre linéaire et utilisons la structure répétitive de la matrice de transition pour obtenir toutes les solutions à l’équation. Les solutions de l'équation de Poisson font appel à un inverse généralisé, appelé la matrice de déviation. Nous développons ensuite une formule récursive pour le calcul de cette matrice dans le cas fini et nous dérivons une expression explicite des éléments de cette dernière dans le cas infini.<p>Ensuite, nous analysons la dérivée de premier ordre de la distribution stationnaire d'une file fluide markovienne perturbée. Celle-ci nous amène à développer l'analyse de la matrice des temps de premier retour au niveau initial – matrice caractéristique des files fluides markoviennes. <p>Enfin, dans les files fluides markoviennes, nous étudions la fonction de répartition en temps fini du niveau et des fonctions de répartitions jointes (telles que le niveau à un instant donné et le niveau maximum atteint pendant un intervalle de temps donné). Nous montrerons que cette technique permet de trouver des bonnes approximations et de calculer efficacement ces fonctions de répartitions. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

<p>Dans ce travail nous abordons deux problèmes non résolus en Probabilité appliquée. Nous les approchons tous deux sous un angle nouveau, en utilisant des outils aussi variés que les chaînes de Markov, les mouvements Browniens, les transformations de Schwarz-Christoffel, les processus de Poisson et la théorie des temps d'arrêts optimaux. <p><p>Problème de la ruine pour N joueurs<p><p>Le problème de la ruine pour $N$ joueurs est un problème célèbre dont la solution pour $N=2$ est connue depuis longtemps. Nous l'abordons premièrement en toute généralité, en le modélisant comme un problème d'absorption pour une chaîne de Markov. Nous obtenons les distributions associées à ce problème et nous décrivons un algorithme (appelé {it folding algorithm}) permettant de diminuer considérablement le nombre d'opérations nécessaires à une résolution complète. Cette étude nous permet de mettre en avant un certain nombres de relations de récurrence satisfaites par les probabilités de ruines associées à chaque état de la chaîne de Markov. Nous étudions ensuite une version asymptotique du problème de la ruine pour 3 joueurs. Nous utilisons les propriétés d'invariance des mouvements Browniens par transformations conformes pour décrire une résolution de ce problème via les transformations de Schwarz-Christoffel. Cette méthode dépasse le cadre strict du problème de la ruine pour 3 joueurs et s'applique à d'autres problèmes de temps d'atteinte d'un bord par un mouvement Brownien. <p><p>Problème de Robbins<p><p>Ce problème s'inscrit dans le cadre de la théorie des temps d'arrêts optimaux. C'est un problème d'analyse séquentielle dans lequel un observateur examine $n$ variables aléatoires indépendantes de manière séquentielle et doit en sélectionner exactement une sans rappel. L'objectif est de déterminer une stratégie qui permette de minimiser le rang moyen de l'observation sélectionnée. <p><p> Nous décrivons un modèle alternatif de ce problème, dans lequel le décideur observe un nombre aléatoire d'arrivées distribuées suivant un processus de Poisson homogène sur un horizon fixe $t$. Nous prouvons l'existence d'une stratégie optimale pour chaque horizon, et nous montrons que la fonction de perte associée à cette stratégie est uniformément continue sur $R$. Nous décrivons une fonction de perte restreinte qui permet d'obtenir une estimation de la valeur asymptotique du problème, et nous obtenons la valeur asymptotique associée à des stratégies spécifiques. Nous obtenons ensuite une équation intégro-diffférentielle sur la fonction de perte associée à la stratégie optimale. Finalement nous étudions les valeurs asymptotiques du problème et nous les comparons à celles du problème en temps discret. Nous concluons cette thèse en décrivant des stratégies spécifiques qui permettent d'obtenir des estimations sur le comportement asymptotique de la fonction de perte. <p><p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Les files d'attente fluides sont des processus markoviens à deux dimensions, où la première composante, appelée le niveau, représente le contenu d'un réservoir et prend des valeurs continues, et la deuxième composante, appelée la phase, est l'état d'un processus markovien dont l'évolution contrôle celle du niveau. Le niveau de la file fluide varie linéairement avec un taux qui dépend de la phase et qui peut prendre n'importe quelle valeur réelle.<p><p>Dans cette thèse, nous explorons le lien entre les files fluides et les processus QBD, et nous appliquons des arguments utilisés en théorie des processus de renouvellement pour obtenir la distribution stationnaire de plusieurs modèles fluides.<p><p>Nous commençons par l'étude d'une file fluide avec un réservoir de taille infinie; nous déterminons sa distribution stationnaire, et nous présentons un algorithme permettant de calculer cette distribution de manière très efficace. Nous observons que la distribution stationnaire de la file fluide de capacité infinie est très semblable à celle d'un processus QBD avec une infinité de niveaux. Nous poursuivons la recherche des similarités entre les files fluides et les processus QBD, et nous étudions ensuite la distribution stationnaire d'une file fluide de capacité finie. Nous montrons que l'algorithme valable pour le cas du réservoir infini permet de calculer toutes les quantités importantes du modèle avec un réservoir fini.<p><p>Nous considérons ensuite des modèles fluides plus complexes, de capacité finie ou infinie, où le comportement du processus markovien des phases peut changer lorsque le niveau du réservoir atteint certaines valeurs seuils. Nous montrons que les méthodes développées pour des modèles classiques s'étendent de manière naturelle à ces modèles plus complexes.<p><p>Pour terminer, nous étudions les conditions nécessaires et suffisantes qui mènent à l'indépendance du niveau et de la phase d'une file fluide de capacité infinie en régime stationnaire. Ces résultats s'appuient sur des résultats semblables concernant des processus QBD.<p><p>Markov modulated fluid queues are two-dimensional Markov processes, of which the first component, called the level, represents the content of a buffer or reservoir and takes real values; the second component, called the phase, is the state of a Markov process which controls the evolution of the level in the following manner: the level varies linearly at a rate which depends on the phase and which can take any real value.<p><p>In this thesis, we explore the link between fluid queues and Quasi Birth-and-Death (QBD) processes, and we apply Markov renewal techniques in order to derive the stationary distribution of various fluid models.<p><p>To begin with, we study a fluid queue with an infinite capacity buffer; we determine its stationary distribution and we present an algorithm which performs very efficiently in the determination of this distribution. We observe that the equilibrium distribution of the fluid queue is very similar to that of a QBD process with infinitely many levels. We further exploit the similarity between the two processes, and we determine the stationary distribution of a finite capacity fluid queue. We show that the algorithm available in the infinite case allows for the computation of all the important quantities entering in the expression of this distribution.<p><p>We then consider more complex models, of either finite or infinite capacities, in which the behaviour ff the phase process may change whenever the buffer is empty or full, or when it reaches certain thresholds. We show that the techniques that we develop for the simpler models can be extended quite naturally in this context.<p><p>Finally, we study the necessary and sufficient conditions that lead to the independence between the level and the phase of an infinite capacity fluid queue in the stationary regime. These results are based on similar developments for QBD processes. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished