LECTURE 21ReviewBirth-Death ProcessM/M/1 Queue (1)M/M/1 Queue (2)The Phone Company Problem (1)The Phone Company Problem (2)M/M/m QueueGambler’s Ruin (1)Calculating Absorption ProbabilitiesGambler’s Ruin (2)Expected Time to AbsorptionLECTURE 21• Readings: Section 6.4Lecture outline• Markov Processes – III– Review of steady-state behavior– Queuing applications– Calculating absorption probabilities– Calculating expected time to absorptionReview• Assume a single class of recurrent states, aperiodic. Then, where does not depend on the initial conditions• . can be found as the unique solution of the balance equations:together withBirth-Death Process• General case:0 1 2 3 Nii + 1• Locally, we have:• Balance equations:• Why? (More powerful, e.g. queues, etc.)M/M/1 Queue (1)• Poisson arrivals with rate•Exponential service time with rate• server•Maximum capacity of the system =• Discrete time intervals of (small) length :N-1N0 1i-1i• Balance equations:• Identical solution to the random walk problem.M/M/1 Queue (2)• Define:•Then:• To get , use:• Consider 2 cases!The Phone Company Problem (1)• Poisson arrivals (calls) with rate• Exponential service time (call duration), rate• servers (number of lines)• Maximum capacity of the system =• Discrete time intervals of (small) length :N-1N0 1i-1i• Balance equations:• Solve to get:The Phone Company Problem (2)N-1N0 1i-1i• Balance equations:• Solution:• Consider the limiting behavior as . •Therefore:(Poisson)M/M/m Queue• Poisson arrivals with rate•Exponential service time with rate• servers•Maximum capacity of the system =• Discrete time intervals of (small) length :N-1Nj-1j0 1i-1im• Balance equations:Gambler’s Ruin (1)• Each round, Charles Barkley wins 1 thousand dollars with probability and looses 1 thousand dollars with probability• Casino capital is equal to• He claims he does not have a gambling problem!• Both and are absorbing! 0 1 2 mCalculating Absorption Probabilities• Each state is either transient or absorbing• Let be one absorbing state• Definition: Let be the probability that the state will eventually end up in given that the chain starts in state •For•For• For all other :Gambler’s Ruin (2)0 1 2 mExpected Time to Absorption1 234• What is the expected number of transitions until the process reaches the absorbing state, given that the initial state is ?•• For all other
View Full Document
Unlocking...