M/M/1 Arrival and Departure Time Occupancy Distributions2.22002/08/092002/11/11BartSinclairbs@rice.eduCharletReedstromcharlet@rice.eduBartSinclairbs@rice.edu(Blank Abstract)
The continuous-time chain for the M/M/1 queue has the following
state transition graph.
The state probabilities are given by
πkρk1ρ.
Looking at the M/M/1 system only at transistions gives rise to
the following discrete-time chain.
The single-step probability matrix for the discrete-time chain
is
P01000…μλμ0λλμ00…0μλμ0λλμ0…00μλμ0λλμ…⋮⋮⋮⋮⋮
Solving
π′Pπ′ yields
π′1μλμπ′0π′11ρπ′0π′01π′2μλμπ′1π′21ρρπ′0π′1λλμπ′3μλμπ′2π′31ρρ2π′0π′2λλμπ′4μλμπ′3π′41ρρ3π′0
and in general,
kk1π′k1ρρk1π′0.
Normalization:
k0π′kπ′0k11ρρk1π′0π′011ρi0ρiπ′011ρ1ρ1π′01ρ2π′k1ρk11ρ22arrival sees k jobs ahead of itarrivalarrival in state karrival in state k & arrivalarrivalarrival in state karrivalarrivalk0π′kstate karrivalπ′01k1ρk11ρ22λλμ1ρ2k1ρk11ρ2λμλλλμ1ρ21ρ2k1ρk1ρ21ρ211ρ112
which could have been inferred directly since, for the system to
be stable, half of the transistions must be arrivals and half
must be departures (in the long run).
arrival sees k jobs ahead of itπ′kλλμ12ρk1ρ
What about departing jobs?
departing job leaves k jobsdeparturedeparture in state k+1departure in state k+1departureρk1ρ22μλμ12ρk1ρ2λμμμλμ12ρk1ρ
Hence, the probability that an arrival sees k jobs ahead of it
is equal to the probability that a departure leaves k jobs
behind it, which is equal to the probability that the system is
in state k in steady-state.