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 (dark 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

⌫2
The ergodicity condition is therefore
⇢ =

⌫1
+

⌫2
< 1
Kernel method
This is just one of various ways that zero-pairs (x , y) will let vanish
parts of the functional equation
h1P(x , y) = h2P(x , 0) + h3P(0, y) + h4P(0, 0)
The function h1 is referred to as kernel, and choosing zeropairs
(x , y) such that h1(x , y) = 0 is known as the kernel method
Priority for queue 1 (p = 1)
h1P(x , y) = h2P(x , 0) + h3P(0, y) + h4P(0, 0)
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)
Priority for queue 1 (p = 1)
h1P(x , y) = h3P(0, y) + h4P(0, 0)
h1(x , y) = (+ ⌫1)xy x2y ⌫1y2
h2(x , y) = 0
h3(x , y) = ⌫2 x(1 y) + ⌫1 y(x y)
h4(x , y) = ⌫2 x(y 1)
Priority for queue 1 (p = 1)
y(x2 (+ ⌫1)x + ⌫1y) · P(x , y) = h3P(0, y) + h4P(0, 0)
Now use
⇠(y) =
+ ⌫1
p
(+ ⌫1)2 4⌫1y
2
for which h1(⇠(y), y) = 0. This yields
P(0, y) = h4(⇠(y), y)
h3(⇠(y), y)
P(0, 0)
and
P(x , y) =
h3(x , y)
h1(x , y)
P(0, y) +
h4(x , y)
h1(x , y)
P(0, 0)
The latter implies (with ⇢1 = /⌫1)
P(x , 1) =
1 ⇢1
1 ⇢1x ) P(N1 = n) = (1 ⇢1)⇢
n
1
Priority for queue 2 (p = 0)
Again the functional equation greatly simplifies due to
h3(x , y) = 0. Then, for ⌘(x) = ⌫2/(+ ⌫2 x), we see that
h1(x , ⌘(x)) = 0 and hence
P(x , 0) = h4(x , ⌘(x))P(0, 0)
h2(x , ⌘(x))
=
(⌫1⌫2 ⌫1x)(1 ⇢)
2(x x⇤)(x x⇤) =
c1
x x⇤ +
c2
x x⇤ ,
with
x⇤ =
+ ⌫1 + ⌫2
p
(+ ⌫1 + ⌫2)2 4⌫1⌫2
2
and
c1 =
(⌫1⌫2 ⌫1x⇤)(1 ⇢)
2(x⇤ x⇤) , c2 =
(⌫1⌫2 ⌫1x⇤)(1 ⇢)
2(x⇤ x⇤) .
Priority for queue 2 (p = 0)
This gives
P(x , 1) =
⌫1
x

c1
x x⇤ +
c2
x x⇤ (1 ⇢)

and
P(N1 = n) ⇠ ⌫
2
1x
⇤ ⌫21⌫2
3(x⇤ x⇤)(x⇤)2 (1 ⇢)
✓
1
x⇤
◆n
.
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
Consider the following random walk in the quarter plane
In the interior of the state space, the walk steps (1, 0) w.p.
1p
3 , (0,1) w.p. 1+p3 and (1, 1) w.p. 13 .
On the horizontal axis, the walk steps (1, 0) w.p. 12 and
(1, 1) w.p. 12 .
On the vertical axis, the walk steps (1, 0) w.p. 1p2 and
(0,1) w.p. 1+p2 .
Aziz, Starobinski and Thiran (2008):
Theorem
This model is unstable for p = 0 and stable for p 2 (0, 1].
Denote the joint stationary probabilities by P(N1 = n,N2 = k) and
let
P(x , y) =
1X
n=0
1X
k=0
P(N1 = n,N2 = k)xnyk
for which we have
h1(x , y)P(x , y) = h2(x , y)P(x , 0)+h3(x , y)P(0, y)+h4(x , y)P(0, 0),
(1)
with
h1(x , y) = 6xy 2(1 p)x2y 2y2 2(1 + p)x ,
h2(x , y) = (1 + 2p)x
2y + y2 2(1 + p)x ,
h3(x , y) = (1 p)x2y 2y2 + (1 + p)x ,
h4(x , y) = (2 + p)x
2y y2 (1 + p)x .
See FIM, Section 1.3, for a general description of how to derive
such functional equations.
Denote the joint stationary probabilities by
⇡(n, k) = P(N1 = n,N2 = k) = lim
t!1P(N1(t) = n,N2(t) = k)
Theorem
For the case p = 1 the stationary distribution of the random walk
has a closed-form solution with ⇡(0, 0) = ⇡(0, 1) = (2p2)/6,
⇡(1, 0) = (
p
2 1)/3 and
⇡(n, k) =
✓
1p
2
◆n ✓
1 1p
2
◆k+1
, n, k 1, (2)
⇡(n, 0) =
2
3
✓
1 1p
2
◆✓
1p
2
◆n
, n 2, (3)
⇡(0, k) =
1
3
✓
1 1p
2
◆k
, k 2. (4)
Proof
For the case p = 1 the balance equations for n 2 read
⇡(n, k) =
1
3
⇡(n + 1, k 1) + 2
3
⇡(n, k + 1), k 2, (5)
⇡(n, 1) =
1
2
⇡(n + 1, 0) +
2
3
⇡(n, 2), (6)
⇡(n, 0) =
2
3
⇡(n, 1) +
1
2
⇡(n 1, 0). (7)
First substitute a trial solution ⇡(n, k) = C · ↵nk and
⇡(n, 0) = C · d · ↵nk into (5) and (6), and divide by ↵nk1 to
obtain
=
1
3
↵+
2
3
2, (8)
=
1
2
d↵+
2
3
2, (9)
and hence d = 23 . Substituting the same trial solution into (7)
yields (upon some rewriting)
↵ = ↵ +
1
2
. (10)
Note that it follows from (10) and ↵ < 1 that < 12 .
Combining these equations gives an equation for
23 52 + 3 1
2
= 0 (11)
with solutions 12(2
p
2), 12 ,
1
2(2 +
p
2). Therefore, the values of ↵
and that lead to a convergent solution of the stationary
distribution are given by
↵ =
1p
2
, = 1 1p
2
. (12)
We now need to match this trial solution with the remaining
balance equations:
⇡(0, k) =
1
3
⇡(1, k 1) + ⇡(0, k + 1), k 2, (13)
⇡(0, 1) =
1
2
⇡(1, 0) + ⇡(0, 2), (14)
⇡(1, 0) =
2
3
⇡(1, 1) + ⇡(0, 0). (15)
Substituting the trial solution ⇡(n, k) = C · · k into (13) yields
= 2 + 13↵ and hence (with ↵, as in (12))
=
↵
3(1 ) =
2
6 3p2 .
Combining (14), (15) and ⇡(0, 0) = ⇡(0, 1) yields ⇡(0, 0) = 13C .
Summing over all probabilities identifies the normalization constant
as C = 1 1p
2
, which completes the proof.
Corollary
For the case p = 1 we have the marginal distributions
P(N1 = n) =
7
p
2 8
6
✓
1p
2
◆n
, n 1, (16)
P(N2 = k) =
✓
1
3
+
1p
2
◆✓
1 1p
2
◆k
, k 1, (17)
P(N1 = 0) = 13p2 ⇡ 0.2357 and P(N2 = 0) = 2+
p
2
6 ⇡ 0.5690.
In terms of generating functions we thus find that
P(x , y) =
2
3
2p2 + (p2 1)(x + y) (3 2p2)xy
(2p2x)(2 (2p2)y) (18)
and
P(x , 0) =
2p2 + (p2 1)x
6 3p2x , P(0, y) =
2p2 + (p2 1)y
6 3(2p2)y ,
and it is straightforward to check that these functions satisfy the
functional equation (1). Starting from the functional equation (1)
and deriving, in a direct way, (18) as its solution is an open
problem and would be of interest from a methodological
perspective. Who can tell me how to do this?
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
The tandem queue with p = 0, 1 are typical examples of the kernel
method as it is known in the field of combinatorics:
Prodinger (2004), Pemantle & Wilson (2008), Flajolet & Sedgewick
(2008), Bousquet-Melou (2000-2008) and many many more works
The kernel method has also a long history in two-queue models:
join-the-shortest-queue Kingman (1961), serve-the-longest-queue
Flatto (1989), coupled processors Fayolle & Iasnogorodski (1979)
These queueing models are among the most dicult random walks in the
quarter plane and typically lead to a solution in terms of
(Riemann-Hilbert) boundary value problems:
Malyshev (1972, pioneering work), Cohen (1988, survey) and
textbooks by Cohen & Boxma (1983), Fayolle, Iasnogorodski &
Malyshev (1999), JvL (2005), JvL & Resing (2006), JvL &
Guillemin (2009)
The tandem queue with p 2 (0, 1) yields a random walk that
requires the boundary value technique
The solution of P(x , y) will be dicult and does not allow for
explicit inversion
We therefore aim at deriving expressions of the type
P(N1 = n) ⇠ f (n) · ⇣n
This requires:
1 A full solution of P(x , y), and P(x , 1) =
P1
n=0 P(N1 = n)xn
2 Determining the dominant singularity ⇣ of P(x , 1)
3 Obtaining asymptotics using singularity analysis
Asymptotics for priority case
Change the notation (my sincere apologies!) according to
⌫1 = ⌫2 = µ1 + µ2 and p = µ1/(µ1 + µ2) and assume
+ µ1 + µ2 = 1 The functional equation becomes
h1(x , y)P(x , y) = h2(x , y)P(x , 0)+h3(x , y)P(0, y)+h4(x , y)P(0, 0)
where
h1(x , y) = xy x2y µ1y2 µ2x ,
h2(x , y) = µ2(y
2 x),
h3(x , y) = µ1(x y2),
h4(x , y) = µ1x(y 1) + µ2y(x y).
and in case we give priority to station 1, µ2 = 0 and things simplify.
As earlier, we find that
P(x , y) =
⇢1x(1 ⇠(y)) + x y
(⇢1 + 1)x ⇢1x2 y P(0, y), (19)
where ⇢i = /µi and
P(0, y) =
(1 y)P(0, 0)
1 y ⇢2y(1 ⇠(y)) , (20)
(P(0, 0) = 1 ⇢1 ⇢2) and
⇠(y) =
1 + ⇢1
2⇢1

1
q
1 4⇢1y/(1 + ⇢1)2

. (21)
From this it follows that
P(1, y) =
1 y + ⇢1(1 ⇠(y))
1 y P(0, y). (22)
The function ⇠(y) represents the pgf of the number of customers
served in a busy period of an M/M/1 queue with arrival rate
and service rate µ1. Denote this random variable by ⇠. Then:
P(⇠ = n) = 1
n
✓
2n 2
n 1
◆
⇢n11
(1 + ⇢1)2n1
, n = 1, 2, . . . . (23)
Stirling’s approximation n! ⇠ nnenp2⇡n yields✓
2n
n
◆
⇠ 2
2n
p
⇡n
, (24)
and thus
P(⇠ = n) ⇠ 1
n
22n2p
⇡(n 1)
1 + ⇢1
⇢1
⇢n1
(1 + ⇢1)2n
=
1 + ⇢1
2⇢1
1
2
p
⇡n3
p
np
n 1
⇣ 4⇢1
(1 + ⇢1)2
⌘n
⇠ 1 + ⇢1
2⇢1
1
2
p
⇡n3
⇣ 4⇢1
(1 + ⇢1)2
⌘n
. (25)
We are primarily interested in P(N2 = n) for n large, but we don’t
have an explicit inversion of the pgf. Therefore, we resort to
singularity analysis.
For general ↵ we have that
[zn](1 z)↵ = (1)n
✓
↵
n
◆
=
✓
n + ↵ 1
n
◆
=
(n + ↵)
(↵)(n + 1)
,
(26)
where (z) is the Gamma function defined for Re(z) > 0 as
(z) =
Z 1
0
tz1etdt. (27)
Applying Stirling’s approximation (n + 1) ⇠ nnenp2⇡n then
gives (see e.g. Flajolet & Sedgewick 2009)
[zn](1 z)↵ = n
↵1
(↵)
⇣
1 +O(1/n)
⌘
. (28)
We now apply the above result to ⇠(y). Denote by Cy the complex
y -plane and observe that the function ⇠(y) is analytic in
Cy\[(1 + ⇢1)2/(4⇢1),1), i.e. it has a branch point at
yB =
(1 + ⇢1)2
4⇢1
. (29)
This particular case is covered by (28) with ↵ = 1/2, which gives
P(⇠ = n) = [yn]⇠(y) = 1 + ⇢1
2⇢1
[yn]
q
1 4⇢1y/(1 + ⇢1)2
= 1 + ⇢1
2⇢1
⇣ 4⇢1
(1 + ⇢1)2
⌘n
[yn]
p
1 y
= 1 + ⇢1
2⇢1
⇣ 4⇢1
(1 + ⇢1)2
⌘n n3/2
(1/2)
⇣
1 +O(1/n)
⌘
=
1 + ⇢1
2⇢1
⇣ 4⇢1
(1 + ⇢1)2
⌘n 1
2
p
⇡n3
⇣
1 +O(1/n)
⌘
.(30)
Note that (30) yields (25).
We now turn to the function P(1, y) and study the asymptotic
behavior of
[yn]P(1, y) = P(N2 = n)
by means of singularity analysis. The singularities of P(1, y)
consist of the branch point yB and zeros of the denominator of the
right-hand side of (20):
1 y ⇢2y(1 ⇠(y)) = 0. (31)
The question then is which singularity has the smallest modulus,
since the singularity of P(1, y) with the smallest modulus is
dominant and determines the asymptotic behavior of the
coecients of P(1, y), i.e. P(N2 = n), for large values of n.
Because we already know that P(1, y) has a branch point in yB , it
remains to be investigated whether P(1, y) has a pole in
1 < |y | < yB , so whether (31) has a solution in 1 < |y | < yB .
First observation
Lemma
If
⇢2 <
2⇢1(1 ⇢1)
(1 + ⇢1)2
=: ⇢c , (32)
then the only solution to (31) in the region |y | < yB is given by
y = 1.
Proof Rouche´’s theorem. ⇤
Candidate solutions
We seek for solutions to (31), or
1 4⇢1
(1 + ⇢1)2
y =
⇣ 2⇢1
1 + ⇢1
⇣ 1
⇢2y
1
⇢2
1
⌘
+ 1
⌘2
. (33)
The relevant solution is given by
yP =
⇢2 ⇢1 ⇢1⇢2 +
q
4⇢1⇢22 + (⇢2 ⇢1 ⇢1⇢2)2
2⇢22
. (34)
Lemma
If ⇢2 < ⇢c , the dominant singularity of the function P(1, y) is the
branch point yB . If ⇢2 > ⇢c , the dominant singularity of the
function P(1, y) is the pole yP . If ⇢2 = ⇢c , the dominant
singularity of the function P(1, y) is yB = yP .
Lemma
P(1, y) ⇡
8<: P(1, yB) + 1
p
1 y/yB , ⇢2 < ⇢c ,
2/
p
1 y/yB , ⇢2 = ⇢c ,
3/(1 y/yP), ⇢2 > ⇢c ,
(35)
where P(1, y) ⇡ f (y) indicates that P(1, y)/f (y)! 1 when y
tends to its dominant singularity yB or yP , and
1 = 2P(0, 0)⇢1(1 + ⇢1)(⇢2 + 2⇢1⇢2 + ⇢
2
1(4 + ⇢2))
(⇢2 + ⇢21(2 + ⇢2) 2(1 ⇢2)⇢1)2
,
2 =
2P(0, 0)⇢1(1 ⇢1)
⇢2(1 + ⇢1)2
,
3 =
P(0, 0)
yP
· 1 yP + ⇢1(1 ⇠(yP))1 ⇢2(1 ⇠(yP)) + ⇢2yP⇠0(yP) .
Applying (28) for ↵ = 1/2, 1/2 and 1 then yields
Theorem
(a) If ⇢2 < ⇢c ,
P(N2 = n) ⇠ 1 1
2
p
⇡n3
✓
1
yB
◆n
.
(b) If ⇢2 = ⇢c ,
P(N2 = n) ⇠ 2 1
2
p
⇡n
✓
1
yB
◆n
.
(c) If ⇢2 > ⇢c ,
P(N2 = n) ⇠ 3
✓
1
yP
◆n
,
Methods for tail asymptotics
Generating function methods: Malyshev 1972, 1973; Flatto
and McKean 1977; Fayolle and Iasnogorodski 1979; Fayolle,
King and Mitrani 1982; Cohen and Boxma 1983; Flatto and
Hahn 1984; Flatto 1985; Fayolle, Iasnogorodski and Malyshev
1991; Wright 1992; Kurkova and Suhov 2003; JvL 2005;
Morrison 2007; JvL-Guillemin 2009;
Probabilistic methods: McDonald 1999; Borovkov and
Mogul’skii 2001; Foley and McDonald 2001, 2005-2009,
Miyazawa 2008-2009
Matrix analytic methods: Takahashi, Fujimoto and Makimoto
2001; Haque 2003; Miyazawa 2004; Miyazawa and Zhao 2004;
Kroese, Scheinhardt and Taylor 2004; Haque, Liu and Zhao
2005; Motyer and Taylor 2006; Li, Miyazawa and Zhao 2007;
He, Li and Zhao 2008
Combinatorics: Bousquet-Melou 2005-2009; Mishna
2006-2009; Hou and Mansour 2008, and many more...
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
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)
A closer look at the kernel
We have that h1(X±(y), y) = 0 with
X±(y) =
1
2y
⇣
(rˆ y 1/r2)±
p
d2(y)
⌘
where rˆ = 1 + 1/r1 + 1/r2, r1 = /(p⌫1), r2 = /((1 p)⌫2) and
d2(y) = (rˆ y 1/r2)2 4y3/r1
d2(y) has three roots in R: 0 < y1 < y2  1 < y3
d2(y) > 0 for y 2 (1, y1) [ (y2, y3)
d2(y) < 0 for y 2 (y1, y2) [ (y3,1)
Similarly, h1(x ,Y±(x)) = 0 for
Y±(x) =
r1
2
⇣
(rˆ x)x ±
p
d1(x)
⌘
where d1(x) = ((rˆ x)x)2 4x/(r1r2)
d1(x) has four real roots: x1 = 0 < x2  1 < x3 < x4
d1(x) > 0 for x 2 (1, x1) [ (x2, x3) [ (x4,1)
d1(x) < 0 for x 2 (x1, x2) [ (x3, x4).
Analytic continuation
Lemma
The function X ⇤(y) defined in C \ ([y1, y2] [ [y3,1)) by
X ⇤(y) =
⇢
X+(y) when y 2 {z : <(z)  y2,=(d2(z+)) < 0} [ (1, y1)
X(y) otherwise
where z+ = <(z) + i |=(z)|, is analytic
Lemma
The function Y ⇤(x) defined in C \ ([x1, x2] [ [x3, x4]) by
Y ⇤(x) =
8<: Y+(x) when x 2 {z : <(z)  x2,=(d1(z
+)) < 0} [ (1, x1)
Y+(x) when x 2 {z : <(z) x3,=(d2(z+)) > 0} [ (x4,1)
Y(x) otherwise
is analytic
Theorem
The function X ⇤(y) is a conformal mapping from Dy onto Dx .
The reciprocal function is Y ⇤(x)
Lemma
We have X ⇤(@Dy ) ⇢ [x1, x2] and Y ⇤(@Dx) ⇢ [y1, y2]
Boundary value problem
When h1(x , y) = 0 we have that
P(x , 0) =
p
1 pP(0, y) (1 ⇢)
h4(x , y)
h2(x , y)
and hence for x 2 @Dx and y = Y ⇤(x)
= (P(x , 0)) = =
✓
(1 ⇢)h4(x , y)
h2(x , y)
◆
This is a classical Riemann-Hilbert problem. Simple calculations
yield
=
✓
h4(x , y)
h2(x , y)
◆
=
⌫2y(r1x2 y)
2ir1x(1 p)Qx(y)
where Qx(y) = ⌫1y2 + ⌫2(⌫2 ⌫1 + )y ⌫22
Theorem
The function P(x , 0) is given by
P(x , 0) =
8>><>>:
1
2⇡i
Z
@Dx
gx(z)
z x dz for x 2 Dx ,
gx(x) +
1
2⇡i
Z
@Cx
gx(z)
z x dz for x 2 C \ Dx ,
(36)
where Cx is a contour in Dx surrounding the slit [x1, x2] and such
that the function gx given by
gx(x) = (1 ⇢)⌫2Y
⇤(x)(p⌫1Y ⇤(x) x2)
(1 p)xQx(Y ⇤(x)) (37)
The function P(x , 0) is a meromorphic function in C \ [x3, x4] with
singularities at the solutions to the equation Qx(Y ⇤(x)) = 0 if
they exist
Resultants
When h1(x , y) = 0 we have that
P(x , 0) =
p
1 pP(0, y) (1 ⇢)
h4(x , y)
h2(x , y)
The common solutions of the equations h1(x , y) = 0 and
h2(x , y) = 0 are then potential singularities for the function P(x , 0)
The resultant in x of the polynomials h1(x , y) and h2(x , y) is a
polynomial of degree 5
Qy (x) = ⌫2⌫1(1 p)2x2(x 1)Qy (x)
where Qy (x) = 2x2 (+ ⌫1 + ⌫2)x + ⌫1⌫2. This quadratic
polynomial has two roots, one of which
x⇤ =
+ ⌫1 + ⌫2
p
(+ ⌫1 + ⌫2)2 4⌫1⌫2
2
2 (1, x3]
The resultant in y of the polynomials h1(x , y) and h2(x , y) is a
polynomial of degree 5
Qx(y) = ⌫1(1 p)2y2(y 1)Qx(y)
where Qx(y) = ⌫1y2 + ⌫2(⌫2 ⌫1 + )y ⌫22 . This quadratic
polynomial has two roots, one of which
y⇤ =
⌫2
2⌫1
✓
(⌫2 ⌫1 + ) +
q
(⌫2 ⌫1 + )2 + 4⌫1
◆
2 (1, y3]
Lemma
The equation Qx(Y ⇤(x)) = 0 has a solution in (1, x3], which is
necessarily equal to x⇤ 2 (1, x3], if and only if y⇤ = Y ⇤(x⇤)
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
What were we doing again?
Let us return to
P(x , 1) =
1X
n=0
P(N1 = n)xn
for which the key functional equation gives
P(x , 1) = ⌫1
(1 p)P(x , 0) pP(0, 1) (1 p)(1 ⇢)
x p⌫1
The dominant singularity of P(x , 1) will thus be one of the
following three candidates:
1 x = x3
2 x = x⇤
3 x = p⌫1 =
1
r1
Lemma
If r2  1, then
(1 p)P r11 , 0 pP(0, 1) (1 p)(1 ⇢) = 0
and 1/r1 is removable. If r2 > 1 (and then r1  1 by stability) we
have
(1 p)P r11 , 0 pP(0, 1) (1 p)(1 ⇢) < 0
and the point 1/r1 is a singularity of P(x , 1)
Theorem
I. If y⇤ = Y ⇤(x⇤) and x⇤ < x3, which can occur only if r1  1, then
P(N1 = n) ⇠ (1)1
✓
1
x⇤
◆n
II. If y⇤ 6= Y ⇤(x⇤) and r2 > 1 (and then r1  1),
P(N1 = n) ⇠ (1)2 (r1)n
III. If y⇤ 6= Y ⇤(x⇤) and r2  1, 1/r1 is removable from P(x , 1) and
P(N1 = n) ⇠ (1)3
1
n
p
n
✓
1
x3
◆n
IV. If y⇤ = Y ⇤(x⇤) and x⇤ = x3,
P(N1 = n) ⇠ (1)4
1p
n
✓
1
x3
◆n
where
(1)1 =
⌫1⌫2(1 ⇢)((1 p)⌫2x⇤ p⌫1(y⇤)2)
(x⇤ p⌫1)(⌫22 + ⌫1(y⇤)2)x⇤
(1)2 = P(0, 1) +
1 p
p

1 ⇢ P(r11 , 0)

(1)3 =
(1 ⇢)⌫1⌫2
4
p
⇡(x3 p⌫1)
2(1p)
p⌫2
x23 + 2x3 (p+ ⌫1)
Qy (x3)Q⇤y (x3)
p
x3⌧x
(1)4 =
(1 ⇢)⌫1⌫2
2
p
⇡(x3 p⌫1)
2(1p)
p⌫2
x23 + 2x3 (p+ ⌫1)p
x3Q0y (x3)Q⇤y (x3)
⌧x
with ⌧x =
p
(x3 x1)(x3 x2)(x4 x3) and
Q⇤y (x) =
1
2
✓
x p⌫1y
⇤
x⇤
◆✓
x p⌫1y⇤
x⇤
◆
.
Example Case I
Take as parameter values
= 1.1, ⌫1 = 6, ⌫2 = 9, p = 0.5, r1 = 0.37, r2 = 0.24, ⇢ = 0.31
for which
x⇤ = 4.3303, y⇤ = Y ⇤(x⇤) = 1.6864, (1)1 = 0.5392
and
n P(N1 = n) (1)1 (x⇤)n
10 2.3921e-007 2.3261e-007
20 1.0087e-013 1.0034e-013
50 8.0560e-033 8.0552e-033
100 1.2033e-064 1.2033e-064
200 2.6854e-128 2.6854e-128
300 5.9927e-192 5.9927e-192
Example Case II
Take as parameter values
= 1.1, ⌫1 = 6, ⌫2 = 2, p = 0.7, r1 = 0.26, r2 = 1.83, ⇢ = 0.73
for which
x⇤ = 1.4545, y⇤ = 1.3333 6= Y ⇤(x⇤) = 1.5584, (1)2 = 0.4620
and
n P(N1 = n) (1)2 (r1)n
10 7.9471e-007 7.0154e-007
20 1.1343e-012 1.0653e-012
50 3.7864e-030 3.7307e-030
100 3.0200e-059 3.0127e-059
200 1.9649e-117 1.9647e-117
300 1.2813e-175 1.2813e-175
Similar results can be obtained for N2
The same technique applies to the general class of
two-dimensional one-step random walks in the quarter plane
Determining the dominant singularities could be done without
resorting to the boundary value technique
Many interesting and classical special cases












































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































学霸联盟