# Rare events in a polling system:
Rays & Spirals

Robert D. Foley
ISYE Georgia Institute of Technology
<EMAIL_ADDRESS>

and

David R. McDonald
Mathematics and Statistics University of Ottawa
<EMAIL_ADDRESS>
###### Abstract

It’s a situation everyone dreads. A road is down to one lane for repairs.
Traffic is let through one way until the backlog clears and then traffic is
let through the other way to clear that backlog and so on. When stuck in a
very long queue it is inevitable to wonder how did I get into this mess?

We study a polling model with a server having exponential service time with
mean $1/\mu$ alternating between two queues, emptying one queue before
switching to the other. Customers arrive at queue one according to a Poisson
process with rate $\lambda_{1}$ and at queue two with rate $\lambda_{2}$. We
discuss how we get at a rare event with a large number of customers in the
system. In fact this can happen in two different ways depending on the
parameters. In one case one queue simply explodes and runs away without
emptying. We call this the ray case. In the other spiral case the queues are
successively emptied but in a losing battle as the system zigzags to the rare
event. This dichotomy extends to the steady state distribution and leads to
quite different asymptotic behaviour in the two cases.

AMS Subject Classification: 60J10 (primary), 60J50 (secondary).

##  1 Tandem polling model

We are interested in the way rare events occur and where possible in
estimating the steady state probability of these rare events for Markov chains
of the type that typically arise in modelling polling networks. The
probabilities of such rare events are usually difficult to obtain—simulation
can be very slow. Consider two queues labeled 1 and 2. A Poisson stream of
jobs arrives with intensity $\lambda_{1}$ to queue 1 where jobs are served in
order of arrival. A Poisson stream of jobs arrives with intensity
$\lambda_{2}$ to queue 2. Hence the customer arrival rate is
$\lambda=\lambda_{1}+\lambda_{2}$. A single server services both queues with
exponential service time having mean $1/\mu$. The server remains at a queue
serving jobs until there are no more jobs to serve before switching to the
other queue. If there are jobs present, the server is working. For convenience
and without loss of generality, we assume that $\lambda+\mu=1$. To avoid
degenerate situations, we assume that $\lambda_{1}>0$, $\lambda_{2}>0$ and
$\mu>0$.

There is a vast literature on polling systems. The earliest reference is [35]
and a good review is found in [36]). The paper [5] considers our model with
the additional twist that if queue 2 is being served but queue 1 reaches a
threshhold then the server preemptively switches back to serving queue 1. [6]
deals with our exhaustive service model as well as the threshhold model. Both
papers are able to give the joint generating function of the steady state
joint queue length distribution. Both give results on mean queue sizes in
steady state and other interesting relationships but don’t say much about
large deviations of the queues.

The state of the system is denoted by $(x,y,s)$ where $(x,y)$ is the joint
queue length of queues 1 and 2 and $s\in\\{1,2\\}$ is the queue being served.
When $(x,y)=(0,0)$, then $s=1$. Note that $(x,0,2)$ for $x\geq 0$ and
$(0,y,1)$ for $y\geq 1$ are not in the state space. Let $S$ denote the state
space, and $Q$ the generator of, this Markov process $M$. Under our
assumptions, the Markov process is irreducible. If the Markov process is
positive recurrent, let $\pi$ denote the stationary distribution. We may be
interested in $\pi(x,y,1)$ or $\pi(x,y,2)$ where $x+y=\ell$ is a large integer
and we are interested in the large deviation path of excursions from the
origin to points $(x,y,1)$ or $(x,y,2)$ such that $x+y=\ell$. We shall see
that depending on the parameters there are two distinct ways of temporarily
overloading the queues. One way is for the server to have an extraordinarily
long busy period. During this busy period the server can’t keep up with the
arrivals to the queue it is serving so both queues get large together. This is
the explosion or ray case. For other parameters the most likely path is a
spiral where the server alternates between emptying the two queues but in a
losing battle. Each time the server returns to a queue it is longer than
before! Such spirals have been observed to cause instability of multiclass
reentrant networks even when the load on each server is less than one (see [7]
and for an review see [8]. The situations are of course different. Our queues
are stable but it is striking that the large deviations can occur because of
the same spiral behaviour.

Large deviations of processes with boundaries have been studied extensively;
see [38] and [14]. Large deviation results for polling models where the server
has Markovian routing between queues are given in [9] and [10]. The local rate
function is derived and a large deviation principle is established. The
technique can be used to estimate the (rough) stationary probability decay
rate. Large deviation results are also given in [16] for polling systems where
the server is routed between queues according to a Bernoulli service schedule.
This paper establishes a rate function and derives upper and lower bounds on
the probability that the queue length of each queue exceeds a certain level
(i.e., the buffer overflow probability).

A complementary (but far less general) approach using harmonic functions was
developed in [30, 21, 20, 22]. This technique enables one to obtain exact
asymptotics of the stationary distribution of the queues. In particular if one
wishes calculate the steady state probability $\pi(F)$ for some rare event $F$
then one finds an $h$-transformation that converts $M$ into a twisted chain
$\mathcal{M}$ for which the rare event is no longer rare. Equivalently one
studies the (extreme) point on the Martin boundary of $M$ associated with the
harmonic function $h$ whose twist drifts toward $F$. Chang and Down [13] used
this approach to study polling models under limited service policies. Our
paper is complementary to theirs in that ours studies exhaustive service.

The paper by Ignatiouk-Robert [19] explores the Martin boundary of random
walks killed along a killing boundary. Her paper has a close connection to
large deviation theory and to our techniques. Extending Ignatiouk-Robert’s
paper, [37] studies singular random walks like ours but with absorption
outside a cone. Positive harmonic functions are exhibited using the
compensation approach [2, 3]. Their cone of harmonic functions is much more
complicated than our simple extension of the classical Ney and Spitzer results
[32]. These papers and ours point to a circle of ideas (Martin boundary -
large deviations - asymptotics of $\pi$) with more open questions than
answers.

One could quite rightly object that the service times of the cars released to
drive on the one available lane are in no way exponential. The polling model
studied is more appropriate for a server serving two queues of retail customer
or computer jobs. It is however the simplest model we know to illustrate the
different ways such systems overload so we will work it out in detail. A more
sensible model might be to take $\mu$ to be deterministic. One might regard
instead the state of the two queues $(x,y,1)$ or $(x,y,2)$ at service times.
In this case there would be a random number of arrivals to each queue per
service period with means $\lambda_{1}$ and $\lambda_{2}$ respectively. To be
even more realistic we include a switch over period when there are no
services. This corresponds to the delay in getting traffic flowing in the
reverse direction. Indeed in [26] switch over times are included and if one
assigns holding costs it is shown that the exhaustive service policy is
optimal for reducing long run discounted costs. We will briefly study a more
general model in Section 5. The method and the main features are the same;
i.e. either the queue being served runs away to a large value or the server
does succeed in successively emptying each queue only to find the other queue
has built up to a higher level than before.

###  1.1 State space & macro behavior:

Let sheet $s$ be all states where the server is at queue $s$. The projection
of the two sheets onto the plane gives the joint queue length. When the server
is at 2, the joint queue length is drifting southeasterly as can be seen from
the possible customer flows and rates in the right sheet of Fig. 1. When the
server is processing customers at 1, the queue length process is drifting
northwesterly as can be seen in the left sheet of Fig. 1.

The two sheets look like a coffee filter if the sides of the sheets’
corresponding axes are glued together. When folded flat, the two creases line
up along each axis, and the point of the filter is at the origin. The left
sheet in Fig. 1, which includes the $x$-axis, corresponds to the server at
queue 1; the right sheet in Fig. 1, which includes the $y$-axis but not the
origin, corresponds to the server at 2. Whenever the Markov process crosses
the crease going from one sheet to the other, the server moves to the other
queue. Crossing a crease is like going through a turnstile since the process
can only cross in one direction. Along the $x$-axis, the server can move from
queue 2 to queue 1. Along the $y$-axis, the server can move from queue 1 to
queue 2.

(a)$\circ$$\circ$$\circ$$\circ$$\circ$$\circ$$\circ$$\circ$$\circ$$\circ$(f)$\lambda_{1}$$\mu$$\lambda_{2}$(d)$\mu$$\lambda_{1}$$\lambda_{2}$(c)(e)$\lambda_{1}$$\mu$$\lambda_{2}$driftdrift(b)(g)$\lambda_{1}$$\lambda_{2}$$\mu$
Figure 1: Jump rates when queue $1$ is served are on the left sheet and on the
right sheet when queue $2$ is served. Open circles denote points not in the
state space

###  1.2 Stability of the tandem polling model

Each job brings an amount of work $1/\mu$. Since the system is non-idling, in
order that the load on the single server is less than its capacity we assume
that

$\displaystyle\lambda_{1}+\lambda_{2}$ $\displaystyle<$ $\displaystyle\mu,$
(1)

which is a necessary and sufficient conditions for stability and is equivalent
to having a unique stationary distribution $\pi$. In fact the total queue
length $Z$ is an $M|M|1$ queue with arrival rate
$\lambda=\lambda_{1}+\lambda_{2}$ and service rate $\mu$. This chain is stable
if $\rho<1$ and the steady state is $\pi(\ell)=(1-\rho)\rho^{\ell}$ for
$\ell=0,1,\ldots$ where $\rho=\lambda/\mu$. Clearly the total queue length is
a stable chain if and only if $M$ is stable. Moreover
$\pi(0,0,1)=\pi(0)=1-\rho$ by definition (there is no state $(0,0,2)$).

###  1.3 Uniformization

It is convenient to study the Markov chains whose uniformization is $Z$ or
$M$. Denote the associated transition kernel by $K$ in both cases. The
homogenization of the combined chain $Z$ has transition kernel $K$ on
$S=\\{0,1,2,\ldots\\}$ where $K(u,u+1)=\lambda$ and $K(u,u-1)=\mu$ for $u>0$
and $K(0,1)=\lambda$ and $K(0,0)=\mu$. $\pi(z)=(1-\rho)\rho^{z}$ is the
associated stationary probability. The homogenization of $M$ has transition
kernel $K$

${K}(u,v)=\begin{cases}\lambda_{1}&\text{ if $u=(x,y,s)$ and $v=(x+1,y,s)$
}\\\ \lambda_{2}&\text{ if $u=(x,y,s)$ and $v=(x,y+1,s)$ }\\\ \mu&\text{ if
$u=(x,y,1)$, $x>1$, $v=(x-1,y,1)$}\\\ \mu&\text{ if $u=(1,y,1)$,
$v=(0,y,2)$}\\\ \mu&\text{ if $u=(x,y,2)$, $y>1$, $v=(x,y-1,2)$}\\\ \mu&\text{
if $u=(x,1,2)$, $v=(x,0,1)$}\\\ \mu&\text{ if $u=(0,0,1)$ and $u=v$}\\\
0&\text{ otherwise.}\\\ \end{cases}$ (2)

for all pairs of states $(u,v)$.

###  1.4 Twisted $Z$

Extend $K$ to $\mathbb{Z}$ giving the free kernel $\overline{K}$:
$\overline{K}(u,u+1)=\lambda$ and $\overline{K}(u,u-1)=\mu$ for all $u$. Let
$G=\sum_{n=0}^{\infty}\overline{K}^{d}$ be the associated potential. Define
$\blacktriangle$ to be $\\{z:z\leq 0\\}$ in $\mathbb{Z}$ and
$\Delta=S\setminus\blacktriangle=\\{0\\}$. Let $\overline{K}_{\blacktriangle}$
be the taboo kernel $\overline{K}$ killed on $\blacktriangle$ and let
$G_{\blacktriangle}$ be the associated potential.

$h(u)=\rho^{-u}$ is harmonic for $\overline{K}$. The associated
$h$-transformed kernel is $\mathcal{K}(u,v)=\overline{K}(u,v)h(v)/h(u)$; i.e.
$\mathcal{K}(u,u+1)=\lambda$ and $\mathcal{K}(u,u-1)=\mu$ for all $u$. Let

$\mathcal{G}(u,v)=\sum_{n=0}^{\infty}\mathcal{K}^{n}(u,v)=G(u,v)\frac{h(v)}{h(u)}$

be the associated potential. Let $\mathcal{K}_{\blacktriangle}$ be the taboo
kernel $\mathcal{K}$ killed on $\blacktriangle$ and let
$\mathcal{G}_{\blacktriangle}$ be the associated taboo potential.

We now use the representation

$\displaystyle\pi(z)$ $\displaystyle=$
$\displaystyle\sum_{u\in\Delta}\pi(u)G_{\blacktriangle}(u;z))=\sum_{u\in\Delta}\frac{h(u)}{h(z)}\pi(u)\mathcal{G}_{\blacktriangle}(u;z))$
(3) $\displaystyle=$
$\displaystyle(1-\rho)\rho^{-z}\mathcal{G}_{\blacktriangle}(0;z)).$

This just means ${\cal G}_{\blacktriangle}(0;z)=1$. The probability
$\mathcal{Z}$, starting at $x>0$, escapes to infinity without returning to $0$
is $1-\rho^{x}$ so the probability of escaping from $0$ is
$\mu(1-\rho^{1})=\mu-\lambda$. Taking $z=\ell$ this means means the expected
number of visits to $\ell$ is $1/(\mu-\lambda)$ given the twisted chain does
escape from $0$.

###  1.5 Twisted $M$

For the uniformized free kernels $\overline{K}_{1}$ and $\overline{K}_{2}$
define the transforms
$\Phi_{s}(\alpha,\beta)=\sum_{x,y}\overline{K}_{s}((0,0),(x,y)\alpha^{x}\beta^{y}$
for $s=1,2$. Using convexity we see the two ”eggs”, $\Phi_{1}(\alpha,\beta)=1$
and $\Phi_{2}(\alpha,\beta)=1$, have two points of intersection; i.e. $(1,1)$
and $(\rho^{-1},\rho^{-1})$. Hence $h(x,y,s)=\rho^{-(x+y)}$ is harmonic for
$K$ away from $(0,0,1)$. We may therefore calculate the $h$-transform. The
transition kernel of the resulting twisted chain $\mathcal{M}$ is:

$\displaystyle\mathcal{K}(a,b)$
$\displaystyle=\begin{cases}\tilde{\lambda}_{1}=\frac{\lambda_{1}}{\lambda}\mu&\text{
if $a=(x,y,s)$ and $b=(x+1,y,s)$ }\\\
\tilde{\lambda}_{2}=\frac{\lambda_{2}}{\lambda}\mu&\text{ if $a=(x,y,s)$ and
$b=(x,y+1,s)$ }\\\ \tilde{\mu}=\lambda&\text{ if $a=(x,y,1)$, $x>1$,
$b=(x-1,y,1)$}\\\ \tilde{\mu}=\lambda&\text{ if $a=(1,y,1)$, $b=(0,y,2)$}\\\
\tilde{\mu}=\lambda&\text{ if $a=(x,y,2)$, $y>1$, $b=(x,y-1,2)$}\\\
\tilde{\mu}=\lambda&\text{ if $a=(x,1,2)$, $b=(x,0,1)$}\\\ \mu&\text{ if
$u=(0,0,1)$ and $u=v$}\\\ 0&\text{ otherwise.}\end{cases}$ (4)

Note that $\mathcal{K}$ is super-stochastic at $(0,0,1)$.

We note the above could be generalized. Suppose the service rate is different
for the two queues; i.e. $\mu_{1}$ on sheet 1 and $\mu_{2}$ on sheet $2$. The
points of intersection of the two ”eggs”:
$\lambda_{1}\alpha+\lambda_{2}\beta+\mu_{1}\alpha^{-1}=1$ and and
$\lambda_{1}\alpha+\lambda_{2}\beta+\mu_{2}\beta^{-1}=1$ gives a point
$(\gamma_{1},\gamma_{2})$ where

$\gamma_{2}=\frac{\mu_{2}}{\mu_{1}}\gamma_{1}\mbox{ and
}\gamma_{1}=\frac{1-\sqrt{1-4(\lambda_{1}\mu_{1}+\lambda_{2}\mu_{2})}}{\frac{2}{\mu_{1}}(\lambda_{1}\mu_{1}+\lambda_{2}\mu_{2})}.$

Hence the $h(x,y)=\gamma_{1}^{x}\gamma_{2}^{y}$ is harmonic on both sheets
away from $(0,0,1)$. We may use this harmonic function to obtain a transient
twisted chain whose path gives the large deviation path of the original chain
as above. Again the $h$-transformed chain can be a ray or a spiral. Then, by
the above arguments, the large deviation paths are rays as discussed in
Section 2 or spirals discussed in Section 4.

###  1.6 Path of the rare event of hitting a high level

We will now describe how $M$ hits the level $\ell$ at some point $(x,y,s)$;
i.e. when $x+y=\ell$. Let $F=\\{(x,y,s):x+y\geq\ell\\}$ and
$\alpha=\\{(0,0,1)\\}$. Let $\tau_{F}=\min\\{n\geq 0:M(n)\in F\\}$ and
$\tau_{\alpha}=\min\\{n\geq 1:M(n)=\alpha\\}$ Let
$h_{\alpha}(x,y,s)=P_{(x,y,s)}[\tau_{F}<\tau_{\alpha}]$ with
$h_{\alpha}(0,0,1)=0$ and $h_{\alpha}(p)=1$ if $p\in F$ where $p=(x,y,s)$.
$h_{\alpha}$ is harmonic except on $F$. Simple calculation shows
$(\rho^{-(x+y)}-1)/(\rho^{-\ell}-1)$ also satisfies the same conditions and
since two harmonic functions agreeing on their boundaries are equal we know
$h_{\alpha}(x,y,s)=(\rho^{-(x+y)}-1)/(\rho^{-\ell}-1)$.

As above define the twisted Markov chain $\mathcal{M}_{\alpha}$ with twisted
kernel

$\mathcal{K}_{\alpha}(p,q)=K(p,q)h_{\alpha}(q)/h_{\alpha}(p)$

for $p\notin\\{\alpha\\}\cup F$. Define

$\mathcal{K}_{\alpha}(\alpha,p)=K(\alpha,p)h_{\alpha}(p)/\sum_{q\neq(0,0,1)}K(\alpha,q)h_{\alpha}(q).$

Let $\mathcal{P}^{h_{\alpha}}$ denote the probability measure constructed from
$\mathcal{K}_{\alpha}$. Since $h_{\alpha}(\alpha)=0$ the twisted chain cannot
return to $\alpha$. If follows that $\mathcal{M}_{\alpha}$ hits $F$ before
$\alpha$ with probability one.

Pick a path $(a_{0},a_{1},\ldots a_{T-1},a_{T})$ starting at
$a_{0}=\alpha=(0,0,1)$ that enters $F$ for the first time at $a_{T}$ before
returning to $\alpha$. We see

$\displaystyle P_{\alpha}[M(n)=a_{n},0\leq n\leq T|\tau_{F}<\tau_{\alpha}]$
$\displaystyle=$ $\displaystyle P_{\alpha}[M(n)=a_{n},0\leq n\leq
T]/P_{\alpha}[\tau_{F}<\tau_{\alpha}]$ $\displaystyle=$
$\displaystyle\mathcal{P}^{h_{\alpha}}_{\alpha}[\mathcal{M}(n)=a_{n},0\leq
n\leq
T]h_{\alpha}^{-1}(a_{T})/\mathcal{E}_{\alpha}^{h_{\alpha}}[\chi\\{\tau_{F}<\tau_{\alpha}\\}h_{\alpha}^{-1}(M(\tau_{F}))]$
$\displaystyle=$
$\displaystyle\mathcal{P}^{h_{\alpha}}_{\alpha}[\mathcal{M}(n)=a_{n},0\leq
n\leq T]$ (6)

since $h_{\alpha}$ equals $1$ on $F$ and since $\mathcal{M}$ can’t hit
$\alpha$ but must hit $F$ under measure $\mathcal{P}^{h_{\alpha}}$.

In other words the probability of the path conditioned on the rare event of
leaving $\alpha$ and going directly to $F$ is the same as that of a path for
the $h_{\alpha}$-transformed chain. Moreover, suppose $H_{\ell}$ is a set of
large deviation paths that leave $\alpha$ that hit $F$ before returning to
$\alpha$ such that
$P_{\alpha}[H_{\ell}]/P_{\alpha}[\tau_{F}<\tau_{\alpha}]\sim 1$ as
$\ell\to\infty$. Typically $H_{\ell}$ is a tube of radius $\epsilon\ell$
around a fluid limit as in Theorem 6.15 in [38]. Then

$1\sim
P_{\alpha}[H_{\ell}|\tau_{F}<\tau_{\alpha}]=\mathcal{P}^{h_{\alpha}}_{\alpha}[H_{\ell}];$

i.e. the large deviation paths of $P_{\alpha}$ are almost surely the paths of
$h_{\alpha}$-transformed chain. We note in passing that $F$ could be any set
far from $\alpha$ and all the above calculations hold.

We can use $\mathcal{K}_{\alpha}$ to simulate large deviations to $F$ and in
particular estimate the hitting distribution on $F$. $h_{\alpha}$ does not
depend on the transition probabilities of kernel $K$ for transitions inside
$F$; i.e. we can change $K(f,\cdot)$ at any point $f\in F$ without changing
$h_{\alpha}$ or $G_{F}$. Consequently above shows that the large deviation
path from $\alpha$ to $F$ does not depend on $K(f,\cdot)$ at any point $f\in
F$.

Note that $h_{\alpha}(x,y,s)\approx h(x,y,s)=\rho^{\ell-(x+y)}$. In other
words the exact rare event kernel $\mathcal{K}_{\alpha}$ is approximately the
same as the $h$-transformed kernel. In fact all the calculations above work
equally well with $\mathcal{K}(p,q)=K(p,q)h(q)/h(p)$ (even at $p=\alpha$.

$\displaystyle P_{\alpha}[M(n)=a_{n},1\leq n\leq\ell|\tau_{F}<\tau_{\alpha}]$
$\displaystyle=$ $\displaystyle P_{\alpha}[M(n)=a_{n},1\leq
n\leq\ell]/P_{\alpha}[\tau_{F}<\tau_{\alpha}]$ $\displaystyle=$
$\displaystyle\mathcal{P}^{h}_{\alpha}[\mathcal{M}(n)=a_{n},1\leq
n\leq\ell]h^{-1}(a_{\ell})/\mathcal{E}^{h}[\chi\\{\tau_{F}<\tau_{\alpha}\\}h^{-1}(M(\tau_{F}))]$
$\displaystyle=$
$\displaystyle\mathcal{P}^{h}_{\alpha}[\mathcal{M}(n)=a_{n},1\leq
n\leq\ell]/\mathcal{P}_{\alpha}^{h}[\tau_{F}<\tau_{\alpha}]$ $\displaystyle=$
$\displaystyle\mathcal{P}^{h}_{\alpha}[\mathcal{M}(n)=a_{n},1\leq
n\leq\ell|\tau_{F}<\tau_{\alpha}].$ (8)

For simulations of trajectories of the measure $\mathcal{P}^{h}_{\alpha}$ this
just means we reject trajectories which return to $0$ before hitting $F$ and
these are just a fixed proportion since trajectories under
$\mathcal{P}^{h}_{\alpha}$ drift toward $F$.

The drift of the twisted chain on sheet 1 is
$m^{1}:=(\tilde{\lambda}_{1}-\tilde{\mu},\tilde{\lambda}_{2})$ and the drift
of the twisted chain on sheet 2 is
$m^{2}:=(\tilde{\lambda}_{1},\tilde{\lambda}_{2}-\tilde{\mu},)$. There are two
cases: rays or spirals. There is a ray on sheet 1 if
$\tilde{\lambda}_{1}-\tilde{\mu}>0$. There is a ray on sheet 2 if
$\tilde{\lambda}_{2}-\tilde{\mu}>0$. If both sheets are rays we call it the
ray-ray case. On a sheet with a ray the rare event occurs when the queue just
explodes due to fast arrivals and slow service. In the spiral case
$\tilde{\lambda}_{1}-\tilde{\mu}<0$ and $\tilde{\lambda}_{2}-\tilde{\mu}<0$
and in this case we show that the server alternates between emptying the two
queues but in a losing battle. We explore the two cases in following sections.

The twisted chain provide a means of estimating $\pi$. Let
$G_{\blacktriangle}((0,0,1);(x,y,s)$ denote the mean number of hits at
$(x,y,s)$ where $x+y=\ell$ before returning to $\blacktriangle=\\{(0,0,1)\\}$.
We can use the representation

$\displaystyle\pi(x,y,1)$ $\displaystyle=$
$\displaystyle\pi(0,0,1)G_{\blacktriangle}((0,0,1);(x,y,s))$ (9)
$\displaystyle=$ $\displaystyle\pi(0,0,1){\cal
G}_{\blacktriangle}((0,0,1);(x,y,s))\frac{h(0,0)}{h(x,y)}$ $\displaystyle=$
$\displaystyle(1-\rho)\rho^{\ell}{\cal G}_{\blacktriangle}((0,0,1);(x,y,s)).$

Note that $\sum_{s\in\\{1,2\\}}\sum_{x+y=\ell}{\cal
G}_{\blacktriangle}((0,0,1);(x,y,s))=1$ as above.

The above representation (9) shows we can obtain the distribution of $\pi$ on
$\\{(x,y,s)\\}$ by simulating ${\cal G}_{\blacktriangle}((0,0,1);(x,y,1))$.
However, for the polling model, this representation is not practical for
giving the asymptotics of $\pi$ analytically because it involves paths
crossing from one sheet to the other where the transition kernel changes
discontinuously. This also constitutes a complication for the large deviation
approach. In the next subsection we show how to avoid this complication by
restricting the representation to one sheet.

We summarize our definitions and assumptions:

The transition kernel $K$ given in (2) has
$\lambda_{1}>0,\quad\lambda_{2}>0,\quad\lambda\coloneqq\lambda_{1}+\lambda_{2}<\mu,$
and w.l.o.g. that $\lambda+\mu=1.$ (10) Under these conditions, $K$ is
irreducible over the state space $S$ and has a stationary distribution denoted
by $\pi$. (10)

The ray condition on sheet 1; i.e. $\tilde{\lambda}_{1}>\tilde{\mu}$ or
$\rho^{-1}\lambda_{1}>\lambda$. (R1)

The ray condition on sheet 2; i.e. $\tilde{\lambda}_{2}>\tilde{\mu}$ or
$\rho^{-1}\lambda_{2}>\lambda$. (R2)

##  2 The ray case

In this section we assume there is a ray on sheet 1; i.e.
$\tilde{\lambda}_{1}-\tilde{\mu}>0$. We wish to give the asymptotics of
$\pi(x,y,1)$ where $x+y=\ell$ as $\ell\to\infty$. There is a problem with
periodicity since our chain has period $2$. Since $\pi$ is the invariant
probability of $K$ and of $(K+I)/2$ we could replace $K$ by $(K+I)/2$ in this
section. Instead we will just ignore periodicity for now and fix things up in
Theorems 1 and 2.

To evaluate $\pi(x,y,1)$ we will extend the transition kernel $K$ to the free
kernel $\overline{K}$ in the interior of sheet 1 to the whole plane
$\mathbb{Z}^{2}$. This is in fact a random walk increments $J$ where

$\displaystyle\overline{K}((0,0);(0,1))$ $\displaystyle=$ $\displaystyle
P[J=(0,1)]=\lambda_{2},\overline{K}((0,0);(1,0))=P[J=(1,0)]=\lambda_{1}$ and
$\displaystyle\overline{K}((0,0);(-1,0))=P[J=(-1,0)]=\mu.$

We can drop the notation indicating sheet $1$ for the free process; i.e.
$(x,y)$ replaces $(x,y,1)$.

We will apply the results in Ney and Spitzer [32]. For $a,b\in\mathbb{Z}^{2}$
let $\overline{G}(a,b)=\sum_{n=0}^{\infty}\overline{K}^{n}(a,b)$ be the
potential associated with a random walk on $\mathbb{Z}^{d}$ with kernel
$\overline{K}$ and let

$\phi(u)=E[\exp(u\cdot J)]=\sum_{v}e^{v\cdot u}\overline{K}(0,v)$

be the associated transform. Define $D^{\phi}=\\{u|\phi(u)\leq 1\\}$ which is
a convex set with surface $\partial D^{\phi}=\\{u|\phi(u)=1\\}$.

We summarize our assumptions:

each point in $\partial D^{\phi}$ has a neighbourhood in which $\phi$ is
finite. ((1.4) in [32]:) $m=\sum_{v}v\overline{K}(0,v)\neq 0$. ((1.3) in
[32]:) $\\{v:\overline{K}(0,v)>0)\\}$ does not lie in a subspace of
$\mathbb{Z}^{d}$. (Nonsingular:)

All these assumptions clearly hold in our nearest neighbour example. Let
$|\cdot|$ be the $\ell^{1}$ norm; i.e. $|(x,y)|=|x|+|y|$ and let $||\cdot||$
be the $\ell^{2}$ norm.

By [11] and [25], $h(z)=\exp(z\cdot u)$ is an extremal harmonic function in
the Martin boundary for the Martin kernel $k(a;b)=G(a;b)/G(0;b)$ where
$a,b,0\in\mathbb{Z}^{d}$. We introduce the transition kernel
$\overline{K}^{u}(a,b)=\overline{K}(a,b)e^{u\cdot(b-a)}$ where $\phi(u)=1$ and
the associated random walk with increments $J^{u}$. The mean vector of
$\overline{K}^{u}$ is

$m^{u}=\sum_{v\in\mathbb{Z}^{d}}v\overline{K}^{u}(0,v)=\nabla\phi(u).$

Let $d^{u}=m^{u}/|m^{u}|$. Denote the potential $\overline{G}^{u}(a,b)$. Note
$\overline{G}^{u}(a,b)=\overline{G}(a,b)\exp(u\cdot(b-a))$. If we pick
$\overline{u}=(\ln(\rho^{-1}),\ln(\rho^{-1}))^{\prime}$ then
$\overline{u}\in\partial D^{\phi}$ and
$\overline{K}^{\overline{u}}=\overline{\mathcal{K}}$ and
$\overline{G}^{\overline{u}}=\overline{\mathcal{G}}$ where
$\overline{\mathcal{K}}$ is the free twisted kernel obtained by
$h$-transformation using the harmonic function $h(x,y)=\rho^{-(x+y)}$ and
$\overline{\mathcal{G}}$ is the associated potential.

Theorem 1.2 and its Corollary 1.3 in [32] shows the Martin compactification is
equivalent to the the compactification $\overline{\mathbb{Z}}^{d}$ of
$\mathbb{Z}^{d}$ with respect to the metric
$\rho(a,b)=|\frac{a}{1+|a|}-\frac{b}{1+|b|}|$. Corollary 1.3 shows any
sequence $b_{n}$ such that $b_{n}/||b_{n}||\to d^{u}/||d^{u}||$; i.e.
converging to $p$ in the $\rho$-compactification also converges to a boundary
point (we also call $p$) in the Martin boundary; i.e.
$k(a;b_{n})\to\exp(a\cdot u)$. Thus Corollary 1.3 in [32] gives an equivalence
between the topology of the geometric boundary and the topology of the Martin
boundary.

Theorems 1.2 and 2.2 in Ney and Spitzer [32] require (1.1), (1.2), (1.3) and
(1.4) given there. (1.1) just requires that the kernel $\overline{K}$ be a
random walk kernel which is our situation. (1.3) and (1.4) are [2] and [1]
above. However (1.2) requires irreducibility; i.e. for all $x$,
$\overline{K}^{n}(0,x)>0$ for some $n$ and this not true in our example since
there are no southern jumps on sheet 1. Thus the Martin kernel
$\overline{G}(a,b)/\overline{G}(0,b)$ is not defined for $b$ pointed in a
southern direction. This is not a worry since we are interested only in
directions inside the cone $\mathcal{C}$ generated by the support of
$\overline{K}(0,\cdot)$; i.e. the cone generated
$\\{v:\overline{K}(0,v)>0\\}$. In the appendix we prove that we can choose $u$
where $\phi(u)=1$ such that the mean direction $d^{u}$ lies anywhere in the
interior of $\mathcal{C}$. The appendix also shows how to point $d^{u}$ along
the boundary of $\mathcal{C}$.

The asymptotics of ${\cal G}(a;z)$ are given by Theorem 2.2 in [32]. Following
[32] define the quadratic form

$Q^{u}[\theta]=(\theta\cdot
Q^{u}\theta)=\sum_{v\in\mathbb{Z}^{d}}|(v-m^{u})\cdot\theta|^{2}\overline{K}^{u}(0,v)$

which is the variance of $J^{u}\cdot\theta$ so $Q^{u}$ is the covariance
matrix of $J^{u}$. These quadratic forms are positive definite since if
$Q^{u}(\theta)=0$ for some $\theta\neq 0$ then $(v-m^{u})\cdot\theta=0$ on the
support of $\overline{K}^{u}(0,\cdot)$; i.e. on $v$ such that
$\overline{K}(0,v)>0$. This means $(v-m^{u})\cdot\theta$ is a constant for $v$
such that $\overline{K}(0,v)>0$; i.e. $\\{v-m:\overline{K}(0,v)>0)\\}$ lies in
a subspace of $\mathbb{Z}^{d}$ which violates our Assumption [3]. Hence
$Q^{u}[\theta]>0$ for all $\theta$; i.e. $Q^{u}$ is positive definite. The
inverse of $Q^{u}$ is denoted by $\Sigma^{u}$ and the corresponding
determinants are denoted by $|Q^{u}|$ and $|\Sigma^{u}|=|Q^{u}|^{-1}$.

The proof of Corollary 1.3 in [32] without assuming (1.2) follows the proof
given on page 121 just after the statement of Theorem 2.2 in [32]. Using the
notation in [32] the key point is that

$\lim_{n\to\infty}\frac{G(x,x_{n})}{G(0,x_{n})}=\lim_{n\to\infty}\frac{G^{u_{n}}(x,<t_{n}\mu^{u_{n}}>)}{G^{u_{n}}(0,<t_{n}\mu^{u_{n}}>)}e^{u_{n}\cdot
x}.$

Using the uniformity in $u$ in Theorem 2.2 in [32] the fraction on the right
hand side of the above expression tends to $1$ so $G(x,x_{n})/G(0,x_{n})\to
e^{u\cdot x}$ giving Corollary 1.3 in [32]. The proof of Theorem 2.2 requires
Lemmas 2.4 through 2.11. These lemmas require (1.2) but only to show $Q^{u}$
is positive definite but this follows from our Condition [3] so (1.2) is not
needed (see the comment at the top of page 127 in [32]). We conclude, under
the Conditions [1], [2] and [3], that Theorems 1.2 and 2.2 in [32] both hold
provided only that Theorem 2.2 be modified to a homeomorphism between
$\partial D^{\phi}$ and $\overline{\mathbb{Z}}^{d}\cap\mathcal{C}$.

We also define $\blacktriangle$ to be the complement of $\\{(x,y,1):x\geq
1,y\geq 1\\}$ in $\mathbb{Z}^{2}$. This defines
$\Delta=S\cap\blacktriangle=\\{(x,0,1):x\geq 0\\}$; i.e. the boundary points
of $S$ in the plane. Let $\mathcal{K}_{\blacktriangle}$ be the taboo kernel
$\mathcal{K}$ killed on $\blacktriangle$ and let
$\mathcal{G}_{\blacktriangle}$ be the associated potential. These kernels are
identical to the corresponding free kernels killed on $\blacktriangle$ and we
denote the free kernels as $\overline{\mathcal{K}}_{\blacktriangle}$,
$\overline{\mathcal{K}}$ and $\overline{\mathcal{K}}_{\blacktriangle}$. We
recall the representation (9)

$\displaystyle\pi(x,y,1)$ $\displaystyle=$ $\displaystyle
h(x,y)^{-1}\sum_{(z_{1},z_{2},1)\in\Delta}h(z_{1},z_{2})\pi(z_{1},z_{2},1){\cal
G}_{\blacktriangle}((z_{1},z_{2});(x,y))$ (11) $\displaystyle=$
$\displaystyle\rho^{\ell}\sum_{z}\rho^{-z}\pi(z,0,1)\overline{{\cal
G}}_{\blacktriangle}((z,0);(x,y))\mbox{ where }x+y=\ell.$

We can now give the asymptotics of (11). First define

$\displaystyle\Pi^{\overline{{\cal K}}}_{\blacktriangle}(a,b)$
$\displaystyle=$
$\displaystyle\mathcal{P}_{a}[\overline{\mathcal{J}}(\tau_{\blacktriangle})=b,\tau_{\blacktriangle}<\infty]\mbox{
for }a\in S,b\in\blacktriangle.$

where $\overline{\mathcal{J}}$ is the random walk with kernel
$\overline{\mathcal{K}}$. Note that $\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(a,\cdot)$ has support on the $x$ and $y$ axes. For
$a\in\Delta$ and $z\in S\setminus\blacktriangle$, $\overline{{\cal G}}(a;z)$
can be decomposed as the expected number of visits to $z$ before hitting
$\blacktriangle$; i.e. $\overline{{\cal G}}_{\blacktriangle}(a,z)$ and the
expected number of visits to $z$ by trajectories hitting $z$ after hitting
blacktriangle $\blacktriangle$; i.e.
$\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(a,w))\overline{{\cal G}}(w;z)$. Therefore

$\displaystyle\overline{{\cal G}}_{\blacktriangle}(a,z)$ $\displaystyle=$
$\displaystyle\overline{{\cal
G}}(a;z)-\sum_{w\in\blacktriangle}\Pi^{{\overline{\cal
K}}}_{\blacktriangle}(a,w))\overline{{\cal G}}(w;z)$ (12)

for $a=(x,0)$ and $z\in\mathbb{Z}^{2}\setminus\blacktriangle$.

Let $d^{u}(\ell)=(x,y)=<\ell\cdot d^{u}>$ where $<\cdot>$ denotes the nearest
lattice point in $\mathbb{Z}^{2}$ on the line $x+y=\ell$. Then $d^{u}(\ell)$
converges to a boundary point $p$ in the $\rho$-compactification
$\overline{\mathbb{Z}}^{d}$ associated with the direction $d^{u}$. Corollary
1.3 in [32] establishes that $d^{u}$ converges to a point in the Martin
boundary; i.e. $k(a;d^{u}(\ell))\to\exp(a\cdot u)$. Hence, for any $(x,y)$,

$\frac{\overline{{\cal G}}((x,y);d^{\overline{u}}(\ell))}{\overline{{\cal
G}}((0,0);d^{\overline{u}}(\ell))}=\frac{\overline{G}^{\overline{u}}((x,y);d^{\overline{u}}(\ell))}{\overline{G}^{\overline{u}}((0,0);d^{\overline{u}}(\ell))}\to
1$

as $\ell\to\infty$. Note that the above result shows

$\frac{\overline{{\cal
G}}((0,0);d^{\overline{u}}(\ell)-(x,y))}{\overline{G}^{\overline{u}}((0,0);d^{\overline{u}}(\ell))}\to
1;$

i.e. the exact rounding off by $<>$ doesn’t change the result.

Consequently, from representation (11)

$\displaystyle\pi(d^{\overline{u}}(\ell))=\rho^{\ell}\sum_{z\in\Delta}h(z)\pi(z){\cal
G}_{\blacktriangle}(z;d^{\overline{u}}(\ell))$ $\displaystyle=$
$\displaystyle\rho^{\ell}\sum_{z\in\Delta}h(z)\pi(z)(\overline{{\cal
G}}(z;w)-\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(z,w)\overline{{\cal G}}(w;z))$ $\displaystyle=$
$\displaystyle\rho^{\ell}\overline{{\cal G}}((0,0);d^{\overline{u}}(\ell))$
$\displaystyle\cdot\left(\sum_{z\in\Delta}h(z)\pi(z)\frac{\overline{{\cal
G}}(z;d^{\overline{u}}(\ell))}{\overline{{\cal
G}}((0,0);d^{\overline{u}}(\ell)}-\sum_{z\in\Delta}h(z)\pi(z)\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(z;w)\frac{\overline{{\cal
G}}(w;d^{\overline{u}}(\ell))}{\overline{{\cal
G}}((0,0);d^{\overline{u}}(\ell))}\right).$

To go further we need $\sum_{z\in\Delta}h(z)\pi(z)<\infty$ but this is shown
in Appendix A.1 when there is a ray on sheet 1. Then using Proposition 1 below
we can apply dominated convergence to get

$\displaystyle\pi(d^{\overline{u}}(\ell))$ $\displaystyle\sim$
$\displaystyle\rho^{\ell}\overline{{\cal
G}}((0,0);d^{\overline{u}}(\ell))\left(\sum_{z\in\Delta}h(z)\pi(z)-\sum_{z\in\Delta}h(z)\pi(z)\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(z,;w))\right)$ $\displaystyle=$
$\displaystyle\rho^{\ell}\overline{{\cal
G}}((0,0);d^{\overline{u}}(\ell))\sum_{z\in\Delta}h(z)\pi(z)\mathcal{P}^{h}_{z}[\mathcal{M}\mbox{
never hits }\blacktriangle]$

We remark that is tempting to consider the Martin kernel

$k_{\gamma}(a;d^{\overline{u}}(\ell))=\frac{\overline{{\cal
G}}(a;d^{\overline{u}}(\ell)}{\sum_{z\in\Delta}h(z)\pi(z)\overline{{\cal
G}}(z;d^{\overline{u}}(\ell))}.$

Then
$\liminf_{\ell\to\infty}k_{\gamma}(a;d^{\overline{u}}(\ell))\leq\frac{1}{\sum_{z\in\Delta}h(z)\pi(z)}$.
Hence any subsequential limit is bounded and since $1$ is extremal for ${\cal
K}$ we conclude these harmonic limits are constant functions. We could
therefore avoid Proposition 1. The problem is the limit might be zero even if
$\sum_{z\in\Delta}h(z)\pi(z)<\infty$ so a result like Proposition 1 seems to
be necessary.

Let $b^{u}(\ell)=<\ell\cdot m^{u}>$ where $<>$ means the nearest lattice
point. Note that

$d^{u}(\ell)=<\ell\cdot\frac{m^{u}}{|m^{u}|}>=<\frac{\ell}{|m^{u}|}\cdot
m^{u}>=b^{u}(\frac{\ell}{|m^{u}|}).$

Theorem 2.2 in [32] gives

$\overline{{\cal
G}}((0,0,1);b^{\overline{u}}(\ell))\sim(2\pi\ell)^{-(d-1)/2}[|Q^{\overline{u}}|(m^{\overline{u}}\cdot\Sigma^{\overline{u}}m^{\overline{u}})]^{-1/2}$

where the dimension $d$ is $2$ and where $\Sigma^{\overline{u}}$ is the
inverse of $Q^{\overline{u}}$, the covariance matrix of the twisted random
walk increments; i.e.
$Q^{\overline{u}}=E[(\mathcal{J}-m^{\overline{u}})\cdot(\mathcal{J}-m^{\overline{u}})^{\prime})]$
and $|Q^{\overline{u}}|$ is the determinant of $Q^{\overline{u}}$.
Consequently,

$\overline{{\cal
G}}((0,0,1);d^{\overline{u}}(\ell))\sim\frac{1}{\sqrt{2\pi\ell/|m^{\overline{u}}|}}[|Q^{\overline{u}}|(m^{\overline{u}}\cdot\Sigma^{\overline{u}}m^{\overline{u}})]^{-1/2}$

We conclude

######  Theorem 1.

If there is a ray on sheet 1; i.e. $\tilde{\lambda}_{1}>\tilde{\mu}$ then

$\displaystyle\pi(d^{\overline{u}}(\ell))$ $\displaystyle\sim$ $\displaystyle
B^{\overline{u}}\rho^{\ell}\frac{1}{\sqrt{2\pi\ell/|m^{\overline{u}}|}}$

where

$B^{\overline{u}}=([|Q^{\overline{u}}|(m^{\overline{u}}\cdot\Sigma^{\overline{u}}m^{\overline{u}})]^{-1/2})(\sum_{z\in\Delta}h(z)\pi(z)P_{z}[\mathcal{M}\mbox{
never hits }\blacktriangle]).$

###### Proof.

The only issue is periodicity. If we had replaced $K$ by $(K+I)/2$ then that
issue disappears so the above theorem holds but $Q^{\overline{u}}$,
$\Sigma^{\overline{u}}$ and $m^{\overline{u}}$ above are the covariance, the
inverse covariance and the mean of $(\overline{K}^{u}+I)/2$ respectively. Let
$Q_{K}^{\overline{u}}$, $\Sigma_{K}^{\overline{u}}$ and $m_{K}^{\overline{u}}$
above are the covariance, the inverse covariance and the mean of
$\overline{K}^{u}$. The value of $\pi(d^{\overline{u}}(\ell))$ is the same for
both kernels. The value $(\sum_{z\in\Delta}h(z)\pi(z)P_{z}[\mathcal{M}\mbox{
never hits }\blacktriangle])$ for the kernel $(\overline{K}^{u}+I)/2$ is half
that for the kernel $\overline{K}^{u}$ because staying at $z$ means hitting
$\blacktriangle$.

Let $L$ be an independent random variable such that $P(L=1)=1/2$. Then the
increment of the random walk with kernel $(\overline{K}^{u}+I)/2$ can be
written $L\cdot J$ where as above $J$ is the increment of the walk with kernel
$\overline{K}^{u}$. Consequently $m^{\overline{u}}=E[L\cdot J]=E[J]/2$. Next,

$\displaystyle Q^{\overline{u}}(\theta)$ $\displaystyle=$ $\displaystyle
E[(LJ-E[LJ])\cdot\theta]^{2}$ $\displaystyle=$ $\displaystyle
E[(LJ\cdot\theta)^{2}]-\frac{(E[J]\cdot\theta)^{2}}{4}=\frac{E[(J\cdot\theta)^{2}]}{4}-\frac{(E[J]\cdot\theta)^{2}}{4}$
$\displaystyle=$
$\displaystyle\frac{1}{4}E[(J-E[J])\cdot\theta]^{2}=\frac{1}{4}Q_{K}^{\overline{u}}(\theta);$

i.e. $Q^{\overline{u}}=Q_{K}^{\overline{u}}/2$ and
$\Sigma^{\overline{u}}=2\Sigma_{K}^{\overline{u}}$. Hence
$(m^{\overline{u}}\cdot\Sigma^{\overline{u}}m^{\overline{u}})=(m_{K}^{\overline{u}}\cdot\Sigma_{K}^{\overline{u}}m_{K}^{\overline{u}})/2$.

The value of the determinant
$|Q^{\overline{u}}|=(\frac{1}{2})^{d}|Q_{K}^{\overline{u}}|/4$ so the value of
$B^{\overline{u}}=((\frac{1}{2})^{d}\cdot\frac{1}{2})^{-1/2}\cdot\frac{1}{2})B_{K}^{\overline{u}}$
where $B_{K}^{\overline{u}}$ is the corresponding value for the kernel $K$.
Finally the value of

$(2\pi\frac{\ell}{|m^{\overline{u}}|})^{-(d-1)/2}=(\frac{1}{2})^{-(d-1)/2}(2\pi\frac{\ell}{|m_{K}^{\overline{u}}|})^{-(d-1)/2}.$

The product of all these extra factors is
$((\frac{1}{2})^{d}\cdot\frac{1}{2})^{-1/2}\cdot(\frac{1}{2})^{-(d-1)/2}=1$ so
we see we were justified in ignoring periodicity (even in dimension $d$). ∎

If we consider another direction $d^{u}$ then again

$\overline{G}^{u}((0,0);b^{u}(\ell))\sim\frac{1}{\sqrt{2\pi\ell}}[|Q^{u}|(m^{u}\cdot\Sigma^{u}m^{u})]^{-1/2}$

where $\Sigma^{u}$ is the inverse of $Q^{u}$, the covariance matrix of the
random walk with kernel $\overline{K}^{u}$; i.e.
$Q^{u}=E[(J^{u}-m^{u})\cdot(J^{u}-m^{u})^{\prime})]$ and $|Q^{u}|$ is the
determinant of $Q^{u}$. However

$\displaystyle\overline{{\cal G}}((0,0);b^{u}(\ell))$ $\displaystyle=$
$\displaystyle\overline{G}((0,0);b^{u}(\ell))\exp(\overline{u}\cdot
b^{u}(\ell))$ $\displaystyle=$ $\displaystyle\exp((\overline{u}-u)\cdot
b^{u}(\ell))\overline{G}^{u}((0,0);d(\ell))$ $\displaystyle\sim$
$\displaystyle\exp(\ell(\overline{u}-u)\cdot
d^{u})\frac{1}{\sqrt{2\pi\ell}}[|Q^{u}|(m^{u}\cdot\Sigma^{u}m^{u})]^{-1/2}.$

However $d^{u}=\nabla[\phi(u)]/|\nabla[\phi(u)]|$ and $\nabla[\phi(u)]$ is
orthogonal to the supporting hyperplane (in fact a line) at the extremal point
$u$ of the convex set $\partial D^{\phi}$. Consequently for $\overline{u}$ or
any other point in $\partial D^{\phi}$,
$(\overline{u}-u)\cdot\nabla[\phi(u)]<0$. Consequently

######  Theorem 2.

Along any northern direction $d^{u}$

$\displaystyle\pi(d^{u}(\ell))$ $\displaystyle=$ $\displaystyle
O(\frac{\rho^{\ell}}{\sqrt{\ell}})\exp(-\alpha_{d^{u}}\ell)$

where $\alpha_{d^{u}}=(\overline{u}-u)\cdot d^{u}>0$.

######  Proposition 1.

$\frac{\overline{{\cal G}}(z;b^{\overline{u}}(\ell))}{\overline{{\cal
G}}((0,0);b^{\overline{u}}(\ell))}$ is uniformly bounded in $\ell$ and $z$ on
the $x$ or $y$ axes of sheet 1.

###### Proof.

From Theorem 2.2 in [32],

$\overline{G}^{u}((0,0);b^{u}(\ell))\sim\frac{1}{\sqrt{2\pi\ell}}[|Q^{u}|(m^{u}\cdot\Sigma^{u}m^{u})]^{-1/2}$

uniformly in $u$; i.e. we can take $L$ sufficiently large so that

$(1-\epsilon)<\overline{{\cal
G}}((0,0);b^{u}(\ell))\frac{\sqrt{2\pi\ell}}{[|Q^{u}|(m^{u}\cdot\Sigma^{u}m^{u})]^{-1/2}}<(1+\epsilon)$

for $\ell>L$ uniformly in $u$. Now consider $z\in\blacktriangle$ of the form
$z=<a\ell>$ where $a=(a_{1},a_{2})$. Since $\overline{K}$ and
$\overline{\mathcal{K}}$ have no southern jumps, $\overline{{\cal
G}}(z;b^{\overline{u}}(\ell))=0$ if $a_{1}>1$. If $a_{1}\leq 1$ then
$p(\ell)=b^{\overline{u}}(\ell)-<a\ell>=<c\ell>$ is in the cone formed from
the support of $\overline{K}$ or $\mathcal{K}$.

Pick $u^{*}$ such that $\phi(u^{*})=1$ and
$d^{u^{*}}=\nabla\phi(u^{*})/\nabla\phi(u^{*})|$ is in direction $p(\ell)$ so
$p(\ell)=<\ell|c|d^{u^{*}}>$. Moreover

$\overline{\mathcal{G}}^{u^{*}}((0,0);p(\ell))\sim\frac{1}{\sqrt{2\pi|c|\ell}}[|\mathcal{C}^{u^{*}}|(m^{u^{*}}\cdot\Sigma^{u^{*}}m^{u^{*}})]^{-1/2}$

where $\Sigma^{u^{*}}$ is the inverse of $\mathcal{C}^{u^{*}}$, the covariance
matrix of the random walk with kernel $\mathcal{K}^{u^{*}}$ and
$|\mathcal{C}^{u^{*}}|$ is the determinant of $\mathcal{C}^{u^{*}}$.

Hence,

$\displaystyle\overline{\mathcal{G}}((0,0);p(\ell))$ $\displaystyle=$
$\displaystyle\overline{G}^{\overline{u}}((0,0);p(\ell))=\overline{G}((0,0);p(\ell))e^{\overline{u}\cdot
p(\ell)}$ $\displaystyle=$ $\displaystyle e^{(\overline{u}-u^{*})\cdot
p(\ell)}\overline{G}^{u^{*}}((0,0);p(\ell))$ $\displaystyle\leq$
$\displaystyle e^{(\overline{u}-u^{*})\cdot
p(\ell)}(1+\epsilon)\frac{1}{\sqrt{2\pi|c|\ell}}[|Q^{u^{*}}|(m^{u^{*}}\cdot\Sigma^{u^{*}}m^{u^{*}})]^{-1/2}$

as long as $|c|\ell>L$. Again by the convexity of $D^{\phi}$,
$(\overline{u}-u^{*})\cdot p(\ell)\leq 0$. Moreover, since the support of
$\overline{K}$ is finite we use Theorem 10 to see probabilities
$\overline{K}(0,v)e^{u\cdot v}$ where $u\in\partial D^{\phi}$ form a compact
set. Hence $|Q^{u}|$ and $(m^{u}\cdot\Sigma^{u}m^{u})$ are bounded away from
zero and infinity (see Lemma 2.4 in [32]).

Hence, for $z=<a\ell>\in\blacktriangle$,

$\displaystyle\frac{\overline{{\cal
G}}(z;b^{\overline{u}}(\ell))}{\overline{{\cal
G}}((0,0);b^{\overline{u}}(\ell))}=\frac{\overline{\mathcal{G}}((0,0);p(\ell))}{\overline{{\cal
G}}((0,0);b^{\overline{u}}(\ell))}$ $\displaystyle\leq$
$\displaystyle(1+\epsilon)\frac{1}{\sqrt{2\pi|c|\ell}}[|Q^{u^{*}}|(m^{u^{*}}\cdot\Sigma^{u^{*}}m^{u^{*}})]^{-1/2}(\frac{1}{\sqrt{2\pi\ell}}[|Q^{\overline{u}}(m^{\overline{u}}\cdot\Sigma^{\overline{u}}m^{\overline{u}})]^{-1/2})^{-1}$
$\displaystyle\leq$ $\displaystyle(1+\epsilon)\frac{1}{\sqrt{|c|}}C$

where $C$ is a constant independent of $u^{*}$ or $\overline{u}$. Moreover,
for $z=<a\ell>\in\blacktriangle$ there is a minimum value of $|c|$ taken on
the $x$ or $y$ axes. Hence the above bound is uniform in
$z=<a\ell>\in\blacktriangle$. ∎

This gives a precise picture of a run-away queue on sheet $1$. The paths to
the boundary $x+y=\ell$ drift in direction $d^{\overline{u}}$. Moreover
$\pi(d^{\overline{u}}(\ell))$ is of order $\rho^{\ell}/\sqrt{\ell}$ while
points on the boundary a distance $\epsilon\ell$ from $b^{\ell}$ have
probability $\pi$ exponentially smaller in $\ell$. By symmetry there are
analogues to Theorems 1 and 2 on sheet 2. This partially explains the
histogram 2 of hits on level $\ell=1000$ of the ray-spiral case $\mu=.65$,
$\lambda_{1}=.3$ and $\lambda_{2}=.05$ based on simulating $10^{6}$ busy
periods of the twisted chain. There were no hits on sheet 2 at level $1000$.
The mode is $x=(691,309)$ while the theory predicts $(690.48,309.52)$. The
histogram is not normal because all the mass is within one standard deviation.
We have no theoretical prediction for the shape of the histogram.

Figure 2: Ray-Spiral case: $\lambda_{1}=0.3$, $\lambda_{2}=0.05$, $\mu=0.65$

##  3 The ray case: all directions

We note that the methodology used in the ray case above can be generalized to
any direction. To find $\pi(b^{u}(\ell))$ we must define $\blacktriangle$ to
cut out the boundary and then check that $\sum_{z\in\Delta}e^{u\cdot
z}\pi(z)<\infty$ where $\Delta=S\cap\blacktriangle$. Also take
$\alpha=\vec{0}=(0,0,\cdots,0)$ and note that the function
$h_{\alpha}(z)=(e^{u\cdot z}-1)/(e^{u\cdot b^{u}(\ell)}-1)$ is harmonic and
satisfies $h_{\alpha}(\vec{0})=0$ and $h_{\alpha}(b^{u}(\ell))=1$. Take
$F=\\{b^{u}(\ell)\\}$ and apply the reasoning in Subsection 1.6. We get that
for any path $(a_{0},a_{1},\ldots a_{T-1},a_{T})$ starting at
$a_{0}=\alpha=(0,0,1)$ and entering $F$ for the first time at $a_{T}$:

$\displaystyle P_{\alpha}[M(n)=a_{n},1\leq n\leq
T|\tau_{F}<\tau_{\alpha}]=\mathcal{P}^{h_{\alpha}}_{\alpha}[\mathcal{M}(n)=a_{n},1\leq
n\leq T];$

i.e. if the large deviation paths of the chain twisted by $h_{\alpha}$ lie in
some set $H_{\ell}$ then the same is true of the original chain conditioned
that a large deviation occurs.

Consider the free kernel of our polling model on sheet 1 $\overline{K}$ on
$\mathbb{Z}^{2}$. Since the support of $\overline{K}$ is
$S_{\rho}=\\{(1,0),(-1,0),(0,1)\\}$ it follows from Theorem 9 that for any
direction $\beta=(\beta_{1},\beta_{2})$ such that $\beta_{2}\geq 0$ there
exists a twist $u$ such that $\overline{K}^{u}$ has mean $\mu^{u}$ in
direction $\beta$. In this section we evaluate the decay of $\pi(b^{u}(\ell))$
in all north-easterly directions. We just assume there is a ray one sheet 1;
i.e. $\tilde{\lambda}_{1}-\tilde{\mu}>0$; i.e.
$\sqrt{\mu\lambda_{1}}>\lambda$. By twisting the free kernel $\overline{K}$
into the direction $\beta=(0,1)$ we will obtain what we call a bridge path.
Let $\exp(u_{1}x+u_{2}y)=\alpha_{T}^{x}\beta_{T}^{y}$. Find $\alpha_{T}$ and
$\beta_{T}$ such that

$\alpha_{T}\lambda_{1}+\beta_{T}\lambda_{2}+\alpha_{T}^{-1}\mu=1\mbox{ and
}\alpha_{T}^{-1}\mu=\lambda_{1}\alpha_{T}.$

Clearly $\alpha_{T}=\sqrt{\mu/\lambda_{1}}$ and
$\beta_{T}=(1-2\sqrt{\mu\lambda_{1}})/\lambda_{2}$. Note that $\beta_{T}$ is
positive since $\lambda\mu\leq 1/4$ so $\mu\lambda_{1}<1/4$ and so
$2\sqrt{\mu\lambda_{1}}<1$.

######  Proposition 2.

$\alpha_{T}<\rho^{-1}$ if and only if sheet 1 is a ray.

###### Proof.

$\alpha_{T}=\sqrt{\mu/\lambda_{1}}<\rho^{-1}$ if and only if
$\lambda<\sqrt{\mu\lambda_{1}}$; i.e. if and only there is a ray on sheet 1. ∎

Figure 3: Ray-Spiral case: $\lambda_{1}=6/20$, $\lambda_{2}=1/20$, $\mu=13/20$

$(\alpha_{E},\beta_{E})$$(\rho^{-1},\rho^{-1})$$(\alpha_{T},\beta_{T})$$(\gamma_{T},\beta_{T})$Curve
1Curve 2

Curve 1: $\lambda_{1}\alpha+\lambda_{2}\beta+\mu\alpha^{-1}=1$ is associated
with sheet 1 and Curve 2: $\lambda_{1}\alpha+\lambda_{2}\beta+\mu\beta^{-1}=1$
is associated with sheet 2. The points $(1,1)$ and $(\rho^{-1},\rho^{-1})$ are
the only intersection points on both curves. $(\alpha_{T},\beta_{T})$ is the
top of the curve associated with sheet 1 so $\beta_{T}>\rho^{-1}$. Moreover by
Proposition 2, $\alpha_{T}<\rho^{-1}$.

Denote the right most point on Curve 2 by $(\alpha_{E},\beta_{E})$ where

$\displaystyle\alpha_{E}=(1-2\sqrt{\mu\lambda_{2}})/(2\lambda_{1})\mbox{ and
}\beta_{E}=\sqrt{\mu/\lambda_{2}}$ (15)

by the above argument. Since $(\rho^{-1},\rho^{-1})$ lies on Curve 2 it
follows that $\alpha_{E}>\rho^{-1}>\alpha_{T}$. Since there are no other
intersection points it follows that there is a point $(\gamma_{T},\beta_{T})$
on Curve 2 where $\gamma_{T}>\rho^{-1}$. We use these points later.

###  3.1 Computing $\pi(1,y,1)$ and $\pi(0,y,2)$

In order to determine if a large deviation is a ray on the first sheet we need
precise estimates of $\pi(x,0,1)$. We proceed in a roundabout manner.

####  3.1.1 A bridge to $(1,y,1)$

We will now obtain the asymptotics of $\pi(1,y,1)$ as $y$ gets large.
Intuitively the large deviation path to the point $(1,y,1)$ is a bridge which
skims above the $y$-axis. We take $\Delta=\\{(x,0,1):x\geq 1\\}$ and
$\blacktriangle=\\{(x,y):x\geq 1,y\geq 1\\}^{c}$ inside $\mathbb{Z}^{2}$. We
consider the free kernel on sheet 1 $\overline{K}$ to have a killing
$K((1,y,1),(0,y,2)$ at points $(1,y)$ where the chain leaves sheet 1. To twist
the free kernel $\overline{K}$ to make a bridge path consider a rough
$h_{T}$-transform where $h_{T}(x,y)=\alpha_{T}^{x}\beta_{T}^{y}$.

Let $\mathcal{K}_{T}$ denote the $h_{T}$-transformed kernel. The Markovian
part (the $x$-component) of $\mathcal{K}_{T}$ is
$s=\hat{\mathcal{K}}_{T}(x,x)=\lambda_{2}\beta_{T}$ for $x\geq 1$ and

$p=\hat{\mathcal{K}}_{T}(x,x+1)=\hat{\mathcal{K}}_{T}(x,x-1)=\sqrt{\mu\lambda_{1}}\mbox{
for }x\geq 2.$

Hence $\hat{\mathcal{K}}_{T}(x,x-1)=p$ for $x\geq 2$. At $x=1$
$\hat{\mathcal{K}}_{T}(1,2)=\sqrt{\mu\lambda_{1}}$ but
$\hat{\mathcal{K}}_{T}(1,0)=0$ since this is a transition off sheet 1. Hence
$\hat{\mathcal{K}}_{T}$ has a killing $\kappa=\sqrt{\mu\lambda_{1}}$ at points
$(1,y)$. The mean drift in the $y$-direction at $(x,y)$ for $x\geq 2$ is
$d_{+}=\lambda_{2}\beta_{T}$.

Note that $\hat{h}_{0}(x)=x$ is harmonic for $\hat{\mathcal{K}}_{T}$ and the
associated $\hat{h}_{0}$-transform gives a Markovian kernel satisfying the
conditions of Theorem 1 in [29]. Consequently $\hat{h}_{0}$ is unique harmonic
function for $\hat{\mathcal{K}}_{T}$ and consequently
$h(x,y)=\hat{h}_{0}(x)h_{T}(x,y)=x\alpha_{T}^{x}\beta_{T}^{y}$ is harmonic for
$\overline{K}$ killed on the $y$-axis.

Again the $h$-transform of $\overline{K}$ is denoted by
$\overline{\mathcal{K}}$ which is associated with the twisted chain
$\mathcal{M}$ and the associated potential is $\overline{\mathcal{G}}$.
$\overline{\mathcal{K}}_{\blacktriangle}$ is the kernel killed on hitting
$\blacktriangle$. Also note that $\sum_{x}x\alpha_{T}^{x}\pi(x,0,1)<\infty$
since $\alpha_{T}<\rho^{-1}$ and $\pi(x,0,1)\leq(1-\rho)\rho^{x}$. Again
recall the representation (9),

$\displaystyle\pi(1,y,1)$ $\displaystyle=$ $\displaystyle
h(1,y)^{-1}\sum_{x\geq 0}h(x,0)\pi(x,0,1){\cal
G}_{\blacktriangle}((x,0);(1,y))$ (16) $\displaystyle=$
$\displaystyle\alpha_{T}\beta_{T}^{-y}\sum_{x}x\alpha_{T}^{x}\pi(x,0,1)\overline{{\cal
G}}_{\blacktriangle}((x,0);(1,y)).$

Let $\gamma(x,0)=h_{0}(x)\alpha_{T}^{x}\pi(x,0,1)\chi_{\Delta}((x,0))$ and
$\gamma_{\blacktriangle}(w)=\gamma\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(w)$ where $w\in\blacktriangle$ and $\Pi^{\overline{{\cal
K}}}_{\blacktriangle}((x,0);w))$ is the probability of hitting $w$ if the
twisted chain started at $(x,0)$ enters $\blacktriangle$. As in (2),

$\displaystyle\gamma\overline{{\cal G}}_{\blacktriangle}(1,y)$
$\displaystyle=$ $\displaystyle\sum_{x}\gamma(x,0)\overline{{\cal
G}}((x,0);(1,y))-\sum_{x}\gamma(x,0)\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}((x,0);(w,0)))\overline{{\cal G}}((w,0);(1,y))$
$\displaystyle=$ $\displaystyle\gamma\overline{{\cal
G}}(1,y)-\gamma_{\blacktriangle}\overline{{\cal G}}(1,y).$

We will check below that, $y\to\infty$, $\frac{\overline{{\cal
G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y))}$ is uniformly bounded
in $x$ and tends to $1$ as $y\to\infty$. If this is true then

$\frac{\gamma\overline{{\cal
G}}(1,y)}{\overline{\mathcal{G}}((1,0);(1,y)}=\sum_{x}x\alpha_{T}^{x}\pi(x,0,1)\frac{\overline{\mathcal{G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y))}\to\sum_{x}x\alpha_{T}^{x}\pi(x,0,1)$

and

$\displaystyle\frac{\gamma_{\blacktriangle}\overline{{\cal
G}}(1,y)}{\overline{\mathcal{G}}((1,0);(1,y))}=\sum_{x}x\alpha_{T}^{x}\pi(x,0,1)\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}((x,0);w))\frac{\overline{\mathcal{G}}(w;(1,y))}{\overline{\mathcal{G}}((1,0);(1,y))}$
$\displaystyle\to$
$\displaystyle\sum_{x}x\alpha_{T}^{x}\pi(x,0,1)\mathcal{P}_{(x,0)}[\mathcal{M}\mbox{
hits }\blacktriangle].$

In which case,

######  Proposition 3.

If there is a ray on sheet 1 then

$\pi(1,y,1)\sim\alpha_{T}^{-1}\beta_{T}^{-y}\overline{\mathcal{G}}((1,0);(1,y)\sum_{x\in\Delta}x\alpha_{T}^{x}\pi(x,0,1)\mathcal{P}_{(x,0)}[\mathcal{M}\mbox{
never hits }\blacktriangle].$

We have therefore stripped out the exponential decay $\beta_{T}^{-y}$ out of
$\pi(1,y,1)$ leaving the polynomial decay
$\overline{\mathcal{G}}((1,0);(1,y)$.

Next recall

$\overline{\mathcal{G}}((1,0);(1,y))=\mathcal{G}_{T}((1,0);(1,y)\frac{\hat{h}_{0}(1)}{\hat{h}_{0}(1)}=\mathcal{G}_{T}((1,0);(1,y).$

$\mathcal{G}_{T}((1,0);(1,y)$ was analyzed analytically in [22]. To see that
requires relabeling or shifting the first quadrant so $(1,0)\to(0,0)$ and
$((1,y)\to(0,y)$. Denote the relabelled or shifted kernel by $\mathcal{K}_{s}$
and the associated potential by $\mathcal{G}_{s}$. Hence
$\mathcal{K}_{s}((x,y);((u,v))=\mathcal{K}_{T}((x+1,y);((u+1,v))$ and
$\mathcal{G}_{T}((1,0);(1,y)=\mathcal{G}_{s}((0,0);(0,y)$. In these new
coordinates the probability of killing $\kappa$ at any point $(0,y)$ is
$\mathcal{K}_{T}((1,y);(0,y)=\mu\alpha_{T}^{-1}$ and
$p_{0}:=\mathcal{K}_{s}((0,y);(1,y))=p$. By Proposition 1 in [22], ${\cal
G}_{s}((0,0);(y,0))\sim C_{+}\,y^{-3/2}$ where
$C_{+}=\frac{p}{\kappa^{2}}\sqrt{\frac{d_{+}}{2\pi(1-s)}}$

######  Theorem 3.

If $\mu\cdot(\lambda_{1}/\lambda)-\lambda>0$ then

$\pi(1,y,1)\sim\alpha_{T}\beta_{T}^{-y}C_{+}y^{-3/2}\sum_{x\in\Delta}x\alpha_{T}^{x}\pi(x,0,1)\mathcal{P}_{(x,0)}[\mathcal{M}\mbox{
never hits }\blacktriangle].$

###### Proof.

We still need to check that, $y\to\infty$, for $x\in\Delta$,
$\frac{\overline{{\cal G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y)}$
is uniformly bounded in $x$ and tends to $1$ as $y\to\infty$. First remark
that $\overline{\mathcal{K}}$ has period $2$. We could proceed by taking $x$
odd and $y$ even but it is easier to recall that we could just as well have
redefined $\overline{\mathcal{K}}$ as
$\frac{1}{2}\overline{\mathcal{K}}+\frac{1}{2}I$. This eliminates the
periodicity problem so $\overline{\mathcal{K}}$ satisfies Kesten’s uniform
aperiodicity property (1.5) in [29]. Also that $1$ is the unique harmonic
function for $\hat{\mathcal{K}}$ so Condition A5.5 holds. We may now apply
Proposition 4 in [22] to conclude $\frac{\overline{{\cal
G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y)}\to 1$ as $y\to\infty$.

To show $\frac{\overline{{\cal
G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y)}$ is bounded uniformly
bounded $x$ we use the argument in Section 7.3 in [22]. For paths
$\omega^{\prime}$ of $\mathcal{M}$ starting from $(1,0)$ define
$N_{(1,y)}(\omega^{\prime})$ to be the number of visits by $\mathcal{M}$ to
$(1,y)$ following the trajectory $\omega^{\prime}$. Similarly define for paths
$\omega$ of $\mathcal{M}$ starting from $(x,0)$ define $N_{(1,y)}(\omega)$ to
be the number of hits at $(\ell,0)$.

Now consider the product space of all paths $\omega$ of $\mathcal{M}$ which
start from $(x,0)$ times paths $\omega^{\prime}$ which start from $(1,0)$. On
this product space we can define a coupled path starting from $(1,0)$ which
follows $\omega^{\prime}$ until $\omega^{\prime}$ hits the path $\omega$ and
then follows $\omega$. Given a path $\omega$ which hits $(1,y)$, we note that
all paths $\omega^{\prime}$ must hit the path $\omega$ because the path
$\omega^{\prime}$ is trapped between the $y$-axis and the path $\omega$
(recall $\mathcal{K}((1,t),(0,t))=0$ for all $t$). Define
$N_{(1,y)}(\omega^{\prime},\omega)$ to be the number of hits at $(1,y)$ by the
coupled path. Then, for any $\omega^{\prime}$ and any $\omega$,
$N_{(1,y)}(\omega)\leq N_{(1,y)}(\omega^{\prime},\omega)$. But
$E[N_{(1,y)}(\omega^{\prime},\omega)]=E[N_{(1,y)}(\omega^{\prime})]$. Hence
$E[N_{(1,y)}(\omega)]\leq E[N_{(1,y)}(\omega^{\prime})]$; i.e.

$\overline{{\cal G}}((x,0);(1,y))\leq\overline{{\cal G}}((1,0);(1,y)).$

∎

In the above we have followed the argument in [22]. Instead we could have used
the much more general argument in [19] to check that, as $y\to\infty$,
$\frac{\overline{{\cal G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y))}$
tends to $1$ as $y\to\infty$. In [19] the Martin boundary of is obtained for a
killed random walk on a half-space. This is exactly what we need in our
special case since falling off sheet 1 is equivalent to killing. Moreover in
our special nearest-neighbour case, the function $h_{a,+}(z)=h_{a,+}(x,y)$
defined before Theorem 1 in [19], reduces to $x\exp(a\cdot
z)=x\alpha_{T}^{x}\beta_{T}^{y}$. when
$a\in\partial_{0}D=(\ln(\alpha_{T}),\ln(\beta_{T}))$; i.e. it reduces to the
harmonic function we used in the bridge case.

####  3.1.2 Extending to $\pi(0,y,2)$

Henceforth in this section we assume there is a ray on sheet 1; i.e.
$\mu\cdot(\lambda_{1}/\lambda)-\lambda>0$. We can bootstrap the asymptotics of
$\pi(1,y,1)$ to obtain the asymptotics of $\pi(0,y,2)$. It suffices to
consider

$\displaystyle\pi(0,y,2)$ $\displaystyle=$
$\displaystyle\mu\pi(1,y,1)+\lambda_{2}\pi(0,y-1,2)+\mu\pi(0,y+1,2)\mbox{ for
}y\geq 1$ (17)

where we recall $\pi(0,0,2)=0$ by definition so $\pi(0,0,1)=(1-\rho)$. This
immediately yields the lower bound $\pi(0,y,2)\geq\mu\pi(1,y,1)$.

On the other hand, we can define
$\Pi_{2}(z)=\sum_{y=1}^{\infty}z^{y}\pi(0,y,2)$ and
$\Pi_{1}(z)=\sum_{y=1}^{\infty}z^{y}\pi(1,y,1)$. Multiplying (17) by $z^{y}$
and summing from $y=1$ we get

$\displaystyle\Pi_{2}(z)$ $\displaystyle=$
$\displaystyle\mu\Pi_{1}(z)+\lambda_{2}z\sum_{y=1}^{\infty}z^{y-1}\pi(0,y-1,2)+\frac{\mu}{z}\sum_{y=1}^{\infty}z^{y+1}\pi(0,y+1,2)$
$\displaystyle=$
$\displaystyle\mu\Pi_{1}(z)+\lambda_{2}z\Pi_{2}(z)+\frac{\mu}{z}(\Pi_{2}(z)-z\pi(0,1,2))$

so

$\displaystyle\Pi_{2}(z)$ $\displaystyle=$ $\displaystyle-\frac{\mu
z}{\lambda_{2}z^{2}-z+\mu}\left(\Pi_{1}(z)-\pi(0,1,2)\right).$ (18)

We wish to show (18) is analytic on a disk of radius greater than $\beta_{T}$
except for a singularity at $\beta_{T}$. Now the left hand side above is
analytic at least in the ball of radius $\rho^{-1}$ since
$\pi(0,y,2)\leq(1-\rho)\rho^{y}$ so the right hand side is also.
$\lambda_{2}z^{2}-z+\mu=0$ has real roots since
$\lambda_{2}\mu<\lambda\mu<1/4$ using $\lambda+\mu=1$ and stability. The root
$(1-\sqrt{1-4\mu\lambda_{2}}/(2\lambda_{2})$ is less than $1$ if and only if
$1-2\lambda_{2}<\sqrt{1-4\mu\lambda_{2}}$; i.e. if and only if
$\lambda_{2}+\mu<1$ and this is always true. Hence the pole at
$(1-\sqrt{1-4\mu\lambda_{2}}/(2\lambda_{2})$ must then cancel a factor in the
numerator.

On the other hand the root $(1+\sqrt{1-4\mu\lambda_{2}}/(2\lambda_{2})$ is
greater than $\beta_{T}$ if and only if

$\displaystyle\sqrt{1-4\mu\lambda_{2}}+4\sqrt{\mu\lambda_{1}}-1$
$\displaystyle>$ $\displaystyle 0.$ (19)

For fixed $\lambda_{1}\in[0,1/2]$. the above function is decreasing as we see
by setting $\mu=1-\lambda_{1}-\lambda_{2}$ and by taking the partial
derivative in $\lambda_{2}$. Since we have a ray on sheet 1,
$\lambda_{1}\rho^{-1}>\lambda$; i.e. $f(\lambda_{2})>1$ where

$\displaystyle f(\lambda_{2})$ $\displaystyle=$
$\displaystyle\lambda_{1}(1-\lambda_{1}-\lambda_{2})/(\lambda_{1}+\lambda_{2})^{2}.$
(20)

Moreover, for fixed $\lambda_{1}$, $f(\lambda_{2})$ is decreasing in
$\lambda_{2}$ again by taking partial derivatives. Since
$f(0)=(1-\lambda_{1})/\lambda_{1}\geq 1$ for $0\leq\lambda_{1}\leq 1/2$ it
follows we can define $\lambda_{2}^{*}=g(\lambda_{1})$ be the unique value
such that $f(\lambda_{2}^{*})=1$. Hence
$\lambda_{1}(1-\lambda_{1}-\lambda_{2}^{*})=(\lambda_{1}+\lambda^{*}_{2})^{2}$
that is, finding the positive root,
$\lambda_{2}^{*}=(-3\lambda_{1}+\sqrt{\lambda_{1}^{2}+4\lambda_{1}})/2$. We
conclude that (19) holds if it holds on the curve
$(\lambda_{1},\lambda_{2}^{*})$.

Now (19) certainly holds if $4\sqrt{\mu\lambda_{1}}-1\geq 0$ since
$\sqrt{1-4\mu\lambda_{2}}>0$ if $\lambda_{1}>0$. Alternatively assume
$4\sqrt{\mu\lambda_{1}}-1<0$. (19) holds if and only if

$\displaystyle 1-4\mu\lambda_{2}^{*}$ $\displaystyle>$
$\displaystyle(1-4\sqrt{\mu\lambda_{1}})^{2}\mbox{ or equivalently if and only
if}$ $\displaystyle 2\sqrt{\mu\lambda_{1}}$ $\displaystyle>$
$\displaystyle\lambda_{2}^{*}\mu+4\mu\lambda_{1}\mbox{ or equivalently if and
only if}$ $\displaystyle 2\sqrt{\mu\lambda_{1}}$ $\displaystyle>$
$\displaystyle\frac{(-3\lambda_{1}+\sqrt{\lambda_{1}^{2}+4\lambda_{1}})}{2}\mu+4\mu\lambda_{1}\mbox{
or equivalently if and only if}$ $\displaystyle 4$ $\displaystyle>$
$\displaystyle 5\sqrt{\mu\lambda_{1}}+\sqrt{\lambda_{1}+4}.$

The latter inequality is certainly true because $\sqrt{\mu\lambda_{1}}\leq
1/4$ and $\sqrt{\lambda_{1}+4}\leq\sqrt{4.5}$ and $5/4+\sqrt{4.5}<5$. We
conclude that (19) holds.

By Theorem 3, $\Pi_{1}(z)$ has radius of convergence $\beta_{T}$. We shift the
pole in $\Pi_{1}(z)$ to $1$ by defining $w=z/\beta_{T}$ to give

$\displaystyle\Pi_{2}(\beta_{T}w)$ $\displaystyle=$
$\displaystyle-\frac{\mu\beta_{T}w}{\lambda_{2}(\beta_{T}w)^{2}-\beta_{T}w+\mu}\left(\Pi_{1}(\beta_{T}w)-\pi(0,1,2)\right).$
(21)

The right hand side of the above is analytic in $w$ in the disk of radius
greater than $1$ except for the singularity at $1$. To calculate the
asymptotics of $\pi(0,y,2)$ we use the results in [17]. Hence, as $w\to 1$,

$\Pi_{2}(\beta_{T}w)\sim-\frac{\mu\beta_{T}}{\lambda_{2}\beta_{T}^{2}-\beta_{T}+\mu}\left(\Pi_{1}(\beta_{T}w)-\pi(0,1,2)\right).$

Note that since $\beta_{T}$ is between the roots of $\lambda_{2}z^{2}-z+\mu=0$
so $\lambda_{2}\beta_{T}^{2}-\beta_{T}+\mu<0$. Consequently the coefficient of
(21) is positive and modulo this positive constant the asymptotics of
$\pi(0,y,2)$ are the same as $\pi(1,y,1)$.

######  Corollary 1.

If $\mu\cdot(\lambda_{1}/\lambda)-\lambda>0$ then as $y\to\infty$,
$\pi(0,y,2)\sim C_{1}\beta_{T}^{-y}y^{-3/2}$ where $C_{1}$ is a fixed
constant.

###  3.2 The Cascade case

There are two distinct ways to reach $(x,1,2)$. When $\beta_{T}\leq\beta_{E}$
we have cascade paths. When $\beta_{T}>\beta_{E}$ we have cascade paths. We
now estimate the asymptotics of $\pi(x,0,1)$ in the cascade case. Therefore,
in addition to our assumption of a ray on sheet 1 in this subsection, we
assume $\beta_{T}\leq\beta_{E}$. In the cascade case the large deviation path
to $(x,1,2)$ first climbs the $y$-axis and then cascades across to $(x,1,2)$.

####  3.2.1 Extending to $\pi(x,1,2)$ in the Cascade case

We use the technique developed in [23] and [24]. First we find a measure
$\psi$ which is invariant on the second sheet of the form
$\psi(x,y)=\psi_{0}(y)\gamma_{T}^{-x}\beta_{T}^{-y}$ where $\psi(x,0)=0$.
$\psi(0,y)$ has roughly the same asymptotics as $\pi(0,y,2)$. The associated
time reversal $\overleftarrow{M}$ with respect to $\psi$ has kernel
$\overleftarrow{K}$ and we note $\overleftarrow{K}((x,1),(x,0))=0$ because
$\psi(x,0)=0$. Moreover $\overleftarrow{M}$ has negative drift; i.e.
$\overleftarrow{K}((x,y),(x-1,y))=\gamma_{T}^{-1}\lambda_{1}$.

If $\psi$ is invariant on sheet 2 at $(x,y)$ then

$\displaystyle\sum_{s,t}\overleftarrow{K}((x,y),(s,t))\frac{\pi(s,t)}{\psi((s,t)}=\sum_{s,t}\frac{\psi((s,t)}{\psi(x,y)}\overline{K}((s,t),(x,y))\frac{\pi(s,t)}{\psi((s,t)}$
$\displaystyle=$
$\displaystyle\frac{1}{\psi(x,y)}\sum_{s,t}\pi(s,t)\overline{K}((s,t),(x,y))=\frac{\pi(x,y)}{\psi(x,y)}$

so $\pi/\psi$ is harmonic for $\overleftarrow{K}$ and
$\pi(\overleftarrow{M}(n))/\psi(\overleftarrow{M}(n))$ is a martingale.

Let $\Delta=\\{(0,y,2):y\geq 1\\}$. Recall

$\displaystyle\pi(x,1,2)$ $\displaystyle=$
$\displaystyle\sum_{y}\pi(0,y,2)E_{(x,1,2)}[\mbox{\\# visits to $(x,1,2)$
before $M$ returns to $\Delta$}].$

If we redefine $M$ as having a killing at $(x,1,2)$ if there is a transition
to $(x,0,1)$, this will not change the above representation. Now do the time
reversal with respect to $\psi$ starting at $(x,1,2))$ or use the martingale
property of $\pi/\psi$ to get

$\displaystyle\frac{\pi(x,1,2)}{\psi(x,1,2)}$ $\displaystyle=$ $\displaystyle
E_{(x,1,2)}[\frac{\pi(\overleftarrow{M}(\tau))}{\psi(\overleftarrow{M}(\tau))}]$
(22)

where $\tau$ is the first time $\overleftarrow{M}$ hits $\Delta$.

We now show $\psi$ actually exists and that
$\frac{\pi(0,y,2)}{\psi(0,y,2)}=\frac{\pi(0,y,2)}{\psi_{0}(y)\beta_{T}^{-y}}$
is bounded. We pick $\gamma_{T}$ so

$\displaystyle\gamma_{T}\lambda_{1}+\beta_{T}^{-1}\mu+\beta_{T}\lambda_{2}=1.$
(23)

In order that $\psi$ be invariant it must satisfy

$\psi_{0}(y)\gamma_{T}^{-x}\beta_{T}^{-y}=\psi_{0}(y)\gamma_{T}^{-(x-1)}\beta_{T}^{-y}\lambda_{1}+\psi_{0}(y+1)\gamma_{T}^{-x}\beta_{T}^{-(y+1)}\mu+\psi_{0}(y-1)\gamma_{T}^{-x}\beta_{T}^{-(y-1)}\lambda_{2};$

that is

$\psi_{0}(y)=\gamma_{T}\lambda_{1}\psi_{0}(y)+\beta_{T}^{-1}\mu\psi_{0}(y+1)+\beta_{T}\lambda_{2}\psi_{0}(y-1).$

Because of (23), $\psi_{0}$ is harmonic for the random walk with probability
transition kernel

$\hat{\mathcal{K}}^{T}(y,y)=s=\gamma_{T}\lambda_{1},\hat{\mathcal{K}}^{T}(y,y+1)=u=\beta_{T}^{-1}\mu,\hat{\mathcal{K}}^{T}(y,y-1)=d=\beta_{T}\lambda_{2}.$

Up to constants there is a unique positive solution with $\psi_{0}(0)=0$. This
follows as a consequence of the nearest neighbour character of
$\hat{\mathcal{K}}^{T}$. Knowing $\psi_{0}(0)=0$ and the value of
$\psi_{0}(1)$ allows us to iteratively determine all of $\psi_{0}$.

By inspection the unique positive solution with $\psi_{0}(0)=0$ is
$\psi_{0}(y)=1-(d/u)^{y}$ if $d<u$. But $d<u$ means
$\beta_{T}\lambda_{2}<\beta_{T}^{-1}\mu$; i.e.

$\beta_{T}<\sqrt{\frac{\mu}{\lambda_{2}}}=\beta_{E}$

and this is true by hypothesis. Using Corollary 1,

$\frac{\pi(0,y,2)}{\psi(0,y,2)}=\frac{\pi(0,y,2)}{\psi_{0}(y)\beta_{T}^{y}}\sim
C_{1}y^{-3/2}.$

If $d=u$ then the unique solution up to constants is $\psi_{0}(y)=y$. Hence,

$\frac{\pi(0,y,2)}{\psi(0,y,2)}=\frac{\pi(0,y,2)}{\psi_{0}(y)\beta_{T}^{y}}\sim
C_{1}y^{-5/2}.$

$\overleftarrow{M}$ drifts north-west if $d>u$ or west if $d=u$. Consequently
$\overleftarrow{M}(\tau)$ is distributed higher up the $y$-axis as the
starting point $(x,1,2)$ tends to infinity. Define
$C(x)=E_{(x,1,2)}[C_{1}(\overleftarrow{M}(\tau))^{-3/2}]$ if $d<u$ or
$C(x)=E_{(x,1,2)}[C_{1}(\overleftarrow{M}(\tau))^{-5/2}]$ if $d=u$. Either way
$C(x)$ tends to zero at a polynomial rate as $x\to\infty$. Consequently from
(22) we conclude

######  Theorem 4.

If $\mu\cdot(\lambda_{1}/\lambda)-\lambda>0$ and $\beta_{T}\leq\beta_{E}$ then
as $x\to\infty$, $\pi(x,1,2)\sim C(x)\beta_{T}^{-1}\gamma_{T}^{-x}$ where
$C(x)\to 0$ as $x\to\infty$.

####  3.2.2 Extending to $\pi(x,0,1)$

By the method used in Corollary 1 we remark that using the equilibrium
equation

$\pi(x,0,1)=\lambda_{1}\pi(x-1,0,1)+\mu\pi(x+1,0,1)+\mu\pi(x,1,2)$

and multiplying by $z^{x}$ and summing from $x=1$ to infinity we get

$\Pi_{1}(z)=\lambda_{1}z(\Pi_{1}(z)+\pi(0,0,1))+\frac{\mu}{z}(\Pi_{1}(z)-z\pi(1,0,1))+\mu\Pi_{2}(z)$

where $\Pi_{1}(z)=\sum_{x=1}^{\infty}z^{x}\pi(x,0,1)$ and
$\Pi_{2}(z)=\sum_{x=1}^{\infty}z^{x}\pi(x,1,2)$. Hence

$\Pi_{1}(z)(1-\lambda_{1}z-\mu/z)=\mu\Pi_{2}(z)+\lambda_{1}z\pi(0,0,1)-\mu\pi(1,0,1)\mbox{
or }$ $\displaystyle\Pi_{1}(z)$ $\displaystyle=$
$\displaystyle-\frac{z}{\lambda_{1}z^{2}-z+\mu}(\mu\Pi_{2}(z)+\lambda_{1}z\pi(0,0,1)-\mu\pi(1,0,1)).$
(24)

The smaller root of $\lambda_{1}z^{2}-z+\mu=0$ is at
$r_{-}=(1-\sqrt{1-4\mu\lambda_{1}}/(2\lambda_{1})$ which is less than $1$ if
and only if $1-2\lambda_{1}<\sqrt{1-4\mu\lambda_{1}}$ and this is always true.
Hence the pole at $(1-\sqrt{1-4\mu\lambda_{1}}/(2\lambda_{1})$ must then
cancel a factor in the numerator.

On the other hand the root $r_{+}=(1+\sqrt{1-4\mu\lambda_{1}}/(2\lambda_{1})$
is greater than $\alpha_{E}$ if and only if

$\displaystyle\frac{(1+\sqrt{1-4\mu\lambda_{1}}}{2\lambda_{1}}>\frac{1-2\sqrt{\lambda_{2}\mu}}{2\lambda_{1}}$

and this is always true - just square both sides and simplify. Hence

$\displaystyle r_{-}<1<\rho^{-1}<\gamma_{T}<\alpha_{E}<r_{+}.$ (25)

By Theorem 4, $\Pi_{2}(z)$ has radius of convergence $\gamma_{T}$ in the
cascade case and we shall see later in Theorem 7, $\Pi_{2}(z)$ has radius of
convergence $\alpha_{E}$ in the bridge case. Hence the right hand side of (24)
is analytic in a disk of radius $\gamma_{T}$ in the cascade case and
$\alpha_{E}$ in the bridge case. As in Subsection 3.1.2, we shift the
singularity by taking either $w=z/\gamma_{T}$ or $w=z/\alpha_{E}$ and apply
the results in [17] to conclude $\pi(x,0,1)$ has the same asymptotics as
$\pi(x,1,2)$ multiplied by the constant
$-\gamma_{T}/(\lambda_{1}\gamma_{T}^{2}-\gamma_{T}+\mu)$ in the cascade case
and by the constant $-\alpha_{E}/(\lambda_{1}\alpha_{E}^{2}-\alpha_{E}+\mu)$
in the bridge case. We remark that these constants are indeed positive because
$\alpha_{E}$ and $\gamma_{T}$ lie between the roots of
$\lambda_{1}z^{2}-z+\mu=0$ because of (25). We have established

######  Theorem 5.

If $\tilde{\lambda}_{1}-\tilde{\mu}>0$ then as $x\to\infty$, $\pi(x,0,1)\sim
C_{2}\pi(x,1,2)$. where $C_{2}$ is a constant.

####  3.2.3 Asymptotics of $\pi(b^{u}(\ell))$ for
$\alpha_{T}<e^{u_{1}}\leq\gamma_{T}$ in the cascade case

Using the results in by Appendix A.1, pick a twist such that
$\alpha_{T}<e^{u_{1}}\leq\gamma_{T}$. The mean of the twisted kernel points
north-east. We can now repeat the calculations in Theorem 1 with
$h(x,y)=\exp(u_{1}x+u_{2}y)$. We take $\Delta=\\{(x,0,1):x\geq 1\\}$ and
$\blacktriangle=\\{(x,y):x\geq 1,y\geq 1\\}^{c}$ inside $\mathbb{Z}^{2}$. The
key fact to check is that $\sum_{x\geq 0}h(x,0)\pi(x,0)<\infty$. But

$\displaystyle\sum_{x\geq 0}h(x,0)\pi(x,0)$ $\displaystyle=$
$\displaystyle\sum_{x\geq 0}e^{u_{1}x}\pi(x,0)$ $\displaystyle\leq$
$\displaystyle\sum_{x\geq 0}e^{u_{1}x}C\gamma_{T}^{-x}$

by Theorems 5 and 4 where $C$ is some constant. This sum is finite since
$e^{u_{1}}\leq\gamma_{T}$ and we conclude

######  Theorem 6.

If $\tilde{\lambda}_{1}>\tilde{\mu}$ and $\beta_{T}\leq\beta_{E}$ and
$\alpha_{T}<e^{u_{1}}\leq\gamma_{T}$ then

$\displaystyle\pi(d^{u}(\ell))$ $\displaystyle\sim$ $\displaystyle
B^{u}e^{-u\cdot d^{u}(\ell)}\frac{1}{\sqrt{2\pi\ell/|m|}}$

where

$B^{u}=([|Q^{u}|(m^{u}\cdot\Sigma^{u}m)]^{-1/2})(\sum_{z\in\Delta}h(z)\pi(z)P_{z}[\mathcal{M}\mbox{
never hits }\blacktriangle]).$

We conclude that large deviations on sheet 1 in north-north-east directions is
a ray. However for north-east-east directions on sheet 1 the large deviation
path is not a ray and we investigate these paths next.

####  3.2.4 Asymptotics of $\pi(b^{u}(\ell))$ for $\gamma_{T}<e^{u_{1}}$ in
the cascade case

Consider a point $w$ such on sheet 1 that $\phi(w)=1$ and
$e^{w_{1}}>\gamma_{T}$. Let $(x^{w},y^{w})=<\ell\cdot d^{w}>$. Construct an
invariant measure on the sheet 1 of the form $\psi(x,y)=e^{-(u_{1}x+u_{2}y)}$
where $u$ belongs to the egg for sheet 1 such that $e^{u_{1}}=\alpha_{E}$.
This is possible because $\gamma_{T}<\alpha_{E}$ with the argument above.
Consequently a line dropped from $(\gamma_{T},\beta_{T})$ must hit the egg on
sheet 1 at some point $(\gamma_{T},\delta_{T})$ where $\delta_{T}=e^{u_{2}}$.
Construct an invariant measure on the sheet 1 of the form
$\psi(x,y)e^{-(u_{1}x+u_{2}y)}=\gamma_{T}^{-x}\delta_{T}^{-y}$. Again using
time reversal

$\displaystyle\frac{\pi(x,y,1)}{\psi(x,y)}$ $\displaystyle=$ $\displaystyle
E_{(x,y,1)}[\frac{\pi(\overleftarrow{M}(\tau))}{\psi(\overleftarrow{M}(\tau))}]$
$\displaystyle\sim$ $\displaystyle
C_{2}\cdot\beta_{T}^{-1}E_{(x,y,1)}[C(\overleftarrow{M}(\tau))]\beta_{T}^{-1}=D(x,y)$

by Theorems 4 and 5. $D(x,y)$ tends to zero as $x\to\infty$ at a polynomial
rate. This gives

$\pi(x^{w},y^{w},1)\sim D(x^{w},y^{w})\gamma_{T}^{-x^{w}}\delta_{T}^{-y^{w}}$

as $x^{w}\to\infty$. In the cascade case the large deviation path from
$(0,0,1)$ to $x^{w},y^{w},1$ is a bridge up the $y$-axis on sheet 1 followed
by a jump to sheet 2 followed by a cascade across sheet 2 to some point
$(x,1,2)$ followed by a transition to sheet 1 and then along the path twisted
by $(e^{u_{1}},e^{u_{2}})=(\gamma_{T},\delta_{T})$ to $(x^{w},y^{w},1)$.

###  3.3 The bridge case

Here we study the bridge case where $\beta_{T}>\beta_{E}$. In the bridge case
the large deviation path skims along the $x$-axis on sheet 2 to reach
$(x,1,2)$.

####  3.3.1 Extending to $\pi(x,1,2)$ in the Bridge case

We repeat the argument in Subsection 3.1.1. We define $\Delta=\\{(0,y,2):y\geq
1\\}$ and $\blacktriangle=\\{(x,y,2):x\geq 0,y>0\\}^{c}$. We consider the free
kernel $\overline{K}$ with killing probability $K((x,1,2),(x,0,1))$ on points
$(x,1)$ where there are transitions from sheet 2 to sheet 1. To twist the free
kernel $\overline{K}$ to make a bridge path consider a rough $h_{E}$-transform
where $h_{E}(x,y)=\alpha_{E}^{x}\beta_{E}^{y}$ and where we already obtained
$\beta_{E}=\sqrt{\mu/\lambda_{2}}$ and
$\alpha_{E}=(1-2\sqrt{\mu\lambda_{2}})/(2\lambda_{1})$. We again remark that
$(\rho^{-1},\rho^{-1})$ lies on Curve 2 so it follows that
$\alpha_{E}>\rho^{-1}>\alpha_{T}$.

Let $\mathcal{K}_{E}$ denote the $h_{E}$-transformed kernel. The Markovian
part (the $y$-component) of $\mathcal{K}_{E}$ is
$s=\hat{\mathcal{K}}_{E}(y,y)=\lambda_{1}\alpha_{E}$ for $y\geq 1$ and

$\hat{\mathcal{K}}_{E}(y,y+1)=\hat{\mathcal{K}}_{E}(y,y-1)=\sqrt{\mu\lambda_{2}}=p\mbox{
for }y\geq 2.$

Hence $\hat{\mathcal{K}}_{E}(y,y-1)=p$ for $y\geq 2$. At $y=1$
$\hat{\mathcal{K}}_{E}(1,2)=\sqrt{\mu\lambda_{2}}$ but we define a transition
$K((x,1,2),(x,0,1))$ to be a killing so $\hat{\mathcal{K}}_{E}(1,0)=0$ since
this is a transition off sheet 1. Hence $\hat{\mathcal{K}}_{E}$ has a killing
$\kappa=\sqrt{\mu\lambda_{2}}$ at point $1$. The mean drift in the
$x$-direction at $(x,y)$ for $y\geq 1$ is $d_{+}=\lambda_{1}\alpha_{E}$.

Again note that $\hat{h}_{0}(y)=y$ is harmonic for $\hat{\mathcal{K}}_{E}$ and
the associated $\hat{h}_{0}$-transform gives a Markovian kernel satisfying the
conditions of Theorem 1 in [29]. Consequently $\hat{h}_{0}$ is unique harmonic
function for $\hat{\mathcal{K}}_{E}$ and consequently
$h(x,y)=\hat{h}_{0}(x)h_{E}(x,y)=y\alpha_{E}^{x}\beta_{E}^{y}$ is harmonic for
$\overline{K}$. Again the $h$-transform of $\overline{K}$ is denoted by
$\overline{\mathcal{K}}$ which is associated with the twisted chain
$\mathcal{M}$ and the associated potential is $\overline{\mathcal{G}}$.
$\overline{\mathcal{K}}_{\blacktriangle}$ is the kernel killed on hitting
$\blacktriangle$. We recall the representation (11),

$\displaystyle\pi(x,1,2)$ $\displaystyle=$ $\displaystyle
h(x,1)^{-1}\sum_{y\geq 0}h(0,y)\pi(0,y,2)\overline{{\cal
G}}_{\blacktriangle}((0,y);(x,1))$ (26) $\displaystyle=$
$\displaystyle\beta_{E}\alpha_{E}^{-x}\sum_{y}y\beta_{E}^{y}\pi(0,y,2)\overline{{\cal
G}}_{\blacktriangle}((0,y);(x,1)).$

By Corollary 1, $\pi(1,y,2)=o(\beta_{T}^{-y})$ and by hypothesis
$\beta_{T}>\beta_{E}$ so

$\sum_{y}y\beta_{E}^{y}\pi(0,y,2)<\infty.$

Let $\gamma(0,y)=h_{0}(y)\alpha_{E}^{y}\pi(0,y,1)\chi_{\Delta}((0,y))$ and
$\gamma_{\blacktriangle}(w)=\gamma\Pi^{\overline{{\cal
K}}}_{\blacktriangle}(w)$ where $w\in\blacktriangle$ and $\Pi^{\overline{{\cal
K}}}_{\blacktriangle}((0,y);w))$ is the probability of hitting $w$ if the
twisted chain started at $(0,y)$ enters $\blacktriangle$. Again using Lemma 12

$\displaystyle\gamma\overline{{\cal G}}_{\blacktriangle}(x,1)$
$\displaystyle=$ $\displaystyle\sum_{x}\gamma(0,y)\overline{{\cal
G}}((0,y);(x,1))-\sum_{y}\gamma(0,y)\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}((0,y);(w,0)))\overline{{\cal G}}((w,0);(x,1))$
$\displaystyle=$ $\displaystyle\gamma\overline{{\cal
G}}(x,1)-\gamma_{\blacktriangle}\overline{{\cal G}}(x,1).$

We use the same method as in the proof of Theorem 3 to show that $x\to\infty$,
$\frac{\overline{{\cal G}}((0,y);(x,1))}{\overline{\mathcal{G}}((0,1);(1,y))}$
is uniformly bounded in $y$ and tends to $1$ as $x\to\infty$. If this is true
then

$\frac{\gamma{\cal
G}(1,y)}{\overline{\mathcal{G}}((1,0);(1,y)}=\sum_{x}x\alpha_{E}^{x}\pi(x,0,1)\frac{\overline{\mathcal{G}}((x,0);(1,y))}{\overline{\mathcal{G}}((1,0);(1,y))}\to\sum_{y}y\alpha_{E}^{y}\pi(0,y,1)$

and

$\displaystyle\frac{\gamma_{\blacktriangle}\overline{{\cal
G}}(x,1)}{\overline{\mathcal{G}}((0,1);(x,1))}=\sum_{y}x\alpha_{E}^{y}\pi(0,y,2)\sum_{w\in\blacktriangle}\Pi^{\overline{{\cal
K}}}_{\blacktriangle}((0,y);w))\frac{{\mathcal{G}}(w;(x,1))}{\overline{\mathcal{G}}((0,1);(x,1))}$
$\displaystyle\to$
$\displaystyle\sum_{y}y\alpha_{E}^{y}\pi(0,y,2)\mathcal{P}_{(0,y)}[\mathcal{M}\mbox{
hits }\blacktriangle].$

In which case,

$\pi(x,1,2)\sim\beta_{E}^{-1}\alpha_{E}^{-x}\overline{\mathcal{G}}((1,0);(1,y)\sum_{y\in\Delta}y\beta_{E}^{y}\pi(0,y,2)\mathcal{P}_{(0,y)}[\mathcal{M}\mbox{
never hits }\blacktriangle].$

We have therefore stripped out the exponential decay $\alpha_{E}^{-x}$ out of
$\pi(x,1,2)$ leaving the polynomial decay
$\overline{\mathcal{G}}((0,1);(x,1)$.

Next recall
$\mathcal{G}((0,1);(x,1)=\mathcal{G}_{E}((0,1);(x,1)\frac{\hat{h}_{0}(1)}{\hat{h}_{0}(1)}=\mathcal{G}_{E}((0,1);(x,1)$.
Again we note $\mathcal{G}_{E}((0,1);(x,1)$ was analyzed analytically in [22].
This again requires relabeling or shifting the first quadrant so
$(0,1)\to(0,0)$ and $(x,1)\to(x,0)$. Denote the relabelled or shifted kernel
by $\mathcal{K}_{s}$ and the associated potential by $\mathcal{G}_{s}$. Hence
$\mathcal{K}_{s}((x,y);((u,v))=\mathcal{K}_{E}((x,y+1);((u,v+1))$ and
$\mathcal{G}_{E}((0,1);(x,1)=\mathcal{G}_{s}((0,0);(x,0)$. In these new
coordinates the probability of killing $\kappa$ at any point $(x,0)$ is
$\mathcal{K}_{E}((x,1);(x,0))=\mu\beta_{E}^{-1}$ and

$p_{0}:=\hat{\mathcal{K}}_{s}(0,1)=\hat{\mathcal{K}}_{s}(y,y+1)=p=\hat{\mathcal{K}}_{s}(y,y-1).$

By Proposition 1 in [22], ${\cal G}_{s}((0,0);(0,x))\sim C_{+}\,x^{-3/2}$
where $C_{+}=\frac{p_{0}}{\kappa^{2}}\sqrt{\frac{d_{+}}{2\pi(1-s)}}$

######  Theorem 7.

If $\tilde{\lambda}_{1}-\tilde{\mu}>0$ and $\beta_{T}>\beta_{E}$ then

$\pi(x,1,2)\sim\beta_{E}^{-1}\alpha_{E}^{-x}C_{+}x^{-3/2}\sum_{y}y\beta_{E}^{y}\pi(0,y,2)\mathcal{P}_{(0,y)}[\mathcal{M}\mbox{
never hits }\blacktriangle].$

####  3.3.2 Extending to $\pi(x,0,1)$ in the bridge case

This extension was accomplished in Theorem 5 for both the cascade and bridge
cases.

####  3.3.3 Asymptotics of $\pi(b^{u}(\ell))$ for
$\alpha_{T}<e^{u_{1}}\leq\alpha_{E}$ in the bridge case

Again, using the results in by Appendix A.1, pick a twist such that
$\alpha_{T}<e^{u_{1}}\leq\alpha_{E}$. The mean of the twisted kernel points
north-east. We can now repeat the calculations in Theorem 1 with
$h(x,y)=\exp(u_{1}x+u_{2}y)$. We take $\Delta=\\{(x,0,1):x\geq 1\\}$ and
$\blacktriangle=\\{(x,y):x\geq 1,y\geq 1\\}^{c}$ inside $\mathbb{Z}^{2}$. The
key fact to check is that $\sum_{x\geq 0}h(x,0)\pi(x,0)<\infty$. But

$\displaystyle\sum_{x\geq 0}h(x,0)\pi(x,0)$ $\displaystyle=$
$\displaystyle\sum_{x\geq 0}e^{u_{1}x}\pi(x,0)$ $\displaystyle\leq$
$\displaystyle\sum_{x\geq 0}\alpha_{E}^{x}\pi(x,0)<\sum_{x\geq
0}\alpha_{E}^{x}Cx^{-3/2}\alpha_{E}^{-x}$

by Theorems 5 and 7 where $C$ is some constant. Since this sum is finite we
conclude

######  Theorem 8.

If $\tilde{\lambda}_{1}>\tilde{\mu}$ and $\alpha_{T}<e^{u_{1}}\leq\alpha_{E}$
then

$\displaystyle\pi(d^{u}(\ell))$ $\displaystyle\sim$ $\displaystyle
B^{u}e^{-u\cdot d^{u}(\ell)}\frac{1}{\sqrt{2\pi\ell/|m|}}$

where

$B^{u}=([|Q^{u}|(m^{u}\cdot\Sigma^{u}m)]^{-1/2})(\sum_{z\in\Delta}h(z)\pi(z)P_{z}[\mathcal{M}\mbox{
never hits }\blacktriangle]).$

We conclude that large deviations on sheet 1 in north-north-east directions is
a ray. However for north-east-east directions on sheet 1 the large deviation
path is not a ray and we investigate these paths next.

####  3.3.4 Asymptotics of $\pi(b^{u}(\ell))$ for $\alpha_{E}<e^{u_{1}}$ in
the bridge case

The large deviation path to these points is not a ray but rather a path the
does a large deviation on sheet 2 before returning to sheet 1. In the Bridge
case consider a point $w$ such on sheet 1 that $\phi(w)=1$ and
$e^{w_{1}}>\alpha_{E}$. Let $(x^{w},y^{w})=<\ell\cdot d^{w}>$. Construct an
invariant measure on the sheet 1 of the form $\psi(x,y)=e^{-(u_{1}x+u_{2}y)}$
where $u$ belongs to the egg for sheet 1 such that $e^{u_{1}}=\alpha_{E}$.
This is possible because the asymptote of the egg
$\lambda_{1}\alpha+\lambda_{2}\beta+\mu\alpha^{-1}=1$ as $\beta\to 0$ is given
by $\lambda_{1}\alpha+\mu\alpha^{-1}=1$; i.e.
$\alpha=(1+\sqrt{1-4\lambda_{1}\mu})/(2\lambda_{1})$ which is greater than
$\alpha_{E}=(1-2\sqrt{\mu\lambda_{2}})/(2\lambda_{1})$. Consequently a line
dropped from $(\alpha_{E},\beta_{E})$ must hit the egg on sheet 1 at some
point $(\alpha_{E},\gamma_{E})$ where $\gamma_{E}=e^{u_{2}}$. Now construct
the time reversal with $\psi$. Note that the mean drift of the time reversal
is $-m^{w}$ in direction $-d^{w}$. Next recall (22) so

$\displaystyle\frac{\pi(x,y,1)}{\psi(x,y)}$ $\displaystyle=$ $\displaystyle
E_{(x,y,1)}[\frac{\pi(\overleftarrow{M}(\tau))}{\psi(\overleftarrow{M}(\tau))}].$

But $\pi(x,0,1)/\psi(x,0)\sim C_{4}x^{-3/2}$ by Theorems 7 and 5 where $C_{4}$
is some constant. The time reversal drifting in direction $-d^{w}$ will hit
the $x$-axis with probability one. The value of the function

$C(x,y)=E_{(x,y,1)}[\frac{\pi(\overleftarrow{M}(\tau))}{\psi(\overleftarrow{M}(\tau))}]\sim
E_{(x,y,1)}[C_{4}(\overleftarrow{M}(\tau))^{-3/2}]$

clearly tends to zero as $x\to\infty$ at a polynomial rate. This gives

$\pi(x^{w},y^{w},1)\sim C(x^{w},y^{w})\gamma_{E}^{-x^{w}}\beta_{E}^{-y^{w}}.$

Clearly the large deviation path from $(0,0,1)$ to $x^{w},y^{w},1$ is an
immediate leap to sheet 2 followed by a bridge along the $x$-axis for a
certain distance. Next the path leaps back to the first sheet and then follows
the path twisted by $(e^{u_{1}},e^{u_{2}})=(\alpha_{E},\gamma_{E})$.

##  4 Worse and Worse-the spiral-spiral case

We assume $\tilde{\lambda}_{1}-\tilde{\mu}<0$ and
$\tilde{\lambda}_{2}-\tilde{\mu}<0$. By adding these conditions we see that
$\rho>1/2$. We can investigate $\pi(x,y,s)$ for $s=1,2$ and for $x+y=\ell$ for
$\ell$ large. Let $\blacktriangle=\Delta=\\{(0,0,1)\\}$.
$h(x,y,s)=\rho^{-(x+y)}$ is harmonic on $\blacktriangle^{c}$. Using the
harmonic function $\rho^{-(x+y)}$ we can produce the free twisted chain with
kernel $\mathcal{K}$. We will first describe how large deviation paths to a
point $(x,y,s)$ where $x+y=\ell$ occur.

Starting on sheet 1 at $(u,0,1)$, the mean number of steps for the
$h$-transformed chain to drift across to the $y$ axis is
$u/(\lambda-\rho^{-1}\lambda_{1})$. During that time the mean rise in $y$ is
$\rho^{-1}\lambda_{2}u/(\lambda-\rho^{-1}\lambda_{1})$. This means that on
average the twisted chain hits the $y$ axis at $v=u+f_{1}\cdot u$ where

$f_{1}=\frac{\rho^{-1}\lambda_{2}}{\lambda-\rho^{-1}\lambda_{1}}-1=\frac{\mu-\lambda}{\lambda-\rho^{-1}\lambda_{1}}.$

Note that $f_{1}$ is positive since

$\frac{\mu-\lambda}{\lambda-\rho^{-1}\lambda_{1}}>0\mbox{ if and only if
}\lambda-\rho^{-1}\lambda_{1}>0$

where the later expression is positive by hypothesis in the spiral-spiral
case.

Similarly starting on sheet 2 at $(0,v,2)$, the mean number of steps to drift
across to the $x$ axis is $v/(\lambda-\rho^{-1}\lambda_{2})$. During that time
the mean rise in $x$ is
$\rho^{-1}\lambda_{1}v/(\lambda-\rho^{-1}\lambda_{2})$. This means that on
average the twisted chain hits the $x$ axis at $v+f_{2}\cdot v$ where

$f_{2}=\frac{\rho^{-1}\lambda_{1}}{\lambda-\rho^{-1}\lambda_{2}}-1=\frac{\mu-\lambda}{\lambda-\rho^{-1}\lambda_{2}}.$

Again $f_{2}$ is positive since $\lambda-\rho^{-1}\lambda_{2}>0$ by hypothesis
in the spiral-spiral case. It follows that the spiral-spiral path essentially
follows a sequence of similar triangles which grow exponentially.

We can make conjecture about the form of $\pi$. Let
$\mathcal{G}=\sum_{n=0}^{\infty}\mathcal{K}^{n}$ be the associated potential.
Let $\mathcal{K}_{\blacktriangle}$ be the taboo kernel $\mathcal{K}$ killed on
$\blacktriangle$ and let $\mathcal{G}_{\blacktriangle}$ be the associated
potential. We have the representation

$\displaystyle\pi(x,y,s)$ $\displaystyle=$
$\displaystyle(1-\rho)\rho^{x+y}{\cal G}_{\blacktriangle}((0,0,1);(x,y,s)).$
(27)

Let $\gamma(x,y)=(1-\rho){\cal G}_{\blacktriangle}((0,0,1);(x,y,s))$ and
$\kappa(x,y)=(1-\rho){\cal G}_{\blacktriangle}((0,0,1);(x,y,2))$ so
$\pi(x,y,1)=\rho^{x+y}\gamma(x,y)$ and $\pi(x,y,2)=\rho^{x+y}\kappa(x,y)$.
Also let

$\displaystyle a=\lambda_{1}\rho^{-1},b=\mu\rho\mbox{ and
}c=\lambda_{2}\rho^{-1}.$ (28)

Note that $b>a$ and $b>c$ in spiral-spiral case. $\mathcal{M}$ has transition
probabilities given by $a$, $b$ and $c$ and

$\displaystyle\gamma(x,y)=a\gamma(x-1,y)+b\gamma(x+1,y)+c\gamma(x,y-1)\mbox{
if }x,y\geq 1$
$\displaystyle\kappa(x,y)=a\kappa(x-1,y)+b\kappa(x,y+1)+c\kappa(x,y-1)\mbox{
if }x,y\geq 1$
$\displaystyle\gamma(x,0)=a\gamma(x-1,0)+b\gamma(x+1,0)+b\kappa(x,1)\mbox{ if
}x\geq 1$
$\displaystyle\kappa(0,y)=b\gamma(1,y)+b\kappa(0,y+1)+c\kappa(0,y-1)\mbox{ if
}y\geq 1.$

Note that

$(1-\rho)\rho^{\ell}=\sum_{x+y=\ell}(\pi(x,y,1)+\pi(x,y,2))=\rho^{\ell}\sum_{x+y=\ell}(\gamma(x,y)+\kappa(x,y,2))$

so $\sum_{x+y=\ell}(\gamma(x,y)+\kappa(x,y))=(1-\rho)$

It is reasonable to assume that, for $\ell$ large and $x+y=\ell$,

$\gamma(x,y)\sim\alpha(x)/\ell\mbox{ and }\kappa(x,y)\sim\beta(y)/\ell$

so $\sum_{x=1}^{\ell}\alpha(x)+\sum_{y=1}^{\ell}\beta(y)\sim(1-\rho)\ell$.
$\alpha$ and $\beta$ approximately satisfy

$\displaystyle\frac{1}{\ell}\alpha(x)$ $\displaystyle=$
$\displaystyle\frac{a}{\ell-1}\alpha(x-1)+\frac{b}{\ell+1}\alpha(x+1)+\frac{c}{\ell-1}\alpha(x)$
(29) $\displaystyle\frac{1}{\ell}\alpha(\ell)$ $\displaystyle=$
$\displaystyle\frac{a}{\ell-1}\alpha(\ell-1)+\frac{b}{\ell+1}\alpha(\ell+1)+\frac{b}{\ell+1}\beta(1)$
(30) $\displaystyle\frac{1}{\ell}\beta(y)$ $\displaystyle=$
$\displaystyle\frac{a}{\ell-1}\beta(y)+\frac{b}{\ell+1}\beta(y+1)+\frac{c}{\ell-1}\beta(y-1)$
(31) $\displaystyle\frac{1}{\ell}\beta(\ell)$ $\displaystyle=$
$\displaystyle\frac{c}{\ell-1}\beta(\ell-1)+\frac{b}{\ell+1}\beta(\ell+1)+\frac{b}{\ell+1}\alpha(1).$
(32)

It follows from (30) and (32) that

$\frac{b}{\ell+1}\beta(1)=\frac{c}{\ell-1}\alpha(\ell)\mbox{ and
}\frac{b}{\ell+1}\alpha(1)=\frac{a}{\ell-1}\beta(\ell)$

so to order zero $b\beta(1)=c\alpha(\ell)$ and $b\alpha(1)=a\beta(\ell)$ .

The $y$-axis acts like a turnstile on sheet 1 and the $x$-axis acts like a
turnstile on sheet 2; i.e. they act like absorbing boundaries. Consequently if
is reasonable to conjecture that

$\displaystyle\alpha(x)$ $\displaystyle=$ $\displaystyle
C_{1}(1-\left(\frac{a}{b}\right)^{x})-f\left(\frac{x}{\ell}\right)$
$\displaystyle\beta(y)$ $\displaystyle=$ $\displaystyle
C_{2}(1-\left(\frac{c}{b}\right)^{y})-g\left(\frac{y}{\ell}\right)$

where $f$ and $g$ are differentiable and where $f(0)=0$ and $g(0)=0$.
Substitute $\alpha$ of this form into (29) and retain the terms of order zero
and of order $1/\ell$. This gives

$\displaystyle
C_{1}(1-\left(\frac{a}{b}\right)^{x})-f\left(\frac{x}{\ell}\right)$
$\displaystyle=\frac{a}{\ell-1}(C_{1}(1-\left(\frac{a}{b}\right)^{x-1})-f\left(\frac{x-1}{\ell-1}\right))$
$\displaystyle+\frac{b}{\ell+1}(C_{1}(1-\left(\frac{a}{b}\right)^{x+1})-f\left(\frac{x+1}{\ell+1}\right))$
$\displaystyle+\frac{c}{\ell-1}(C_{1}(1-\left(\frac{a}{b}\right)^{x})-f\left(\frac{x}{\ell-1}\right))$

Figure 4: Spiral-Spiral case: $\lambda_{1}=0.3$, $\lambda_{2}=0.15$,
$\mu=0.55$

Now use the first order approximations

$\frac{x-1}{\ell-1}-\frac{x}{\ell}\sim-\frac{1-x/\ell}{\ell},\frac{x+1}{\ell+1}-\frac{x}{\ell}\sim\frac{1-x/\ell}{\ell},\frac{x}{\ell-1}-\frac{x}{\ell}\sim-\frac{x/\ell}{\ell}$

and

$f\left(\frac{x-1}{\ell-1}\right)-f\left(\frac{x}{\ell}\right)\sim-f^{\prime}\left(\frac{x}{\ell}\right)\frac{(1-x/\ell)}{\ell},$

and $f\left(\frac{x+1}{\ell+1}\right)-f\left(\frac{x}{\ell}\right)\sim
f^{\prime}\left(\frac{x}{\ell}\right)\frac{(1-x/\ell)}{\ell}$ and

$f\left(\frac{x}{\ell-1}\right)-f\left(\frac{x}{\ell}\right)\sim-f^{\prime}\left(\frac{x}{\ell}\right)\frac{x/\ell}{\ell}.$

To first order (4) requires

$f^{\prime}(s)((b-a)(1-s)+cs)+(a+c-b)f(s)=C_{1}(a+c-b)-C_{1}\left(\frac{a}{b}\right)^{\ell
s}$

where $s=x/\ell$. The function $(a/b)^{\ell s}$ goes to zero for $s>0$ as
$\ell\to\infty$ so we discard it. Hence we solve
$f^{\prime}(s)+r(s)f(s)=C_{1}r(s)$ where
$r(s)=\frac{(a+c-b)}{((b-a)(1-s)+cs)}$.

Multiply the integrating factor $I(s)=((b-a)(1-s)+cs)$ and we get
$(I(s)f(s))^{\prime}=C_{1}(a+c-b)$. Integrating we get
$I(s)f(s)=C_{1}(a+c-b)s+k$ where $k$ is a constant which must be $0$ if
$f(0)=0$. Hence $f(s)=C_{1}\frac{(a+c-b)s}{((b-a)(1-s)+cs)}$. Similarly
$g(s)=C_{1}\frac{(a+c-b)s}{((b-c)(1-s)+as)}$. Consequently

$\displaystyle\alpha(x)$ $\displaystyle=$ $\displaystyle
C_{1}\left((1-\left(\frac{a}{b}\right)^{x})-\frac{(a+c-b)x/\ell}{((b-a)(1-x/\ell)+cx/\ell)}\right)$
(34) $\displaystyle\beta(y)$ $\displaystyle=$ $\displaystyle
C_{2}\left((1-\left(\frac{c}{b}\right)^{y})-\frac{(a+c-b)y/\ell}{((b-c)(1-y/\ell)+ay/\ell)}\right).$
(35)

Next the relations $b\beta(1)=c\alpha(\ell)$ and $b\alpha(1)=a\beta(\ell)$ to
first order give

$bC_{2}(1-\frac{c}{b})=cC_{1}(1-\frac{(a+c-b)}{c}\mbox{ and
}bC_{1}(1-\frac{a}{b})=aC_{2}(1-\frac{a+c-b}{a}).$

Both equations imply $C_{2}=C_{1}\frac{(b-a)}{(b-c)}.$

Finally we use the fact that

$\displaystyle\frac{1}{\ell}\sum_{x=1}^{\ell}\alpha(x)+\frac{1}{\ell}\sum_{y=1}^{\ell}\beta(y)\sim(1-\rho).$
(36)

But

$\frac{1}{\ell}\sum_{x=1}^{\ell}\alpha(x)\approx
C_{1}-\frac{C_{1}}{\ell}\frac{a/b}{1-a/b}-C_{1}\int_{0}^{1}\frac{(a+c-b)s}{(b-a)(1-s)+cs}ds.$

Since $\int\frac{s}{p+qs}ds=\frac{1}{q^{2}}(p+qs-p\log(p+qs))$ we have
$\int_{0}^{1}\frac{s}{(b-a)(1-s)+cs}ds=\frac{1}{(a+c-b)^{2}}((a+c-b)+(b-a)log((b-a)/c))$.
Hence

$\frac{1}{\ell}\sum_{x=1}^{\ell}\alpha(x)\approx-\frac{C_{1}}{\ell}\frac{a/b}{1-a/b}-C_{1}\frac{(b-a)}{a+c-b}\log(\frac{b-a}{c})\mbox{
which is positive since }b<a+c.$

Similarly
$\frac{1}{\ell}\sum_{y=1}^{\ell}\beta(y)\approx-\frac{C_{2}}{\ell}\frac{c/b}{1-c/b}-C_{2}\frac{(b-c)}{a+c-b}\log(\frac{b-c}{a})$.
Using (36) and $C_{2}=C_{1}\frac{(b-a)}{(b-c)}$ we get

$\displaystyle C_{1}$ $\displaystyle=$ $\displaystyle\frac{C(\ell)}{b-a}\mbox{
and }C_{1}=\frac{C(\ell)}{b-c}\mbox{ where }$ (37) $\displaystyle C(\ell)$
$\displaystyle=$
$\displaystyle(1-\rho)(a+c-b)(log(\frac{ac}{(b-a)(b-c)})-\frac{1}{\ell}(a+c-b)(\frac{a}{(b-a)^{2}}+\frac{c}{(b-c)^{2}}))^{-1}.$

(34) and (35) now give $\alpha$ and $\beta$.

To test our conjecture that $\gamma(x,y)\sim\alpha(x)/\ell\mbox{ and
}\kappa(x,y)\sim\beta(y)/\ell$ we simulated $n=10^{6}$ trajectories of
$\mathcal{M}$ starting from $(0,0,1)$ using Julia [28]. We count the number of
visits $N(x,y,s)$ to $(x,y,s)$ before hitting $\Delta$ for $x+y=\ell$. Then

$EN(x,y,1)={\cal G}_{\blacktriangle}((0,0,1);(x,y,1))\cdot
n=\frac{\gamma(x,y)}{(1-\rho)}\cdot n$

and

$EN(x,y,2)={\cal G}_{\blacktriangle}((0,0,1);(x,y,2))\cdot
n=\frac{\kappa(x,y)}{(1-\rho)}\cdot n.$

Hence, if $N=\sum_{x+y=\ell}(N(x,y,1)+N(x,y,2))$, as $\ell\to\infty$,

$\frac{N(x,y,1)}{N}\approx\frac{\gamma(x,y)}{\sum_{x+y=\ell}(\gamma(x,y)+\kappa(x,y))}=\frac{\gamma(x,y)}{(1-\rho)}\approx\frac{\alpha(x)}{\ell(1-\rho)}$

and

$\frac{N(x,y,2)}{N}\approx\frac{\beta(y)}{\ell(1-\rho)}.$

Table 1: Values multiplied by $10^{6}$ and rounded $x$ | $1$ | $2$ | $3$ | $4$ | $3$ | $6$ | $7$ | $8$ | $9$ | $10$
---|---|---|---|---|---|---|---|---|---|---
$N(x,y,1)/N$ | 339 | 594 | 816 | 1030 | 1179 | 1283 | 1384 | 1479 | 1518 | 1581
$\alpha(x)/(\ell(1-\rho))$ | 334 | 605 | 825 | 1004 | 1150 | 1267 | 1362 | 1439 | 1501 | 1551

We took $\lambda_{1}=0.3$, $\lambda_{2}=0.15$ and $\mu=0.55$. We took
$\ell=600$. In Figure 4 the simulated curve is $N(x,y,1)/N$ for $x+y=600$
while the theoretical curve is $\alpha(x)/(\ell(1-\rho))$. The curves for
$N(x,y,2)/N$ and $\beta(y)/(\ell(1-\rho))$ are similarly close. The maximum
relative error between $N(x,y,1)/N$ and $\alpha(x)/(\ell(1-\rho))$ for
$x\in\\{1,2,\ldots,\ell\\}$ is $5.2$ percent. The fit for small values of $x$
is even better (see Table 1). Our experimental results lead to the following
conjecture.
Conjecture: In the spiral-spiral case, for $x+y=\ell$,
$\pi(x,y,1))\sim\rho^{\ell}\frac{\alpha(x)}{\ell}$ and
$\pi(x,y,2))\sim\rho^{\ell}\frac{\beta(y)}{\ell}$ as $\ell\to\infty$ where
$\alpha$ is given at (34) and $\beta$ is given at (35) and where $C_{1}$ and
$C_{2}$ are given at (37).

##  5 Traffic at a road closure

A service period consists of the time it takes for a car to cross the section
of road under repair. We will assume service time takes one unit of time.
Traffic travels one way until the queue is emptied and all the cars complete
the crossing. Then the cars in the other direction are released and traffic
continues one way until that queue is emptied and all cars have completed the
crossing. During a service period a random number of cars arrive at queue 1
having density $f$ and a random number arrive at queue 2 having density $g$.
We assume the number of arrivals in a period are independent of the number of
arrivals during other service periods and also independent of the arrivals at
the other queue. Moreover we assume $\lambda_{1}+\lambda_{2}<1$ where
$\lambda_{1}=\sum_{n=0}^{\infty}nf(n)$ and
$\lambda_{1}=\sum_{n=0}^{\infty}ng(n)$

We describe this system in the same way we did for the polling system; i.e.
state of the system is denoted by $(x,y,s)$ where $(x,y)$ is the joint queue
length of queues 1 and 2 and $s\in\\{1,2\\}$ is the queue being served. When
$(x,y)=(0,0)$, then $s=1$. Hence

$\displaystyle K((x,y,1);(x+u-1,y+v,1))$ $\displaystyle=$ $\displaystyle
f(u)g(v)\mbox{ for }x>1$ $\displaystyle K((1,y,1);(0,y+v,2))$ $\displaystyle=$
$\displaystyle f(0)g(v)\mbox{ for }x=1$ $\displaystyle
K((x,y,2);(x+u,y+v-1,2))$ $\displaystyle=$ $\displaystyle f(u)g(v)\mbox{ for
}y>1$ $\displaystyle K((x,1,2);(x+u,0,1))$ $\displaystyle=$ $\displaystyle
f(u)g(0)\mbox{ for }y>1.$

We won’t add a switch over time to avoid complications.

Note that $(x,0,2)$ for $x\geq 0$ and $(0,y,1)$ for $y\geq 1$ are not in the
state space $S$. Let $F(z)=\sum_{n=0}^{\infty}f(n)z^{n}$ and
$G(w)=\sum_{n=0}^{\infty}g(n)w^{n}$. We note that
$\psi(\gamma)=\gamma^{-1}F(\gamma)G(\gamma)$ equals $1$ when $\gamma=1$.
Moreover assuming both queues have nonzero probability of at least one arrival
during a busy period we have $\psi(\gamma)\to\infty$ as $\gamma\to\infty$.
Next,

$\displaystyle\frac{d}{d\gamma}\psi(\gamma)|_{\gamma=1}$ $\displaystyle=$
$\displaystyle-1+F^{\prime}(1)+G^{\prime}(1)$ $\displaystyle=$
$\displaystyle-1+\lambda_{1}+\lambda_{2}<0.$

Finally $\psi(\gamma)$ is convex so there exists a unique point $\alpha>1$
such that $\psi(\alpha)=1$ unless either of $F(\alpha)$ or $G(\alpha)$ is
infinite. We will just assume finiteness.

Define the function $h(x,y,s)=h(x,y,s,k)=\alpha^{x+y}$. We first check $h$ is
harmonic at points $(x,y,s)$ if $(x,y)\neq(0,0)$:

$\displaystyle\sum_{u,v}h(x+u-1,y+v,1)f(u)g(v)=\frac{F(\alpha)G(\alpha)}{\alpha}h(x,y,1)=h(x,y,1)\mbox{
if }x>1$
$\displaystyle\sum_{u>0,v}h(u,y+v,1)f(u)g(v)+h(0,y+v,2)f(0)g(v)=\frac{F(\alpha)G(\alpha)}{\alpha}h(x,y,1)$
$\displaystyle=h(1,y,1)\mbox{ if }x=1$
$\displaystyle\sum_{u,v}h(x+u,y+v-1,2)f(u)g(v)=\frac{F(\alpha)G(\alpha)}{\alpha}h(x,y,2)=h(x,y,2)\mbox{
if }y>1$ $\displaystyle\sum_{u,v>0}h(x+u,y+v-1,2)f(u)g(v)+h(x+u,0,1)f(u)g(0)$
$\displaystyle=\frac{F(\alpha)G(\alpha)}{\alpha}h(x,1,2)=h(x,1,2)\mbox{ if
}y=1.$

We can therefore twist the joint probability of $n$ customer arrivals during a
service period to queue 1 and $m$ to queue 2 from $f(n)g(m)$ to
$f(n)\alpha^{n}g(m)\alpha^{m}/\alpha$:

$\displaystyle\mathcal{K}((x,y,1);(x+m-1,y+n,1))$ $\displaystyle=$
$\displaystyle K((x,y,1);(x+m-1,y+n,1))\frac{h(x+m-1,y+n,1)}{h(x,y,1)}$
$\displaystyle=$ $\displaystyle f(n)\alpha^{n}g(m)\alpha^{m}/\alpha\mbox{ if
}x>1$ $\displaystyle\mathcal{K}((1,y,1);(x+m-1,y+n,1,1))$ $\displaystyle=$
$\displaystyle K((1,y,1);(x+m-1,y+n,1,1))\frac{h(x+m-1,y+n,1,1)}{h(1,y,1)}$
$\displaystyle=$ $\displaystyle f(n)\alpha^{n}g(m)\alpha^{m}/\alpha.$

and

$\displaystyle\mathcal{K}((x,y,2);(x+m,y+n-1,2))$ $\displaystyle=$
$\displaystyle K((x,y,2);(x+m,y+n-1,2))\frac{h(x+m-1,y+n,2)}{h(x,y,2)}$
$\displaystyle=$ $\displaystyle f(n)\alpha^{n}g(m)\alpha^{m}/\alpha$
$\displaystyle\mathcal{K}((x,1,2);(x+m,y+n-1,2,1))$ $\displaystyle=$
$\displaystyle K((x,1,2);(x+m,n,2))\frac{h(x+m,n,2,1)}{h(x,y,2)}$
$\displaystyle=$ $\displaystyle f(n)\alpha^{n}g(m)\alpha^{m}/\alpha.$

These are all probability kernels by the definition of $\alpha$.

The joint density of the twisted increment on sheet 1 is

$(f(n)\alpha^{n}/\alpha)(g(n)\alpha^{m})=(\frac{f(n)\alpha^{n}/\alpha}{F(\alpha)/\alpha})(\frac{g(m)\alpha^{m}}{G(\alpha)}).$

The marginal mean increment in $x$ is

$\frac{1}{F(\alpha)/\alpha}\sum_{n=0}^{\infty}(n-1)f(n)\alpha^{n}/\alpha=\frac{\alpha}{F(\alpha)/\alpha}\frac{d}{d\gamma}(F(\gamma)/\gamma)|_{\gamma=\alpha}=\alpha\frac{d}{d\gamma}(\log(F(\gamma)/\gamma))|_{\gamma=\alpha}.$

The marginal mean increment in $y$ is

$\frac{1}{G(\alpha)}\sum_{m=0}^{\infty}mg(m)\alpha^{m}=\alpha\frac{d}{d\gamma}(\log(G(\gamma)))|_{\gamma=\alpha}.$

The mean increment in the total number in the system is therefore

$\displaystyle\alpha\frac{d}{d\gamma}(\log(F(\gamma)/\gamma))|_{\gamma=\alpha}+\alpha\frac{d}{d\gamma}(\log(G(\gamma)))|_{\gamma=\alpha}=\alpha\frac{d}{d\gamma}(\log(\frac{F(\gamma)G(\gamma)}{\gamma}))$
$\displaystyle=$
$\displaystyle\alpha\frac{d}{d\gamma}(\log(\psi(\gamma)))|_{\gamma=\alpha}.$

But this is positive by the construction of $\alpha$. We conclude the twisted
chain is transient on sheet 1. The same is true on sheet 2.

We again see there is a spiral or a ray on sheet 1 if

$\alpha\frac{d}{d\gamma}(\log(F(\gamma)/\gamma))|_{\gamma=\alpha}<0,\mbox{ or
}\alpha\frac{d}{d\gamma}(\log(F(\gamma)/\gamma))|_{\gamma=\alpha}>0.$

Similarly there is a spiral or a ray on sheet 2 if

$\alpha\frac{d}{d\gamma}(\log(G(\gamma)/\gamma))|_{\gamma=\alpha}<0\mbox{ or
}\alpha\frac{d}{d\gamma}(\log(G(\gamma)/\gamma))|_{\gamma=\alpha}>0.$

We won’t go further but we do see the ray-spiral phenomenon is fairly common.

##  Appendix A Using the Foster-Meyn-Tweedie criterion

Let $h_{\Delta}\coloneqq h\bm{\mathbb{1}}_{\Delta}.$ In the proof of Prop. 1,
we need to know that when the ray condition (R1) holds on sheet 1

$\pi
h_{\Delta}=\sum_{z\in\Delta}\pi(z)h(z)=\sum_{x=0}^{\infty}\rho^{-x}\pi(x,0,1)<\infty.$
(38)

It is easy to see that $\sum_{x=0}^{\infty}\alpha^{x}\pi(x,0,1)<\infty$ for
$\alpha<\rho^{-1}$ since the stationary distribution for $x$ jobs in the
system is $(1-\rho)\rho^{x}.$ It is reasonable to suspect that the tail of
$\pi(x,0,1)$ is even lighter when (R1) holds. We give two results in this
section. The first result Prop. 4 shows that

$\sum_{x=0}^{\infty}\alpha^{x}\pi(x,0,1)<\infty$ (39)

for a value of $\alpha>\rho^{-1}$ provided that both (R1) and (R2) hold. The
second result Prop. 5 uses an approach inspired by Chang and Down [12, 13] to
show that (38) holds when only (R1) is assumed to hold.

######  Proposition 4.

If conditions (K), (R1), and (R2) hold, then (39) holds with

$\alpha=\alpha_{E}=\frac{1-2\sqrt{\lambda_{2}\mu}}{\lambda_{1}}>\rho^{-1},$

which means that (38) holds.

###### Proof.

Define the Lyapunov function $V(x,y,s)\coloneqq\alpha_{E}^{x}\beta_{E}^{y}.$
where the point $(\alpha_{E},\beta_{E})$ is the easternmost point on Curve 2
as defined in (15). We will show that

$KV-V\leq-f+g$ (40)

where $f$ and $g$ are nonnegative functions with $r\alpha_{E}^{x}\leq
f(x,0,1)$ for all $x$ where $r>0$ and $\pi g=\sum_{z\in S}\pi(z)g(z)<\infty.$
It would then follow from Theorem 14.3.7 of [31] that $\pi f\leq\pi g;$ hence,

$r\sum_{x=0}^{\infty}\pi(x,0,1)\alpha_{E}^{x}\leq\pi f\leq\pi g<\infty.$

Let $f(x,y,s)=rV(x,y,1)\delta_{1}(s)$ where
$r=\mu(\beta_{E}^{-1}-\alpha_{E}^{-1})$ and $\delta$ is the Kronecker delta
function; i.e.,

$\delta_{x}(y)\coloneqq\delta_{x,y}\coloneqq\begin{cases}1,&\text{for
$x=y$;}\\\ 0,&\text{for $x\neq y$.}\end{cases}$

Note that $r>0.$ This follows from the following argument. Let
$(\hat{\alpha},\hat{\beta})$ be any other solution lying on Curve 2:
$\lambda_{1}\alpha+\lambda_{2}\beta+\mu\beta^{-1}=1$. Then
$\hat{\alpha}<\alpha_{E}.$ The second component of the gradient of
$\lambda_{1}{\alpha}+\lambda_{2}{\beta}+\mu_{2}{\beta}^{-1}$ evaluated at
$(\alpha_{E},\beta_{E})$ is zero. If the second component evaluated at
$(\hat{\alpha},\hat{\beta})$ is positive, then $\beta_{E}<\hat{\beta}.$ Let
$(\hat{\alpha},\hat{\beta})=(\rho^{-1},\rho^{-1})$, which lies on Curve 2.
Under (R2), the second component of the gradient evaluated at
$(\rho^{-1},\rho^{-1})$ is positive, so

$\beta_{E}<\rho^{-1}<\alpha_{E},$

which means that $r>0$.

Since $V$ is harmonic on sheet 2 and $f(x,y,2)=0,$ we know that (40) holds on
sheet 2. Let $g(z)$ be zero at all states except

$g(0,0,1)=KV(0,0,1)+f(0,0,1)=\lambda_{1}\alpha_{E}+\lambda_{2}\beta_{E}+\mu+r.$

Then (40) also holds at state $(0,0,1)$.

For the rest of sheet 1, notice that

$\displaystyle KV(x,y,1)$
$\displaystyle=\lambda_{1}V(x+1,y,1)+\lambda_{2}V(x,y+1,1)+\mu V(x-1,y,1)$
$\displaystyle=(1-\mu(\beta_{E}^{-1}-\alpha_{E}^{-1}))V(x,y,1)$
$\displaystyle=(1-r)V(x,y,1)$

where we used the sheet 2 identitiy
$1=\lambda_{1}\alpha_{E}+\lambda_{2}\beta_{E}+\mu\beta_{E}^{-1}.$ Thus, on
sheet 1 away from the origin,

$KV(x,y,1)-V(x,y,1)\leq-rV(x,y,1),$

and we have shown that (40) holds, which completes the proof. ∎

######  Proposition 5.

If conditions (K) and (R1) hold, then (38) holds.

We delay the proof of Prop. 5 until Subsection A.2.

###  A.1 Nonnegative matrices and the Chang-Down approach

Chang and Down have [12, 13] have developed a novel approach to showing that
$\pi h_{\Delta}<\infty.$ We revisit the Chang-Down approach, but first we need
to develop several results for nonnegative matrices. Let $\mathcal{J}$ (i.e.,
“script J”) be a matrix. Assume that the elements are indexed by pairs of
elements of $S$ where $S$ is countable. We assume that $\mathcal{J}$ satisfies
the following condition:

For all $(i,j)\in S^{2}$, $\mathcal{J}(i,j)\geq 0,$ $\mathcal{J}^{n}(i,j)$ is
finite, and $\mathcal{J}$ is irreducible. That is, for any $i$ and $j$, there
exists $n=n(i,j)\geq 0$ such $\mathcal{J}^{n}(i,j)>0.$ ($\mathcal{J}$)

Let $E$ and $\Delta$ be nonempty subsets of $S$ where $E$ contains a finite
number of elements but $\Delta$ may contain an infinite number of elements.
Define

$\displaystyle\mathcal{J}_{E}(i,j)$
$\displaystyle\coloneqq\begin{cases}\mathcal{J}(i,j),&\text{for $i\not\in
E$;}\\\ 0,&\text{for $i\in E$.}\end{cases}$ (41)
$\displaystyle\mathcal{J}_{E}(i,\Delta)$
$\displaystyle\coloneqq\sum_{j\in\Delta}\mathcal{J}_{E}(i,j)$

Let $\mathcal{J}_{E}^{n}$ be the $n$th power of $\mathcal{J}_{E}$ where
$\mathcal{J}_{E}^{0}(i,j)=\delta_{i,j}.$ Note that
$\mathcal{J}_{E}^{n}(k,\Delta)=0$ if $n\geq 1$ and $k\in E$ and that
$\mathcal{J}_{E}^{0}(k,\Delta)=\bm{\mathbb{1}}_{\Delta}(k).$ Define the column
vectors $G_{E}$ and $H_{E}$ as

$\displaystyle G_{E}(i)$ $\displaystyle\coloneqq\sum_{n\geq
0}\mathcal{J}_{E}^{n}(i,\Delta)$ (42) $\displaystyle H_{E}$
$\displaystyle\coloneqq\mathcal{J}G_{E}.$ (43)

If $\mathcal{J}_{E}$ is substochastic, then $G_{E}(i)$ can be interpreted as
the expected number of visits to $\Delta$ until hitting $E$ or being killed.
The following expression for $G_{E}$ will prove useful.

$\displaystyle G_{E}(i)$ $\displaystyle=\sum_{n\geq
0}\mathcal{J}_{E}^{n}(i,\Delta)$
$\displaystyle=\bm{\mathbb{1}}_{\Delta}(i)+\sum_{k}\mathcal{J}_{E}(i,k)\sum_{n\geq
1}\mathcal{J}_{E}^{n-1}(k,\Delta)$
$\displaystyle=\bm{\mathbb{1}}_{\Delta}(i)+\sum_{k}\mathcal{J}_{E}(i,k)G_{E}(k)$
$\displaystyle=\begin{cases}\bm{\mathbb{1}}_{\Delta}(i)+\mathcal{J}G_{E}(i)=\bm{\mathbb{1}}_{\Delta}(i)+H_{E}(i),&\text{for
$i\not\in E$;}\\\ \bm{\mathbb{1}}_{\Delta}(i),&\text{for $i\in
E$.}\end{cases}$ (44)

We will need to know when $H_{E}$ is finite. Here are two sufficient
conditions.

######  Lemma 1.

Assume condition $(\mathcal{J})$. If there exists an $i\in S$ such that

$\sum_{n=1}^{\infty}\mathcal{J}^{n}(i,\Delta)<\infty,$ (45)

then $H_{E}(i)<\infty$ for all $i\in S$.

###### Proof.

If $\sum_{n=1}^{\infty}\mathcal{J}^{n}(i,\Delta)=\infty$ for some $i$, then it
follows from irreducibility that
$\sum_{n=1}^{\infty}\mathcal{J}^{n}(i,\Delta)=\infty$ for all $i$. Hence, from
the hypothesis, we know that (45) holds for all $i\in S$. Since
$\mathcal{J}_{E}\leq\mathcal{J},$

$\displaystyle H_{E}(i)$ $\displaystyle=\mathcal{J}G_{E}(i)$
$\displaystyle=\sum_{k}\mathcal{J}(i,k)\sum_{n\geq
0}\mathcal{J}_{E}^{n}(k,\Delta)$
$\displaystyle\leq\sum_{k}\mathcal{J}(i,k)\sum_{n\geq
0}\mathcal{J}^{n}(k,\Delta)$ $\displaystyle=\sum_{n\geq
1}\mathcal{J}^{n}(i,\Delta)$ $\displaystyle<\infty.$

∎

######  Lemma 2.

Assume condition $(\mathcal{J})$. If $H_{E}(i)<\infty$ for all $i\in E$, then
$H_{E}(i)<\infty$ for all $i\in S$.

###### Proof.

On the contrary, assume there exists $j\not\in E$ with $H_{E}(j)=\infty$.
Since $G_{E}(j)=\bm{\mathbb{1}}_{\Delta}(j)+H_{E}(j),$ by (44), we know that
$G_{E}(j)$ is also infinite. By irreducibility, there exists a path
$(i_{0},i_{1},\dotsc,i_{n})$ with $i_{0}=i$, $i_{n}=j$, and
$\mathcal{J}(i_{m},i_{m+1})>0$ for $m=0,\dotsc,n-1$. Let $i_{k}$ be the last
time that the path is in $E$; that is, $k=\max\\{m<n|i_{m}\in E\\}.$ Hence,

$H_{E}(i_{k})\geq\mathcal{J}\mathcal{J}_{E}^{n-k-1}(i_{k},i_{n})G_{E}(i_{n})=\infty,$

which is a contradiction. ∎

######  Remark 1.

Suppose that states not in $E$ communicate with respect to $\mathcal{J}_{E}$.
Then if $G_{E}(i)$ is infinite for one state $i\not\in E$, then $G_{E}(i)$ and
$H_{E}(i)$ are infinite for all states not in $E$.

######  Lemma 3.

If $H_{E}(i)<\infty$ for all $i\in E$, then

$\mathcal{J}G_{E}-G_{E}\leq-\bm{\mathbb{1}}_{\Delta}+b\bm{\mathbb{1}}_{E}$
(46)

for the finite, positive constant $b=\max_{i\in E}H_{E}(i)$.

###### Proof.

Since $G_{E}\leq\bm{\mathbb{1}}_{\Delta}+H_{E}$ by (44), it follows that
$G_{E}(i)$ is also finite for all $i\in E$. Since

$\displaystyle H_{E}(i)$
$\displaystyle=\mathcal{J}G_{E}(i)=\mathcal{J}(i,\Delta)+\sum_{k}\mathcal{J}(i,k)\sum_{n\geq
1}\mathcal{J}_{E}^{n}(k,\Delta),$

it also follows that $\mathcal{J}(i,\Delta)$ is finite for $i\in S$.

To see that (46) holds for $i\not\in E$, the l.h.s. simplifies to
$-\bm{\mathbb{1}}_{\Delta}(i)$ after using (44), so we have equality in this
case. When $i\in E$, the l.h.s. simplfies to
$H_{E}(i)-\bm{\mathbb{1}}_{\Delta}(i).$ By choosing $b=\max_{i\in E}H_{E}(i)$,
the inequality holds. The constant $b$ is finite since $E$ is a finite set. ∎

The Chang-Down approach to establishing that $\pi h_{\Delta}<\infty$ is to
establish that (46) holds. The following proposition describes this
connection.

######  Proposition 6.

Let

$\mathcal{J}(i,j)=\frac{K(i,j)h(j)}{h(i)}$

where $0<h<\infty$. Assume that condition $(\mathcal{J})$ holds. If
$H_{E}(i)<\infty$ for all $i\in E$, then (38) holds.

###### Proof.

Substituting for $\mathcal{J}$ in (46) gives

$\displaystyle\sum_{j\in S}\frac{K(i,j)h(j)}{h(i)}G_{E}(j)-G_{E}(i)$
$\displaystyle\leq-\bm{\mathbb{1}}_{\Delta}(i)+b\bm{\mathbb{1}}_{E}(i)$
$\displaystyle\sum_{j\in S}K(i,j)h(j)G_{E}(j)-G_{E}(i){h(i)}$
$\displaystyle\leq-{h(i)}\bm{\mathbb{1}}_{\Delta}(i)+b{h(i)}\bm{\mathbb{1}}_{E}(i)$
$\displaystyle KV(i)-V(i)$ $\displaystyle\leq-
h_{\Delta}(i)+bh(i)\bm{\mathbb{1}}_{E}(i)$

where $V(i)=h(i)G_{E}(i),$ which is finite for all $i\in S$ by (44) since
$H_{E}(i)$ is finite for all $i\in S$ by Lemma 2. Hence, from Theorem 14.3.7
of [31], (38) holds. ∎

There are similarities and differences between the above and pp. 140–142 of
[13]. For example, our $\mathcal{J}$ is not the same as their
$K_{\mathcal{W}}$ since the latter is stochastic, and hence, our (45) is not
exactly the same as their equation in Lemma 4.1.5(i). The biggest difference
might be that in Lemma 4.1.5(ii), they assume (20), which would be equivalent
to us assuming that $G_{E}(i)$ is finite for all $i$. However, we make the
stronger assumption that $H_{E}(i)$ is finite. The stronger assumption is
necessary to guarantee that our $b$ and their $B$ or $B^{\prime}$ is finite.
In particular, in the proof of Lemma 4.1.5(ii), even if their $V_{0}(y)$ is
finite for all $y$ there is no guarantee that $B^{\prime}$ (after taking the
maximum over $z$) is finite. However, this does not cause a problem in the
application to the polling model, since the support of $K_{W}(z,\cdot)$ is
finite.

Another difference is our inclusion of Lemma 1. The Chang-Down approach seems
like the best way of showing that $\pi h_{\Delta}<\infty$ when only a finite
number of rows of $\mathcal{J}$ have row sums greater than 1\. It certainly
works well for the polling model. We have included Lemma 1 in the hope that it
may prove useful in extending the Chang-Down approach to problems where an
infinite number of rows of $\mathcal{J}$ have row sums greater than 1.

###  A.2 Proof of Prop. 5

We use Prop. 6. Let $E=(0,0,1),$ $\Delta=$ $K$ given by (2), and
$h(x,y,s)=\rho^{-(x+y)}$. Recall that $\Delta$ is the $x$-axis. Since $h$ is
harmonic except at $E$, $\mathcal{J}$ will be stochastic except for the row
indexed by state $(0,0,1)$. (At state $(0,0,1)$, $\mathcal{J}$ is
superstochastic.)

To make use of the above lemmas we recall Theorem 14.3.7 in [31] which applies
to irreducible Markov chains with steady state $\pi$: if $V$, $f$ and $g$ are
two non-negative, finite valued functions on $S$ and

$\displaystyle KV(i)-V(i)$ $\displaystyle\leq$ $\displaystyle-f(i)+s(i)$ (47)

for all $i\in S$ then $\sum_{i\in S}f(i)\pi(i)\leq\sum_{i\in S}s(i)\pi(i)$.
Consequently, to prove $\sum_{i\in S}h(i)\pi(i)<\infty$ it suffices to find a
Lyapunov function $V$ such that

$KV(i)-V(i)\leq-h(i)\chi_{\Delta}+B_{0}\delta_{E}\mbox{ for some finite set
$E$}$

and some constant $B$. As in [13], divide by $h(i)$ and rewrite the above as

$\sum_{j\in
S}K(i,j)\frac{h(j)}{h(i)}\frac{V(j)}{h(j)}-\frac{V(i)}{h(i)}\leq-\chi_{\Delta}+B\delta_{E}$

where $B$ is a constant. Now define the kernel
$\mathcal{J}(i,j)=K(i,j)h(j)/h(i)$ for $i,j\in S$. By Lemma 3, $V=G_{E}$ and
$B$ will exist if $H(i)<\infty$ for all $i$.

In our ray case $h(x,y,s)=\rho^{-(x+y)}$ and $\Delta=\\{(x,0,1):x\geq 0\\}$.
We pick $E=\\{(0,0,1)\\}$. Note that $\mathcal{J}$ is exactly our twisted
kernel $\mathcal{K}$ (as defined at (4) which is super-stochastic at
$(0,0,1)$). Let $i_{0}=(0,0,1)$ then
$H_{E}(i_{0})=\mu+\tilde{\lambda}_{1}H_{E}(1,0,1)+\tilde{\lambda}_{2}H_{E}(0,1,2)$.
Away from $i_{0}$ $\mathcal{J}$ is stochastic with jumps east-west-north on
sheet 1 and east-south-north on sheet 2. Notice that returns to $\Delta$
involve a geometric number of jumps east or west on $\Delta$ followed by a
loop through sheet 2 followed by a geometric number of jumps on $\Delta$
followed by another loop and so on. The geometric number $N$ of jumps east and
west has distribution
$P(N=n)=(\tilde{\lambda}_{1}+\tilde{\mu})^{n}\cdot\tilde{\lambda}_{2}$ and
thus has finite mean. Starting at any $(x,0,1)$ the chance $p$ of simply
drifting away on a ray on sheet 1 and never doing another loop is greater than
$\tilde{\lambda}_{1}(1-\frac{\tilde{\mu}}{\tilde{\lambda}_{1}})$ since this is
the probability the east-west component which has drift
$\tilde{\lambda}_{1}-\tilde{\mu}>0$ drifts to $+\infty$ without returning to
$x$. Consequently the number of loops $L$ has finite expectation and if
$N_{i}$ is the number of visits on loop $i$ then the total number of visits to
$\Delta$ is $\sum_{i=1}^{L}N_{i}$. This has a finite expected value by Wald’s
Lemma. Therefore $H_{E}(0,0,1)<\infty$. Therefore we have checked the
condition for Lemma 1 and then using Lemma 2 we can apply Proposition 6 to get
our result.

In [13] customers arrive at rate $\lambda_{i}$ to queues
$Q_{(i)},i=1,\ldots,N$ and are given limited service from a single server. A
state can be represented as $s=(q_{1},q_{2},\ldots,q_{N},z,i)$ where the
$q_{i}$ are the respective queue sizes and $z$ is the queue currently being
served and $i$ is the number of service completions during the current visit
to queue $z$ ($0\leq i\leq k_{z}$ where $k_{z}$ is the service limit; i.e. the
maximum number of customers served per visit to queue z). If a server empties
a queue it moves on to the next nonempty queue. On page 136 of [13] there is a
description of the free chain with kernel $\overline{K}$ constructed from the
original chain with kernel $K$ by always serving the customers in queues (1)
through (N) up to the service limit even if  the queue becomes zero or
negative. The original chain would not enter these states because the server
would have just moved to the next nonempty queue. The set $\Delta\subset S$ is
the set of states where $\overline{K}\neq K$. The harmonic function used is
$h(s)=\rho^{-(q_{1}+q_{2}+\ldots+q_{N})}$ where
$\rho=\sum_{i=1}^{N}\lambda_{i}/\mu<1$. Note that $h$ is harmonic for
$\overline{K}$. The associated twisted or $h$-transformed chain makes the
twisted sum of queues $\sum_{i=1}^{N}\mathcal{Q}_{(i)}$ drift to infinity.

We note that $h$ is harmonic for $K$ at all points in $S$ including $\Delta$
except for $(0,0,\ldots,0,N,0)$. This is because $h(s)$ only depends on the
sum of the queue sizes. Consequently a transition from a state $s$
representing a service at queue $i\in\\{1,2,\ldots,N\\}$ where $q_{i}=1$
results in a decrease of $(q_{1}+q_{2}+\ldots+q_{N})$ by one regardless if the
server moves next to another queue as specified by $K$ or to a state where the
server continues serving queue $i$ even when nonempty as specified by
$\overline{K}$. $h$ is harmonic at $s$ either way. At $e=(0,0,\ldots,0,N,0)$,
$h$ is not harmonic for $K$ so $\mathcal{J}$ is not stochastic and is in fact
super-harmonic:

$\sum_{f}\overline{\mathcal{K}}(e,f)=(\sum_{i=1}^{N}\lambda_{i})\rho^{-1}+\mu\rho=1$

while

$\sum_{f}\mathcal{J}(e,f)=(\sum_{i=1}^{N}\lambda_{i})\rho^{-1}+\mu>1.$

Consequently take $E=\\{e\\}$. The proof that $H_{E}(e)<\infty$ follows
because away from $\Delta$, $\mathcal{J}=\overline{\mathcal{K}}$ and
$\sum_{i=1}^{N}\mathcal{Q}_{(i)}$ has a positive drift as in [13].

Lemma 4.1.4 in [13] follows from (47) with $f(i)=h(i)\chi_{\Delta}(i)$ and
$g(i)=B_{0}\chi_{E}(i)$ where $E$ is a finite set. The proof of (18) given in
[13] is doubtful because there is no guarantee $\sum_{i}\pi(i)V(i)<\infty$.
Moreover the hypotheses of Lemma 4.1.5 don’t say anything about $B^{\prime}$
being finite in the proof of (ii) implies (i). In spite of these problems that
are fixed with Lemma 2 and Lemma 3, the general idea is excellent and we wish
we had thought of it ourselves. We anticipate this method will find other
applications.

##  Appendix B Twisting toward a given direction

[11] and [25] showed the extremal harmonic functions on $\mathbb{Z}^{d}$ are
of the form $h(x)=\exp(\alpha\cdot x)$. We want to use these harmonic
functions to twist our random walk into the direction of a vector $\beta$. The
question is which directions $\beta$ can be achieved? In our polling example
$S_{\rho}=\\{(1,0),(-1,0),(0,1)\\}$ and $\rho$ defines probabilities
$\lambda_{1}$, $\mu$ and $\lambda_{2}$ to these points respectively. We want
to twist in all directions $\beta=(\beta_{1},\beta_{2})$ with $\beta_{2}\geq
0$:

Proposition 5.3 in [25] provides an answer but the proof is incomplete.
Theorems VII.4.3 and VII.4.4 in [18] provide a partial answer to our question.
There it is shown that for any $\beta$ in the interior of the closed convex
hull of the support $S_{\rho}$ there exists a $\theta$ such that
$\beta=\nabla\Lambda(\theta)$; i.e.

$\beta=\sum_{x}x\frac{e^{\theta\cdot x}}{\phi(\theta)}\rho(x).$

However this twist generates a factor $\phi(\theta)$ which messes up the
calculation of the probability of large deviation. We want to find a $\theta$
such that $\phi(\theta)=1$ and such that the twist drifts in direction
$\beta$.

Consider a distribution on $\mathbb{Z}^{d}$ having distribution $\rho$ which
may be substochastic. The distribution $\rho$ has support $S_{\rho}$. Recall
that the moment generating function of $\rho$ is
$\phi(\theta)=\sum_{x}e^{\theta\cdot x}\rho(x)$. As in Condition 6.2.1 (a) in
[14] we assume $\phi(\theta)<\infty$ for all $\theta$. By (a) in Lemma 6.2.3
in [14] $\phi(\theta)$ is a convex function differentiable everywhere. Define
$\Lambda(\theta)=\log(\phi(\theta))$. $\Lambda(\theta)$ is convex and
differentiable on its domain $dom(\Lambda)=R^{d}$.

We shall consider a random walk with increments having distribution $\rho$ on
the convex cone $\mathcal{C}$ with base $o$ generated by $S_{\rho}$ whre
$o=(0,\ldots,)\in R^{d}$. Hence the random walk has kernel
$\overline{K}(x,y)=\overline{K}(o,y-x)=\rho(y-x)$ on the state space
$S=\mathbb{Z}^{d}\cap\mathcal{C}$. As in our polling example $S$ may be a
strict subset of $\mathbb{Z}^{d}$. We do suppose $o$ is standard in the sense
of Dynkin [15]; i.e. $0<\overline{G}(o,y)$ for all $y\in\mathcal{C}$ where
$\overline{G}(x,y)=\sum_{k=0}^{\infty}\overline{K}^{k}(x,y)$ is the Greens
function. $\overline{G}(o,y)$ is finite when $\rho$ is substochastic or when
the mean drift $m$ is nonzero. Consider a new probability measure with support
$o\cup S_{\rho}$ where $\rho$ is scaled down by a factor $q$ and the remaining
mass $1-q$ is assigned to $o$. The new probability measure has moment
generating function $\phi_{q}(\theta)=q\phi(\theta)+1-q$ and cumulant
generating function $\Lambda_{q}(\theta)=\log(\phi_{q}(\theta)).$ Notice that
$\nabla\phi_{q}(\theta)=q\nabla\phi(\theta).$ Also notice that
$\phi_{q}(\theta)=1$ iff $\phi(\theta)=1$ iff $\Lambda_{q}(\theta)=0$ iff
$\Lambda(\theta)=0.$

Consequently if we can find $\theta^{*}$ and $\lambda^{*}$ such that such that
$\phi_{q}(\theta^{*})=1$ and $\nabla\phi_{q}(\theta^{*})=\lambda^{*}q\beta.$
Then, $\Lambda_{q}(\theta^{*})=\Lambda(\theta^{*})=0.$ Also
$\nabla\phi(\theta^{*})=\lambda^{*}\beta;$ i.e. we have found our twist for
the original kernel.

Consequently, without loss of generality we assume $o\in S_{\rho}$. We
summarize our assumptions in this Appendix

  * •

$\phi$ is finite everywhere.

  * •

Either $\rho$ is substochastic (i.e. $\rho(\mathbb{Z}^{d})<1$) or $\rho$ is
stochastic (i.e. $\rho(\mathbb{Z}^{d})=1$) and the mean
$m=\nabla\Lambda(0)\neq 0$.

  * •

$o\in S_{\rho}$.

Define $U^{d}$ to be the unit sphere. Our goal is to find a twist in any
direction $\beta\in U^{d}\cap\mathcal{C}$. The Fenchel-Legendre transformation
of $\Lambda(\theta)$ is
$\Lambda^{*}(\beta)=\sup_{\theta}(\theta\cdot\beta-\Lambda(\theta))$.
$\Lambda^{*}(\beta)$ is also convex and differentiable on its domain
$dom(\Lambda^{*})=\\{\beta:\Lambda^{*}(\beta)<\infty\\}$. Let $conv(S_{\rho})$
denote the convex hull of the set $S_{\rho}$. The relative interior of the
convex hull generated by $S_{\rho}$ is denoted by $ri(conv(S_{\rho}))$ in
[14]. By Lemma 6.2.3 (d) in [14] $ri(conv(S_{\rho}))$ is equal to the relative
interior of $dom(\Lambda^{*})$ which is denoted by $ri(dom(\Lambda^{*}))$;
i.e. $ri(conv(S_{\rho}))=ri(dom(\Lambda^{*}))$. For any $\alpha\in
ri(conv(S_{\rho}))=ri(dom(\Lambda^{*}))$, Lemma 6.2.3 in [14] shows,
$\Lambda^{*}(\alpha)$ is attained at a point $\theta\in\mathcal{D}_{\Lambda}$
such that $\alpha=\nabla\Lambda(\theta)$.

######  Theorem 9.

Pick a direction $\beta\in U^{d}$ in the relative interior of $\mathcal{C}$.
Then there exists a unique $\lambda^{*}>0$, a unique $\theta^{*}$ such that
$\phi(\theta^{*})=1$ and an exponential change of measure such that

$\displaystyle\beta=\frac{1}{\lambda^{*}}\nabla\phi(\theta^{*})=\frac{1}{\lambda^{*}}\sum
xe^{\theta^{*}\cdot x}\rho(x).$ (48)

Moreover the map $\beta\to\overline{K}^{\theta^{*}}$ is one-to-one and
continuous on the interior of $U^{d}\cap\mathcal{C}$. This means
$\overline{K}^{\theta^{*}}$, the $h^{\theta^{*}}$-transform of the kernel
$\overline{K}$ with respect to $h^{\theta^{*}}(x)=\exp(\theta^{*}\cdot x)$ has
a mean drift in the direction $\beta$.

###### Proof.

Consider the function $g(\lambda)=\Lambda^{*}(\lambda\beta)/\lambda$. There
must exist some $\gamma$ such that $\gamma\beta$ is the interior of
$conv(S_{\rho})$, the convex cone generated by $S_{\rho}$ so
$g(\gamma)<\infty$. By the convexity of $\Lambda^{*}$ and the fact that $o\in
S_{\rho}$, the domain of $g$; i.e. $\\{\lambda:g(\lambda)<\infty\\}$ is an
interval $(0<\overline{\lambda})$ containing $\gamma$.

Suppose $\overline{\lambda}=+\infty$. Then
$g(\lambda)\geq\theta\cdot\beta-\Lambda(\theta)/\lambda$ for all $\theta$.
Take $\theta=t\beta$ where $t>0$ so $g(\lambda)\geq
t|\beta|^{2}-\Lambda(t\beta)/\lambda$. Let $\lambda\to\infty$ so
$\liminf_{\lambda\to\infty}g(\lambda)\geq t|\beta|^{2}$ where $t$ is
arbitrarily large. It follows that
$\liminf_{\lambda\to\infty}g(\lambda)=\infty$. Consequently if
$\overline{\lambda}=+\infty$ then
$\liminf_{\lambda\to\infty}g(\lambda)=\infty$.

On the other hand if $\overline{\lambda}<+\infty$ then either
$\Lambda^{*}(\overline{\lambda}\beta)=\infty$ in which case
$g(\overline{\lambda})=\infty$ or
$\Lambda^{*}(\overline{\lambda}\beta)<\infty$. In this case

$\displaystyle\lim_{\lambda\uparrow\overline{\lambda}}g^{\prime}(\lambda)$
$\displaystyle=$
$\displaystyle\lim_{\lambda\uparrow\overline{\lambda}}\left(\frac{\lambda\frac{d\Lambda^{*}(\lambda\beta)}{d\lambda}-\Lambda^{*}(\lambda\beta)}{\lambda^{2}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{\overline{\lambda}^{2}}\left(\overline{\lambda}\lim_{\lambda\uparrow\overline{\lambda}}\frac{d\Lambda^{*}(\lambda\beta)}{d\lambda}-\Lambda^{*}(\overline{\lambda}\beta)\right)$
$\displaystyle=$ $\displaystyle\infty$

because $\frac{d\Lambda^{*}(\lambda\beta)}{d\lambda}\to+\infty$ as
$\lambda\uparrow\overline{\lambda}$ since $\Lambda^{*}$ is steep at the
boundary (see Theorem 1 in [33] which shows $\Lambda^{*}$ is steep or
essentially smooth because $\Lambda$ is). Hence $g^{\prime}(\lambda)\to\infty$
as $\lambda\uparrow\overline{\lambda}$ when $\overline{\lambda}<\infty$.

The other boundary of the domain of $g(\lambda)$ is at $\lambda=0$. As above
$g(\lambda)\geq\theta\cdot\beta-\Lambda(\theta)/\lambda$. Pick $\theta$ such
that $\Lambda(\theta)<0$. This is certainly possible in the substochastic case
because $\Lambda(0)<0$. In the stochastic case when $\nabla\Lambda(0)=m\neq
0$, $\Lambda(\theta)<0$ if we pick $\theta$ close to zero in the direction
$-m$. Hence $-\Lambda(\theta)/\lambda\to+\infty$ as $\lambda\downarrow 0$.
Hence, $g(\lambda)\to\infty$ as $\lambda\to 0$.

We have proven $g(\lambda)\to\infty$ as $\lambda\to\overline{\lambda}=\infty$
or $\lambda\to 0$ so $g$ can’t have a minimum at endpoints like this. If
$\overline{\lambda}<\infty$ then either
$\lim_{\lambda\uparrow\overline{\lambda}}g(\lambda)\to\infty$ or
$\lim_{\lambda\uparrow\overline{\lambda}}g^{\prime}(\lambda)=\infty$. Either
way it follows that there exist a $\lambda^{*}$ such that
$g^{\prime}(\lambda^{*})=0$ where $0<\lambda^{*}<\overline{\lambda}$.

Consequently $inf_{\lambda>0}\Lambda^{*}(\lambda\beta)/\lambda$ is finite and
is achieved at $\lambda^{*}$. At this value

$\displaystyle\frac{d}{d\lambda}\left(\frac{\Lambda^{*}(\lambda\beta)}{\lambda}\right)|_{\lambda=\lambda^{*}}=\frac{\lambda^{*}\nabla\Lambda^{*}(\lambda^{*}\beta)\cdot\beta-\Lambda^{*}(\lambda^{*}\beta)}{\lambda^{2}}=0.$

So

$\displaystyle\lambda^{*}\nabla\Lambda^{*}(\lambda^{*}\beta)\cdot\beta-\Lambda^{*}(\lambda^{*}\beta)=0.$
(49)

Next,

$\displaystyle\Lambda^{*}(\lambda^{*}\beta)=\theta^{*}\cdot\lambda^{*}\beta-\Lambda(\theta^{*})\mbox{
where }$ (50)
$\displaystyle\lambda^{*}\beta=\nabla\Lambda(\theta^{*})=\sum\frac{xe^{\theta^{*}\cdot
x}}{\phi(\theta^{*})}\rho(x).$ (51)

Since $\Lambda$ is convex and differentiable it follows that
$\Lambda^{**}=\Lambda$ by D2.6 in [18] or [34]. Hence
$\Lambda(\theta^{*})=\sup_{v}(v\cdot\theta^{*}-\Lambda^{*}(v))$ where the sup
is attained at $v^{*}$ where $\theta^{*}=\nabla\Lambda^{*}(v^{*})$. On the
other hand, by (50),
$\Lambda(\theta^{*})=\theta^{*}\cdot\lambda^{*}\beta-\Lambda^{*}(\lambda^{*}\beta)$
so the supremum is attained at $v^{*}=\lambda^{*}\beta$ and hence
$\theta^{*}=\nabla\Lambda^{*}(\lambda^{*}\beta)$.

Next,

$\displaystyle\Lambda(\theta^{*})$ $\displaystyle=$
$\displaystyle\lambda^{*}\beta\cdot\nabla\Lambda^{*}(\lambda^{*}\beta)-\Lambda^{*}(\lambda^{*}\beta)$
$\displaystyle=$ $\displaystyle 0\mbox{ by (\ref{xx}),}$

i.e. $\phi(\theta^{*})=1$. Now (48) follows from (51).

The uniqueness of $\theta^{*}$ follows from the convexity of the level curve
$\Lambda(\theta)=0$ since there is only one point $\theta^{*}$ such that
$\nabla\Lambda(\theta^{*})$ points in direction $\beta$. This fixes
$\lambda^{*}$ since $\lambda^{*}\beta=\nabla\Lambda(\theta^{*})$.

The map of $\beta\to\lambda^{*}$ defined by (49) is differentiable on the
interior of $U^{d}\cap\mathcal{C}$. Hence the map of

$\beta\to\lambda^{*}\beta\to\theta^{*}\to
h^{\theta^{*}}\to\overline{K}^{\theta^{*}}$

given by (48) is differentiable on the interior of $U^{d}\cap\mathcal{C}$. ∎

######  Remark 2.

$\overline{G}(x,y)=\overline{G}^{\theta^{*}}(x,d)e^{-\theta^{*}\cdot(y-x)}$
and $\overline{G}(0,y)=\overline{G}^{\theta^{*}}(0,y)e^{-\theta^{*}\cdot y}$
so

$k(x,y)=\frac{\overline{G}(x,y)}{\overline{G}(0,y)}=\frac{\overline{G}^{\theta^{*}}(x,y)}{\overline{G}^{\theta^{*}}(0,y)}e^{\theta^{*}\cdot
x}=k^{\theta^{*}}(x,y_{n})e^{\theta^{*}\cdot x}.$

Pick a sequence of $y_{\ell}$ such that $|y_{n}|\to\infty$ in direction
$\beta$. Corollary 1.3 in [32] shows $k^{\theta^{*}}(x,y_{\ell})\to 1$ so
$k(x,y_{\ell})\to e^{\theta^{*}\cdot x}$ (This is a statement about the
smoothness of $\overline{G}^{\theta^{*}}(0,y)$ and irreducibility on
$\mathbb{Z}^{d}$ is unnecessary). Hence the direction
$\beta=\lambda^{*}\nabla\Lambda(\theta^{*})$ corresponds to a point on the
Martin boundary associated with the extremal harmonic function
$e^{\theta^{*}\cdot x}$.

It may be the case that the support of $S_{\rho}$ before adding $o$ is
contained in a hyperplane in $R^{n}$. A simple example would be
$S_{\rho}=\\{(1,0),(0,1)\\}$ with arbitrary weights. Nevertheless Theorem 9
applies. Moreover in such a case $\lambda^{*}\beta$ must lie in this
hyperplane because

$\lambda^{*}\beta=\nabla\phi(\theta^{*})=\sum xe^{\theta^{*}\cdot x}\rho(x);$
(52)

i.e. $\lambda^{*}\beta$ is a convex combination of the vectors in the support
of $\rho$, which means that $\lambda^{*}\beta$ lies in the hyperplane.

Now let $\overline{\rho}$ be a countable probability measure on a discrete
lattice in $R^{n+m}$. Suppose the convex cone $\overline{\mathcal{C}}$ with
base $o\in R^{n+m}$ generated by $S_{\overline{\rho}}$. is an affine space in
$R^{n+m}$ of the form

$\displaystyle\overline{S}$ $\displaystyle=$
$\displaystyle\\{(x_{1},\ldots,x_{n},y_{1},\ldots y_{m}):\mbox{ where
}(x_{1},\ldots,x_{n})\in R^{n};$ $\displaystyle\mbox{ and
}y_{k}=L_{k}(x_{1},\ldots,x_{n}),k=1,\ldots,m\\}$

where $L_{k}$ are linear functions of $(x_{1},\ldots,x_{n})$ for
$k=1,\ldots,m$. Letting $x=(x_{1},\ldots,x_{n})^{T}$ and

$y=(L_{1}(x_{1},\ldots,x_{n}),\ldots,L_{m}(x_{1},\ldots,x_{n}))^{T}=Lx$

we can express the coordinates of points in the support of $\overline{\rho}$
by $(x,Lx)$. The moment generating function can be written

$\phi_{\overline{\rho}}(\theta,\alpha)=\sum_{x}\exp(\theta\cdot x+\alpha\cdot
Lx)\overline{\rho}(x,Lx).$

Suppose $\overline{\beta}$ is a given direction in the relative interior of
$\overline{\mathcal{C}}$. Consequently $\overline{\beta}=(\beta,L\beta)$ where
$\beta$ is in the relative interior of the cone $\mathcal{C}$ with base $o\in
R^{n}$ generated by the projection of the point masses from $R^{n+m}$ to
$R^{n}$. Denote the projected point mass by $\rho$; i.e.
$\rho(x)=\overline{\rho}(x,Lx)$. By Theorem 48 there exists a unique
$\lambda^{*}>0$ in $R^{n}$ and a unique $\theta^{*}$ in $R^{n}$ such that
$\phi_{\rho}(\theta^{*})=1$ and an exponential change of measure such that

$\displaystyle\beta=\frac{1}{\lambda^{*}}\nabla\phi_{\rho}(\theta^{*})=\frac{1}{\lambda^{*}}\sum
xe^{\theta^{*}\cdot x}\rho(x).$ (53)

Moreover

$\nabla\phi_{\overline{\rho}}(\theta,\alpha)=\sum_{(x,y)}(x,Lx)\exp(\theta\cdot
x+\alpha\cdot Lx)\overline{\rho}(x,Lx)$

and evaluating at $\theta=\theta^{*}$ and $\alpha=0$ we get

$\displaystyle\nabla\phi_{\overline{\rho}}(\theta^{*},0)$ $\displaystyle=$
$\displaystyle\sum_{(x,Lx)}(x,Lx)\exp(\theta^{*}\cdot x)\rho(x)$
$\displaystyle=$
$\displaystyle(\lambda^{*}\beta,L(\lambda^{*}\beta))=\lambda^{*}(\beta,L\beta).$

We therefore have an exponential change of measure to point the mean in
direction $(\beta,L\beta)$.

We now address the issue of a direction $\beta\in U^{d}$ on the boundary of