Markov Chains

1. A student is concerned about her car and does not like dents. When she drives to

school, she has a choice of parking it on the street in one space, parking it on the street

and taking up two spaces, or parking in the lot. If she parks on the street in one space,

her car gets dented with probability If she parks on the street and takes two spaces,

the probability of a dent is and the probability of a $15 ticket is Parking in a

lot costs $5, but the car will not get dented. If her car gets dented, she can have it

repaired, in which case it is out of commission for 1 day and costs her $50 in fees and

cab fares. She can also drive her car dented, but she feels that the resulting loss of

value and pride is equivalent to a cost of $9 per school day. She wishes to determine

the optimal policy for where to park and whether to repair the car when dented in

order to minimize her (long-run) expected average cost per school day.

a) Formulate this problem as a Markov decision process by identifying the states and

Cik

decisions and then finding the .

Let the states represent whether the student's car is dented, i = 1, or not, i = 0.

b) Identify all the (stationary deterministic) policies. For each one, find the transition

matrix and write an expression for the (long-run) expected average cost per period

probabilities (π0, π1, …, πM).

in terms of the unknown steady-state

Assuming the student's car has no dent initially, once she decides to park in lot, state

1 will never be entered. In that case, the decision chosen in state 1 does not affect the

expected average cost. Hence, it is enough to consider five stationary deterministic

policies.

c) Find the optimal policy by exhaustive enumeration.

2. Every Saturday night a man plays poker at his home with the same group of friends.

If he provides refreshments for the group (at an expected cost of $14) on any given

Saturday night, the group will begin the following Saturday night in a good mood

with probability and in a bad mood with probability . However, if he fails to

provide refreshments, the group will begin the following Saturday night in a good

mood with probability and in a bad mood with probability , regardless of their

mood this Saturday. Furthermore, if the group begins the night in a bad mood and

then he fails to provide refreshments, the group will gang up on him so that he incurs

expected poker losses of $75. Under other circumstances, he averages no gain or loss

on his poker play. The man wishes to find the policy regarding when to provide

refreshments that will minimize his (long-run) expected average cost per week.

a) Formulate this problem as a Markov decision process by identifying the states and

decisions and then finding the C .

ik

0 1