Imperial College London bachelor of science final report Lie Algebras and Markovian Arrival Processes Supervisor: Prof. Peter Harrison Author: Ashmi Mehta Second-Supervisor: Dr. Giuliano Casale Abstract Liealgebraisamathematicalconceptthatinvolvesvariousalgebraictheories,butithassome very strong links with other areas of mathematics. Lie algebra and matrix Lie groups can be have an extensive use in the real world today, especially when solving problems related to Markovian arrival processes (MAPs). From its name, we can detect that MAPs have a connection with Markov chains and the Markov property. In this report, we will give a formal definition of MAPs and how Markov chains relate to it. MAPs are widely used in today’s world as we can not only apply this model to scientific cases but also in daily-life situations. For instance, when jobs arrive in a queue (say on a network) then this can be modeled using MAPs or another example would be modeling the number of people arriving in a queue. This report will introduce the different matrix Lie groups and its corresponding Lie algebra, which will form the basis of this project. We will then use two of these groups, SL(2,R) and SU(2), and model them using MAPs, i.e. generate the rate matrices using Lie algebra and its key properties. Hence, in that section we will break down the steps on how to solve such a problem as well as include a further section where we apply these rate matrices to define a new concept. We will also give a verification of the solutions using MATLAB. The advantage of applying the commutator relation in order to solve the problem is to obtain a method that one could solve by hand (for simple cases) rather then relying only on computers. In reality we know that not everything is perfect, hence in the case of MAPs we may not always have all the information. Therefore, we may need to estimate the unobserved data using the estimation-maximisation(EM) algorithm. A small discussion of the advantages and disadvantages of a second approach that is based on moments is also included. Finally, we will explore some applications of the EM algorithm as well as discover where and how we can apply it. Afurtherinvestigationwillbecarriedouttoidentifyifwecanfindtheratematricesformatrix Lie groups that have higher dimensions, such as 3 x 3. However, this is mostly left as future work. Other extensions also include, modeling MAPs on other matrix Lie groups other than the two already mentioned; and comparing outcomes of the EM algorithm and the moment based approach when applied to real data. 1 Acknowledgement I would like to thank my supervisor, Prof. Peter Harrison for his endless support, inspiration and enthusiasm throughout this project. He always remained patient and confident in my ability to deliver results. IwouldalsoliketothankDr. GiulianoCasale,forhisadviceandconstructivefeedbackduring the interim report submission. I would also like to take this opportunity to thank my personal tutor, Dr. Alessandra Russo, who has guided me throughout my three years at Imperial College. Finally, I would like to thank my friends and my family for their encouragement and blessings throughout my three years at Imperial College. 2 CONTENTS CONTENTS Contents 1 Introduction 5 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Layout of the report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Background 7 2.1 Matrix Lie Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Examples Of Matrix Lie Groups . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Simple Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Homomorphisms And Isomorphisms . . . . . . . . . . . . . . . . . . . . . . 19 2.7 The Polar Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.8 Lie Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.9 The Matrix Exponential and Computing The Exponential of a Matrix . . . . 21 2.10 The Matrix Logarithm and More Properties of the Matrix Exponential . . . . 23 2.11 The Lie Algebra of a Matrix Lie Group . . . . . . . . . . . . . . . . . . . . . 26 2.11.1 The General Linear Group. . . . . . . . . . . . . . . . . . . . . . . . 27 2.11.2 The Special Linear Group . . . . . . . . . . . . . . . . . . . . . . . . 27 2.11.3 The Unitary Group . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.11.4 The Orthogonal Group . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.11.5 The Generalised Orthogonal Group . . . . . . . . . . . . . . . . . . . 28 2.11.6 The Symplectic Group . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.11.7 The Heisenberg Group . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.12 Properties of Lie Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.13 Lie Algebra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.14 The Baker-Campbell-Hausdorff Formula . . . . . . . . . . . . . . . . . . . . 33 3 Markovian Arrival Process (MAP) 37 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Example: SL(2,R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2.1 Solving for C and D . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.2 Implementing C and D . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 Example: SU(2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.1 Investigate SU(3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3 CONTENTS CONTENTS 4 Coded Examples in MATLAB 53 4.1 Why use MATLAB? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Example: sl(2,R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 Estimation-Maximisation (EM) For MAPs 58 5.1 General EM algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2 EM and MAPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2.1 Formulas for the M-Step . . . . . . . . . . . . . . . . . . . . . . . . 61 5.2.2 Formulas for the E-step . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.2.3 Computing the EM algorithm . . . . . . . . . . . . . . . . . . . . . . 65 5.2.4 Example using Uniformisation. . . . . . . . . . . . . . . . . . . . . . 68 6 Evaluation 71 6.1 Result From Lie Algebra Examples . . . . . . . . . . . . . . . . . . . . . . . 71 6.2 Efficiency of Estimation-Maximisation Algorithm . . . . . . . . . . . . . . . 72 7 Conclusion & Future Work 73 7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.2.1 Larger Dimension Matrices . . . . . . . . . . . . . . . . . . . . . . . 73 7.2.2 Simplify Large Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.2.3 Other Matrix Lie Groups . . . . . . . . . . . . . . . . . . . . . . . . 74 7.2.4 Apply EM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.2.5 Other Forms of MAPs. . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.2.6 Stiff Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4 1 INTRODUCTION 1 Introduction In this chapter, we will look at the history of Lie Groups and its unique features. We will also highlight the problems that can be solved with matrix Lie groups and Lie algebra while also discussing some of the applications of this theory. This chapter is divided into four sections, where Section 1.1 will focus on the motivation of the project and a short history of the topic. Section 1.2 outlines the applications of the theory and what the objective is. Finally, section 1.3 will provide a summary of how this report is organised. 1.1 Motivation There are a lot of theorems and proofs involved in mathematics and the beauty about this subjectisitsapplicationsinalldifferentfieldsrangingfromphysicstoeconomics. Furthermore, overtheyearswecanfindnewwaysofapplyingthesecenturyoldmathematicalconceptsand see the world around us advance. Matrix Lie groups and Lie algebra have been researched extensively,butunderstandingitsroleinmatrixexponentiationwithapplicationstocontinuous time Markov chains is very interesting and useful in reality as it has many applications. Lie Groups are named after Sophius Lie, who laid the foundations of the continuous transfor- mationgrouptheory. AsLiegroupsaresmoothmanifoldstheycanbestudiedusingdifferential calculus and the key idea of this theory is to replace the global object (the group) with a lo- cal/linearised version of the group. Lie groups were initially introduced to help solve and simplify ordinary as well as partial differential equations.[1] The most beautiful and useful feature about Lie groups is that it can be applied in two of broadest mathematical divisions, algebra and geometry. Their algebraic properties are derived from the group axioms, while their geometric properties are identified from group operations with points in a topological space. ThestudyofmatrixLiegroupscanbefacilitatedbylinearisingthegroupintheneighbourhood of its identity and this results in a structure called a Lie algebra. The Lie algebra retains most of the properties of the original matrix Lie group, but not necessarily all. In addition, the majority of the Lie group properties can be recovered by the inverse of the linearisation operation, which is known as exponential mapping. Since a Lie algebra is a linear vector space, we can study it by using all the standard tools defined for linear vector spaces.[1] In particular, we can define the inner products and make standard choices of the basis vectors. These tools such as the inner product, can then be extended over the entire group manifold using the group multiplication operation. This area of mathematics has a clear application within the computer science field i.e. the theory of Lie algebra and Markovian arrival processes will be used to show how we can solve queueing system problems. This project will allow us to further explore Markovian arrival processes (MAP) and understand the differences when various underlying distributions are used. The main process that this project will focus on is the Poisson process/distribution as well as the continuous-time Markov process and we will discuss examples that highlight the link between Lie algebra and MAPs. 1.2 Objectives This project aims to explore Lie algebra and matrix Lie groups in terms of matrix exponential as well as apply the theory to applications such as continuous-time Markov chains (CTMC). Morespecifically,wewillgoindepthintosomeofthetheoryandapplyLiealgebraandmatrix Lie groups to the class of Markovian arrival processes (MAP). 5 1.3 Layout of the report 1 INTRODUCTION One of the aims at the end of this project is to understand the link between MAPs and Lie algebra. Inaddition,wewouldliketodiscusshowwecouldusematrixexponentialstosimplify some of the equations that appear in examples involving MAPs. We will be working with two different matrix Lie groups and these will be discussed further in the next chapter. Another aim is to understand the method of solving problems related to MAPs i.e. finding the two rate matrices C and D as these are very important elements of a MAP. Further explanations about the rate matrices and their definitions will follow in later chapters. We willalsouseMATLABtogeneratethesematricesandapplythemtodifferentsituations,such as the estimation-maximisation algorithm. We will also briefly discuss the estimation and maximisation (EM) algorithm and how we can applythattoMAPs. Inotherwords, wewillanswerquestionssuchaswhyshouldweusethis algorithm and in what cases is it useful? We we will also discuss the two different ways of applying the EM algorithm, i.e. either using differential equations or uniformisation. ThefinalaimistolookintotheEMalgorithmandapplyittoMAPs. Wewillbreakdowneach step of the algorithm and see how to use the equations in order to solve a specific problem. 1.3 Layout of the report This report is organised as follows: • Chapter 2 outlines the relevant work in Lie algebra that will form the basis of this project. It focuses on matrix Lie groups, and some of these will be discussed in further detail. In addition, we discuss and prove some of the key theorems and propositions related to Lie algebra. • Chapter 3 introduces the concept of Markovian arrival processes (MAP). We will in- troduce the method of solving MAPs as well as provide two examples based on matrix Lie groups. Finally, we will investigate how we could potentially solve higher dimension matrices, namely 3 x 3. • Chapter4iscloselylinkedwiththepreviouschapteraswetakethosetwoexamplesand validate the results in MATLAB. • Chapter5 introducesarelativelynewtopic, theestimationand maximisationalgorithm forMAPs. Wewillgiveanoverviewofthealgorithmanddescribeitsimportancewithin MAPs. • Chapter6iswherewewillevaluateourresultsandcheckifwehavesuccessfullyachieved our aims that we outlined at the onset of this report. • Chapter 7 summarises the contributions of this project and will be a formal conclusion to this report. We will discuss any limitations we encountered along with suggestions for how to develop this project in the future. 6 2 BACKGROUND 2 Background In this chapter, we will explore in more detail the theory behind matrix Lie groups and Lie algebra. We will also prove some key theorems and propositions as shown in [2] and these will be applied intheproject. Wewill definea matrix Liegroup and givemany examples that highlight the importance of this mathematical concept. Furthermore, we will understand the link between matrix Lie groups and its respective Lie algebra. ThereisemphasisonallthedifferentmatrixLiegroupsaseachoneportraysuniqueproperties. However, this project will focus on the special linear group and the special unitary group. We end this chapter by proving the Baker-Hausdorff-Campbell Lemma, which is important and heavily used in the study of Markovian arrival processes.. 2.1 Matrix Lie Groups In order to understand the other matrix Lie groups in depth, one must be familiar with the concept of general linear groups. Definition 2.1.1. A general linear group over the real numbers is denoted by: GL(n,R) This is the group of all n x n invertible matrices with real entries. Definition 2.1.2. A general linear group over the complex numbers is denoted by: GL(n,C) This is the group of all n x n invertible matrices with complex entries. Wecaneasilyshowthatthegenerallineargroupsareagroupunderthematrixmultiplication operation as: 1. The product of two invertible matrices is an invertible matrix 2. Matrix multiplication is associative 3. The identity of any matrix is the identity of the group 4. An invertible matrix has by definition an inverse Definition 2.1.3. LetA beasequenceofcomplexmatricesinM (C),whereM (C)isthespaceofalln x n m n n matrices with complex entries. Hence, we can say that A converges to a matrix A if every corresponding entry in A m m converges to its respective entry in A as m→∞. For instance, as m→∞ then (A ) converges A ∀1≤k,l≤n m kl kl Now, we can combine Definition 2.1.2. and Definition 2.1.3. and write a new definition for a concept called matrix Lie groups. 7 2.2 Examples Of Matrix Lie Groups 2 BACKGROUND Definition 2.1.4. A matrix Lie group is a closed subgroup, say G, of GL(n,C) with the following property: • If A is any sequence of matrices in G, and A converges to a matrix A then there m m can only be two possibilities: – A∈G or – A is not invertible [Note: G is a closed subset of GL(n,C), but this does not imply that G is closed in M (C). n Nonetheless, there are many examples of matrix Lie groups which are also closed in M (C).] n A simple counterexample, which is not closed and hence is not a matrix Lie group is the set of all invertible, n x n, matrices with every entry being real and rational. We know that such a matrix is a subgroup of GL(n,C), however it is not closed as we can show that a sequence of invertible matrices with rational entries can converge to an invertible matrix with some irrational entries. 2.2 Examples Of Matrix Lie Groups Example 1. The general linear group: GL(n,R) and GL(n,C) Themoststraightforwardexampleisthegenerallineargroups,GL(n,R)andGL(n,C),which are also matrix Lie groups and can be proved just by using the definition. [Note: From group theory we know that a group is also a subgroup of itself.] Hence, GL(n,R), is by definition a subgroup of itself. So, if A is a sequence of matrices in m GL(n,R) and A converges to A then either A∈GL(n,R) or A is not invertible. m In addition, GL(n,C), is also subgroup of itself. Therefore, just like the previous case if A m is a sequence of matrices in GL(n,C) and A converges to A then the entries of A are real, m hence either A∈GL(n,C) or A is not invertible. Example 2. The special linear group: SL(n,R) and SL(n,C) Thespeciallineargroupisagroupofn x nmatricesoverRorCwithrealorcomplexentries and each matrix has a determinant equal to one. Clearly, SL(n,R) and SL(n,C) are subgroups of the general linear groups GL(n,R) and GL(n,C), respectively. Moreover, if A is a sequence of matrices, all with determinant one, m and if A converges to A then A will also have determinant one. This is true because the m determinant of the product of two square matrices say X and Y is equal to the product of their individual determinants i.e. det(XY) = det(X)det(Y) 8 2.2 Examples Of Matrix Lie Groups 2 BACKGROUND and this can be extended to a finite number of matrices. So, in this case as the determinant of each matrix in the sequence of A is one then as A converges to A it implies that A m m also has determinant one. Example 3. The orthogonal group: O(n) and the special orthogonal group: SO(n) Thereareafewdifferentwaystodefineanorthogonalmatrixandeachdefinitionisimportant in order to show that O(n) is a matrix Lie group: Definition 2.2.1. A n x n matrix is orthogonal if its column vectors are orthonormal i.e. if A is an orthogonal matrix then the columns of A would be orthonormal and defined as: n (cid:88) A A = δ ij ik jk i=1 1≤ j,k ≤ n where δ is defined as the Kronecker delta: jk if j =k then δ = 1 jk if j (cid:54)=k then δ = 0 jk Proposition 2.2.2. A is an orthogonal, n x n, matrix if it preserves the inner product. The inner product is defined as: (cid:104)x,y(cid:105) = xTy n (cid:88) = x y i i i=1 where x,y ∈Rn and xT is the transpose of x. So, A preserves the inner product if: (cid:104)Ax,Ay(cid:105) = (cid:104)x,y(cid:105) 9