1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help setting up Markov Chain

  1. Mar 3, 2015 #1

    ElijahRockers

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    A certain laid-back runner owns three pairs of shoes, which he keeps by either the front
    or back doors of his house. Each morning he is equally likely to leave through the front
    or back door, and then after his run, he is equally likely to enter through the front or
    back door. He takes off his shoes and leaves them at whatever door he enters. If there are
    no shoes at the door he leaves from, then he runs barefooted. We want to determine the
    proportion of time that the runner runs barefooted, in the long run (pun intended). Solve
    this problem using a Markov Chain (specify the states, give the transition probabilities,
    and determine the required steady-state probability). Hint: You only need to keep track
    of the number of pairs of shoes at one of the doors.

    3. The attempt at a solution
    Not sure how to set this one up, not much experience with Markov chains.

    I've set up a chain with 4 states: 0, 1, 2, 3, each state representing the number of shoes at the front door, with transition matrix:

    $$ P =
    \left( \begin{array}{cccc}
    .75 & .25 & 0 & 0 \\
    .25 & .5 & .25 & 0 \\
    0 & .25 & .5 & .25 \\
    0 & 0 & .25 & .75\end{array} \right)$$

    I don't know if this is helpful though, because what I'm really looking for is a probability that's sort of buried in the .75 probabilities. e.g. the probability there are three shoes at the front door, and he leaves through the back door. This probability is .5, but there's also the probability of .25 that he leaves through the front door and returns through the front door, returning us to state 3.

    Am I setting up the chain incorrectly? Basically, 50% of those 75% transition probabilities account for him running bare-foot, but I don't see anyway to include that in the transition matrix
     
  2. jcsd
  3. Mar 3, 2015 #2

    wabbit

    User Avatar
    Gold Member

    Hi your matrix looks alright to me, you can recheck it looking in each state at what happens in each case : front-to-back (front shoe count drops by 1 unless already 0), back-to-front (up 1 unless already 3) and other cases (no change).
     
  4. Mar 3, 2015 #3

    ElijahRockers

    User Avatar
    Gold Member

    Thanks for replying. Yea I get the transition probabilities are correct, but I'm not sure how to extract the barefoot running part of the question. If I could somehow represent that in the transition matrix, then I could find the steady state behavior and find the answer
     
  5. Mar 3, 2015 #4

    wabbit

    User Avatar
    Gold Member

    I'm not sure I get your point - the barefoot case is already included, that s why starting with state 0 and applying transition front-to-back you know what happens (nothing as it turns out) - without barefoot that would just be left undefined.


    Ooooh OK missed that question sorry. Give me a minute.

    Never mind, thought you were asked to determine the whole steady state distribution - anyway that's what I'd do :
    He runs barefoot when
    - starting from state 0 and going to front door, or
    - state 3 / back door
    So what you need is the steady state probability of state 0 and 3 (and 1 and 2 while you're at it). So your first task is to compute that steady state distribution. Do you know how to do that ?
    (You don't need to worry about bare feet at this point)
     
    Last edited: Mar 3, 2015
  6. Mar 3, 2015 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I think your matrix ##P## is OK, so I will deal mostly with other aspects of your question.

    If ##q(n) = (q_0(n), q_1(n),q_2(n),q_3(n))## (a row-vector) is the vector of state-occupancy probabilities at time ##n = 0,1,2, \ldots##, then we have
    [tex] q(n+1) = q(n) \cdot P [/tex]
    Note: this assumes the usual, but not universal) convention that ##p_{ij}## is the 1-step probability of going from state ##i## to state ##j##---so that the rows of ##P## sum to 1. Occasionally one sees the opposite convention, where the columns sum to 1 instead. (In your case it does not really matter, since ##P## is symmetric, so is its own transpose.)

    If we let ##n## denote the "leaving time", he runs barefoot with probability 1/2 in states 0 and 3, so the probability ##b(n)## that he runs barefoot at time ##n## is
    [tex] b(n) = \frac{1}{2} q_0(n) + \frac{1}{2} q_3(n) [/tex]
    Can you find the long-run average of the ##b(n)##, or the limiting value ##b(\infty) = \lim_{n \to \infty} b(n)##?

    You could also try to incorporate the bare/shod running conditions by re-defining "state" to mean "j shoes were at front door and am now running shod" or "j shoes were at front door and am now running barefoot". If we label the states as (0,s),(1,s),(2,s),(3,s), (0,b),(1,b), (2,b),(3,b) [s = shod, b = bare] then we have an 8-state Markov chain. However, you can easily recognize that states (1,b) and (2,b) do not really exist (because if there were 1 or 2 shoes at the front door he would not be running barefoot, no matter which door he used to go on his run). In other words, states (1,b) and (2,b) can never be occupied: we cannot start in either of them, and we can never reach them from any other state---so we might as well throw them out. Therefore, there are really just 6 states (0,s),(1,s),(2,s),(3,s),(0,b),(3,b). You can work out the 6×6 1-step transition probability matrix, and then get the long-run barefoot proportion by working out the long probabilities of being in states (0,b) or (3,b).
     
    Last edited: Mar 3, 2015
  7. Mar 3, 2015 #6

    ElijahRockers

    User Avatar
    Gold Member

    Thanks I think this will help. I tried making a state diagram of shod and bare earlier, but I switched to the shore count space because I thought it would be easier. I'll try it that way instead when I get home.
     
  8. Mar 3, 2015 #7

    wabbit

    User Avatar
    Gold Member

    Elijah : don't give up on getting the steady state distribution from your matrix. It's not difficult.
    Hint Ray included tte equation for q(n). What happens when n gets large ?
     
  9. Mar 3, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, but if you notice the symmetry it's very easy to get the steady state distribution. It immediately comes down to only one unknown.
     
  10. Mar 4, 2015 #9

    ElijahRockers

    User Avatar
    Gold Member

    Solved. Used the 4-state matrix, found the long run state-occupancy of state 0 and 3, and multiplied each by a half. Thanks y'all. :)
     
  11. Mar 4, 2015 #10

    wabbit

    User Avatar
    Gold Member

    Well done sir! :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted