One example of the use of a discrete time Markov chain to solve a problem in computer systems performance evaluation comes from the machine repair model. The machine repair model presented below is actually only one possible model from a family of models that can be used to look at the reliability and performance of a computer system consisting of one or more parts that can fail and be repaired.

The particular machine repair model we use in this example has a single computer that may fail, and a single repairman who services it when it does fail. The machine can be in any of five states:

We can represent the system as a discrete time Markov chain with the following state transition probabilities (rows represent present states, columns represent next states):

Blanks indicate that it is not possible to make a transition directly between the two states.

Ordering states in the state probability vector as they appear above, we have the following single step transition probability matrix. P=( 0.050.9300.020 0.100.430.430.040 00.600.350.050 0000.800.20 0.750000.25 ) P 0.05 0.93 0 0.02 0 0.10 0.43 0.43 0.04 0 0 0.60 0.35 0.05 0 0 0 0 0.80 0.20 0.75 0 0 0 0.25 You should verify that this is an ergodic chain. Since the chain is finite, all you have to do is prove irreducibility and aperiodicity.

As shown in the module on solving discrete-time Markov chains, this chain can be solved using Matlab in several ways. One way to find the steady state probability vector in Matlab is to raise the matrix to a power such that the rows are all the same, to the precision you want. P20=( 0.07970.42840.28340.16450.0439 0.07970.42840.28340.16450.0439 0.07970.42840.28340.16450.0439 0.07970.42840.28340.16450.0439 0.07970.42840.28340.16450.0439 ) P 20 0.0797 0.4284 0.2834 0.1645 0.0439 0.0797 0.4284 0.2834 0.1645 0.0439 0.0797 0.4284 0.2834 0.1645 0.0439 0.0797 0.4284 0.2834 0.1645 0.0439 0.0797 0.4284 0.2834 0.1645 0.0439

A second way of solving this chain is to use the eigenvector approach.

          [v,d] = eig(P')

d=( -0.27240000 01.0000000 000.109800 0000.31570 00000.7270 ) d -0.2724 0 0 0 0 0 1.0000 0 0 0 0 0 0.1098 0 0 0 0 0 0.3157 0 0 0 0 0 0.7270 The d matrix contains the eigenvalues of the P matrix (actually, the transpose of the P matrix, since we are looking for left eigenvectors). The second eigenvector in the v matrix corresponds to the second eigenvalue, which has value 1.

          v(:,2) = [-0.1458  -0.7832  -0.5181  -0.3007  -0.0802]
    

To find the actual steady state probability vector, we need to normalize the vector so that its elements sum to one:

          sum(v(:,2)) = -1.8280

          pi = v(:,2)/sum(v(:,2))
    

π=0.07970.42820.28340.16450.0439 π 0.0797 0.4282 0.2834 0.1645 0.0439

Finally, we can find the solution directly as the solution of a set of linear equations. Begin by subtracting the identity matrix from the single-step probability transition matrix. J5 is the identity matrix of rank 5. P−J5=( -0.950.9300.020 0.10-0.570.430.400 00.60-0.650.050 000-0.200.20 0.75000-0.75 ) P J5 -0.95 0.93 0 0.02 0 0.10 -0.57 0.43 0.40 0 0 0.60 -0.65 0.05 0 0 0 0 -0.20 0.20 0.75 0 0 0 -0.75 This matrix is singular, so replace one of the Chapman-Kolmogorov equations with the normalization equation. In this example, we will replace the equation for the "in repair" state (the last column). P1=( -0.950.9300.021 0.10-0.570.430.401 00.60-0.650.051 000-0.201 0.750001 ) P1 -0.95 0.93 0 0.02 1 0.10 -0.57 0.43 0.40 1 0 0.60 -0.65 0.05 1 0 0 0 -0.20 1 0.75 0 0 0 1 Now solve the set of five independent, simultaneous linear equations.

         pi = [0  0  0  0  1]/P1
    

π=0.07970.42820.28340.16450.0439 π 0.0797 0.4282 0.2834 0.1645 0.0439

With these steady state probabilities, we can answer several questions of possible interest. For example, the fraction of time that the system is broken is the probability that the model is in either of the states broken or in repair, or 20.84% of the time.

We could improve the fraction of time that the system is not broken by either increasing its reliability (reducing the probability that the model makes a transition from state idle, busy, or waiting to state broken) or by reducing the time it takes the repairman to begin work on the system when it is broken. Suppose we take the latter approach. If we reduce the probability that the model makes the transition back to state broken given that it is in state broken from 0.8 to 0.2, we find that π=0.09100.48870.32330.04690.0500T π 0.0910 0.4887 0.3233 0.0469 0.0500 , and the machine is broken only 9.69% of the time.

Content actions

Add module to:

My Favorites Login Required (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own Login Required (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 member, a community, or a respected organization.

What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Footer

This work is licensed by Bart Sinclair under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by Elizabeth Gregory on Jun 9, 2005 10:41 am GMT-5.