LECTURE 20ReviewRecurrent and Transient StatesPeriodic StatesSteady-State ProbabilitiesExampleExampleVisit Frequency InterpretationRandom Walk (1)Random Walk (2)Random Walk (3)Birth-Death Process (1)Birth-Death Process (2)LECTURE 20• Readings: Section 6.3Lecture outline• Markov Processes – II– Markov process review.– Steady-state behavior.– Birth-death processes.Review• Discrete state, discrete time, time-homogeneous– Transition probabilities– Markov property• State occupancy probabilities, given initial state :• Key recursion:Recurrent and Transient States• State is recurrent if:– Starting from , and from wherever you can go, there is a way of returning to .• If not recurrent, a state is called transient.– If is transient then as . – State is visited a finite number of times.• Recurrent Class:– Collection of recurrent states that “communicate” to each other, and to no other state.5 1 23 4 6 789Periodic States• The states in a recurrent class are periodic if: – They can be grouped into groups so that all transitions from one group lead to the next group.2 75134896Steady-State Probabilities• Do the converge to some ?(independent of the initial state )•Yes, if:– Recurrent states are all in a single class, and– No periodicity.• Start from key recursion:– Take the limit as :– Additional equation:Example1 2Example1 2• Assume process starts at state 1.••Visit Frequency Interpretation• (Long run) frequency of being in :• Frequency of transitions :• Frequency of transitions into :jlkmRandom Walk (1)• A person walks between two ( -spaced) walls:– To the right with probability– To the left with probability– Pushes against the walls with the same probabilities. 0 1 2 mii + 1• Locally, we have:• Balance equations:Random Walk (2)• Justification:Random Walk (3)• Define:•Then:• To get , use:Birth-Death Process (1)• General (state-varying) case:0 1 2 3 mii + 1• Locally, we have:• Balance equations:• Why? (More powerful, e.g. queues, etc.)Birth-Death Process (2)• Special case: and for all and, again, define (called “load factor”). – Less general (but more so than the random walk).• Assume and (in
View Full Document
Unlocking...