Markov Analysis

Chapter 12Markov AnalysisPart 3 Probabilistic Decision ModelsLearning ObjectivesGive examples of systems that may lend themselves to be analyzed by a Markov model.Explain the meaning of transition probabilities.Describe the kinds of system behaviors that Markov analysis pertains to.Use a tree diagram to analyze system behavior.Use matrix multiplication to analyze system behavior.Use an algebraic method to solve for steady-state probabilities.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Learning Objectives (cont’d)Analyze absorbing states, namely accounts receivable, using a Markov model.List the assumptions of a Markov model.Use Excel to solve various problems pertaining to a Markov model.After completing this chapter, you should be able to:3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Characteristics of a Markov SystemIt will operate or exist for a number of periods.In each period, the system can assume one of a number of states or conditions.The states are both mutually exclusive and collectively exhaustive.System changes between states from period to period can be described by transition probabilities, which remain constant.The probability of the system being in a given state in a particular period depends only on its state in the preceding period and the transition probabilities. It is independent of all earlier periods.4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Markov Analysis: AssumptionsMarkov Analysis AssumptionsThe probability that an item in the system either will change from one state (e.g., Airport A) to another or remain in its current state is a function of the transition probabilities only.The transition probabilities remain constant.The system is a closed one; there will be no arrivals to the system or exits from the system.5Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–1 Examples of Systems That May Be Described as Markov6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–2 Transition Probabilities for Car Rental Example7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. System BehaviorBoth the long-term behavior and the short-term behavior of a system are completely determined by the system’s transition probabilities.Short-term behavior is solely dependent on the system’s state in the current period and the transition probabilities.The long-run proportions are referred to as the steady-state proportions, or probabilities, of the system.8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–1 Expected Proportion of Period 0 Rentals Returned to Airport A9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Methods of System Behavior AnalysisTree DiagramA visual portrayal of a system’s transitions composed of a series of branches, which represent the possible choices at each stage (period) and the conditional probabilities of each choice being selected.Matrix MultiplicationAssumes that “current” state proportions are equal to the product of the proportions in the preceding period multiplied by the matrix of transition probabilities.Involves the multiplication of the “current” proportions, which is referred to as a probability vector, by the transition matrix.10Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Methods of System Behavior Analysis (cont’d)Algebraic SolutionThe basis for an algebraic solution is a set of equations developed from the transition matrix.Because the states are mutually exclusive and collectively exhaustive, the sum of the state probabilities must be 1.00, and another equation can be developedf rom this requirement. The result is a set of equations that can be used to solve for the steady-state probabilities.11Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–2 Tree Diagrams for the Car Rental Example for One Period12Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–3 Two-Period Tree Diagrams for Car Rental Example13Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–3 Period-by-Period Proportions for the Rental Example, and theSteady-State Proportions Based on Matrix Multiplications14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–4 Development of Algebraic Equations15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–4 Transition Probabilities for the Machine Maintenance Example16Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12-1 Worksheet for the Markov Analysis of the Machine Maintenance Problem17Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–5 Decision Tree Representation of the Machine Maintenance Problem: Initial State = Operation18Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–6 Decision Tree Representation of the Machine MaintenanceProblem Initial State = Broken19Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12-2 Solver Parameters Specification Screen of the MachineMaintenance Problem20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–5 Transition Matrix for Examples 12-5, 12-6, and 12-721Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–7 Tree Diagram for Example 12-5, Starting from X (Initial State = X)22Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–8 Tree Diagram for Example 12-5, Starting from Y (Initial State =Y)23Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–3 Worksheet for the Markov Analysis of the Acorn University Problem24Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–4 Second Worksheet for the Markov Analysis of the Acorn University Problem25Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–5 Third Worksheet for the Markov Analysis and Steady-State Probabilities of the Acorn University Problem26Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–6 Parameters Specification Screen for the Acorn UniversityProblem27Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Cyclical, Transient, and Absorbing SystemsCyclical systemA system that has a tendency to move from state to state in a definite pattern or cycle.Transient systemA system in which there is at least one state—the transient state—where once a system leaves it, the system will never return to it.Absorbing systemA system that gravitates to one or more states—once a member of a system enters an absorbing state, it becomes trapped and can never exit that state.28Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–6 An Example of a Cyclical SystemTable 12–7 An Example of System with a Transient StateTable 12–8 An Example of a System with Absorbing States29Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 12–9 Probability Transition Diagrams for the Transition Matrices Given in Tables 12-6, 12-7, and 12-830Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–7 Excel Worksheet for Example 12-10: The Acorn Hospital Absorbing State Problem31Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 12–9 Answers to Example 12-10, Part 1 a through f32Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–8 Worksheet for The Markov Analysis of Solved Problem 433Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–9 Solver Parameters Specification Screen for the Steady-StateCalculations for Solved Problem 434Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–10 Worksheet for the Steady-State Calculations of Solved Problem 535Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–11 Solver Parameters Specification Screen for the Steady-State Calculations for Solved Problem 536Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 12–12 Excel Worksheet for Solved Problem 6: Accounts Receivable—Absorbing State Problem37Copyright © 2007 The McGraw-Hill Companies. All rights reserved.