# 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$_1$) = x$_1$) = P(x(t$_{n+1}$) = x$_{n+1}$ | x(t$_n$) = x$_n$) where t$_1$ < t$_2$ < … < t$_n$ < t$_{n+1}$ and x$_1$, x$_2$, …, 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$_1$ = i$_1$, x$_2$ = i$_2$, …, 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$_{00}$ = 0, P$_{01}$ = ¾ , P$_{02}$ = ¼ , P$_{12}$ = ¾
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 π$_0$ + π$_1$ + π$_2$ = 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$_0$) = i$_0$) = 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.