We are often interested in the state an arriving customer observes in a queue. If arrivals are Poisson, then the average arrival sees the system in its equilibrium state.
This may seem counterintuitive. When a customer arrives, we might expect the system to be slightly emptier in anticipation of the arrival. However, this is not the case for Poisson processes: they are uniformly distributed over time, and arrivals after time 
Kelly’s Lemma provides a way of using the time reversal of a Markov chain to calculate its stationary distribution. In theory, it is just a rewrite of the stationary distribution and time-reversal results for continuous-time chains. However, in application, it is different; you can take a guess at the time reversal of a chain $Q’$, and if you are right, i.e., if it checks out in Kelly’s Lemma, you get the stationary distribution as a consequence.
Continue reading “Kelly’s Lemma”We quickly recap the results known for discrete time that also hold in continuous time. (The slight advantage from a modeling perspective is that in continuous time, transitions occur distinctly, which gives more chances for reversibility to hold)
Continue reading “Stationary Distributions (Continuous Time)”Many queues can be modeled as discrete-time Markov chains. Here, the state is the length of the queue, and fluctuations in arrivals and service give the random evolution from one time period to the next. Here is a diagram of a queue.
Figure: arrivals occur from the left and are stored in a buffer. Jobs or customers are represented as rectangles. A server is represented by a circle, which processes the jobs, and they then depart on the right-hand side.
Continue reading “A discrete-time single-server queue”
Applied Probability Notes 