3rd Edition Chapter 1 - F A R A D A Y第三版1章- F R D y

1、Part IIIMarkov Chains & Queueing SystemsDiscrete-Time Markov ChainsStationary Distributions & Limiting ProbabilitiesState ClassificationLimiting Theorems For Markov ChainsContinuous-Time Markov Chains110. Discrete-Time Markov Chain Definition of Markov Processes A random process is said to be a Mark

2、ov Process if, for any set of n time points t1t2 0 for some n 0.Communicating States State i and j communicates, written i j, if i j and j i.Communicating Class A communicating class is a nonempty subset of states C such that if i C , then j C if and only if i j.27State ClassificationPeriodic and Ap

3、eriodic State i has period d if d is the largest integer such that pii(n) = 0 whenever n is not divisible by d (pii(n) 0 whenever n is divisible by d). If d = 1, then state i is called aperiodic. Transient and Recurrent States In a finite Markov chain, a state i is transient if there exists a state

4、j such that i j but j i; otherwise, if no such state j exists, then state i is recurrent.Irreducible Markov chain A Markov chain is irreducible if there is only one communicating class. 28Example 12.1The Markov chain is with each branch pij 0. How many communicating classes?Sol：021654329Example 12.2

5、Consider the five-state discrete random walk with Markov chain What is the period of each state i ? Sol：24310p1pp1pp111p30Theorem 12.1Communicating states have the same period. Pf：31Example 12.3The Markov chain is with each branch pij 0. Find the periodicity of each communicating class.Sol：021654332

6、Theorem 12.2If i is recurrent and i j, then j is recurrent.Sol：33Example 12.4The Markov chain is with each branch pij 0. Identify each communicating class and indicate whether it is transient or recurrent.Sol：24310534Theorem 12.3If state i is transient, then Ni, the number of visits to state i over

7、all time, has expected value ENi 0. If the system starts in state j C1 = 0, 1, 2, the system never leaves C1.If the system starts in communicating class C3 = 4, 5, the system never leaves C3.If the system starts in the transient state 3, then in the first step there is a random transition to either

8、state 2 or to state 4 and the system then remains forever in the corresponding communicating class. 24310537Part IIIMarkov Chains & Queueing SystemsDiscrete-Time Markov ChainsStationary Distributions & Limiting ProbabilitiesState ClassificationLimiting Theorems For Markov ChainsContinuous-Time Marko

9、v Chains3813. Limiting Theorems For Markov ChainsFor Markov chains with multiple recurrent classes, the limiting state probabilities depend on the initial state distribution.For understanding a system with multiple communicating classes, we need to examine each recurrent class separately as an irred

10、ucible system consisting of just that class.In this part, we first focus on irreducible, aperiodic chains and their limiting state probabilities.39Theorem 13.1For an irreducible, aperiodic, finite Markov chain with states 0, 1, 2, , K, the limiting n-step transition matrix iswhere is the column vect

11、or and is the unique vector satisfying40Theorem 13.1 (contd)Pf：41Theorem 13.2For an irreducible, aperiodic, finite Markov chain with transition matrix P and initial state probability vector p(0) , Pf：42Example 13.1For the packet voice communications system of Example 12.8, use Theorem 13.2 to calcul

12、ate the stationary probabilities . Sol：011/1401/10099/100139/14043Example 13.2A digital mobile phone transmits one packet in every 20-ms time slot over a wireless connection. A packet is received error with probability p = 0.1, independent of other packets. Whenever 5 consecutive packets are receive

13、d in error, the transmitter enters a timeout state. During the timeout state, the mobile terminal performs an independent Bernoulli trial with success probability q = 0.01 in every slot. When a success occurs, the mobile terminal starts transmitting in the next slot as though no packets had been in

14、error. Construct a Markov chain for this system. What are the limiting state probabilities? 44Example 13.2 (Contd)Sol：24310p1pp1pp1pp1pp5q1p1q45Theorem 13.3Consider an irreducible, aperiodic, finite Markov chain with transition probabilities pij and stationary probabilities i. For any partition of t

15、he state space into disjoint subsets S and S, Pf：46Example 13.3 In each time slot, a router can either store an arriving data packet in its buffer or forward a stored packet (and remove that packet from its buffer). In each time slot, a new packet arrives with probability p, independent of arrivals

16、in all other slots. This packets is stored as long as the router is storing fewer than c packets. If c packets are already buffered, then the new packet is discarded by the router. If no new packet arrives and n 0 packets are buffered by the router, then the router will forward one buffered packet.

17、That packet is then removed from the router. Let Xn denote the number of buffered packets at time n. Sketch the Markov chain for Xn and find the stationary probabilities. 47Example 13.3 Sol：ii+110p1pp1pp1p1pcp1ppSS48Periodic States and Multiple Communicating Classes Theorem 13.4：For an irreducible,

18、recurrent, periodic, finite Markov chain with transition matrix P, the stationary probability vector is the unique nonnegative solution ofPf：49Example 13.4Find the stationary probabilities for the Markov chain shown to the right. Sol：21011150Theorem 13.5 For a Markov chain with recurrent communicati

19、ng classes C1, Cm, let denote the limiting state probabilities associated with class k. Given that the system starts in a transient state i, the limiting probability of state j iswhere PBik is the conditional probability that the system enters class Ck.Pf：51Example 13.5For each possible starting sta

20、te i0,1,4, find the limiting state probabilities for the following Markov chain. Sol：2103/41/21/4431/21/21/41/43/41/23/452Countably Infinite ChainsCountably infinite Markov chains has infinite set of states 0, 1, 2, . We will consider only a single communicating class here. (Irreducible Markov chain

21、s)Multiple communicating classes represent distinct system modes that are coupled only through an initial transient phase that results in the system landing in one of the communicating classes.53Example 13.6Suppose that the router in Example 13.3 has unlimited buffer space. In each time slot, a rout

22、er either store an arriving data packet in its buffer or forward a stored packet ( and remove that packet from its buffer). In each time slot, a new packet is stored with probability p, independent of arrivals in all other slots. If no new packet arrives, then one packet will be removed from the buf

23、fer and forwarded. Sketch the Markov chain for Xn, the number of buffered packets at time n. Sol：210p1pp1pp1p1p54Theorem 13.6：Chapman-Kolmogorov Eqs.The n-step transition probabilities satisfyPf：Omitted.55Theorem 13.7The state probabilities pj(n) at time n can be found by either one iteration with t

24、he n-step transition probabilities or n iterations with the one-step transition probabilitiesPf：Omitted.56Visitation, First Return Time, No. of ReturnsDefinitions：Given that the system is in state i at an arbitrary time,(a) Eii is the event that the system eventually returns to visit state i. (b) Ti

25、i is the time (number of transitions) until the system first returns to state i, (c) Nii is the number of times (in the future) that the system returns to state i.Definition：For a countably infinite Markov chain, state i is recurrent if PEii=1; otherwise state i is transient.57Example 13.7A system w

26、ith states 0, 1, 2, has Markov chainNote that for any state i 0, pi,0 = 1/(i+1) and pi,i+1= i/(i+1). Is state 0 transient or recurrent?Sol：243101/21/32/31/43/41/511/24/558Theorem 13.8The expected number of visits to state i over all time isPf：59Theorem 13.9State i is recurrent if and only if ENii= .

27、Pf：60Example 13.8The discrete random walk introduced in Example 10.4 has state space , 1, 0, 1, and Markov chainIs state 0 recurrent?Sol：02112p1pp1pp1pp1pp1pp1p61Positive Recurrence and Null RecurrenceDefinition：A recurrent state i is positive recurrent if ETii 0 and pii = 1 for states i with i = 0.

28、 Definition：The Communicating Classes of a Continuous-Time Markov Chain are given by the communicating classes of its embedded discrete-time Markov chain.69Irreducible Continuous-Time Markov ChainDefinition：A continuous-time Markov chain is irreducible if the embedded discrete-time Markov chain is irreducible. Definition：An irreducible continuous-time Markov chain is positive recurrent if for all states i, the time Tii to return to state i satisfying ETii 1. 21012230134378Theorem 14.3For a birth-death queue with arrival rate i and service rate i , the stationary probabilities pi satisfyPf