Continuous Time Markov Chains 1.

Note: This contains some mistakes and needs to be rewritten. In general it is correct.

Goal

We will define and show some basic properties of Markov chains (MCs), and then discuss continuous time MCs.

Markov Chains

MCs are descriptions of discrete states linked by transition probabilities. Suppose a system can be in three states: $A$, $B$, and $C$. As time goes on, this system transitions from one state to another. For instance, $A \to C$ followed by $C \to A$ followed by $A \to B$. By observing this system we can approximately measure the probabilities or rates at which the system transitions occur.

If the system evolves deterministically, then it will spend exactly a specific amount of time in one state before transitioning to another state. The inverse of this time is the rate for the transition.

If the system evolves randomly, then it may remain in a state for a random amount of time before transitioning. In this case, we have transition probabilities rather than rates. In this respect, there are still important differences between discrete time and continuous time MCs.

We will continue to discuss networks and discrete time Markov Chains (DTMCs) to some degree in order to highlight the particular properties of continuous time Markov Chains (CTMCs). However, this note will focus on CTMCs.

Memory

For many important applications, systems that can be modeled by MCs evolve in a memoryless fashion. Actually, few MCs that are not memoryless can easily be analyzed in closed form, which is probably why we like model systems amenable to memoryless MCs.

Discrete Time Markov Chains

In a deterministic system there can only be one possible transition from each state. Otherwise, how would it choose which way to go? The next step in randomness is to have a number of possible transitions from each state occurring randomly with measurable probabilities. For example, the transition $A \to B$ might occur with a probability $p_{A \to B} = 0.2$ and the transition $A \to C$ occur with probability $p_{A \to C} = 0.7$. Thus, in a CTMC, we have no sense of physical time advancing. Instead, we index successive states of the system by some integer, say $i$ or $n$ or $\alpha$. Notice that the probabilities in my example add to $1$. When transitioning out of the state $A$, the system has to go somewhere! We will see an interesting modification of this when we consider events in continuous time.

Representations of Markov Chains

Two convenient representations of MCs are employed. The first is graphical. Essentially, a dependency graph. Graph elements representing individual states are connected with arrows representing possible transitions. I'll make one to show as soon as I install and learn to use canviz.

The second representation is in matrix form and lends itself to mathematical analysis. Both rows and columns represent the different states of the system, thus the matrix is square. Each entry describes the transition from the row state to the column state. This description will be different depending on whether the the system evolves deterministically, randomly, and/or in discrete or continuous time (more on that later).

Here is a matrix that represents all the transitions in a hypothetical CTMC:

\begin{bmatrix} 0.1 & 0.7 & 0.2 \\ 0.8 & 0.1 $ 0.1 \\ 0.4 & 0.3 & 0.3 \\ \end{bmatrix}

If our example were deterministic network, then the matrix could instead just have ones and zeros (for discrete time) or it could have rates which would represent approximately how long you need to wait or the system to change state. Also in the case of a deterministic network, or a random but discrete time MC, there would be no numbers on the diagonal, since we would again only be concerned with changes in state, and no strict passage of time. However, in the latter case, the rows would add to 1. This is because the numbers in the rows would represent probabilities for transitioning to the state in the respective column. Since the systems transitions to somewhere with probability 1, the rows must sum to 1.

A CTMC has a very important difference, which is reflected in the fact that it does have entries on the diagonal, as in our example. A CTMC represents a system in which time is advancing continuously. The matrix entries represent infinitesimal transition rates for a very tiny time step $\delta t$. It is understood that the system will eventually go to a new state.

However, in any particular infinitesimal interval the system may NOT transition. We represent this by a probability or rate for the system to stay in its current state. In the diagrammatic representation this is expressed as an arrow that loops back on the same state. In the matrix representation this is expressed by transition rates on the diagonal, since these represent the probabilities that the system will stay in its current state during the next $\Delta t$.

Examples

Here is a short list of MC applications that is both incomplete insufficient in detail. It does give a sense of the broad range of applications as well as the different ways one can think of states and transitions.

As mentioned above, CTMCs can model systems that are or can be thought of as being approximately memoryless, which again means that the system does not remember what states it has been in leading up to being in the current state -- systems that live entirely in the moment.

Queues

One of the important practical applications of MCs is in modeling queuing systems. A classic example is machines which may break down randomly at any time, and one or more technicians who service the machines. Perhaps the servicing time also has some probability distribution. As will be discussed in another note, if the probability of a machine breaking down at any moment is fairly small, then the machine breakdowns are essentially memoryless. In this example, the "state" of the system is the list of which machines are active and which are in repair. This classic example also has numerous equivalent variants: people in line to get service at some counter, requests to an internet server, etc.

Population and Counting

Another classic application is in various "counting processes". In a counting process, the various states of the system are the numbers of something, such as the number of molecules of a certain chemical in a reaction, the number of individuals in a population, etc. An important class of these is called "birth and death processes", which have application in biology including population dynamics of species and the spread of epidemics.

Real and Hypothetical Networks

Google uses a Markov type model to rank pages. An world wide web user remains on a certain page for a certain amount of time before going to another. Thus, there is a probabilistic rate associated with page links. The world-wide-web is somewhere between a physical network of interconnected physical entities and a virtual network of hypothetical entities or states. The internet, which is the physical network of servers, is a physical network. Markov models can also be used to model network traffic. For instance, the path of a single packet through the internet can be a Markov chain. The packet travels to a server and remains there for a certain amount of time before being routed to another server.

Climate

Markov chains are often used in modeling climate. By discretizing the values of a climate variable such as temperature or pressuer, these values can be thought of as the states of a Markov chain. Because climate has natural periodicities, one can use DTMCs for modeling successive days, for instance. Or, for events that occur intermittently, such as rain or extreme winds, one can use CTMCs.

Summary and Conclusion

CTMCs are a useful tool for modeling many real world processes that can be described as a system that will reside for random periods of time in one of many states before transitioning to another, randomly chosen state. The additional requirement is that the time between transitions as well as the choice of transition are completely random and unaffected by the history of the system, including even the immediately preceding transition.

CTMCs also have many useful and interesting properties, some of which we will discuss in other notes. These include the Poisson Process, which governs the probability distribution of waiting times between transitions between states.