Part 2
The kernel method for (reflected) 2-D random walks
Overview
1 Nice solutions
Lattice path counting
A tandem queue with priority
A weird example
2 Singularity analysis
Demonstration by example
3 Ugly solutions (dark side of the kernel method)
Boundary value problems
Asymptotics for rare events
Example from combinatorics
See Knuth (1973) or Prodinger (2004).
Start from the origin. Move from (n, i) to (n + 1, i ± 1),
except in the case i = 0, when you can only go to (n + 1, 1).
How many paths leads from the origin to (n, i)
Let the generating function fi (u) describe all walks leading to
(n, i). Then [un]fi (u) represents the number of walks from
(0, 0) to (n, i).
We can see that
fi (u) = ufi1(u) + ufi+1(u), i 1,
f0(u) = 1 + uf1(u)
and with F (u, z) =
P
i0 fi (u)z
i this gives
F (u, z) f0(u) = uzF (u, z) + u
z
[F (u, z) f0(u) zf1(u)]
F (u, z) = uzF (u, z) +
u
z
[F (u, z) F (u, 0)] + 1,
or better:
F (u, z) =
uF (u, 0) z
uz2 z + u .
The denominator vanishes for
z(u) =
1±p1 4u2
2u
.
The root z0(u) =
1p14u2
2u is the bad one, so for this root the
numerator should vanish as well:
uF (u, 0) = z0(u)
leading to an explicit representation of F (u, z).
Overview
1 Nice solutions
Lattice path counting
A tandem queue with priority
A weird example
2 Singularity analysis
Demonstration by example
3 Ugly solutions (da
rk side of the kernel method)
Boundary value problems
Asymptotics for rare events
A tandem queue with coupled processors
Customers arrive at queue 1 according to a Poisson process
with rate
Each customer requires a two-stage service with exponential
service times with mean 11 and
1
2
The total service rate is constant, 1 say
Queue 1 gets p and queue 2 gets 1 p of the service rate
If one of the queues is empty, the other queue gets service
rate 1
Preliminaries
Let N1(t) and N2(t) denote the queue lengths at time t. Let
P(N1 = n,N2 = k) = lim
t!1P(N1(t) = n,N2(t) = k)
We then aim at determining the bivariate generating function
P(x , y) = E(xN1yN2) =
X
n0
X
k0
P(N1 = n,N2 = k)xnyk
Key functional equation
h1P(x , y) = h2P(x , 0) + h3P(0, y) + h4P(0, 0)
where
h1(x , y) = (+ p 1 + (1 p) 2)xy x2y p 1y2 (1 p) 2x
h2(x , y) = (1 p) [ 1 y(y x) + 2 x(y 1)]
h3(x , y) = p [ 2 x(1 y) + 1 y(x y)]
h4(x , y) = p 2 x(y 1) + (1 p) 1 y(x y)
Key functional equation
h1P(x , y) = h2P(x , 0) + h3P(0, y) + h4P(0, 0)
where
h1(x , y) = (+ p 1 + (1 p) 2)xy x2y p 1y2 (1 p) 2x
h2(x , y) = (1 p) [ 1 y(y x) + 2 x(y 1)]
h3(x , y) = p · h2(x , y)/(1 p)
h4(x , y) = 2 x(y 1) h2(x , y)
With
(y) = 1y
2/( 1y 2y + 2)
we have h2((y), y) = 0 and hence
P((y), y) =
h4((y), y)
h1((y), y)
P(0, 0)
Letting y ” 1 yields
P(0, 0) = 1
1