Skip to content Skip to navigation

Connexions

You are here: Home » Content » Markov Chains

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the author

Recently Viewed

This feature requires Javascript to be enabled.

Markov Chains

Module by: Bart Sinclair

Summary: 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 Xt X t where tt 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.

  1. State Space:
    • continuous-state: Xt X t can take on any value over a finite or infinite continuous interval or set of such intervals
    • discrete-state: Xt X t has only a finite or countable number of possible values s 0 s 1 s 2 … s i … s 0 s 1 s 2 … s i …
    A discrete-state random process is also often called a chain.
  2. index parameter (time):
    • discrete-time: permitted times at which changes in value may occur are finite or countable ( Xt X t may be represented as a set X i 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 tt is the value of Xt X t ; the state of a discrete-time process at time nn is the value of X n 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 tt (continuous-time chain) or nn (discrete-time chain) depends only on the current state Xt X t or X n 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 X n + 1 depends only on X n X n , and not on any X i X i , 1≤i<n 1 i n

Pr X n + 1 = s i | X n = s j ∧ X n − 1 = s k ∧…∧ X 1 = s l =Pr X n + 1 = s i | X n = s j 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 (1)
This is referred to as the Markov property.

Now consider a continuous-time random process in which the random variables Xt X t change value (the process changes state) at times t1t2t3… 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 … 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

  1. the embedded discrete-time process is a discrete-time Markov chain, and
  2. the time between state changes is a random variable with a memory-less distribution.
A distribution function F T · F T · is memory-less if and only if
F T t= F T t+τ|T>τ F T t F T | t τ T τ (2)
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=PrT≤t+τ|T>τ F T t T τ T t τ (3)
Using the definition of conditional probability,
F T t=PrT≤t+τ∧T>tPr|T>τ= F T t+τ- F T τ1- F T τ F T t T t τ T t T τ F T t τ F T τ 1 F T τ (4)
Dividing both sides by tt and taking the limit as t→0 t 0 ,
limt→0 F T tt=limt→0 F T t+τ- F T τt1- F T τ t 0 F T t t t 0 F T t τ F T τ t 1 F T τ (5)
F T ′0= F T ′τ1- F T τ F T 0 F T τ 1 F T τ (6)
F T ′τ+ F T ′0 F T τ- F T ′0=0 F T τ F T 0 F T τ F T 0 0 (7)
The solution to this linear, first-order differential equation is
F T t=1-ⅇ- F T ′0t F T t 1 F T 0 t (8)
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 X n + 1 X n Let p=Pr X n + 1 = X n | X n = s k p X n s k X n + 1 X n for some state s k s k . The probability that X n + 1 X n + 1 is different than X n X n is 1-p 1 p . The probability that X n + 1 X n + 1 is the same as X n X n and X n + 2 X n + 2 is different, is p1-p p 1 p . In general,

Pr X n + i ≠ s k ∧ X n + i − 1 = X n + i − 2 =…= X n + 1 = s k | X n = s k =pi-11-p 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 (9)
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 s0s1s2…si…=012…i… s0 s1 s2 … si … 0 1 2 … i … . In this case, we can just refer to s i s i as ii, and define a birth and death process as:

Definition 1: Birth and Death process
If X n =i X n i , then X n + 1 =i+1 X n + 1 i 1 , or X n + 1 =i X n + 1 i , or X n + 1 =i-1 X n + 1 i 1
That is, state transitions are always between neighboring states.

Comments, questions, feedback, criticisms?

Send feedback