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

《3rd Edition Chapter 1 - F A R A D A Y第三版1章- F R D y.ppt》由会员分享，可在线阅读，更多相关《3rd Edition Chapter 1 - F A R A D A Y第三版1章- F R D y.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Part IIIMarkov Chains&Queueing Systems10.Discrete-Time Markov Chains11.Stationary Distributions&Limiting Probabilities12.State Classification13.Limiting Theorems For Markov Chains14.Continuous-Time Markov Chains110.Discrete-Time Markov Chain Definition of Markov Processes A random process is said to

2、 be a Markov 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 a

3、nd Aperiodic 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 j suc

4、h 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.2Consider t

5、he 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：021654332Theorem 12.2If

6、 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 all time,has expec

7、ted 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 state 2 or to state 4 and the

8、system then remains forever in the corresponding communicating class.24310537Part IIIMarkov Chains&Queueing Systems10.Discrete-Time Markov Chains11.Stationary Distributions&Limiting Probabilities12.State Classification13.Limiting Theorems For Markov Chains14.Continuous-Time Markov Chains3813.Limitin

9、g 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 irreducible system consistin

10、g 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 vector and is the unique vector satis

11、fying40Theorem 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 calculate the stationary probabilities .Sol：0

12、11/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 received in error,the transmitter enters a timeout s

13、tate.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 error.Construct a Markov chain for this system.What

14、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 the state space into disjoint subsets S and S,Pf：46Example 1

15、3.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 in all other slots.This packets is stored as long as the router i

16、s 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.That packet is then removed from the router.Let Xn denote the number of

17、 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,recurrent,periodic,finite Markov chain with transition matrix P,the station

18、ary 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 communicating classes C1,Cm,let denote the limiting state probabilities associated with cl

19、ass 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 state i0,1,4,find the limiting state probabilities for the following Markov chain.Sol：

20、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 chains)Multiple communicating classes represent distinct system modes that are coupled only thr

21、ough 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 router either store an arriving data packet in its buffer or forward a stored packet(and remove

22、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 buffer and forwarded.Sketch the Markov chain for Xn,the number of buffered packets at time n.Sol：210p1

23、pp1pp1p1p54Theorem 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 the n-step transition probabilities or n iterations with the one-step transition probabilitiesPf：Omitted

24、.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)Tii is the time(number of transitions)until the system first returns to state i,(c)Nii is the number of times(i

25、n 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 with 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 r

26、ecurrent?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=.Pf：60Example 13.8The discrete random walk introduced in Example 10.4 has state space,1,0,1,and Markov chainIs state 0 recurrent

27、?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.Definition：The Communicating Classes of a Continuous-Time Markov Chain are given by the communicating classes of its embedded discrete-t

28、ime 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 sta

29、te i satisfying ETii 1.21012230134378Theorem 14.3For a birth-death queue with arrival rate i and service rate i,the stationary probabilities pi satisfyPf：79Theorem 14.4For a birth-death queue with arrival rate i and service rate i,let i=i/i+1.The limiting state probabilities,if they exist,arePf：80Th

30、e M/M/1 QueueThe arrivals are a Poisson process of rate ,independent of the service requirements of the customers.The service time of a customer is an exponential()R.V.,independent of the system state.M/M/1Markovian arrival(Poisson arrivals)Markovian service time(Exponential R.V.)One server81Theorem

31、 14.5The M/M/1 queue with arrival rate 0 and service rate ,has limiting state probabilities,where =/.Pf：82Example 14.5Cars arrive at an isolated toll booth as a Poisson process with arrival rate =0.6 cars per minute.The service required by a customer is an exponential R.V.with expected value 1/=0.3 minutes.What are the limiting state probabilities for N,the number of cars at the toll booth?What is the probability that the toll booth has zero cars some time in the distant future?Sol：83