Markov Chains 2.2 2002/09/22 2002/11/08 Bart Sinclair bs@rice.edu Jacob Grabczewski jgrab@owlnet.rice.edu Bart Sinclair bs@rice.edu Charlet Reedstrom charlet@rice.edu continuous-state continuous-time discrete-state discrete-time exponential distribution Markov chain Markov process Markov property memory-less distribution random process stochastic process Introduction to continuous and discrete Markov chains, including the "birth and death" process. Several of the most powerful analytic techniques for evaluating computer system performance (and many other systems) are based on the theory of Markov chains. A Markov chain is a special case of a Markov process, which itself is a special case of a random or stochastic process. In the most general terms, a random process is a family, or ordered set of related random variables X t where t is an indexing parameter (usually time when we are talking about performance evaluation). There are many kinds of random processes. Two of the most important distinguishing characteristics of a random process are (1) its state space, or the set of values that the random variables of the process can have, and (2) the nature of the indexing parameter. We can classify random processes along each dimension. State Space: continuous-state: X t can take on any value over a finite or infinite continuous interval or set of such intervals discrete-state: X t has only a finite or countable number of possible values s 0 s 1 s 2 … s i … A discrete-state random process is also often called a chain. index parameter (time): discrete-time: permitted times at which changes in value may occur are finite or countable ( X t may be represented as a set X i ) continuous-state: changes may occur anywhere within a finite or infinite interval or set of such intervals The state of a continuous-time random process at a time t is the value of X t ; the state of a discrete-time process at time n is the value of X n . A Markov chain is a discrete-state random process in which the evolution of the state of the process beginning at a time t (continuous-time chain) or n (discrete-time chain) depends only on the current state X t or X n , and not how the chain reached its current state or how long it has been in that state. To be more precise, let's begin with discrete-time chains. In a discrete-time Markov chain, X n + 1 depends only on X n , and not on any X i , 1 i n X n s j X n − 1 s k … X 1 s l X n + 1 s i X n s j X n + 1 s i This is referred to as the Markov property. Now consider a continuous-time random process in which the random variables X t change value (the process changes state) at times t1 t2 t3 … . If we ignore how long the random process remains in a given state, we can view the sequence X t 1 X t 2 X t 3 … as a discrete-time process embedded in the continuous-time process. A continuous-time Markov chain is a continuous-time, discrete-state random process such that the embedded discrete-time process is a discrete-time Markov chain, and the time between state changes is a random variable with a memory-less distribution. A distribution function F T · is memory-less if and only if F T t F T | t τ T τ This says that the distribution of the time until the next state change is not a function of the time since the last change. We can restate this as F T t T τ T t τ Using the definition of conditional probability, F T t T t τ T t T τ F T t τ F T τ 1 F T τ Dividing both sides by t and taking the limit as t 0 , t 0 F T t t t 0 F T t τ F T τ t 1 F T τ F T 0 F T τ 1 F T τ F T τ F T 0 F T τ F T 0 0 The solution to this linear, first-order differential equation is F T t 1 F T 0 t Hence, the only continuous-time, memory-less distribution is the exponential distribution, and the time between state changes in a continuous-time Markov chain is exponentially distributed. For discrete-time Markov chains, the next state may be the same as the current state: X n + 1 X n Let p X n s k X n + 1 X n for some state s k . The probability that X n + 1 is different than X n is 1 p . The probability that X n + 1 is the same as X n and X n + 2 is different, is p 1 p . In general, X n s k X n + i s k X n + i − 1 X n + i − 2 … X n + 1 s k p i 1 1 p Therefore, the number of state transitions between state changes is geometrically distributed. One special type of Markov chain is a birth and death process, in which the states take on all non-negative integer values on a (possibly infinite) range; that is s0 s1 s2 … si … 0 1 2 … i … . In this case, we can just refer to s i as i, and define a birth and death process as: Birth and Death process If X n i , then X n + 1 i 1 , or X n + 1 i , or X n + 1 i 1 That is, state transitions are always between neighboring states.