published_or_final_version / abstract / toc / Mathematics / Master / Master of Philosophy

Thesis (Ph. D.)--University of Wisconsin--Madison, 1962. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Let P(ε) = P0 + A(ε) be a stochasticity preserving analytic perturbation of a stochastic matrix P0. We characterize the hybrid Cesaro limit lim 1 N(ε) Pk(ε), ε↓0 N(ε) ∑ where N(ε) ↑ ∞ as ε ↓ 0, when P0 has eigenvalues on the unit circle in the complex plane other than 1.

Thesis (M. Phil.)--University of Hong Kong, 1982.

published_or_final_version / Mathematics / Master / Master of Philosophy

Thesis (Ph. D.)--University of Washington, 2004. / Vita. Includes bibliographical references (p. 127-134).

Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaf 39).

We consider three problems in this dissertation, all under the unifying theme of random matrix products. The first and second problems are concerned with weak convergence in stochastic matrices and circulant matrices, respectively, and the third is concerned with the numerical calculation of the Lyapunov exponent associated with some random Fibonacci sequences. Stochastic matrices are nonnegative matrices whose row sums are all equal to 1. They are most commonly encountered as transition matrices of Markov chains. Circulant matrices, on the other hand, are matrices where each row after the first is just the previous row cyclically shifted to the right by one position. Like stochastic matrices, circulant matrices are ubiquitous in the literature.In the first problem, we study the weak convergence of the convolution sequence mu to the n, where mu is a probability measure with support S sub mu inside the space S of d by d stochastic matrices, d greater than or equal to 3. Note that mu to the n is precisely the distribution of the product X sub 1 times X sub 2 times and so on times X sub n of the mu distributed independent random variables X sub 1, X sub 2, and so on, X sub n taking values in S. In [CR] Santanu Chakraborty and B.V. Rao introduced a cyclicity condition on S sub mu and showed that this condition is necessary and sufficient for mu to the n to not converge weakly when d is equal to 3 and the minimal rank r of the matrices in the closed semigroup S generated by S sub mu is 2. Here, we extend this result to any d bigger than 3. Moreover, we show that when the minimal rank r is not 2, this result does not always hold.The second problem is an investigation of weak convergence in another direction, namely the case when the probability measure mu's support S sub mu consists of d by d circulant matrices, d greater than or equal to 3, which are not necessarily nonnegative. The resulting semigroup S generated by S sub mu now lacking the nice property of compactness in the case of stochastic matrices, we assume tightness of the sequence mu to the n to analyze the problem. Our approach is based on the work of Mukherjea and his collaborators, who in [LM] and [DM] presented a method based on a bookkeeping of the possible structure of the compact kernel K of S.The third problem considered in this dissertation is the numerical determination of Lyapunov exponents of some random Fibonacci sequences, which are stochastic versions of the classical Fibonacci sequence f sub (n plus 1) equals f sub n plus f sub (n minus 1), n greater than or equal to 1, and f sub 0 equal f sub 1 equals 1, obtained by randomizing one or both signs on the right side of the defining equation and or adding a "growth parameter." These sequences may be viewed as coming from a sequence of products of i.i.d. random matrices and their rate of growth measured by the associated Lyapunov exponent. Following techniques presented by Embree and Trefethen in their numerical paper [ET], we study the behavior of the Lyapunov exponents as a function of the probability p of choosing plus in the sign randomization.

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

La théorie des matrices s'est développée rapidement au cours des dernières décennies en raison de son large éventail d'applications et de ses nombreux liens avec différents domaines des mathématiques, de l'économie, de l'apprentissage automatique et du traitement du signal. Cette thèse concerne trois axes principaux liés à deux objets d'étude fondamentaux de la théorie des matrices et apparaissant naturellement dans de nombreuses applications, à savoir les matrices semi-définies positives et les matrices doublement stochastiques.Un concept qui découle naturellement du domaine de l'apprentissage automatique et qui est lié à la propriété semi-définie positive est celui des matrices de similarité. En fait, les matrices de similarité qui sont semi-définies positives revêtent une importance particulière en raison de leur capacité à définir des distances métriques. Cette thèse explorera la propriété semi-définie positive pour une liste de matrices de similarité trouvées dans la littérature. De plus, nous présentons de nouveaux résultats concernant les propriétés définie positive et semi-définie trois-positive de certains matrices de similarité. Une discussion détaillée des nombreuses applications de tous ces propriétés dans divers domaines est également établie.D'autre part, un problème récent de l'analyse matricielle implique l'étude des racines des matrices stochastiques, ce qui s'avère important dans les modèles de chaîne de Markov en finance. Nous étendons l'analyse de ce problème aux matrices doublement stochastiques semi-définies positives. Nous montrons d'abord certaines propriétés géométriques de l'ensemble de toutes les matrices semi-définies positives doublement stochastiques d'ordre n ayant la p-ième racine doublement stochastique pour un entier donné p . En utilisant la théorie des M-matrices et le problème inverse des valeurs propres des matrices symétriques doublement stochastiques (SDIEP), nous présentons également quelques méthodes pour trouver des classes de matrices semi-définies positives doublement stochastiques ayant des p-ièmes racines doublement stochastiques pour tout entier p.Dans le contexte du SDIEP, qui est le problème de caractériser ces listes de nombres réels qui puissent constituer le spectre d’une matrice symétrique doublement stochastique, nous présentons quelques nouveaux résultats le long de cette ligne. En particulier, nous proposons d’utiliser une méthode récursive de construction de matrices doublement stochastiques afin d'obtenir de nouvelles conditions suffisantes indépendantes pour SDIEP. Enfin, nous concentrons notre attention sur les spectres normalisés de Suleimanova, qui constituent un cas particulier des spectres introduits par Suleimanova. En particulier, nous prouvons que de tels spectres ne sont pas toujours réalisables et nous construisons trois familles de conditions suffisantes qui affinent les conditions suffisantes précédemment connues pour SDIEP dans le cas particulier des spectres normalisés de Suleimanova. / Matrix theory has shown its importance by its wide range of applications in different fields such as statistics, machine learning, economics and signal processing. This thesis concerns three main axis related to two fundamental objects of study in matrix theory and that arise naturally in many applications, that are positive semi-definite matrices and doubly stochastic matrices.One concept which stems naturally from machine learning area and is related to the positive semi-definite property, is the one of similarity matrices. In fact, similarity matrices that are positive semi-definite are of particular importance because of their ability to define metric distances. This thesis will explore the latter desirable structure for a list of similarity matrices found in the literature. Moreover, we present new results concerning the strictly positive definite and the three positive semi-definite properties of particular similarity matrices. A detailed discussion of the many applications of all these properties in various fields is also established.On the other hand, an interesting research field in matrix analysis involves the study of roots of stochastic matrices which is important in Markov chain models in finance and healthcare. We extend the analysis of this problem to positive semi-definite doubly stochastic matrices.Our contributions include some geometrical properties of the set of all positive semi-definite doubly stochastic matrices of order n with nonnegative pth roots for a given integer p. We also present methods for finding classes of positive semi-definite doubly stochastic matrices that have doubly stochastic pth roots for all p, by making use of the theory of M-Matrices and the symmetric doubly stochastic inverse eigenvalue problem (SDIEP), which is also of independent interest.In the context of the SDIEP, which is the problem of characterising those lists of real numbers which are realisable as the spectrum of some symmetric doubly stochastic matrix, we present some new results along this line. In particular, we propose to use a recursive method on constructing doubly stochastic matrices from smaller size matrices with known spectra to obtain new independent sufficient conditions for SDIEP. Finally, we focus our attention on the realizability by a symmetric doubly stochastic matrix of normalised Suleimanova spectra which is a normalized variant of the spectra introduced by Suleimanova. In particular, we prove that such spectra is not always realizable for odd orders and we construct three families of sufficient conditions that make a refinement for previously known sufficient conditions for SDIEP in the particular case of normalized Suleimanova spectra.