xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-2-D

时间：2021-03-22

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

学霸联盟

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

学霸联盟