The continuous-time chain for the M/M/1 queue has the following
state transition graph.

The state probabilities are given by
π
k
=ρk(1−ρ)
π
k
ρ
k
1
ρ
.

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

P=(
01000…
μλ+μ0λλ+μ00…
0μλ+μ0λλ+μ0…
00μλ+μ0λλ+μ…
⋮⋮⋮⋮⋮
)
P
0
1
0
0
0
…
μ
λ
μ
0
λ
λ
μ
0
0
…
0
μ
λ
μ
0
λ
λ
μ
0
…
0
0
μ
λ
μ
0
λ
λ
μ
…
⋮
⋮
⋮
⋮
⋮

(1)
Solving

π
′
P=
π
′
π
′
P
π
′
yields

(
π
′
1μλ+μ=
π
′
0)⇒(
π
′
1=(1+ρ)
π
′
0)
π
′
1
μ
λ
μ
π
′
0
π
′
1
1
ρ
π
′
0
(
π
′
01+
π
′
2μλ+μ=
π
′
1)⇒(
π
′
2=(1+ρ)ρ
π
′
0)
π
′
0
1
π
′
2
μ
λ
μ
π
′
1
π
′
2
1
ρ
ρ
π
′
0
(
π
′
1λλ+μ+
π
′
3μλ+μ=
π
′
2)⇒(
π
′
3=(1+ρ)ρ2
π
′
0)
π
′
1
λ
λ
μ
π
′
3
μ
λ
μ
π
′
2
π
′
3
1
ρ
ρ
2
π
′
0
(
π
′
2λλ+μ+
π
′
4μλ+μ=
π
′
3)⇒(
π
′
4=(1+ρ)ρ3
π
′
0)
π
′
2
λ
λ
μ
π
′
4
μ
λ
μ
π
′
3
π
′
4
1
ρ
ρ
3
π
′
0
and in general,

∀k,k≥1:
π
′
k=(1+ρ)ρk−1
π
′
0
k
k
1
π
′
k
1
ρ
ρ
k
1
π
′
0
.

Normalization:
∑
k
=0∞
π
′
k=
π
′
0+∑
k
=1∞(1+ρ)ρk−1
π
′
0=
π
′
0(1+(1+ρ)∑
i
=0∞ρi)=
π
′
0(1+1+ρ1−ρ)=1
k
0
π
′
k
π
′
0
k
1
1
ρ
ρ
k
1
π
′
0
π
′
0
1
1
ρ
i
0
ρ
i
π
′
0
1
1
ρ
1
ρ
1
π
′
0=1−ρ2
π
′
0
1
ρ
2
π
′
k≥1=ρk−1(1−ρ2)2
π
′
k
1
ρ
k
1
1
ρ
2
2

Prarrival sees k jobs ahead of it=Prarrival in state k|
arrival
=Prarrival in state k & arrivalPrarrival=Prarrival in state kPrarrival
arrival sees k jobs ahead of it
arrival
arrival in state k
arrival in state k & arrival
arrival
arrival in state k
arrival

(2)
Prarrival=∑
k
=0∞
π
′
kPrarrival|
state k
=
π
′
01+∑
k
=1∞ρk−1(1−ρ2)2λλ+μ=1−ρ2+∑
k
=1∞ρk−1(1−ρ)2λ+μλλλ+μ=1−ρ2+1−ρ2∑
k
=1∞ρk=1−ρ2+1−ρ2(11−ρ−1)=12
arrival
k
0
π
′
k
state k
arrival
π
′
0
1
k
1
ρ
k
1
1
ρ
2
2
λ
λ
μ
1
ρ
2
k
1
ρ
k
1
1
ρ
2
λ
μ
λ
λ
λ
μ
1
ρ
2
1
ρ
2
k
1
ρ
k
1
ρ
2
1
ρ
2
1
1
ρ
1
1
2

(3)
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).

Prarrival sees k jobs ahead of it=
π
′
kλλ+μ12=ρk(1−ρ)
arrival sees k jobs ahead of it
π
′
k
λ
λ
μ
1
2
ρ
k
1
ρ
What about departing jobs?

Prdeparting job leaves k jobs=Prdeparture in state k+1|
departure
=Prdeparture in state k+1Prdeparture=ρk(1−ρ2)2μλ+μ12=ρk(1−ρ)2λ+μμμλ+μ12=ρk(1−ρ)
departing job leaves k jobs
departure
departure in state k+1
departure in state k+1
departure
ρ
k
1
ρ
2
2
μ
λ
μ
1
2
ρ
k
1
ρ
2
λ
μ
μ
μ
λ
μ
1
2
ρ
k
1
ρ

(4)
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.