Computer Systems Engineering/Markov models

Markov Models

State diagrams describe the behavior of a system. They describe all possible states of a system (object in UML) and how the state changes as a result of events that reach the system (object).

For example,

It should be noted that Markov Models treat state transitions as a stochastic process.

Let each state be defined by a random variable. The set of random variables {x_n} forms a Markov chain if the probability that the next value (state) is x_n+1 depends only on the present value (state) x_n and not on any previous values. The effect of the entire previous history on future behavior is summed up in the current state. For “discrete time” Markov chains, transitions can only occur at the integers 1,2,3… For “continuous time” Markov chains, transitions can occur at any time. This is important since the past history is specified entirely by the present state, and we cannot also specify how long a process has been in the present state.

Analytically: P(x(t_n+1) = x_n+1 | x(t_n) = x_n, x(t_n-1) = x_n-1, … x(t₁) = x₁) = P(x(t_n+1) = x_n+1 | x(t_n) = x_n) where t₁ < t₂ < … < t_n < t_n+1 and x₁, x₂, …, x_n are in some discrete state space.

Consider the discrete time Markov chain:

Observe: the sum of probabilities of leaving each city is 1.

P(x_n = j | x₁ = i₁, x₂ = i₂, …, x_n-1 = i_n-1) = P(x_n = j | x_n-1 = i_n-1).

P(x_n = j | x_n-1 = i_n-1) is a one-step transition probability. The probability goes from one state E=i at step n-1 to state E=j at step n.

Let P_ij(n) = probability that a system goes from state E_i to state E_j in n-1 steps. Then, is the probability that the system goes from state E_i to state E_k in one step and then goes from state E_k to state E_j in n-1 steps. This is called the Chapman-Kolmogorov equation.

Let P(n) be a matrix. Each entry is P_ij(n). If this is a matrix of n-step transition probabilities, then

(called homogenous if this is independent of n)

Define P_ij = P(x_n = j | x_n-1 = i) as the probability that a system goes to the next state E_j given in state E_i. This is called the set of one-step transition probabilities.

Example: P₀₀ = 0, P₀₁ = ¾ , P₀₂ = ¼ , P₁₂ = ¾

In matrix form:

Let π_j = P(x_n = j) be the probability that the system is in state j at step n. In our example,

The probability in state j at step n+1 is the probability in state i at step n and goes to state j in one step.

In vector form:

In particular,

For example: Let Π(0) = [0,1,0], starting in Columbia.

After a long time, let

Therefore,

Example:

Observe:

The sum of (1) and (2) is negative (3), so therefore there is a linear dependence between the equations, and thus, there is no unique solution. We also know that π₀ + π₁ + π₂ = 1 (i.e. the system must be in some state). This is called a normalizing condition.

Now solve:

Observe:

This is like flipping a coin, where r = probability of heads and 1-r = probability of tails. So, P(sequence of exactly m heads) = r^m (1-r).

How long does a process remain in a state i?

Suppose the process enters state E_i. Then the probability of remaining in state E_i at the next step is P_ii. The probability that the process leaves E_i at the next step is 1-P_ii. Each time step is independent, so P(system remains in state E_i for exactly m additional time steps given that it has just entered state E_i) = (1-P_ii) P_ii^m. In other words, the process stays for m time steps with a probability of m*( P_ii P_ii P_ii …P_ii) and leaves the state on the m+1 step.

Geometric distribution

The average time in state E_i is E(time in state E):

Now, , therefore:

Therefore,

In short, the average time a process stays in a state before leaving is the inverse of the probability that it leaves.

Assume a watch state i for k steps and also that the system does not change state. What is the probability that the process does not leave the state on the next step? Let y = the steps to the first departure.

Thus the process is memory less – as we knew.

Continuous Time Markov Chains

P(x(t_n+1) = j | x(t_n) = i_n … x(t₀) = i₀) = P(x(t_n+1) = j | x(t_n) = i_n)

Recall that Markov chains are memoryless, so a transition does not depend on how long a process is in a given state.

Let τ_i = the amount of time in a state i. P(τ_i > s+t | τ_i > s) = h(t), which is only a function of t (not s). The function shows how long a process is in a state.

Thus, exponential is the only continuous distribution that satisfies this. Again, if we set s,t = 0, then P(τ_i >0) = 1, and

Defining the time-dependent transition probability

Now, consider the times s ≤ u ≤ t. To get from state E_i at time s to E_j at time t, a process must pass through some state at time u. Therefore,

This is the Chapman-Kolmogorov equation, and is exactly analogous to the discrete case, but is difficult to use directly.

Recall that

In the Chapman-Kolmogorov equation, substitute t+h for t:

Divide by h, take the limit as h approaches 0, u approaches t:

This is called Kolmogorov’s forward equation.

Also,

is Kolmogorov’s backward equation.

If time homogeneous transition probabilities do not depend on initial time t but only on interval h, then q_ij(t) = q_ij and q_j(t) = q_j and = P_ij(h), then

State transition probabilities and initial distribution determine all properties of a Markov chain. Observe:

Divide by h, take the limit as h approaches 0, v approaches t:

.

If time homogeneous:

State classifications

Recall that

A state is transient if there is a positive probability that a system will not return to that state. Let X_ji = number of visits to state i starting at state j. The expected value of X_ji, E(X_ji) is

A state i is transient if E(X_ji) is finite. This implies that P_ji(n) approaches 0 as n approaches infinity.

A state i is recurrent if and only if starting from state j, a process returns to state i with a probability of 1. Also, is infinite.

Consider the time it takes to reach a state i from state j for a recurrent chain. Let f_ij(n) = probability of the first visit to j from i in n steps. Let f_ii(n) = probability of the first return from i to i in n steps. Then, the probability of ever visiting j starting from state i is:

State i is recurrent if f_ii = 1, and transient if f_ii < 1. If f_ii = 1, then the mean recurrence time is A state is called recurrent non-null if is finite, and recurrent null if is infinite.

For a recurrent state i, The period of state i, , is the greatest common divisor of a set of positive integers n such that A system is aperiodic if = 1, and periodic if > 1.

A system is absorbing if and only if P_ii = 1.

A Markov chain is irreducible if every state can be reached from every other state in a finite number of steps; All states of an irreducible Markov chain are of the same type. In an aperiodic Markov chain, all states are aperiodic. If one state is periodic with period d, then all are periodic with the same period d.

Continuous Time Markov Chains

Let = random variable = time in state i. A Markov property means the probability of a transition cannot depend on how long the system has been in a state.

Now for s=0, and we have

s = t = 0 again requires

Now,

Therefore, the time in state is exponentially distributed with parameter which may depend on the state.

We have seen that = time in state i and that Let t be a very small increment of time h:

This last equation is the probability that a system leaves a state in the next increment of time h. This can be expressed in a Taylor series:

Number the states 0,1… Let = probability of transition to a higher numbered state (birth). Let = probability of transition to a lower numbered state (death). Only allow transitions to the next higher or lower numbered state (or stay in the same state). This is called a birth-death process.

Let P(n=k,t) = probability of being in state k at time t. Consider how a process can get into state n=k at time t+h.

For births: must have been in state n=k-1 and a birth occurred

For deaths: must have been in state n=k+1 and a death occurred

If no births and no deaths: must have been in state n=k at time t

Balance Equations

Flow Balance

The equilibrium balance equations can be intuitively constructed by inspection from the state transition rate diagram below.

This is similar to the state transition diagram we have already seen. In equilibrium, the rate of flow of probability into a state must equal the rate of flow of probability out of that state. Hence

Solving the Balance Equations

The quantity is called the “traffic intensity” and is usually denoted by

Recall that the queue will be unstable if jobs arrive faster than they can be served. Thus

As we will see determines most of the properties of interest in the queue. Note that it is determined by the ratio of the arrival and service rates and not their absolute values. Queues with equal traffic intensities can be expected to have similar properties even though their respective arrival or service rates may be quite different.

The constant P(0) is determined using the normalizing requirement, as shown below:

Note the similarity of the last equation to a geometric distribution:

This is the probability that there are k jobs in the queue and is shown below:

The probability that there is at least 1 job in the queue is This is the utilization of the server, the probability that it is busy.

Number in the Queue

The average number of jobs in the queue is

The sum is evaluated by using the following trick: note that

Now since the sum of a derivative is the derivative of the sum,

This is shown below as increases from 0 to 1:

The probability that there are more than some number r of jobs in the queue is

This is shown below for several values of

Note that P(n≥r) decreases geometrically in . Recall also that is the utilization of the server. Thus for lightly utilized servers (small ) the likelihood that there are many jobs in the queue is small. For heavily utilized servers ( near 1) the likelihood that there are a lot of jobs waiting to be served is much higher.

Let T = the average waiting time, T_n = the waiting time for arrival n with n-1 customers in the system, x_i = the service requirement of the ith customer (i = 1,2,…,n), x_o = the remaining service for the customer in service, and x_n = the service requirement of n+1 customers.