Business Simulation Exam

DiscreteTimeMarkovChains_post.pptx

Home >Business & Finance homework help >Business Simulation Exam

ADM 3305 Business Simulation Analytics

Simulation of Stochastic Processes

Discrete Time Markov Chains

All forms (printed, digital, etc.) of course materials prepared by the instructor (including e-mailed or Brightspace content) are protected by copyright. This covers all files, assessments, solutions, cases, recordings and other materials. Copying, scanning, photographing, posting, or sharing by any means is a violation of copyright and will be subject to appropriate penalty as prescribed by University of Ottawa regulation.

Based on “Discrete time Markov chains” lecture notes by X. Xie (2012).

Lectures 7 & 8

Introduction to Stochastic Processes

Discrete Time Markov Chains (DTMCs)

Basic definitions

Classification

Steady-state Analysis

Simulation of DTMCs

Learning goal:

By the end of this lecture, you will have a good feel for how DTMCs work and an idea of the things you can do with them

Stochastic Processes

Motivation

Many real-world systems contain uncertainty and evolve over time

Sometimes we are interested in how a specific random variable evolves over time

Stochastic processes are probability models for such variables

The study of how a random variable evolves over time involves a stochastic process

Components of Stochastic Processes

The state space of a stochastic process is the set of all values that the Xn’s can take

Time n = 0, 1, 2, . . .

State: v-dimensional vector, s = (s1, s2, . . . , sv)

In general, there are m states,

s1, s2, . . . , sm or s0, s1, . . . , sm-1

Also, Xn takes one of m values

Example: Gambler’s Ruin

At time 0 I have X0 = $2, and each day I make a $1 bet. I win with probability p and lose with probability 1 - p. I’ll quit if I ever obtain $4 or if I lose all my money

Let Xn = amount of money I have after the bet on day n

State space is S = { 0, 1, 2, 3, 4 }

Discrete Time Markov Chains

Discrete Time Markov Chain (DTMC)

Definition: A stochastic process with discrete state space and discrete time {Xn, n > 0} is a discrete time Markov Chain (DTMC) if and only if

P[Xn+1 = j | Xn = in, ..., X0 = i0] = P[Xn+1 = j | Xn = in] = pij(n)

In a DTMC, the past history impacts on the future evolution of the system via the current state of the system

pij(n) is called transition probability from state i to state j at time n

Discrete Time Markov Chain (DTMC)

Stochastic process

Discrete

event

Continuous event

Discrete

time

Continuous time

Memoryless

A DTMC is a discrete time and memoryless discrete event stochastic process

Example: A Mouse in a Maze

Which stochastic process can be used to represent the position of the mouse at time t?

Under which assumptions, the system can be represented by a discrete time Markov chain?

start

exit

Example: A Mouse in a Maze

Let {Xn}, n = 0, 1, 2, ..., be the position of the mouse after n rooms visited

Assume that the mouse does not remember the rooms visited previously and that it chooses any corridor equiprobably

start

exit

1/2

1/4

1/2

1/4

Homogeneous DTMC

A DTMC is said to be homogeneous if and only if its transition probabilities do not depend on the time n, i.e., if

P[Xn+1 = j | Xn = i] = P[X1 = j | X0 = i] = pij

A homogeneous DTMC is then defined by its transition matrix P = [pij]i,j ∈ E

Example: A Mouse in a Maze

What is the transition matrix of the process?

start

exit

1/2

1/4

1/2

1/4

P = [1 0 0 0 0 0; 0 ½ ½ 0 0 0; 0 ½ 0 0 ½ 0; ¼ ¼ ¼ 0 0 ¼; 0 0 0 1 0 0; 0 0 0 0 0 1]

Transition Matrix

A square matrix is said stochastic if and only if:

All entries are non negative

Each line sums to one (1)

Properties:

A transition matrix is a stochastic matrix

If P is a stochastic matrix, then Pn is a stochastic matrix too

Observation: In this course, we will limit ourselves to discrete time Markov chains defined on a finite state space E which are homogeneous in time. Most results also extend to countable state space.

Graphic Representation of a DTMC

Example: Weather

The weather can be considered a stochastic process, because it evolves in a probabilistic manner from one day to the next. Suppose for a certain location that this probabilistic evolution satisfies the following description:

The probability of rain tomorrow is 0.6 if it is raining today

The probability of no rain tomorrow (clear) is 0.8 if it is clear today

Model weather evolution as a DTMC by providing the corresponding graphical representation of it

Example: Weather

0.8

0.6

0.2

0.4

Example: Computer Repair

Two aging computers are used for word processing

When both are working in the morning, there is a 30% chance that one will fail by the evening and a 10% chance that both will fail

If only one computer is working at the beginning of the day, there is a 20% chance that it will fail by the close of business

If neither is working in the morning, the office sends all work to a typing service

Computers that fail during the day are picked up the following morning, repaired, and then returned the next morning.

The system is observed after the repaired computers have been returned and before any new failures occur

Model the number of that have failed as a DTMC by providing the corresponding graphical representation of it

Example: Computer Repair

0.3

0.1

0.6

0.2

0.8

Classification of States

Let fjj be the probability of returning to state j after leaving j

A state j is said to be transient if fjj < 1

A state j is said to be recurrent if fjj = 1

A state j is said to be absorbing if pjj = 1

Let Tjj be the average returning time to state j

A recurrent state j is positive recurrent if E[Tjj] is finite

A recurrent state j is null recurrent if E[Tjj] = ∞

Example: A Mouse in a Maze

Classify the states of this example

start

exit

1/2

1/4

1/2

1/4

T: (1), (2), (3), (4)

R: None

A: (0), (5)

Irreducible Markov Chains

A DTMC is said irreducible if and only if a state j can be reached in a finite number of steps from any other state i

An irreducible DTMC is a strongly connected graph

Irreducible Markov Chains

Periodic Markov Chains

A state j is said to be periodic if it is visited only in a number of steps which is multiple of an integer d > 1 called period

A state with a self-loop transition (i.e., pii > 0) is always aperiodic

A state j is said aperiodic otherwise

All states of an irreducible Markov chain have the same period

Is state 1 periodic? If so, what is its period?

Classification of Irreducible Sub-Chains

A DTMC can be partitioned into strongly connected components, each corresponding to an irreducible sub-chain or class

Partitioning a DTMC into Irreducible Sub-Chains

A sub-chain (or class) is said to be absorbing if there is no arc going out of it

Otherwise, the sub-chain (or class) is said to be transient

Transient

sub-chain

Absorbing

sub-chain

Absorbing

sub-chain

Additional Definitions

A state j is said reachable from a state i if there is a path from i to j in the state transition diagram

A subset S of states is said closed if there is no transition leaving S

A closed set S is said irreducible if all states in S are mutually reachable

A Markov chain is said irreducible if its state space is irreducible

Properties (Optional)

If a Markov chain has a finite state space, then at least one state is recurrent

If i is a recurrent state and j is reachable from i, then state j is recurrent

If S is a finite closed irreducible set of states, then every state in S is recurrent

If i is a positive recurrent state and j is reachable from i, then state j is positive recurrent

If S is a closed irreducible set of states, then every state in S is positive recurrent or every state in S is null recurrent or every state in S is transient

If S is a finite closed irreducible set of states, then every state in S is positive recurrent

Analysis of Discrete Time Markov Chains

Sojourn Times

Let Ti be the time spent in state i before jumping to other states

Ti is a random variable with geometric distribution

m-Step Transition Probabilities

The probability of going from state i to state j in m steps is

pij(m) = P{Xn+m = j|Xn = i} = P{Xm = j|X0 = i}

Let P(m) = [pij(m)] be the m-step transition matrix

P(m) = Pm

Chapman-Kolmogorov equation (P(l + m) = P(l)P(m))

Example: A Mouse in a Maze

What is the probability that the mouse is still in room 2 at time 4?

start

exit

1/2

1/4

1/2

1/4

p22(4) ≈ 0.19

Probability of going from i to j in exactly n steps (Optional)

Let fij(n) be the probability of going from state i to state j in exactly n steps (without passing j before) and fij be the probability of going from i to j in a finite number of steps

Similar approach can be used to determine the average time Tij it takes for going from state i to state j

Probability Distribution of the States

Let pi(n) be the probability of being in state i at time n

pi(n) = P{Xn = i}

Let p(n) = (p1(n), p2(n), ...) be the probability distribution over the state space at time n. This distribution depends on:

The transition matrix P

The initial distribution p (0)

If the system is at state i, then pi(0) = 1 and pj(n) = 0, for j ≠ i

What is the relation between p(n), p(0), and P?

Transient State Equations

By conditioning on the state of the system at time n

Property:

Let P be the transition matrix of a Markov chain and p(0) the initial state probability distribution, then over the state space at time n

p(n+1) = p (n)P

p(n)= p(0)Pn

Steady-State Distribution

Key questions :

Does the distribution p(n) converge when n goes to infinity?

If the distribution converges, does its limit p = (p1, p2, ...) depend on the initial distribution p(0)?

If a state is recurrent, what is the percentage of time spent in this state and what is the number of transitions between two successive visits to the state?

If a state is absorbing, what is the probability of ending at this state? What is the average time to this state?

Steady-State Distribution

For an irreducible and aperiodic DTMC with positive recurrent states, the distribution p(n) converges to a limit vector p which is independent of p(0) and is the unique solution of:

pi are also called stationary probabilities (also called steady state or equilibrium distribution)

For an irreducible and aperiodic DTMC, pi is the percentage of time spent in state i

Flow Balance Equations

The equation below can be interpreted as a balance equation of probability flow

where a probability flow pipij is associated to transition (i,j)

Flow balance equation:

is the sum of probability flow into node j

is the sum of flow out of node j

This, outgoing flow = incoming flow

Example: Weather

The probability of rain tomorrow is 0.6 if it is raining today

The probability of no rain tomorrow (clear) is 0.8 if it is clear today

What are the values of the steady-state probabilities for this example?

(1) πC = 0.8 πC + 0.4 πR

(2) πR = 0.2 πC + 0.6 πR

(3) πC + πR = 1

From (1) and (3), πC = 2/3; πR = 1/3.

Example: An Inventory Model

A store that stocks a particular laptop model uses the following (s, S) ordering policy; if the number of laptops in inventory at the beginning of a day is x, then it orders:

• 0 if x ≥ s,

• S - x if x < s.

The order is immediately filled. The daily demands are independent and equal j with probability αj. All demands that cannot be immediately met are lost.

Let Xn denote the inventory level at the end of the n-th day. Model {Xn, n ≥ 1} as a Markov chain by providing its corresponding graphical representation. Assume the store set the policy with s = 1 and S = 3.

Simulation of Discrete Time Markov Chains

Example: Weather

The probability of rain tomorrow is 0.6 if it is raining today

The probability of no rain tomorrow (clear) is 0.8 if it is clear today

Simulate the evolution of the weather for 10 days, beginning the day after a clear day

Example: Catalog Mailing

Each quarter the manager of a retail store divides customers in two classes based on their purchase behavior in the previous quarter. Denote classes as L for low and H for high

The manager wishes to determine to which classes of customers he should send quarterly catalogs. The cost of sending a catalog is $15 per customer and the expected purchase depends on the customer’s class and the manager’s action

If a customer is in class L and receives a catalog, then the expected purchase in the current quarter is $20, and if a class L customer does not receive a catalog his expected purchase is $10

If a customer is in class H and receives a catalog, then his expected purchase is $50, and if is a class H customer does not receive a catalog his expected purchase is $25

Example: Catalog Mailing

The decision whether or not to send a catalog to a customer also affects the customer’s classification in the subsequent quarter

If a customer is class L at the start of present quarter, then the probability he is in the class L at the subsequent quarter is 0.3 if he receives a catalog and 0.5 if he does not.

If a customer is class H in the current period, then the probability that he remains in class H in the subsequent period is 0.8 if he receives a catalog and 0.4 if he does not.

Simulate the evolution of the class of a customer under each mailing strategy and use the results to determine to which classes of customers the store manager should send quarterly catalogs (i.e., to determine the best mailing strategy)

Why do we need simulation?

To evaluate the quality (of an action plan) over uncertain future trajectories (i.e., path-dependent outcomes)

Suppose that you have a trading strategy which determines how much you should buy or sell given the market condition. How can you evaluate how good your strategy is?

Option 1 (Back-testing): Run your strategy against historical prices over a chosen time window and calculate the gain/loss of your strategy.

What can possibly go wrong using back-testing?

Why do we need simulation?

Option 2 (Simulation): Instead of relying on a particular sample path, i.e., historical prices, we may simulate multiple paths to evaluate the performance of a trading strategy

A good trading strategy should perform well across a large number of sample paths

Simulation can be used to “stress test” an action plan (such as a trading strategy), i.e., examining its performance against different scenarios (i.e. multiple sample paths)

Simulation can be used to evaluate any “path-dependent” outcome

[

]

(

)

iiiii

PTnpp

==-

(

)

(

)

(

)

lmlm

ijikkj

ppp

(

)

ijij

ijijikkj

fppf

π = πP π i

i∈E ∑ =1 ⎧ ⎨ ⎪

⎩⎪

p=pP

iÎE

⇔

π j = π i pij i∈E ∑ ,∀j ∈ E

π i i∈E ∑ =1

⎧

⎨ ⎪

⎩ ⎪

iÎE

,"jÎE

iÎE

jiij

iij

jjji