††institutetext: Centre for Theoretical Physics, Department of Physics and
Astronomy,
Queen Mary University of London, E1 4NS, United Kingdom

#  No U(1) ‘electric-magnetic’ duality in Einstein gravity

Ricardo Monteiro<EMAIL_ADDRESS>
###### Abstract

We revisit the question of whether classical general relativity obeys, beyond
the linearised order, an analogue of the global U(1) electric-magnetic duality
of Maxwell theory, with the Riemann tensor playing the role analogous to the
field strength. Following contradictory claims in the literature, we present a
simple gauge-invariant argument that the duality does not hold. The duality
condition is the conservation of the helicity charge. Scattering amplitudes of
gravitons in general relativity, and of gluons in Yang-Mills theory, violate
this selection rule already at tree level. Indeed, the maximally-helicity-
violating (MHV) amplitudes are famous for their simplicity. The duality in the
linearised theories is, therefore, broken by the interactions. In contrast,
the tree-level scattering amplitudes in duality-invariant theories of non-
linear electromagnetism are known to obey helicity conservation. While the
duality is not a symmetry of the full theory of general relativity, it does
hold within a sector of the solution space, including vacuum type D solutions,
where the duality is known to rotate between mass and NUT charge.

QMUL-PH-23-24

##  1 Introduction

The electric-magnetic duality of electromagnetism has long been a source of
inspiration for theoretical developments. Here, we are interested in
investigating the extension of the U(1) duality to other theories.111We will
not discuss the related weak coupling / strong coupling duality, which is
famous in the context of supersymmetric non-Abelian theories Montonen:1977sn ;
Seiberg:1994pq . The duality is known to extend to a class of theories of non-
linear electromagnetism identified in Gaillard:1981rj . In general relativity,
a version of the duality where the Riemann tensor plays the role analogous to
the field strength is known to hold at linearised level; see e.g.
Penrose:1960eq ; Nieto:1999pn ; Hull:2001iu ; Henneaux:2004jw ; Deser:2005sz ;
Bunster:2006rt ; Argurio:2009xr ; Barnich:2008ts . However, ref. Deser:2005sz
reported that the first non-linear correction, i.e. the cubic vertex, does not
admit a duality-invariant formulation, similarly to the case of Yang-Mills
theory Deser:1976iy . The procedure employed was not covariant, and we will
see that, at least in our approach, the cubic vertex is subtle regarding the
duality. It has since been suggested in various instances, in writing or not,
that perhaps a non-linear realisation of the gravitational duality is
possible. In fact, there is a recent claim that this is the case Kol:2022bsd ;
Kol:2023yxd , partly motivated by — but not implied by — developments in
scattering amplitudes Luna:2015paa ; Huang:2019cja ; Alawadhi:2019urr ;
Banerjee:2019saj ; Emond:2020lwi ; Moynihan:2020gxj ; Monteiro:2020plf ;
Crawley:2021auj ; Monteiro:2021ztt .

In this paper, we show that the duality does not hold in the full theory of
general relativity, but explain also why it holds within a certain sector of
solutions to the vacuum Einstein equations, which includes type D vacuum
solutions. Indeed, it is well known that the Kerr-Taub-NUT family of solutions
admits the U(1) duality, rotating between mass and NUT charge. This is an
analogue of the rotation between electric charge and magnetic monopole charge
in electromagnetism.

The understanding of the duality that we employ builds on work that goes a
long way back, to the realisation that the duality’s Noether symmetry is
helicity conservation Calkin:1965 . This can be seen as the invariance of an
action for the positive and negative helicity degrees of freedom of the gauge
boson under chiral U(1) transformations. Helicity conservation is expressed in
a gauge-invariant manner as a selection rule on the scattering amplitudes: the
only admissible non-trivial amplitudes have an equal number of positive and
negative helicity external particles (in a convention where all particles are
incoming, say). The scattering amplitudes of gravitons in Einstein’s theory,
or of gluons in Yang-Mills theory, famously violate this rule. Indeed, the
simplest and best known tree-level amplitudes in these theories are classified
as MHV — maximally-helicity-violating amplitudes. On the other hand, it was
shown in Novotny:2018iph  that all duality-invariant theories of non-linear
electrodynamics satisfy the selection rule, generalising an earlier
observation in Born-Infeld theory Rosly:2002jt . Analogous results have been
obtained in extended supergravities, for the duality acting on a class of
spin-1 particles in the theory (and a quantum anomaly occurs which impacts the
ultraviolet behaviour), as well as in related contexts Carrasco:2013ypa ;
Bern:2013uka ; Freedman:2017zgq ; Bern:2017rjw ; Pavao:2022kog ;
Carrasco:2022jxn ; Carrasco:2023qgz . Our discussion includes a
straightforward explanation of this correspondence between the U(1) duality
and the amplitudes selection rule.

The paper is organised as follows. In section 2, we review the original
duality in Maxwell theory, and the associated conservation of helicity. In
section 3, we discuss the extension of the duality to non-linear
electromagnetism, and its manifestation in terms of a selection rule on the
scattering amplitudes. In section 4, we present the general argument for the
selection rule as the condition for the duality to hold. In sections 5 and 6,
we describe the failure of the duality in Yang-Mills theory and in general
relativity, respectively. In section 7, we discuss a class of algebraically
special gravity solutions where the duality holds, manifesting itself as a
symmetry that rotates between mass and NUT charge. We conclude with brief
remarks in section 8.

##  2 Maxwell theory

The U(1) electric-magnetic duality of Maxwell theory is the statement that the
transformation

$\displaystyle\begin{pmatrix}F_{\mu\nu}\\\ \ast
F_{\mu\nu}\end{pmatrix}\mapsto\begin{pmatrix}F^{\prime}_{\mu\nu}\\\ \ast
F^{\prime}_{\mu\nu}\end{pmatrix}=\begin{pmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{pmatrix}\begin{pmatrix}F_{\mu\nu}\\\ \ast
F_{\mu\nu}\end{pmatrix}$ (1)

preserves the Maxwell equations,

$\displaystyle d\\!\ast\\!F=0\,,\quad dF=0\,.$ (2)

Here, $\ast$ denotes the Hodge dual, such that $\ast
F_{\mu\nu}=\frac{1}{2}\varepsilon_{\mu\nu\alpha\beta}F^{\alpha\beta}$. In
Lorentzian signature, $\ast^{2}=-1$. The chiral nature of the transformation
is clear when we express it in terms of the (anti-)self-dual parts of the
field strength,222This convention will mean that, in later sections, we will
see $F_{+}\sim e-ig$ for the dyon field strength, and $\psi\sim m-in$ for the
Taub-NUT Weyl spinor.

$\displaystyle F_{\pm}=\frac{1}{2}(F\mp i\ast F)\quad\Leftrightarrow\quad\ast
F_{\pm}=\pm iF_{\pm}\,,$ (3)

for which the transformation is

$\displaystyle F_{\pm}\mapsto e^{\pm i\theta}F_{\pm}.$ (4)

In our convention, a self-dual field has positive helicity, and an anti-self-
dual field has negative helicity.

This U(1) transformation is a symmetry of the equations of motion, though not
of the usual action:

$\displaystyle S[A_{\mu}]=-\frac{1}{4}\int
d^{4}x\,F^{\mu\nu}F_{\mu\nu}\;\mapsto\;\cos(2\theta)\,S[A_{\mu}]\,,$ (5)

where we dropped a boundary term. We can easily write an action that makes the
duality manifest in terms of the chiral transformation (4), by using light-
cone gauge. Let us consider double-null coordinates, such that

$\displaystyle
ds^{2}=2(-dudv+dwd{\bar{w}})\,,\quad\square=2(-\partial_{u}\partial_{v}+\partial_{w}\partial_{\bar{w}})\,.$
(6)

Choosing the light-cone gauge condition $A_{u}=0$, we obtain the action

$\displaystyle S[A_{v},A_{w},A_{\bar{w}}]=\int
d^{4}x\,\left(\,\frac{1}{2}\,(\partial_{u}A_{v}-\partial_{\bar{w}}A_{w}-\partial_{w}A_{\bar{w}})^{2}+A_{w}\square
A_{\bar{w}}\right)\,.$ (7)

The component $A_{v}$ can be integrated out exactly, leading to an action for
the two physical degrees of freedom. These are identified with the positive
and negative helicity fields, which in our convention are

$\displaystyle A_{+}=A_{\bar{w}}\,,\quad A_{-}=A_{w}\,.$ (8)

Hence, we obtain the action

$\displaystyle S[A_{\pm}]=\int d^{4}x\,A_{-}\,\square\,A_{+}\,,$ (9)

which is clearly invariant under the chiral transformation

$\displaystyle A_{\pm}\mapsto e^{\pm i\theta}A_{\pm}\,.$ (10)

The associated Noether current is

$\displaystyle
j^{\mu}=i(A_{+}\partial^{\mu}A_{-}-A_{-}\partial^{\mu}A_{+})\,,$ (11)

and the conserved charge is

$\displaystyle{\mathcal{H}}=i\int
d^{3}x\,(A_{+}\partial_{t}A_{-}-A_{-}\partial_{t}A_{+})\,.$ (12)

To interpret this chiral symmetry, we can use the second quantisation
formalism, where we take $A_{\pm}$ to be operators built with creation and
annihilation operators in Fourier space. This leads after normal ordering to

$\displaystyle\mathcal{H}=\int\frac{d^{3}k}{(2\pi^{3})2|\vec{k}|}\,(a^{\dagger}_{+,k}\,a_{+,k}-a^{\dagger}_{-,k}\,a_{-,k})=N_{+}-N_{-}\,.$
(13)

Here, $a_{\pm,k}$ annihilate a photon of helicity $\pm$ and momentum
$k_{\mu}$, while $N_{\pm}$ are the particle number operators for the given
helicity. So the U(1) symmetry implies the conservation of the total helicity.
To our knowledge, this observation was first made in a clear manner in ref.
Calkin:1965 . The story is analogous to that of the chiral symmetry of
massless fermions. In fact, the analogy extends to quantum effects: ref.
Agullo:2016lkj  has shown that the symmetry is anomalous on a curved
background, such that $\langle\nabla_{\mu}j^{\mu}\rangle\sim
R_{\mu\nu\alpha\beta}\ast\\!\\!R^{\mu\nu\alpha\beta}$, similarly to the
fermionic chiral anomaly.

##  3 Non-linear electrodynamics

Let us consider now non-linear extensions of electromagnetism, where the
Lagrangian density is a function of the field strength,

$\displaystyle{\mathcal{L}}(F)=-\frac{1}{4}\,F^{\mu\nu}F_{\mu\nu}+{\mathcal{O}}(F^{4})\,.$
(14)

If the interactions in ${\mathcal{O}}(F^{4})$ are to preserve the symmetry
under $A_{\pm}\mapsto e^{\pm i\theta}A_{\pm}$, they must take the following
schematic form in the action for the two degrees of freedom:

$\displaystyle S[A_{\pm}]=\int
d^{4}x\,\Big{(}\,A_{-}\,\square\,A_{+}+\sum_{n\geq
2}\,\frac{1}{M^{4(n-1)}}\,\partial^{2n}A_{-}^{n}A_{+}^{n}\,\Big{)}\,,$ (15)

where $M$ has units of mass.333When we schematically write $\partial^{2n}$ in
(15), this includes the possibility of $\partial^{2n+m}/\partial^{m}_{u}$,
where $u$ is the light-cone coordinate associated to the gauge choice. As we
will see later in the well-known cases of Yang-Mills and gravity, the
appearance of the integral operation $1/\partial_{u}$ is typical of
interactions in light-cone gauge actions. This presents no difficulties when
considering perturbation theory in Fourier space. In the Feynman diagrams
obtained from such an action, helicity is manifestly conserved at each vertex.
Putting the action into this form, however, may require non-trivial field
redefinitions on top of the gauge choice. The invariant statement is that the
scattering amplitudes (with all external particles taken to be, say, incoming)
must obey the selection rule

$\displaystyle\boxed{\;{\mathcal{A}}(n_{+},n_{-})=0\quad\text{for}\quad
n_{+}\neq n_{-}\;}\,,$ (16)

where $n_{\pm}$ are the number of $\pm$ helicity external particles. That is,
the amplitudes with unequal number of positive and negative helicity external
particles must vanish. Conversely, if the amplitudes satisfy this selection
rule, then using the explicit form of the non-vanishing amplitudes we can in
principle construct an action of the form (15).

Theories of non-linear electromagnetism that admit the electric-magnetic
duality are identified by the Noether-Gaillard-Zumino condition
Gaillard:1981rj :

$\displaystyle
G_{\mu\nu}\ast\\!G^{\mu\nu}=F_{\mu\nu}\ast\\!F^{\mu\nu}\,,\quad\text{with}\quad
G_{\mu\nu}=-2\frac{\partial{\mathcal{L}}}{\partial F^{\mu\nu}}\,.$ (17)

The duality acts as

$\displaystyle\begin{pmatrix}G_{\mu\nu}\\\ \ast
F_{\mu\nu}\end{pmatrix}\mapsto\begin{pmatrix}G^{\prime}_{\mu\nu}\\\ \ast
F^{\prime}_{\mu\nu}\end{pmatrix}=\begin{pmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{pmatrix}\begin{pmatrix}G_{\mu\nu}\\\ \ast
F_{\mu\nu}\end{pmatrix}\,,$ (18)

preserving the equation of motion, $d\\!\ast\\!G=0$ , and the Bianchi
identity, $dF=0$ . Ref. Novotny:2018iph  has shown that the theories of non-
linear electromagnetism admitting the electric-magnetic duality satisfy
helicity conservation at tree level, that is, obey the selection rule
(16).444The Born-Infeld theory is an example of a non-linear electromagnetism
model satisfying the duality condition and, indeed, its tree-level amplitudes
satisfy the selection rule, which was first determined in Rosly:2002jt . Using
unitarity methods, ref. Elvang:2019twd  reported the existence of helicity-
violating amplitudes at one loop; see also Wen:2020qrj ; Elvang:2020kuj . From
the point of view of the action (15), this loop-level U(1) violation
presumably arises from the fact that the field redefinitions required to put
the action into this form affect the measure of the path integral.

##  4 The general argument

The empirical fact that scattering amplitudes in duality-satisfying theories
of non-linear electrodynamics obey the selection rule (16) admits a simple
explanation. In fact, the selection rule is the condition for ‘electric-
magnetic’ duality in a broader range of theories with massless particles.

An obvious difficulty in theories like Yang-Mills or gravity is that, beyond
the linearised level (where the duality is straightforward, as we will review
shortly), it is unclear how to implement the U(1) transformation. This is why
the perspective of scattering amplitudes is helpful: if it is clear how to
implement the transformation at linearised level, then it is clear how it acts
on the asymptotic scattering states, i.e. the initial and final particles in
the amplitude. The U(1) transformation with parameter $\theta$ is implemented
via a unitary operator, $e^{i\theta{\mathcal{H}}}$; we saw that, for photons,
this operator is $e^{i\theta(N_{+}-N_{-})}$. Now, the S-matrix contains all
the information about the time evolution. While we do not know the S-matrix of
quantum gravity, we know in principle all the information required for
classical gravity. The duality is equivalent to the invariance of S-matrix
elements under the duality:

$\displaystyle\langle\text{out}_{\theta}|S|\text{in}_{\theta}\rangle=\langle\text{out}|e^{-i\theta{\mathcal{H}}}Se^{i\theta{\mathcal{H}}}|\text{in}\rangle=\langle\text{out}|S|\text{in}\rangle\,.$
(19)

That is, the operator ${\mathcal{H}}$ commutes with the scattering operator
$S$.

For now, let us consider only one massless particle species, say the
scattering of photons in non-linear electromagnetism, of gluons in Yang-Mills
theory, or of gravitons in general relativity. For these, the U(1) operator is
based on the helicity charge,
$e^{i\theta{\mathcal{H}}}=e^{i\theta(N_{+}-N_{-})}$.555Since ${\mathcal{H}}$
represents the helicity charge, one may instead wish to normalise it such that
$e^{i\theta{\mathcal{H}}}=e^{i\theta s(N_{+}-N_{-})}$, where $s$ is the spin
of the particle, e.g. $s=2$ for gravitons. We will not do this, as it won’t
affect the subsequent discussion. One may absorb $s$ into the duality
parameter $\theta$. Clearly, it is easier to look at amplitudes for initial
and final particles that have definite positive or negative helicity. Now, in
the scattering amplitudes literature, making use of crossing symmetry,
external particles are often taken as being all incoming (or outgoing).666A
massless particle that has helicity $\pm$ seen as incoming, has helicity $\mp$
seen as outgoing. The amplitude is then defined as

$\displaystyle{\mathcal{A}}=\langle
0|T|\text{in}\rangle\,,\quad\text{with}\quad S=1+iT\,.$ (20)

Under the U(1) transformation, we have

$\displaystyle{\mathcal{A}}_{\theta}=\langle
0|T|\text{in}_{\theta}\rangle=\langle
0|Te^{i\theta(N_{+}-N_{-})}|\text{in}\rangle=e^{i\theta(n_{+}-n_{-})}\langle
0|T|\text{in}\rangle=e^{i\theta(n_{+}-n_{-})}{\mathcal{A}}\,,$ (21)

where $n_{\pm}$ are the number of $\pm$ helicity particles in the asymptotic
state $|\text{in}\rangle$. The duality is the statement that the amplitudes
are invariant under U(1). This is, therefore, equivalent to the selection rule
(16) seen previously.

The argument applies more generally. For instance, in Einstein-Maxwell theory,
the electric-magnetic duality holds (classically) as a U(1) symmetry acting on
the gauge field. The selection rule (16) then applies to tree amplitudes for
photons in this theory, which comes out naturally from the formulas in
Cachazo:2014xea ; see also Bern:1999bx ; Chiodaroli:2014xia  for related work.
This should extend to duality-preserving higher-derivative extensions of
Einstein-Maxwell theory, as those studied in Cano:2021tfs .

Another natural setting is to consider the coupling to massive particles, and
the duality is still the statement that the amplitudes are U(1) invariant. In
the Maxwell case, we can introduce dyonic particles, with electric charge $e$
and magnetic monopole charge $g$. The gauge field generated by a static dyon
is

$\displaystyle F=dA=\frac{e}{r^{2}}\,dt\wedge
dr-\frac{g}{r^{2}}\,\ast(dt\wedge dr)\,.$ (22)

By considering the action of U(1) on $F$, we can determine the U(1)
transformation of the charges:

$\displaystyle F_{+}\,\mapsto\,e^{i\theta}F_{+}\quad\Rightarrow\quad
e-ig\,\mapsto\,e^{i\theta}(e-ig)=e^{\prime}-ig^{\prime}\,.$ (23)

Now, the 3-point amplitude for a dyon to absorb a $\pm$ helicity photon is
Huang:2019cja

$\displaystyle{\mathcal{A}}=(e\pm ig)\;\varepsilon_{\pm}\cdot p\,,$ (24)

where $p$ is the momentum of the dyon (say before the interaction), and
$\varepsilon_{\pm}$ is the polarisation vector of the $\pm$ helicity incoming
photon.777While 3-point on-shell kinematics requires complexified momenta in
Lorentzian signature, 3-point amplitudes have proven extremely useful, e.g.
for constructing higher-point or even higher-loop amplitudes via recursion
Britto:2005fq ; Arkani-Hamed:2012zlh  and unitarity methods Bern:2011qt . In
the case of dyons, higher-point amplitudes are poorly understood due to the
well-known difficulties with magnetic monopoles; see Csaki:2020inw  for some
recent progress. Regarding (24) and (22), it was shown in Monteiro:2020plf ;
Crawley:2021auj ; Monteiro:2021ztt , based on the KMOC formalism
Kosower:2018adc , how they are related via an on-shell Fourier transform.
Notice the dyon couples differently to the two helicities of the photon. This
amplitude is invariant under U(1), because the phases cancel between the
coupling and the photon. In gravity, there is an analogue of the
electromagnetic dyon, as we will review later, where the mass and the NUT
charge play roles analogous to the electric and magnetic monopole charges.
This will not imply, however, that the full interacting theory is duality
invariant. In fact, neither the 3-point amplitude (24) nor its gravitational
analogue probe interactions between the massless gauge bosons, which are
absent in the case of electromagnetism.

To conclude this section, notice that if we demand only the ${\mathbb{Z}}_{2}$
electric-magnetic duality, $F\mapsto\ast F$, which corresponds to
$\theta=\pi/2$ , then the selection rule (16) is too strong. From (21), we see
that the requirement $n_{+}=n_{-}$ is substituted by
$(n_{+}-n_{-})/4\in{\mathbb{Z}}$. This weaker requirement will not alter the
failure of the duality in Yang-Mills theory and in gravity, which we will
discuss in the following sections.

##  5 Yang-Mills theory

At linearised level, it is clear that Yang-Mills theory obeys the duality,
because Maxwell theory does. At non-linear level, our argument implies that
the duality fails, because the scattering amplitudes do not obey the selection
rule of helicity conservation. In fact, there is a famous class of tree-level
amplitudes presenting maximal helicity violation (MHV), where all external
gluons have positive helicity except for two. It admits a very simple formula
at $n$ points Parke:1986gb : in spinor-helicity language,

$\displaystyle{\mathcal{A}}(i^{-},j^{-},\text{rest}^{+})=g^{n-2}\,\langle
ij\rangle^{4}\left(\frac{\text{Tr}(T^{a_{1}}T^{a_{2}}T^{a_{3}}\cdots
T^{a_{n}})}{\langle 12\rangle\langle 23\rangle\cdots\langle
n1\rangle}+\text{perm}\right)\,,$ (25)

where ‘perm’ denotes a sum over non-cyclic permutations of the $n$ external
legs. Obviously, there is a conjugate $\overline{\text{MHV}}$ class of
amplitudes, as the theory is parity invariant. Tree amplitudes with all or
(except for 3 points) all-but-one particles of the same helicity vanish, hence
the name MHV for the all-but-two class above.

If we write down the light-cone gauge action Chalmers:1998jb

$\displaystyle S[A_{\pm}]=\int d^{4}x\,\text{Tr}\Bigg{(}$ $\displaystyle
A_{-}\square
A_{+}+2g\Big{(}\frac{\partial_{w}}{\partial_{u}}A_{+}\Big{)}i[\partial_{u}A_{-},A_{+}]+2g\Big{(}\frac{\partial_{\bar{w}}}{\partial_{u}}A_{-}\Big{)}i[\partial_{u}A_{+},A_{-}]$
$\displaystyle-2g^{2}[\partial_{u}A_{-},A_{+}]\frac{1}{\partial_{u}^{2}}[\partial_{u}A_{+},A_{-}]\Bigg{)}\,,$
(26)

we see that it is not invariant under $A_{\pm}\mapsto e^{\pm
i\theta}A_{\pm}$.888As already mentioned, the apparent non-locality here is a
feature of light-cone gauge. This, on top of the lack of manifest Lorentz
invariance, is the price to pay for reducing to two physical off-shell degrees
of freedom. Field redefinitions cannot help, due to the invariant statement
that amplitudes such as (25) violate the duality selection rule. In fact, the
existence of non-vanishing amplitudes for an odd number of particles already
invalidates the duality.

##  6 Gravity

The ‘electric-magnetic’ duality in linearised gravity works similarly to the
case of Maxwell theory; see e.g. Henneaux:2004jw . The Riemann tensor plays
the role analogous to the field strength. The linearised Riemann tensor is

$\displaystyle
R_{\mu\nu\lambda\rho}=\frac{1}{2}\left(\partial_{\mu}\partial_{\rho}h_{\lambda\nu}-\partial_{\nu}\partial_{\rho}h_{\lambda\mu}-\partial_{\mu}\partial_{\lambda}h_{\rho\nu}+\partial_{\nu}\partial_{\lambda}h_{\rho\mu}\right),$
(27)

and its Hodge dual is

$\displaystyle\ast
R_{\mu\nu\lambda\rho}=\frac{1}{2}\,\varepsilon_{\mu\nu\alpha\beta}\,R^{\alpha\beta}{}_{\lambda\rho}\,.$
(28)

The equation of motion is the vacuum Einstein equation,

$\displaystyle R^{\lambda}{}_{\mu\lambda\nu}=0\,,$ (29)

while the first (algebraic) and second (differential) Bianchi identities are,
respectively,

$\displaystyle
R_{\mu[\nu\lambda\rho]}=0\,,\qquad\partial_{[\mu}R_{\nu\lambda]\rho\alpha}=0\,.$
(30)

The duality is the invariance of the equation of motion and the Bianchi
identities under

$\displaystyle\begin{pmatrix}R_{\mu\nu\lambda\rho}\\\ \ast
R_{\mu\nu\lambda\rho}\end{pmatrix}\mapsto\begin{pmatrix}R^{\prime}_{\mu\nu\lambda\rho}\\\
\ast
R^{\prime}_{\mu\nu\lambda\rho}\end{pmatrix}=\begin{pmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{pmatrix}\begin{pmatrix}R_{\mu\nu\lambda\rho}\\\
\ast R_{\mu\nu\lambda\rho}\end{pmatrix}\,.$ (31)

In terms of the (anti-)self-dual parts of the curvature,

$\displaystyle
R^{\pm}_{\mu\nu\lambda\rho}=\frac{1}{2}(R_{\mu\nu\lambda\rho}\mp
i\ast\\!R_{\mu\nu\lambda\rho})\quad\Leftrightarrow\quad\ast
R^{\pm}_{\mu\nu\lambda\rho}=\pm iR^{\pm}_{\mu\nu\lambda\rho}\,,$ (32)

we have the expected chiral transformation,

$\displaystyle R^{\pm}_{\mu\nu\lambda\rho}\mapsto e^{\pm
i\theta}R^{\pm}_{\mu\nu\lambda\rho}\,.$ (33)

For the non-linear problem, let us consider the light-cone action for Einstein
gravity, which can be written in terms of positive and negative helicity
fields — respectively, $h_{+}$ and $h_{-}$. To the first interacting order in
the gravitational coupling $\kappa$, it takes the form

$\displaystyle S[h_{\pm}]=\int d^{4}x\Bigg{(}$ $\displaystyle
h_{-}\,\square\,h_{+}+\kappa\;h_{-}\,\partial_{u}^{2}\left(\left(\frac{\partial_{w}}{\partial_{u}}h_{+}\right)^{2}-h_{+}\,\frac{\partial_{w}^{2}}{\partial_{u}^{2}}h_{+}\right)$
$\displaystyle+\kappa\;h_{+}\,\partial_{u}^{2}\left(\left(\frac{\partial_{{\bar{w}}}}{\partial_{u}}h_{-}\right)^{2}-h_{-}\,\frac{\partial_{{\bar{w}}}^{2}}{\partial_{u}^{2}}h_{-}\right)+{\mathcal{O}}(\kappa^{2})\Bigg{)}.$
(34)

See e.g. Appendix C of Ananth:2006fh  for the derivation, including the
precise origin of $h_{\pm}$ in terms of metric components. We wrote the action
here up to cubic order, but an infinite number of vertices is expected, unlike
the case of Yang-Mills theory. What is similar to Yang-Mills theory is that
the duality under $h_{\pm}\mapsto e^{\pm i\theta}h_{\pm}$ does not hold at
non-linear level. Indeed, the scattering amplitudes violate the selection rule
of helicity conservation. The most compact formula for the MHV amplitudes in
gravity was given in Hodges:2012ym . A fact about MHV amplitudes related to
our discussion is that they can be derived from the amplitude for the helicity
flip of a graviton as it crosses a self-dual spacetime background
Mason:2009afn .

Our conclusion that the duality is broken by interactions agrees with that of
ref. Deser:2005sz , which worked up to cubic order in a non-covariant
formalism. The procedure employed there is not straightforward, and indeed
several authors have since raised the hope that there is an implementation of
the U(1) transformation at non-linear level that exhibits the duality. The
cubic order is actually subtle in the light-cone action, because the non-local
field redefinitions999Here, $\frac{1}{\square}$ is understood in terms of the
Green’s function.

$\displaystyle\tilde{h}_{\pm}=h_{\pm}+\kappa\;\frac{1}{\square}\,\partial_{u}^{2}\left(\left(\frac{\partial_{w}}{\partial_{u}}h_{\pm}\right)^{2}-h_{\pm}\,\frac{\partial_{w}^{2}}{\partial_{u}^{2}}h_{\pm}\right)$
(35)

put the action (34) into the form

$\displaystyle S[\tilde{h}_{\pm}]=\int
d^{4}x\;\left(\tilde{h}_{-}\,\square\,\tilde{h}_{+}+{\mathcal{O}}(\kappa^{2})\right)\,.$
(36)

The duality under $\tilde{h}_{\pm}\mapsto e^{\pm i\theta}\tilde{h}_{\pm}$ then
appears unbroken at this order. This field redefinition is not trivial, and
indeed it eliminates the 3-point graviton amplitudes (where
$\frac{1}{\square}$ would be singular); these amplitudes, however, only have
on-shell support on complex kinematics. Despite this subtlety at 3 points, the
higher-point amplitudes (higher than 4 points) settle the question, due to
helicity violation.101010The four-point tree amplitudes preserve helicity.
Indeed, ‘MHV’ in this case is two-plus two-minus. When early works appeared
applying helicity arguments to gravity amplitudes (e.g. Grisaru:1975bx ;
Grisaru:1976vm ), $(n>4)$-point amplitudes were still too hard to tackle. For
this reason, it was often stated that the interactions preserve helicity. A
careful reading shows that there is no contradiction. The breaking of the
duality by the interactions is an inescapable conclusion: it is independent of
gauge choices and field redefinitions, relying instead on the unambiguous
action of the U(1) transformation on the asymptotic scattering states.

Recently, a proposal was made in Kol:2022bsd  (see also Kol:2023yxd ) that the
duality holds exactly, which conflicts with our conclusion. The claim there is
that there is a way to implement the U(1) transformation that agrees with the
linearised story in the appropriate limit, but applies also non-linearly, by
mapping any vacuum solution into a vacuum solution. In other words, it is an
exact symmetry of the Einstein equations. Consider the curvature 2-form
$\mathfrak{R}_{ab}$ of a vacuum solution. It is claimed in Kol:2022bsd  that
the result of a suitably defined U(1) transformation,
$(\mathfrak{R}_{ab})_{\theta}$, is also the curvature 2-form of a vacuum
solution. This would imply that $(\mathfrak{R}_{ab})_{\theta}$ satisfies
exactly, for an associated metric, all three of the crucial relations:
equation of motion, first Bianchi identity, and second Bianchi identity. Our
argument implies that, for a generic starting solution (we will discuss
exceptions), this is not possible. That is, $(\mathfrak{R}_{ab})_{\theta}$ is
a 2-form, but it cannot be interpreted as the curvature 2-form of a vacuum
solution. Consequently, the proposed U(1) transformation is not a map from a
generic vacuum solution into another, and it does not imply a U(1) duality
symmetry in Einstein gravity.

The first instance we are aware of where the duality in linearised gravity is
mentioned, ref. Penrose:1960eq , agrees with our conclusion, while not
elaborating on a proof. It is noted there that the Weyl spinor111111Using the
spinorial formalism introduced in Penrose:1960eq , the self-dual part of the
curvature is
$R^{+}_{A\dot{A}B\dot{B}C\dot{C}D\dot{D}}=\frac{1}{2}\psi_{ABCD}\varepsilon_{\dot{A}\dot{B}}\varepsilon_{\dot{C}\dot{D}}$
. Note that, in that paper, $\partial_{\mu}$ denotes the covariant derivative.
$\psi_{ABCD}$ must satisfy in vacuum the following non-linear wave equation:

$\displaystyle\square_{g}\,\psi_{ABCD}-3\,\psi_{(AB}{}^{EF}\,\psi_{CD)EF}=0\,,$
(37)

where we use $\square_{g}$ to emphasise the non-trivial metric. The second
(differential) Bianchi identity is crucial in the derivation. Unlike the
analogous Maxwell case, where the wave equation is linear, the U(1)
transformation

$\displaystyle\psi_{ABCD}\,\mapsto\,e^{i\theta}\,\psi_{ABCD}$ (38)

“does not in general give rise to new exact solutions to the field equations”,
quoting Penrose:1960eq . This statement does not exclude the possibility of a
special sector of solutions where the U(1) transformation takes us from one
exact vacuum solution to another. It turns out that this may occur even when
the second term in (37) is non-vanishing, because $\square_{g}$ is also
affected by the U(1) transformation. This is the case for the family of
solutions to be discussed in the next section.

Before proceeding, let us step back and address an intuitive way in which one
may have attempted to define the duality non-linearly in gravity. Suppose that
we have initial data ${\mathcal{I}}$ for which the action of the U(1)
transformation is clear, so we have the map
${\mathcal{I}}\mapsto{\mathcal{I}}_{\theta}$. One may say that the solution
evolved from the initial data ${\mathcal{I}}$, on the one hand, and the
solution evolved from the initial data ${\mathcal{I}}_{\theta}$, on the other
hand, are related by a U(1) transformation in some sense, because the two sets
of initial data are. But this is not the statement that the theory has the
U(1) symmetry. For the theory to have the symmetry, the final data
${\mathcal{F}}({\mathcal{I}})$ obtained by evolving ${\mathcal{I}}$ and the
final data ${\mathcal{F}}({\mathcal{I}}_{\theta})$ obtained by evolving
${\mathcal{I}}_{\theta}$ must themselves be mapped under the duality, i.e.
${\mathcal{F}}({\mathcal{I}})\mapsto{\mathcal{F}}({\mathcal{I}}_{\theta})$.
This is precisely the question that we have addressed in terms of scattering
amplitudes: we have proven that, generically,
${\mathcal{F}}({\mathcal{I}})\not\mapsto{\mathcal{F}}({\mathcal{I}}_{\theta})$
for gravity. In the language used in (19), this corresponds to

$\displaystyle
e^{i\theta{\mathcal{H}}}S|\text{in}\rangle\not=Se^{i\theta{\mathcal{H}}}|\text{in}\rangle$
(39)

for generic $|\text{in}\rangle$ states. That is, ${\mathcal{H}}$ does not
generate a symmetry of the S-matrix.

##  7 A duality-preserving sector of gravity: vacuum type D

We have shown that the duality is broken by the interactions among gravitons.
In linearised gravity, which admits the duality as we discussed, the
interactions among gravitons are neglected. However, in linearised gravity we
still consider interactions with matter, similarly to electromagnetism. We
recall that, in electromagnetism, a static dyon with electric charge $e$ and
magnetic monopole charge $g$ sources the field strength (22). This is
associated to the U(1)-invariant amplitude (24). Similarly, in linearised
gravity, a static particle with mass $m$ and NUT charge $n$ sources the
linearised Taub-NUT solution.121212The notion that this solution is a
gravitational dyon goes far back; see e.g. Dowker1974TheNS . This is
associated to the amplitude

$\displaystyle{\mathcal{A}}=\frac{m\pm
in}{\sqrt{m^{2}+n^{2}}}\;\varepsilon_{\pm}^{\mu\nu}\,p_{\mu}\,p_{\nu}$ (40)

for a ‘nutty particle’ with momentum $p$ to absorb a $\pm$ helicity graviton,
$\varepsilon_{\pm}^{\mu\nu}$ being the latter’s polarisation tensor
Huang:2019cja .131313The momentum of the ‘nutty particle’ is
$p=\sqrt{m^{2}+n^{2}}\;u$, where $u$ is the velocity. By considering the
duality transformation (31) of the linearised Riemann tensor for the Taub-NUT
solution, we can conclude that

$\displaystyle m-in\,\mapsto\,e^{i\theta}(m-in)=m^{\prime}-in^{\prime}\,.$
(41)

Together with the duality transformation of the graviton, this makes the
amplitude (40) U(1)-invariant, as expected by the duality invariance of the
linearised theory.

It turns out that the Taub-NUT family of solutions, labelled by the two
parameters $m$ and $n$, admits the duality at the non-linear level. In fact,
this property extends straightforwardly to the whole family of vacuum
solutions of algebraic type D, labelled by four parameters
$(m,n,\gamma,\epsilon)$; the two parameters $\gamma$ and $\epsilon$ combine to
represent rotation and acceleration. The explicit expressions are not
important for us now, but can be found in Plebanski:1976gy . The important
point is that, for a natural choice of coordinates, the Weyl spinor takes the
form

$\displaystyle\psi_{ABCD}=(m-in)\,\alpha_{(A}\alpha_{B}\beta_{C}\beta_{D)}\,.$
(42)

Here, the spinors $\alpha_{A}$ and $\beta_{A}$ depend on the coordinates, but
not on the parameters $(m,n,\gamma,\epsilon)$. While the solution has four
parameters, only $m$ and $n$ give rise to curvature. Notice that
$\alpha_{A}\beta^{A}\neq 0$, so the second term in (37) is present.
Nevertheless, from this form of the Weyl spinor, it is clear that the U(1)
transformation

$\displaystyle\psi_{ABCD}\,\mapsto\,e^{i\theta}\,\psi_{ABCD}$ (43)

has the effect (41), which takes us from the solution with parameters
$(m,n,\gamma,\epsilon)$ to the solution with parameters
$(m^{\prime},n^{\prime},\gamma,\epsilon)$. That is, it is clear in this
instance that the U(1) transformation leads to an actual curvature tensor,
associated with a metric.141414Had we included a cosmological constant, i.e.
had we considered five parameters $(m,n,\gamma,\epsilon,\Lambda)$, these
statements would still hold, except that $\Lambda$ introduces curvature too,
via the Ricci tensor as opposed to the Weyl tensor.

The argument we gave in the previous section against the non-linear duality is
avoided for this family of solutions. The fact that the duality holds here no
doubt raised hopes that it would hold more generally in the vacuum solution
space of Einstein’s theory. These solutions are, however, not generic
solutions. They are not algebraically general in the sense of the Petrov
classification, but algebraically special — in particular, of type D, which
means they have two principal null directions, associated to $\alpha_{A}$ and
$\beta_{A}$, each of multiplicity two. A related property is that these
solutions admit a double-Kerr-Schild form using complexified coordinates
Plebanski:1976gy , which means that they have features generically encountered
only for linearised solutions. Notice that the form (42) of the Weyl spinor is
linear in $m$ and $n$. The same special characteristics allow for these exact
gravity solutions to be expressed in a very simple manner as a ‘double copy’
of the analogous solutions in electromagnetism Monteiro:2014cda ; Luna:2015paa
; Luna:2018dpt .

We do not know what is the largest class of gravity solutions within which the
duality holds, though it is clear that it includes also some sector of type N
solutions. The expectation is that the solutions in the duality-admitting
class are effectively constructible ‘without interactions among gravitons’,
which excludes situations of clear physical interest. For instance,
interactions among gravitons are crucial in the two-massive-body inspiral or
scattering problems, beyond the leading perturbative order.

##  8 Conclusion

We have shown that Einstein gravity does not share the global U(1) duality
symmetry analogous to the electric-magnetic duality in Maxwell theory. The
symmetry is present only (i) in the linearised approximation, and (ii) at non-
linear level for a special sector of solutions that notably includes vacuum
type D spacetimes, where the duality is known to rotate between mass and NUT
charge.

The argument presented here will not be entirely new to some people, but we
hope to have fleshed it out for a broad audience, and we are not aware of it
being applied to gravity before. The usefulness of scattering amplitudes in
gravity, including at the classical level, is now well established; see e.g.
the recent reviews Bern:2022wqg ; Kosower:2022yvp ; Bjerrum-Bohr:2022blt ;
Buonanno:2022pgc ; Adamo:2022dcm ; DiVecchia:2023frv , where much work is
concerned with gravitational wave physics and/or the double copy. We have
given here an example of the power of scattering amplitudes to provide a sharp
gauge-invariant answer to a question that has generated some confusion over
the years.

Finally, we note that the breaking of the global ‘electric-magnetic’ U(1)
symmetry by interactions in gravity is consistent with the lore that a theory
of quantum gravity should have no global symmetries; see e.g. Banks:1988yz ;
Banks:2010zn ; Harlow:2018tng . This commonly refers to symmetries of ordinary
fields such as the original electric-magnetic duality of Maxwell theory, which
is anomalous on a curved spacetime Agullo:2016lkj . In our instance of pure
Einstein gravity, the global symmetry is broken already at the classical
level. It is worth mentioning in this broader context that, in the literature
dealing with the ultraviolet behaviour of pure (super)gravities, an explicit
connection has been noticed between anomalies and ultraviolet divergences in
four dimensions; see e.g. Carrasco:2013ypa ; Bern:2013uka ; Bern:2015xsa ;
Bern:2017puu ; Bern:2017rjw ; Freedman:2017zgq ; Bern:2019isl ;
Carrasco:2022lbm . This and other developments motivate further study of the
implications of broken symmetries in gravity.

## Acknowledgements

The author is grateful to John Joseph Carrasco, George Doran, Uri Kol, Lionel
Mason, Nathan Moynihan, Congkao Wen and Sam Wikeley for comments or
collaboration on related topics. RM is supported by the Royal Society via a
University Research Fellowship.

## References

  * (1) C. Montonen and D. I. Olive, Magnetic Monopoles as Gauge Particles?, Phys. Lett. B 72 (1977) 117–120.
  * (2) N. Seiberg, Electric - magnetic duality in supersymmetric nonAbelian gauge theories, Nucl. Phys. B 435 (1995) 129–146, [hep-th/9411149].
  * (3) M. K. Gaillard and B. Zumino, Duality Rotations for Interacting Fields, Nucl. Phys. B 193 (1981) 221–244.
  * (4) R. Penrose, A Spinor approach to general relativity, Annals Phys. 10 (1960) 171–201.
  * (5) J. A. Nieto, S duality for linearized gravity, Phys. Lett. A 262 (1999) 274–281, [hep-th/9910049].
  * (6) C. M. Hull, Duality in gravity and higher spin gauge fields, JHEP 09 (2001) 027, [hep-th/0107149].
  * (7) M. Henneaux and C. Teitelboim, Duality in linearized gravity, Phys. Rev. D 71 (2005) 024018, [gr-qc/0408101].
  * (8) S. Deser and D. Seminara, Free spin 2 duality invariance cannot be extended to GR, Phys. Rev. D 71 (2005) 081502, [hep-th/0503030].
  * (9) C. W. Bunster, S. Cnockaert, M. Henneaux, and R. Portugues, Monopoles for gravitation and for higher spin fields, Phys. Rev. D 73 (2006) 105014, [hep-th/0601222].
  * (10) R. Argurio and F. Dehouck, Gravitational duality and rotating solutions, Phys. Rev. D 81 (2010) 064010, [arXiv:0909.0542].
  * (11) G. Barnich and C. Troessaert, Manifest spin 2 duality with electric and magnetic sources, JHEP 01 (2009) 030, [arXiv:0812.0552].
  * (12) S. Deser and C. Teitelboim, Duality Transformations of Abelian and Nonabelian Gauge Fields, Phys. Rev. D 13 (1976) 1592–1597.
  * (13) U. Kol, Duality in Einstein’s Gravity, arXiv:2205.05752.
  * (14) U. Kol and S.-T. Yau, Duality in Gauge Theory, Gravity and String Theory, arXiv:2311.07934.
  * (15) A. Luna, R. Monteiro, D. O’Connell, and C. D. White, The classical double copy for Taub-NUT spacetime, Phys. Lett. B750 (2015) 272–277, [arXiv:1507.01869].
  * (16) Y.-T. Huang, U. Kol, and D. O’Connell, Double copy of electric-magnetic duality, Phys. Rev. D 102 (2020), no. 4 046005, [arXiv:1911.06318].
  * (17) R. Alawadhi, D. S. Berman, B. Spence, and D. Peinador Veiga, S-duality and the double copy, JHEP 03 (2020) 059, [arXiv:1911.06797].
  * (18) A. Banerjee, E. O. Colgáin, J. A. Rosabal, and H. Yavartanoo, Ehlers as EM duality in the double copy, Phys. Rev. D 102 (2020) 126017, [arXiv:1912.02597].
  * (19) W. T. Emond, Y.-T. Huang, U. Kol, N. Moynihan, and D. O’Connell, Amplitudes from Coulomb to Kerr-Taub-NUT, JHEP 05 (2022) 055, [arXiv:2010.07861].
  * (20) N. Moynihan and J. Murugan, On-Shell Electric-Magnetic Duality and the Dual Graviton, arXiv:2002.11085.
  * (21) R. Monteiro, D. O’Connell, D. Peinador Veiga, and M. Sergola, Classical solutions and their double copy in split signature, JHEP 05 (2021) 268, [arXiv:2012.11190].
  * (22) E. Crawley, A. Guevara, N. Miller, and A. Strominger, Black holes in Klein space, JHEP 10 (2022) 135, [arXiv:2112.03954].
  * (23) R. Monteiro, S. Nagy, D. O’Connell, D. Peinador Veiga, and M. Sergola, NS-NS spacetimes from amplitudes, JHEP 06 (2022) 021, [arXiv:2112.08336].
  * (24) M. G. Calkin, An invariance property of the free electromagnetic field, Am. J. Phys. 33 (1965) 958–960.
  * (25) J. Novotný, Self-duality, helicity conservation and normal ordering in nonlinear QED, Phys. Rev. D 98 (2018), no. 8 085015, [arXiv:1806.02167].
  * (26) A. A. Rosly and K. G. Selivanov, Helicity conservation in Born-Infeld theory, in Workshop on String Theory and Complex Geometry, 4, 2002\.  hep-th/0204229.
  * (27) J. Carrasco, R. Kallosh, R. Roiban, and A. Tseytlin, On the U(1) duality anomaly and the S-matrix of N=4 supergravity, JHEP 1307 (2013) 029, [arXiv:1303.6219].
  * (28) Z. Bern, S. Davies, T. Dennen, A. V. Smirnov, and V. A. Smirnov, Ultraviolet Properties of N=4 Supergravity at Four Loops, Phys.Rev.Lett. 111 (2013), no. 23 231302, [arXiv:1309.2498].
  * (29) D. Z. Freedman, R. Kallosh, D. Murli, A. Van Proeyen, and Y. Yamada, Absence of U(1) Anomalous Superamplitudes in $\mathcal{N}\geq 5$ Supergravities, JHEP 05 (2017) 067, [arXiv:1703.03879].
  * (30) Z. Bern, J. Parra-Martinez, and R. Roiban, Canceling the U(1) Anomaly in the $S$ Matrix of $N$=4 Supergravity, Phys. Rev. Lett. 121 (2018), no. 10 101604, [arXiv:1712.03928].
  * (31) N. H. Pavao, Effective observables for electromagnetic duality from novel amplitude decomposition, Phys. Rev. D 107 (2023), no. 6 065020, [arXiv:2210.12800].
  * (32) J. J. M. Carrasco and N. H. Pavao, Virtues of a symmetric-structure double copy, Phys. Rev. D 107 (2023), no. 6 065005, [arXiv:2211.04431].
  * (33) J. J. M. Carrasco and N. H. Pavao, Even-point Multi-loop Unitarity and its Applications: Exponentiation, Anomalies and Evanescence, arXiv:2307.16812.
  * (34) I. Agullo, A. del Rio, and J. Navarro-Salas, Electromagnetic duality anomaly in curved spacetimes, Phys. Rev. Lett. 118 (2017), no. 11 111301, [arXiv:1607.08879].
  * (35) H. Elvang, M. Hadjiantonis, C. R. T. Jones, and S. Paranjape, All-Multiplicity One-Loop Amplitudes in Born-Infeld Electrodynamics from Generalized Unitarity, JHEP 03 (2020) 009, [arXiv:1906.05321].
  * (36) C. Wen and S.-Q. Zhang, D3-Brane Loop Amplitudes from M5-Brane Tree Amplitudes, JHEP 07 (2020) 098, [arXiv:2004.02735].
  * (37) H. Elvang, M. Hadjiantonis, C. R. T. Jones, and S. Paranjape, Electromagnetic Duality and D3-Brane Scattering Amplitudes Beyond Leading Order, JHEP 04 (2021) 173, [arXiv:2006.08928].
  * (38) F. Cachazo, S. He, and E. Y. Yuan, Scattering Equations and Matrices: From Einstein To Yang-Mills, DBI and NLSM, JHEP 07 (2015) 149, [arXiv:1412.3479].
  * (39) M. Chiodaroli, M. Gunaydin, H. Johansson, and R. Roiban, Scattering amplitudes in N=2 Maxwell-Einstein and Yang-Mills/Einstein supergravity, arXiv:1408.0764.
  * (40) Z. Bern, A. De Freitas, and H. L. Wong, On the coupling of gravitons to matter, Phys. Rev. Lett. 84 (2000) 3531, [hep-th/9912033].
  * (41) P. A. Cano and A. Murcia, Duality-invariant extensions of Einstein-Maxwell theory, JHEP 08 (2021) 042, [arXiv:2104.07674].
  * (42) R. Britto, F. Cachazo, B. Feng, and E. Witten, Direct proof of tree-level recursion relation in Yang-Mills theory, Phys. Rev. Lett. 94 (2005) 181602, [hep-th/0501052].
  * (43) N. Arkani-Hamed, J. L. Bourjaily, F. Cachazo, A. B. Goncharov, A. Postnikov, and J. Trnka, Grassmannian Geometry of Scattering Amplitudes.  Cambridge University Press, 4, 2016.
  * (44) Z. Bern and Y.-t. Huang, Basics of Generalized Unitarity, J.Phys.A A44 (2011) 454003, [arXiv:1103.1869].
  * (45) C. Csaki, S. Hong, Y. Shirman, O. Telem, J. Terning, and M. Waterbury, Scattering amplitudes for monopoles: pairwise little group and pairwise helicity, JHEP 08 (2021) 029, [arXiv:2009.14213].
  * (46) D. A. Kosower, B. Maybee, and D. O’Connell, Amplitudes, Observables, and Classical Scattering, JHEP 02 (2019) 137, [arXiv:1811.10950].
  * (47) S. J. Parke and T. R. Taylor, An Amplitude for $n$ Gluon Scattering, Phys. Rev. Lett. 56 (1986) 2459.
  * (48) G. Chalmers and W. Siegel, Simplifying algebra in Feynman graphs. Part 2. Spinor helicity from the space-cone, Phys. Rev. D 59 (1999) 045013, [hep-ph/9801220].
  * (49) S. Ananth, L. Brink, R. Heise, and H. G. Svendsen, The N=8 Supergravity Hamiltonian as a Quadratic Form, Nucl. Phys. B 753 (2006) 195–210, [hep-th/0607019].
  * (50) A. Hodges, A simple formula for gravitational MHV amplitudes, arXiv:1204.1930.
  * (51) L. J. Mason and D. Skinner, Gravity, Twistors and the MHV Formalism, Commun. Math. Phys. 294 (2010) 827–862, [arXiv:0808.3907].
  * (52) M. T. Grisaru, P. van Nieuwenhuizen, and C. C. Wu, Gravitational Born Amplitudes and Kinematical Constraints, Phys. Rev. D 12 (1975) 397\.
  * (53) M. T. Grisaru, H. N. Pendleton, and P. van Nieuwenhuizen, Supergravity and the S Matrix, Phys. Rev. D 15 (1977) 996.
  * (54) J. S. Dowker, The nut solution as a gravitational dyon, General Relativity and Gravitation 5 (1974) 603–613.
  * (55) J. F. Plebanski and M. Demianski, Rotating, charged, and uniformly accelerating mass in general relativity, Annals Phys. 98 (1976) 98–127.
  * (56) R. Monteiro, D. O’Connell, and C. D. White, Black holes and the double copy, JHEP 1412 (2014) 056, [arXiv:1410.0239].
  * (57) A. Luna, R. Monteiro, I. Nicholson, and D. O’Connell, Type D Spacetimes and the Weyl Double Copy, Class. Quant. Grav. 36 (2019) 065003, [arXiv:1810.08183].
  * (58) Z. Bern, J. J. Carrasco, M. Chiodaroli, H. Johansson, and R. Roiban, The SAGEX Review on Scattering Amplitudes, Chapter 2: An Invitation to Color-Kinematics Duality and the Double Copy, arXiv:2203.13013.
  * (59) D. A. Kosower, R. Monteiro, and D. O’Connell, The SAGEX review on scattering amplitudes Chapter 14: Classical gravity from scattering amplitudes, J. Phys. A 55 (2022), no. 44 443015, [arXiv:2203.13025].
  * (60) N. E. J. Bjerrum-Bohr, P. H. Damgaard, L. Plante, and P. Vanhove, The SAGEX review on scattering amplitudes Chapter 13: Post-Minkowskian expansion from scattering amplitudes, J. Phys. A 55 (2022), no. 44 443014, [arXiv:2203.13024].
  * (61) A. Buonanno, M. Khalil, D. O’Connell, R. Roiban, M. P. Solon, and M. Zeng, Snowmass White Paper: Gravitational Waves and Scattering Amplitudes, in Snowmass 2021, 4, 2022.  arXiv:2204.05194.
  * (62) T. Adamo, J. J. M. Carrasco, M. Carrillo-González, M. Chiodaroli, H. Elvang, H. Johansson, D. O’Connell, R. Roiban, and O. Schlotterer, Snowmass White Paper: the Double Copy and its Applications, in 2022 Snowmass Summer Study, 4, 2022.  arXiv:2204.06547.
  * (63) P. Di Vecchia, C. Heissenberg, R. Russo, and G. Veneziano, The gravitational eikonal: from particle, string and brane collisions to black-hole encounters, arXiv:2306.16488.
  * (64) T. Banks and L. J. Dixon, Constraints on String Vacua with Space-Time Supersymmetry, Nucl. Phys. B 307 (1988) 93–108.
  * (65) T. Banks and N. Seiberg, Symmetries and Strings in Field Theory and Gravity, Phys. Rev. D 83 (2011) 084019, [arXiv:1011.5120].
  * (66) D. Harlow and H. Ooguri, Symmetries in quantum field theory and quantum gravity, Commun. Math. Phys. 383 (2021), no. 3 1669–1804, [arXiv:1810.05338].
  * (67) Z. Bern, C. Cheung, H.-H. Chi, S. Davies, L. Dixon, and J. Nohle, Evanescent Effects Can Alter Ultraviolet Divergences in Quantum Gravity without Physical Consequences, Phys. Rev. Lett. 115 (2015), no. 21 211301, [arXiv:1507.06118].
  * (68) Z. Bern, H.-H. Chi, L. Dixon, and A. Edison, Two-Loop Renormalization of Quantum Gravity Simplified, Phys. Rev. D 95 (2017), no. 4 046013, [arXiv:1701.02422].
  * (69) Z. Bern, D. Kosower, and J. Parra-Martinez, Two-loop n-point anomalous amplitudes in N=4 supergravity, Proc. Roy. Soc. Lond. A 476 (2020), no. 2235 20190722, [arXiv:1905.05151].
  * (70) J. J. M. Carrasco, M. Lewandowski, and N. H. Pavao, The color-dual fate of N=4 supergravity, arXiv:2203.03592.


# On the cycle maximum of birth-death processes and networks of queues

Richard J. Boucherie
Stochastic Operations Research
Department of Applied Mathematics
University of Twente
<EMAIL_ADDRESS>

###### Abstract

This paper considers the cycle maximum in birth-death processes as a stepping
stone to characterisation of the cycle maximum in single queues and open
Kelly-Whittle networks of queues. For positive recurrent birth-death processes
we show that the sequence of sample maxima is stochastically compact. For
transient birth-death processes we show that the sequence of sample maxima
conditioned on the maximum being finite is stochastically compact.

We show that the Markov chain recording the total number of customers in a
Kelly-Whittle network is a birth-death process with birth and death rates
determined by the normalising constants in a suitably defined sequence of
closed networks. Explicit or asymptotic expressions for these normalising
constants allow asymptotic evaluation of the birth and death rates, which, in
turn, allows characterisation of the cycle maximum in a single busy cycle, and
convergence of the sequence of sample maxima for Kelly-Whittle networks of
queues.

_Keywords_ Cycle maximum, birth-death process, stochastic compactness, extreme
value theory, network of queues

##  1 Introduction

The maximum number of customers simultaneously present in a queueing system is
an important performance measure that is directly related to the cycle maximum
during a busy cycle (Asmussen (1998)). This paper considers the cycle maximum
in birth-death processes as a stepping stone to characterisation of the cycle
maximum in single queues and open Kelly-Whittle networks of queues (Boucherie
and van Dijk (1991); Henderson and Taylor (1990)). To this end, it is observed
that Norton’s theorem (Boucherie and van Dijk (1993)) implies that the Markov
chain recording the total number of customers in the network is a birth-death
process with birth and death rates determined by the normalising constants in
a suitably defined sequence of closed networks. Explicit or asymptotic
expressions for these normalising constants (Harrison (1985); George et al.
(2012)) allow asymptotic evaluation of the birth and death rates, which, in
turn, allows characterisation of the cycle maximum in a single busy cycle,
${\mathbf{Y}}$, and convergence of the sequence of partial maxima,
${\mathbf{Y}}^{(k)}$, over $k$ busy cycles.

Building on the explicit expression for the cycle maximum in a birth-death
process (Asmussen (1998)), we observe that the dual relation between the
discrete failure rate $\mathbb{P}(\mathbf{Y}=n|\mathbf{Y}\geq n)$ and the
blocking probability $\mathbb{P}(\mathbf{X}=n|\mathbf{X}\leq n)$, with
$\mathbf{X}$ the limiting random variable for state of the process, that was
first observed for the Erlang loss queue in Cohen (1971), extends to general
birth-death processes. This dual relation is of a form similar to the dual or
inverse relation between the $M/G/1$ and $GI/M/1$ queues obtained by
interchanging the service and inter-arrival time distributions, see Takács
(1962); Niu and Cooper (1989); Kimura (1993); Bekker and Zwart (2005).

The limiting behaviour of the sequence of sample maxima ${\mathbf{Y}}^{(k)}$
may be characterised by a sequence of constants $\\{a_{k}>0,~{}b_{k}\\}_{k\geq
1}$, $a_{k}$ bounded, $b_{k}\rightarrow\infty$ as $k\rightarrow\infty$. For
continuous valued $\mathbf{Y}$ such as for the waiting time or workload these
constants are available in literature, see e.g. Boxma and Perry (2009). As
$\mathbf{Y}$ for the birth-death process is discrete valued,
$\lim_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq a_{k}x+b_{k})$ does
not exist, see Serfozo (1987). Bounds for the $\liminf$ and $\limsup$ may be
obtained following the approach in Anderson (1970); Cohen (1982); Vervaat
(1973). For positive recurrent birth-death processes, we show that
$\mathbf{Y}$ is stochastically compact (de Haan and Resnick (1984)), in
particular, we will show that the normalised sequence of sample maxima
$(\mathbf{Y}^{(k)}-b_{k})/a_{k}$ has a subsequence whose distributions
converge weakly to the Gumbel distribution. For transient birth-death
processes, we show that $\mathbf{Y}|\mathbf{Y}<\infty$ is stochastically
compact. The relation between $\mathbf{Y}$ for recurrent processes and
$\mathbf{Y}|\mathbf{Y}<\infty$ for transient processes is similar to the
relation first observed in Cohen (1971) between a process and its dual, as
mentioned above.

Section 2 introduces notation for birth-death processes, and observes the dual
relation for the cycle maximum. Section 3 considers weak and almost sure
convergence of sample maxima. Section 4 considers the cycle maximum for single
queues and a Kelly-Whittle network of queues.

##  2 The cycle maximum for a single cycle

###  2.1 Birth-death process

Consider a birth-death process $(X(t),~{}t\geq 0)$ at state space
$S=\\{0,1,2,\ldots\\}$ with birth rates $\lambda(n)>0$, $n\geq 0$ and death
rates $\mu(n)>0$, $n\geq 1$. In agreement with common notation for queues and
queueing networks, see Boucherie and van Dijk (1991); Henderson and Taylor
(1990), we will express the birth and death rates as

$\lambda(n)=\lambda\frac{\psi(n)}{\phi(n)},\quad n\geq
0,\quad\mu(n)=\mu\frac{\psi(n-1)}{\phi(n)},\quad n>1,$ (1)

with $\psi(n)>0$, $\phi(n)>0$, $n=0,1,2,\ldots$. Let $\rho=\lambda/\mu$.

We assume that $\sum_{n\geq 1}\phi(n)/(\psi(n)+\psi(n-1))=\infty$, which is a
sufficient condition for regularity (Foster (1953)). $(X(t),~{}t\geq 0)$ is
positive recurrent if and only if (iff) $B_{\phi}^{-1}=\sum_{n\in
S}\phi(n)\rho^{n}<\infty$. Then the limiting distribution
$\pi_{\phi}(n)=\lim_{t\rightarrow\infty}\mathbb{P}(X(t)=n)$ exists, and
$\pi_{\phi}(n)=B_{\phi}\phi(n)\rho^{n}$, $n\in S$. Let $\mathbf{X}$ denote the
limiting random variable. From Foster’s criterion (Foster (1953)),
$(X(t),~{}t\geq 0)$ is null recurrent iff $B_{\phi}^{-1}=\infty$ and
$B_{*}^{-1}=\sum_{n\in S}(\psi(n)\rho^{n})^{-1}<\infty$ and transient iff
$B_{*}^{-1}=\infty$. Therefore, if $B_{\psi}^{-1}=\sum_{n\in
S}\psi(n)\rho^{n}<\infty$, then $(X(t),~{}t\geq 0)$ recurrent. Furthermore, if
$B_{\psi}^{-1}<\infty$ the limiting Palm distribution at births
$\pi_{\psi}(n)=\lim_{t\rightarrow\infty}\mathbb{P}_{0}(X(t)=n)=\lim_{t\rightarrow\infty}\lim_{\Delta
t\downarrow 0}\mathbb{P}(X(t)=n|\mbox{ birth in }(t,t+\Delta t))$ exists, and
$\pi_{\psi}(n)=B_{\psi}\psi(n)\rho^{n}$, $n\in S$, see Brumelle (1978).

Observe that $(X(t),~{}t\geq 0)$ is regenerative with renewal epochs $0\leq
T_{0}<T_{1}<T_{2}<\cdots$ each time $(X(t),~{}t\geq 0)$ has a transition from
state 0 to state 1. The generic cycle is the cycle starting at $T_{0}$. Let
$\mathbf{Y}_{k}=\max_{T_{k-1}\leq t<T_{k}}X(t)$ the maximum over the $k$-th
cycle. Then $\mathbf{Y}_{1},\mathbf{Y}_{2},\ldots$ are i.i.d. and distributed
as $\mathbf{Y}=\mathbf{Y}_{1}$, with distribution, see Asmussen (1998),

$\mathbb{P}(\mathbf{Y}\leq
n)=1-\left[\sum_{i=0}^{n}\frac{1}{\psi(i)\rho^{i}}\right]^{-1},\quad
n=1,2,\ldots,$ (2)

which is non-degenerate iff $B_{*}^{-1}=\infty$, i.e., iff $(X(t),~{}t\geq 0)$
is recurrent.

For the $M(\lambda)/M(\mu)/1$-queue, the single server queue with Poisson
arrivals with rate $\lambda$ and exponential service requirements with rate
$\mu$, $\psi(n)=\phi(n)=1$. For the $M(\lambda)/M(\mu)/\infty$-queue, the
infinite-server queue, $\psi(n)=\phi(n)=1/{n!}$. See Section 4 for further
details.

The result for the cycle maximum readily extends to a birth-death process with
finite state space $S=\\{0,1,\ldots,c\\}$, which may be achieved by setting
$\psi(c)=0$. For example, consider the $M(\lambda)/M(\mu)/1/c$-queue, the
single server queue finite waiting room of size $c-1$, for which the
distribution of the cycle maximum is obtained in Al Hanbali and Boxma (2010),
or the $M(\lambda)/M(\mu)/c/c$-queue, the Erlang loss queue. The probability
$\mathbb{P}(\mathbf{Y}\leq c)$ must now be interpreted as the probability that
during a cycle no customers are blocked.

###  2.2 A duality relation for the cycle maximum for queues in equilibrium

From (2) we obtain the conditional probability that the cycle maximum is $n$
given that the cycle maximum is at least $n$:

$\mathbb{P}(\mathbf{Y}=n|\mathbf{Y}\geq
n)=\frac{1}{\psi(n)\rho^{n}}\left[\sum_{i=0}^{n}\frac{1}{\psi(i)\rho^{i}}\right]^{-1}.$
(3)

From the Palm distribution $\mathbb{P}_{0}(\mathbf{X}=n)$ we obtain the
probability that the state at a birth is $n$ given that it is at most $n$:

$\mathbb{P}_{0}(\mathbf{X}=n|\mathbf{X}\leq
n)={\psi(n)\rho^{n}}\left[\sum_{i=0}^{n}{\psi(i)\rho^{i}}\right]^{-1}.$ (4)

The relation between (3) and (4) was first observed in Cohen (1971) for the
Erlang loss queue, where $\mathbb{P}_{0}(\mathbf{X}=c|\mathbf{X}\leq c)$ is
the Erlang loss formula, i.e., the probability that an arriving customer meets
$c$ customers and is blocked, and $\mathbb{P}(\mathbf{Y}=c|\mathbf{Y}\geq c)$
is the probability that no customer is blocked during a cycle, whenever during
this cycle all servers are simultaneously busy at least once.

For the $M(\lambda)/M(\mu)/1$-queue, with stability condition $\lambda<\mu$,
the relation between (3) and (4) is more prominent. We find that

$\mathbb{P}_{M(\mu)/M(\lambda)/1}(\mathbf{Y}=n|\mathbf{Y}\geq
n)=\mathbb{P}_{M(\lambda)/M(\mu)/1}(\mathbf{X}=n|\mathbf{X}\leq n),$

where the non-stable $M(\mu)/M(\lambda)/1$-queue is the dual of the stable
$M(\lambda)/M(\mu)/1$-queue, i.e., the queue obtained by interchanging the
inter-arrival and service time distributions (Kimura (1993)).

##  3 Limit theorems

This section first considers the tail behaviour of $\mathbb{P}(\mathbf{Y}\leq
n)$, and subsequently analyses the normalised sample maxima
$\mathbb{P}((\mathbf{Y}^{(k)}-b_{k})/a_{k}\leq x)$ for
$\mathbf{Y}^{(k)}=\max\\{\mathbf{Y}_{1},\ldots,\mathbf{Y}_{k}\\}$, and
suitable constants $\\{a_{k}>0,~{}b_{k}\\}_{k\geq 1}$. We will characterise
weak and almost sure convergence of the sample maxima for recurrent processes.

###  3.1 Tail behaviour

Recurrence and transience of $(X(t),~{}t\geq 0)$ is characterised by $\psi$,
see Section 2. The ratio test for convergence of the series $B_{\psi}^{-1}$
and $B_{*}^{-1}$ suggest the following notation to characterise convergence:

$\displaystyle\overline{\beta}$ $\displaystyle=$
$\displaystyle\limsup_{n\rightarrow\infty}\psi(n+1)/\psi(n),$
$\displaystyle\underline{\beta}$ $\displaystyle=$
$\displaystyle\liminf_{n\rightarrow\infty}\psi(n+1)/\psi(n),$
$\displaystyle{\beta}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\psi(n+1)/\psi(n),\quad\mbox{if the
limit exists.}$

If $(X(t),~{}t\geq 0)$ is recurrent, then
$\lim_{n\rightarrow\infty}\mathbb{P}(\mathbf{Y}\leq n)=1$. We have the
following asymptotic result.

###### Lemma 1

If $\overline{\beta}\rho<1$, then.

$1-\overline{\beta}\rho\leq\liminf_{n\rightarrow\infty}\frac{1-\mathbb{P}(\mathbf{Y}\leq
n)}{\psi(n)\rho^{n}}\leq\limsup_{n\rightarrow\infty}\frac{1-\mathbb{P}(\mathbf{Y}\leq
n)}{\psi(n)\rho^{n}}\leq 1-\underline{\beta}\rho.$ (5)

If $\beta$ exists, and $\beta\rho<1$, then

$\lim_{n\rightarrow\infty}\frac{1-\mathbb{P}(\mathbf{Y}\leq
n)}{\psi(n)\rho^{n}}=1-{\beta}\rho.$ (6)

Proof The results follow since $T(n)=\frac{1-\mathbb{P}(\mathbf{Y}\leq
n)}{\psi(n)\rho^{n}}$ satisfies

$\frac{1}{T(n+1)}=\rho\frac{\psi(n+1)}{\psi(n)}\frac{1}{T(n)}+1,$

and taking limits $n\rightarrow\infty$. $\Box$

If $(X(t),~{}t\geq 0)$ is transient, then
$\lim_{n\rightarrow\infty}\mathbb{P}(\mathbf{Y}\leq n)=1-B_{*}$. We have the
following asymptotic result.

###### Lemma 2

If $\beta$ exists, and $\beta\rho>1$, then

$\lim_{n\rightarrow\infty}\psi(n)\rho^{n}[1-\mathbb{P}(\mathbf{Y}\leq
n|\mathbf{Y}<\infty)]=[({\beta}\rho-1)B_{*}(B_{*}-1)]^{-1}.$ (7)

Proof The result follows, since
$T(n)=\psi(n)\rho^{n}[1-\mathbb{P}(\mathbf{Y}\leq n|\mathbf{Y}<\infty)]$
satisfies

${T(n+1)}=\rho\frac{\psi(n+1)}{\psi(n)}\frac{\sum_{i=0}^{n}(\psi(i)\rho^{i})^{-1}}{\sum_{i=0}^{n+1}(\psi(i)\rho^{i})^{-1}}T(n)-\frac{1}{(B_{*}-1)\sum_{i=0}^{n+1}(\psi(i)\rho^{i})^{-1}},$

and taking limits $n\rightarrow\infty$. $\Box$

From (6) and (7) we find, if $\beta$ exists,

$\displaystyle\lim_{n\rightarrow\infty}[1-\mathbb{P}(\mathbf{Y}\leq
n)]/[B_{\psi}\psi(n)\rho^{n}]=(1-{\beta}\rho)/B_{\psi},$
$\displaystyle\beta\rho<1,$ (8)
$\displaystyle\lim_{n\rightarrow\infty}[1-\mathbb{P}(\mathbf{Y}\leq
n|\mathbf{Y}<\infty)]/[1/(B_{*}\psi(n)\rho^{n})]=1/[(\beta\rho-1)\mathbb{P}(\mathbf{Y}<\infty)B_{*}],$
$\displaystyle\beta\rho>1.$ (9)

If $\beta\rho<1$, then $B_{\psi}\psi(n)\rho^{n}$ is a non-degenerate
distribution, and for $\beta\rho>1$, $1/(B_{*}\psi(n)\rho^{n})$ is a non-
degenerate distribution. This shows that the tail behaviour of $\mathbf{Y}$
conditioned on $\mathbf{Y}<\infty$ for transient birth-death processes is
similar to that of $\mathbf{Y}$ for recurrent birth-death processes in the
sense that $B_{*}\psi(n)\rho^{n}$ is the "dual" of $B_{\psi}\psi(n)\rho^{n}$
obtained by replacing the birth and death rates $\lambda(n)$ and $\mu(n)$ by
$\lambda_{*}(n)=\mu\frac{\phi(n)}{\psi(n)}$ and
$\mu_{*}(n)=\lambda\frac{\phi(n)}{\psi(n-1)}$.

If $\beta$ exists, and $\beta\rho=1$, the tail behaviour of
$\mathbb{P}(\mathbf{Y}\leq n)$ depends on tail behaviour of $\psi(n)$.

###### Lemma 3

Assume that $\lim_{n\rightarrow\infty}\psi(n)\rho^{n}/n^{p}=\alpha$ for some
$\alpha$, $p$, with $0<\alpha<\infty$, and $-\infty<p<\infty$. Then, for all
$p$, $-\infty<p<\infty$, there exist $\delta(n,p)$, $\gamma(p)$ such that

$\lim_{n\rightarrow\infty}\delta(n,p)[1-\mathbb{P}(\mathbf{Y}\leq
n)]=\gamma(p),$

where

$\delta(n,p)=\left\\{\begin{array}[]{ll}n^{1-p},&\mbox{if }p<1,\\\ \log
n,&\mbox{if }p=1,\\\ 1,&\mbox{if
}p>1,\end{array}\right.\quad\left\\{\begin{array}[]{ll}\alpha({1-p}),&\mbox{if
}p<1,\\\ \alpha,&\mbox{if }p=1,\\\ B_{*},&\mbox{if }p>1.\end{array}\right.$

Proof For all $\epsilon>0$, there exits an $n(\epsilon)$ such that
$(\alpha-\epsilon)n^{p}<\psi(n)\rho^{n}<(\alpha+\epsilon)n^{p}$, so that for
all $n>n(\epsilon)$

$\sum_{i=1}^{n\epsilon)}\frac{1}{\psi(i)\rho^{i}}+\frac{1}{\alpha+\epsilon}\sum_{i=n(\epsilon)+1}^{n}\frac{1}{i^{p}}\leq[1-\mathbb{P}(\mathbf{Y}\leq
n)]^{-1}\leq\sum_{i=1}^{n\epsilon)}\frac{1}{\psi(i)\rho^{i}}+\frac{1}{\alpha+\epsilon}\sum_{i=n(\epsilon)+1}^{n}\frac{1}{i^{p}}.$

$\sum_{i}{i^{-p}}$ converges for $p>1$, $\sum_{i=1}^{n}{i^{-p}}$ behaves like
$\log n$ for $p=1$, and like $n^{1-p}$ for $p<1$, which yield the three cases
and corresponding constants $\gamma(p)$. $\Box$

Similar results may be obtained for other choices than $\psi(n)\rho^{n}\sim
n^{p}$ for the tail behaviour of $\psi(n)$, such as $\psi(n)\rho^{n}\sim
n(\log n)^{p}$ and $\psi(n)\rho^{n}\sim n\log n(\log\log n)^{p}$.

###  3.2 Weak convergence of sample maxima

We will focus on the recurrent cases $\overline{\beta}\rho<1$, and if $\beta$
exists on the cases $\beta\rho<1$ and $\beta\rho>1$, for which we show
stochastic compactness.

A necessary and sufficient condition for the sequence of sample maxima
$\mathbf{Y}^{(k)}$ to possess normalisation constants leading to a non-
degenerate limit is that $\lim_{x\rightarrow
x_{F}}\mathbb{P}(\mathbf{Y}>x)/\mathbb{P}(\mathbf{Y}\geq x)=1$ (Leadbetter et
al., 1983, Theorem 1.7.13). This condition is not satisfied for most discrete
valued distributions such as the Poisson distribution (Leadbetter et al.,
1983, Example 1.7.14), and the geometric distribution (Leadbetter et al.,
1983, Example 1.7.15), that are typically encountered as limiting distribution
of queues. For such systems we may obtain the $\liminf$ and $\limsup$ for the
distribution of the normalised sample maxima, similar to results presented in
Anderson (1970); Cohen (1982).

###### Theorem 4

Assume that $0\leq\overline{\beta}\rho<1$. Then there exists a continuous and
decreasing function $f:[0,\infty)\rightarrow[0,\infty)$ such that for
$-\infty<x<\infty$

$\displaystyle\liminf_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq
f^{-1}({\rm e}^{-x}/[(1-\underline{\beta}\rho)k]+1)\geq{\rm e}^{-{\rm
e}^{-x}},$ (10)
$\displaystyle\limsup_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq
f^{-1}({\rm e}^{-x}/[(1-\overline{\beta}\rho)k])\leq{\rm e}^{-{\rm e}^{-x}}.$
(11)

If in addition $\underline{\beta}>0$ then for $-\infty<x<\infty$

$\displaystyle\liminf_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq
f^{-1}({\rm e}^{-x}/[(1-\underline{\beta}\rho)k])\geq{\rm
e}^{-(\underline{\beta}\rho)^{-1}{\rm e}^{-x}}.$ (12)

Proof Consider the continuous function $g:[0,\infty)\rightarrow[0,\infty)$
obtained from $\psi(n)\rho^{n}$ by linear interpolation. As
$\liminf_{y\rightarrow\infty}g(y+1)/g(y)=\underline{\beta}$,
$\limsup_{y\rightarrow\infty}g(y+1)/g(y)=\overline{\beta}$, there exists an
$y_{0}$ such that $g(y)$ is decreasing for $y>y_{0}$. Set $f(y)=g(y)$, $y\geq
y_{0}$, and $f(y)=y_{0}-y+g(y_{0})$ for $0\leq y\leq y_{0}$. Then $f$ is
continuous and decreasing.

From (5), for all $\epsilon>0$ there exist an $n(\epsilon)$ such that for
$\max\\{y_{0},n(\epsilon)\\}<n\leq y<n+1$ we have $\mathbb{P}(\mathbf{Y}\leq
y)=\mathbb{P}(\mathbf{Y}\leq n)$ and

$1-((1-\underline{\beta}\rho)+\epsilon)f(y-1)\leq\mathbb{P}(\mathbf{Y}\leq
y)\leq 1-((1-\overline{\beta}\rho)-\epsilon)f(y)$ (13)

For $\overline{\beta}\geq 0$, insertion of

$y=f^{-1}({\rm e}^{-x}/[(1-\underline{\beta}\rho)k]),\quad y=f^{-1}({\rm
e}^{-x}/[(1-\overline{\beta}\rho)k]),$ (14)

in the left-hand and right-hand equalities in (13) yields (10) and (11).

If $\underline{\beta}>0$ then for all $\underline{\beta}\rho>\epsilon>0$ there
exists an $y(\epsilon)$ such that
$(\underline{\beta}-\epsilon)g(y)<g(y+1)<(\overline{\beta}-\epsilon)g(y)$,
which is inherited by $f(y)$ for $y\geq\max\\{y_{0},y(\epsilon)\\}$. For
$\max\\{y_{0},n(\epsilon),y(\epsilon)\\}<n\leq y<n+1$ we now obtain

$1-((1-\underline{\beta}\rho)+\epsilon)/(1-\underline{\beta}\rho)f(y-1)\leq\mathbb{P}(\mathbf{Y}\leq
y)\leq 1-((1-\overline{\beta}\rho)-\epsilon)f(y).$

Insertion of $y$ as specified in (14) yields (11) and (12). $\Box$

If $\beta$ exists, and $0<{\beta}\rho<1$, then there exist constants
$\\{a_{k}>0,~{}b_{k}\\}_{k\geq 1}$, $a_{k}$ bounded, $b_{k}\rightarrow\infty$
as $k\rightarrow\infty$, such that for $-\infty<x<\infty$

${\rm e}^{-({\beta}\rho)^{-1}{\rm
e}^{-x}}\leq\liminf_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq
a_{k}x+b_{k})\leq\limsup_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq
a_{k}x+b_{k})\leq{\rm e}^{-{\rm e}^{-x}},$ (15)

see Anderson (1970), with constants such that

$\lim_{k\rightarrow\infty}f^{-1}({\rm e}^{-y}/k)/(a_{k}y+b_{k})=1.$ (16)

This result (15) is not valid for $\overline{\beta}\neq\underline{\beta}$, as
the arguments of $f^{-1}$ in the $\liminf$ and $\limsup$ differ in Theorem 4.
In this case, constants $\\{a_{k}>0,~{}b_{k}\\}_{k\geq 1}$ for the $\liminf$
and $\limsup$ need not coincide.

The result (15) cannot be strengthened, that is
$\lim_{k\rightarrow\infty}\mathbb{P}(\mathbf{Y}^{(k)}\leq a_{k}x+b_{k})$ does
not exist, see (Serfozo, 1987, Theorem 2.3). We may show that every sequence
of sample maxima has a subsequence with limit between the upper and lower
bounds in (15) for fixed $x$. Stochastic compactness makes this precise and
shows that this limit yields a non-degenerate distribution.

######  Definition 5 (Stochastically compact (de Haan and Resnick (1984)))

The sequence of sample maxima $\mathbf{Y}^{(k)}$ is stochastically compact if
there exist constants $\\{a_{k}>0,~{}b_{k}\\}_{k\geq 1}$ such that every
sequence $\\{(\mathbf{Y}^{n(k)}-b_{n(k)})/a_{n(k)}\\}_{k\geq 1}$ contains a
subsequence whose distributions converge weakly to a non-degenerate
probability distribution. Such a limit distribution is called a partial limit
distribution. We will also call the distribution of $\mathbf{Y}$
stochastically compact if the above holds.

###### Theorem 6

If $\beta$ exists, and $0<\beta\rho<1$, then $\mathbb{P}(\mathbf{Y}\leq y)$ is
stochastically compact. The possible partial limit distributions are
$G(x)=\exp(-\exp(-x+\epsilon))$, $-\infty<x<\infty$, with
$\log(\beta\rho)\leq\epsilon\leq 0$.

Proof We will show that $\mathbb{P}(\mathbf{Y}\leq y)$ satisfies the
sufficient conditions in (de Haan and Resnick, 1984, Theorem 4): For some
$\delta>1$,

$\displaystyle\int_{x}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq
y))^{\delta-1}dy<\infty,$ (17)
$\displaystyle\liminf_{x\rightarrow\infty}\frac{\int_{x}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq
y))^{\delta}dy}{(1-\mathbb{P}(\mathbf{Y}\leq
x))\int_{x}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq y))^{\delta-1}dy}>0,$ (18)
$\displaystyle\limsup_{x\rightarrow\infty}\frac{\int_{x}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq
y))^{\delta}dy}{(1-\mathbb{P}(\mathbf{Y}\leq
x))\int_{x}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq y))^{\delta-1}dy}<1.$ (19)

These conditions are satisfied as a consequence of (6). Let
$0<\epsilon<\min\\{\beta\rho,(1-\beta\rho)\\}$. From (6) there exists an
$n(\epsilon)$ such that for all $n>n(\epsilon)$ we have
$((1-\beta\rho)-\epsilon)\psi(n)\rho^{n}\leq 1-\mathbb{P}(\mathbf{Y}\leq
n)\leq((1-\beta\rho)+\epsilon)\psi(n)\rho^{n}$, and
$(\beta\rho)-\epsilon)\psi(n)\rho^{n}<\psi(n+1)\rho^{n+1}<(\beta\rho)+\epsilon)\psi(n)\rho^{n}$.
Combination of these equalities and observing that $\mathbb{P}(\mathbf{Y}\leq
y)=\mathbb{P}(\mathbf{Y}\leq n)$ for $n\leq y<n+1$ shows that
$\mathbb{P}(\mathbf{Y}\leq y)$ satisfies (17) – (19). $\Box$

If $\beta$ exists, and $\beta=0$, from Lemma 1 we obtain that

$\lim_{n\rightarrow\infty}\frac{1-\mathbb{P}(\mathbf{Y}\leq
n-1)}{1-\mathbb{P}(\mathbf{Y}\leq
n)}=\frac{1}{\rho}\lim_{n\rightarrow\infty}\frac{\psi(n-1)}{\psi(n)}=\infty,$

and (de Haan and Resnick, 1984, Corollary 4) implies that
$\mathbb{P}(\mathbf{Y}\leq y)$ is not stochastically compact. In this case,
the bounds on the limiting distribution in Theorem 4 do not enable
characterisation of the limiting behaviour of $\mathbb{P}(\mathbf{Y}^{(k)}\leq
a_{k}x+b_{k})$.

The relation between (8) and (9), suggests that if $\beta$ exists, and
${\beta}\rho>1$ limiting results for the limiting distribution of
$\mathbf{Y}^{(k)}$ conditioned on $\mathbf{Y}^{(k)}<\infty$ are similar to
those of Theorem 6.

###### Theorem 7

If $\beta$ exists, and $1<\beta\rho<\infty$, then $\mathbb{P}(\mathbf{Y}\leq
y|\mathbf{Y}\leq\infty)$ is stochastically compact. The possible partial limit
distributions are $G(x)=\exp(-\exp(-x+\epsilon))$, $-\infty<x<\infty$, with
$-\log(\beta\rho)\leq\epsilon\leq 0$.

Proof Follows the lines of the proof of Theorem 6, but now using the
inequalities
$(\frac{1}{(\beta\rho-1)B_{*}(B_{*}-1)}-\epsilon)\frac{1}{\psi(n)\rho^{n}}\leq
1-\mathbb{P}(\mathbf{Y}\leq
y|\mathbf{Y}\leq\infty)\leq(\frac{1}{(\beta\rho-1)B_{*}(B_{*}-1)}+\epsilon)\frac{1}{\psi(n)\rho^{n}}$
and
$(\frac{1}{\beta\rho}-\epsilon)\frac{1}{\psi(n)\rho^{n}}<\frac{1}{\psi(n+1)\rho^{n+1}}<(\frac{1}{\beta\rho}+\epsilon)\frac{1}{\psi(n)\rho^{n}}$.
$\Box$

If $\beta$ exists, and $\beta=\infty$, we obtain from (de Haan and Resnick,
1984, Corollary 4) that $\mathbb{P}(\mathbf{Y}\leq y|\mathbf{Y}\leq\infty)$ is
not stochastically compact.

###  3.3 Almost sure convergence of sample maxima

We will assume that constants $\\{a_{k}>0,~{}b_{k}\\}_{k\geq 1}$, $a_{k}$
bounded, $b_{k}\rightarrow\infty$ as $k\rightarrow\infty$ exist such that (16)
is satisfied. Observe that $\\{b_{k}\\}_{k\geq 1}$ may then be chosen as
$b_{k}=f^{-1}(1/k)$.

The following result is a corollary of Theorem 4.

###### Corollary 8

Assume that $0\leq\overline{\beta}\rho<1$, and that the constants
$\\{a_{k}>0,~{}b_{k}\\}_{k\geq 1}$ satisfy (16). Then $\mathbf{Y}^{(k)}/b_{k}$
converges for $k\rightarrow\infty$ in probability to 1.

The proof is omitted as it follows standard lines as presented in (Galambos,
1987, Section 4.1), but deviates as the arguments $f^{-1}({\rm
e}^{-x}/[(1-\underline{\beta}\rho)k]+1)$ in (10) and $f^{-1}({\rm
e}^{-x}/[(1-\overline{\beta}\rho)k])$ in (11) are not identical.

If $\beta$ exists, and $0<\beta\rho<1$, the result of Corollary 8 may be
strengthened. The proof follows the lines of the proof of (Galambos, 1987,
Theorem 4.4.4), with the adaptation to incorporate the difference in the
constants $b_{k}$.

###### Theorem 9

Assume that $\beta$ exists, and $0<\beta\rho<1$. Let $b_{k}=\log
k/\log(1/\beta\rho)$. Then

$\mathbb{P}(\lim_{k\rightarrow\infty}\mathbf{Y}^{(k)}/b_{k}=1)=1.$

Proof Observe that $\sum_{n=1}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq tb_{k})$
diverges for all $t\leq 1$ and converges for all $t>1$, so that (Galambos,
1987, Theorem 4.4.1) implies that
$\mathbb{P}(\limsup_{k\rightarrow\infty}\mathbf{Y}^{(k)}/b_{k}=1)=1$.

Observe that $\sum_{n=1}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq
tb_{k}))\exp(-k(1-\mathbb{P}(\mathbf{Y}\leq tb_{k})))$ converges for all
$t<1$, so that (Galambos, 1987, Theorem 4.3.3) with $u_{k}=tb_{b}$ implies
that $\mathbb{P}(\liminf_{k\rightarrow\infty}\mathbf{Y}^{(k)}/b_{k}=1)=1$.
$\Box$

If $0<\underline{\beta}<\overline{\beta}$ we have the bounds
$\mathbb{P}(\limsup_{k\rightarrow\infty}\mathbf{Y}^{(k)}/\underline{b}_{k}\geq
1)=\mathbb{P}(\limsup_{k\rightarrow\infty}\mathbf{Y}^{(k)}/\overline{b}_{k}\leq
1)=1$, with $\underline{b}_{k}=\log k/\log(1/\underline{\beta}\rho)<\log
k/\log(1/\overline{\beta}\rho)=\overline{b}_{k}$, which is insufficient to
conclude the first part of the proof above. If $\overline{\beta}=0$ both parts
of the proof above fail. In that case we require the specific form of $f$ to
obtain convergence results for $\mathbf{Y}^{(k)}$. Below, we consider the
special case $f(x)\sim(\rho/x)^{x}$ as a natural extension of the geometric
case $f(x)\sim\rho^{x}$. This result includes the infinite-server queue.

###### Theorem 10

Let $f(x)=\alpha\gamma^{x}(1/x)^{x+\delta}$, $x>0$, with $\alpha>0$,
$\gamma>0$. Let $b_{k}=f^{-1}(1/k)$. If
$\lim_{n\rightarrow\infty}\mathbb{P}(\mathbf{Y}\leq n)/f(n)=1$, then

$\mathbb{P}(\lim_{k\rightarrow\infty}\mathbf{Y}^{(k)}/b_{k}=1)=1.$

Proof Exploring the form of $f$ and $b_{k}$, we readily find that
$\sum_{n=1}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq tb_{k})$ diverges for all
$t\leq 1$ and converges for all $t>1$, and that
$\sum_{n=1}^{\infty}(1-\mathbb{P}(\mathbf{Y}\leq
tb_{k}))\exp(-k(1-\mathbb{P}(\mathbf{Y}\leq tb_{k})))$ converges for all
$t<1$, so that we may apply (Galambos, 1987, Theorem 4.4.1) and (Galambos,
1987, Theorem 4.3.3). $\Box$

##  4 Examples

###  4.1 The multi-server queue

The birth-death process with birth rates $\lambda(n)=\lambda$,
$n=0,1,2,\ldots$, and death rates $\mu(n)=\min(n,s)\mu$, $n=1,2,\ldots$,
records the evolution of the number of customers in the
$M(\lambda)/M(\mu)/s$-queue, the multi-server queue with $s$ servers, that has
Poisson arrivals with rate $\lambda$ and exponential service requirements with
rate $\mu$. For $n=0,1,\ldots$,

$\psi(n)=\phi(n)=\left\\{\begin{array}[]{ll}\frac{1}{n!},&n\leq
s,\\\\[5.69054pt] \frac{s^{s-n}}{s!},&n>s,\end{array}\right.$

If $\rho/s<1$, we have $\pi_{\phi}(n)=\pi_{\psi}(n)=B_{\phi}\phi(n)\rho^{n}$,
$n=0,1,2,\ldots$. Clearly, $\beta$ exists, and $\beta=1/s$.

Lemmas 1 – 3 show that

$\displaystyle\lim_{n\rightarrow\infty}\left({\frac{s}{\rho}}\right)^{n}[1-\mathbb{P}(\mathbf{Y}\leq
n)]=\frac{s^{s}}{s!}(1-\rho/s)$ $\displaystyle\rho/s<1,$
$\displaystyle\lim_{n\rightarrow\infty}n[1-\mathbb{P}(\mathbf{Y}\leq
n)]=\frac{s^{s}}{s!}$ $\displaystyle\rho/s=1,$
$\displaystyle\lim_{n\rightarrow\infty}\left(\frac{\rho}{s}\right)^{n}[1-\mathbb{P}(\mathbf{Y}\leq
n|\mathbf{Y}<\infty)]=[\frac{s^{s}}{s!}(\frac{\rho}{s}-1)B_{*}(B_{*}-1)]^{-1},$
$\displaystyle\rho/s>1.$

If $\beta\rho=\rho/s<1$, Theorem 6 shows that $\mathbb{P}(\mathbf{Y}\leq y)$
is stochastically compact. The constants are $a_{k}=1/\log(s/\rho)$,
$b_{k}=(\log k)/\log(s/\rho)$. The partial limit distribution is
$G(x)=\exp(-\exp(-x+\epsilon))$, $-\infty<x<\infty$, with
$\log(\rho/s)\leq\epsilon\leq 0$. Theorem 9 shows that $\mathbf{Y}^{(k)}/\log
k$ converges to $\log(s/\rho)$ almost surely.

###  4.2 The infinite-server queue

The birth-death process with birth rates $\lambda(n)=\lambda$,
$n=0,1,2,\ldots$, and death rates $\mu(n)=n\mu$, $n=1,2,\ldots$, records the
evolution of the number of customers in the $M(\lambda)/M(\mu)/\infty$-queue,
the infinite-server queue, that has Poisson arrivals with rate $\lambda$ and
exponential service requirements with rate $\mu$. For $n=0,1,\ldots$,

$\psi(n)=\phi(n)=\frac{1}{n!}.$

We have $\pi_{\phi}(n)=\pi_{\psi}(n)=B_{\phi}\phi(n)\rho^{n}$,
$n=0,1,2,\ldots$. Clearly, $\beta$ exists, and $\beta=0$.

Lemma 1 shows that

$\lim_{n\rightarrow\infty}\frac{n!}{\rho^{n}}[1-\mathbb{P}(\mathbf{Y}\leq
n)]=1.$

This result does not appear as the limiting results for $s\rightarrow\infty$
in the multi-server queue. The factor $n!$ complicates the analysis of the
limiting behaviour. $\mathbb{P}(\mathbf{Y}\leq y)$ is not stochastically
compact. Bounds on the limiting distribution in Theorem 4 do not enable
characterisation of the limiting behaviour of $\mathbb{P}(\mathbf{Y}^{(k)}\leq
a_{k}x+b_{k})$.

Stirling’s formula for $n!$ shows that the function $f(x)$ in (16) is
$f(x)=\frac{1}{\sqrt{2\pi}}(\rho e)^{x}(1/x)^{x+{1\over 2}}$. The constants
are $b_{k}=\log k/\log\log k$, and $a_{k}=(\log
b_{k}+1/(2b_{k})-\log\rho)^{-1}$. Theorem 10 shows that
$\mathbf{Y}^{(k)}/(\log k/\log\log k)$ converges to 1 almost surely.

###  4.3 Kelly-Whittle network of queues

The Markov chain $(X(t),~{}t\geq 0)$ at state space
$S=\\{0,1,2,\ldots\\}^{J}$, with states ${\bf n}=(n_{1},\ldots,n_{J})$, and
transition rates, for ${\bf n}^{\prime}\neq{\bf n}$,

$q({\bf n},{\bf
n}^{\prime})=\left\\{\begin{array}[]{ll}{\displaystyle\mu_{i}\frac{\psi({\bf
n}-{\bf e}_{i})}{\phi({\bf n})}p_{ij}},&\mbox{if~{}}{\bf n}^{\prime}={\bf
n}-{\bf e}_{i}+{\bf e}_{j},~{}i,j=0,\ldots,J,\\\\[8.53581pt]
0,&\mbox{otherwise,}\end{array}\right.$

where ${\bf e}_{i}$ is the $i$-th unit vector, $i=1,\ldots,J$, ${\bf e}_{0}$
the zero-vector, $\psi:S\rightarrow(0,\infty)$ and
$\phi:S\rightarrow(0,\infty)$, records the evolution of the number of
customers in the queues of an open Kelly-Whittle network (Boucherie and van
Dijk (1991); Henderson and Taylor (1990)). If the routing matrix
$P=(p_{ij},~{}i,j=0,\ldots,J)$ is irreducible, the traffic equations
$\lambda_{j}=p_{0j}+\sum_{i=1}^{J}\lambda_{i}p_{ij}$, $j=1,\ldots,J$, have a
unique solution. Let $\rho_{j}=\lambda_{j}/\mu_{j}$, $j=1,\ldots,J$. If
$B_{\phi,KW}^{-1}=\sum_{{\bf n}\in S}\phi({\bf
n})\prod_{j=1}^{J}(\mu_{0}\rho_{j})^{n_{j}}<\infty,$ then $(X(t),~{}t\geq 0)$
is positive recurrent with unique limiting distribution $\pi_{\phi}({\bf
n})=B_{\phi,KW}\phi({\bf n})\prod_{j=1}^{J}(\mu_{0}\rho_{j})^{n_{j}}$, ${\bf
n}\in S$, see Boucherie and van Dijk (1993). If $B_{\psi,KW}^{-1}=\sum_{{\bf
n}\in S}\psi({\bf n})\prod_{j=1}^{J}(\mu_{0}\rho_{j})^{n_{j}}<\infty,$ then
$(X(t),~{}t\geq 0)$ is recurrent with limiting distribution at arrival epochs
of a customer at a station $\pi_{\psi}({\bf n})=B_{\psi,KW}\psi({\bf
n})\prod_{j=1}^{J}(\mu_{0}\rho_{j})^{n_{j}}$, ${\bf n}\in S$, see Boucherie
and van Dijk (1997).

We are interested in the generic cycle maximum $\mathbf{Y}$ of the total
number of customers in the network, $N=\sum_{i=1}^{J}n_{i}$. To this end, for
$N=0,1,2,\ldots$, let

$\Psi(N)=\sum_{\\{{\bf n}:\sum_{i=1}^{J}n_{i}=N\\}}\psi({\bf
n})\prod_{j=1}^{J}\rho_{j}^{n_{j}},\quad\Phi(N)=\sum_{\\{{\bf
n}:\sum_{i=1}^{J}n_{i}=N\\}}\phi({\bf n})\prod_{j=1}^{J}\rho_{j}^{n_{j}}.$

Norton’s theorem shows that the birth-death process at $S=\\{0,1,2,\ldots\\}$
with birth and death rates

$\lambda(N)=\mu_{0}\frac{\Psi(N)}{\Phi(N)},\mbox{ and
}\mu(N)=\frac{\Psi(N-1)}{\Phi(N)}$

records the evolution of the total number of customers in the network of
queues, see (Boucherie and van Dijk, 1993, Theorem 6.4). Thus, the generic
cycle maximum $\mathbf{Y}$ has distribution $\mathbb{P}(\mathbf{Y}\leq
N)=1-\left[\sum_{i=0}^{N}(\Psi(i)\mu_{0}^{i})^{-1}\right]^{-1}$,
$N=1,2,\ldots$.

The tail behaviour of the cycle maximum is determined by
$\Psi(N)=\sum_{\\{{\bf n}:\sum_{i=1}^{J}n_{i}=N\\}}\psi({\bf
n})\prod_{j=1}^{J}\rho_{j}^{n_{j}}$, which coincides with the normalising
constant of a closed Kelly-Whittle network at state space $S_{N}=\\{{\bf
n}:\sum_{i=1}^{J}n_{i}=N\\}$, with transition rates $q({\bf n},{\bf
n}^{\prime})=\mu_{i}\frac{\psi({\bf n}-{\bf e}_{i})}{\psi({\bf n})}p_{ij}$, if
${\bf n}^{\prime}={\bf n}-{\bf e}_{i}+{\bf e}_{j}$, $i,j=1,\ldots,J$. The
limiting distribution is $\pi_{\psi,N}({\bf n})=\Psi(N)^{-1}\psi({\bf
n})\prod_{j=1}^{J}\rho_{j}^{n_{j}}$. The normalising constant for closed
networks is well-studied in literature. Its asymptotic behaviour is available
for several special cases, including networks comprised of multi-server and
infinite-server queues.

####  4.3.1 Network of infinite-server queues

If all queues are infinite-server queues, then $\phi({\bf n})=\psi({\bf
n})=\prod_{i=1}^{J}1/n_{i}!$, and $\Phi(N)=\Psi(N)=(\sum_{j}\rho_{J})^{N}/N!$.
Alternatively, we may write the birth and death rates as
$\lambda(N)=\lambda\frac{\widehat{\Psi}(N)}{\widehat{\Phi}(N)}$, and
$\mu(N)=\mu\frac{\widehat{\Psi}(N-1)}{\widehat{\Phi}(N)}$, with
$\lambda=\mu_{0}$, $\mu=1/\sum_{j}\rho_{j}$,
$\widehat{\Phi}(N)=\widehat{\Psi}(N)=1/N!$. Section 4.2 presents the limiting
results.

####  4.3.2 Network of single-server queues

If all queues are single-server queues, then $\phi({\bf n})=\psi({\bf n})=1$,
and $\Phi(N)=\Psi(N)=\sum_{\\{{\bf
n}:\sum_{i=1}^{J}n_{i}=N\\}}\prod_{j=1}^{J}\rho_{j}^{n_{j}}$. If all
$\rho_{j}$ are distinct, from (Harrison, 1985, Theorem 1),
$\Psi(N)=\sum_{j=1}^{J}\rho_{j}^{N+J-1}/\prod_{i\neq j}(\rho_{j}-\rho_{i})$.

We obtain that $\beta$ exists, and $\beta=\max\\{\rho_{1},\ldots,\rho_{J}\\}$.
If $\beta\mu_{0}<1$, then
$\lim_{N\rightarrow\infty}(\Psi(N)\mu_{0}^{N})/(\beta\mu_{0})^{N}=c$, for some
constant $c$. Theorem 6 shows that $\mathbb{P}(\mathbf{Y}\leq y)$ is
stochastically compact. The constants are $a_{k}=1/\log(1/(\beta\mu_{0}))$ and
$b_{k}=\log k/\log(1/(\beta\mu_{0}))$. The partial limit distribution is
$G(x)=\exp(-\exp(-x+\epsilon))$, $-\infty<x<\infty$, with
$\log(\beta\mu_{0})\leq\epsilon\leq 0$. Theorem 9 shows that
$\mathbf{Y}^{(k)}/\log k$ converges to $\log(1/(\beta\mu_{0}))$ almost surely.

####  4.3.3 Network of multi-server and infinite-server queues

If the network contains single-server, multi-server and infinite-server
queues, an explicit expression for $\Phi(N)=\Psi(N)$ is not available in
closed form. Asymptotic results are available in literature, see e.g., (George
et al., 2012, Theorem 4), where it shown that
$\lim_{N\rightarrow\infty}\Psi(N)/\max\\{\nu_{1},\ldots,\nu_{J}\\}^{N})=c$,
for some constant $c$, with $\nu_{i}=\rho_{i}/s_{i}$ all distinct, and $s_{i}$
the number of available servers at the station. Note that the term
$\max\\{\nu_{1},\ldots,\nu_{J}\\}^{N}$ does not appear in (George et al.,
2012, Theorem 4) as in that theorem the $\nu_{j}$ are scaled such that
$\max\\{\nu_{1},\ldots,\nu_{J}\\}=1$.

We obtain that $\beta$ exists, and $\beta=\max\\{\nu_{1},\ldots,\nu_{J}\\}$.
If $\beta\mu_{0}<1$, then
$\lim_{N\rightarrow\infty}(\Psi(N)\mu_{0}^{N})/(\beta\mu_{0})^{N}=c$, for some
constant $c$. Theorem 6 shows that $\mathbb{P}(\mathbf{Y}\leq y)$ is
stochastically compact. The constants are $a_{k}=1/\log(1/(\beta\mu_{0}))$ and
$b_{k}=\log k/\log(1/(\beta\mu_{0}))$. The partial limit distribution is
$G(x)=\exp(-\exp(-x+\epsilon))$, $-\infty<x<\infty$, with
$\log(\beta\mu_{0})\leq\epsilon\leq 0$. Theorem 9 shows that
$\mathbf{Y}^{(k)}/\log k$ converges to $\log(1/(\beta\mu_{0}))$ almost surely.

####  4.3.4 Network with identical load parameters

We may also evaluate $\Psi(N)$ if some of the load parameters coincide. For
the network of single server queues explicit expressions are available in
(Harrison, 1985, Theorem 2). For the network containing single-server, multi-
server and infinite-server stations an asymptotic expression is available in
(George et al., 2012, Theorem 4), where it shown that
$\lim_{N\rightarrow\infty}\Psi(N)/(N^{|B|-1}\max\\{\nu_{1},\ldots,\nu_{J}\\}^{N})=c$,
for some constant $c$, with
$B=\\{j:\nu_{j}=\max\\{\nu_{1},\ldots,\nu_{J}\\}\\}$. If two parameters
coincide, we may use the Lambert $W$ function (see Corless et al. (1996)) to
approximate the inverse of $f(y)=y(\beta\mu_{0})^{y}$, with
$\beta=\max\\{\nu_{1},\ldots,\nu_{J}\\}$. If $B$ parameters coincide the
inverse of $f(y)=y^{|B|-1}(\beta\mu_{0})^{y}$ must be evaluated.

##  5 Concluding remarks

The result presented in this paper build upon classical results from extremal
value theory for discrete distributions (Anderson (1970); Vervaat (1973)), and
birth-death processes (Asmussen (1998); Cohen (1982)). The results are applied
to study convergence of the sequence of partial maxima for single queues and
open Kelly-Whittle networks of queues. The latter results rely on an amenable
expression for the normalising constant for suitably defined closed networks.
Such expressions are available for networks of single-server, multi-server and
infinite-server queues with distinct load parameters.

The results may readily be generalised to networks with state-dependent
routing (Boucherie and van Dijk (1993)). For positive recurrent networks of
quasi-reversible queues the birth and death rates may also be obtained using
Norton’s theorem, see Boucherie (1998). Careful analysis of these birth and
death rates is required to determine the asymptotic behaviour of these rates,
and hence the limiting behaviour of the sequence of sample maxima.

## Acknowledgements

The author is grateful to prof. J.W. Cohen for inspiring discussions on the
dual relation between the discrete failure rate
$\mathbb{P}(\mathbf{Y}=n|\mathbf{Y}\geq n)$ and the blocking probability
$\mathbb{P}(\mathbf{X}=n|\mathbf{X}\leq n)$ that led to this research. The
results for birth-death processes presented in the unpublished report
(Boucherie (1994)), are now extended to open networks of queues.

## References

  * Asmussen [1998] Søren Asmussen.  Extreme value theory for queues via cycle maxima.  _Extremes_ , 1(2):137–168, 1998.  doi:10.1023/A:1009970005784.  URL https://doi.org/10.1023/A:1009970005784.
  * Boucherie and van Dijk [1991] Richard J. Boucherie and Nico M. van Dijk.  Product forms for queueing networks with state-dependent multiple job transitions.  _Advances in Applied Probability_ , 23(1):152–187, 1991.  ISSN 00018678.  URL http://www.jstor.org/stable/1427516.
  * Henderson and Taylor [1990] W. Henderson and P. G. Taylor.  Product form in networks of queues with batch arrivals and batch services.  _Queueing Systems_ , 6(1):71–87, 1990.  doi:10.1007/BF02411466.  URL https://doi.org/10.1007/BF02411466.
  * Boucherie and van Dijk [1993] Richard J. Boucherie and Nico M. van Dijk.  A generalization of Norton’s theorem for queueing networks.  _Queueing Systems_ , 13(1):251–289, 1993.  doi:10.1007/BF01158934.  URL https://doi.org/10.1007/BF01158934.
  * Harrison [1985] P. G. Harrison.  Technical note—On normalizing constants in queueing networks.  _Operations Research_ , 33(2):464–468, 1985.  doi:10.1287/opre.33.2.464.  URL https://doi.org/10.1287/opre.33.2.464.
  * George et al. [2012] David K. George, Cathy H. Xis, and Mark S. Squillante.  Exact-order asymptotic analysis for closed queueing networks.  _Journal of Applied Probability_ , 49(2):503–520, 2012.  ISSN 00219002.  URL http://www.jstor.org/stable/41713782.
  * Cohen [1971] J. W. Cohen.  Technical note—On a formula dual to Erlang’s loss formula.  _Operations Research_ , 19(7):1759–1760, 1971\.  doi:10.1287/opre.19.7.1759.  URL https://doi.org/10.1287/opre.19.7.1759.
  * Takács [1962] Lajos Takács.  _Introduction to the theory of queues._ Oxford University Press, New York, 1962.  ISBN 0313233578 9780313233579.
  * Niu and Cooper [1989] Shun-Chen Niu and Robert B. Cooper.  Duality and other results for M/G/1 and GI/M/1 queues, via a new ballot theorem.  _Mathematics of Operations Research_ , 14(2):281–293, 1989.  ISSN 0364765X, 15265471.  URL http://www.jstor.org/stable/3689707.
  * Kimura [1993] Toshikazu Kimura.  Duality between the Erlang loss system and a finite source queue.  _Operations Research Letters_ , 13(3):169–173, 1993.
  * Bekker and Zwart [2005] René Bekker and Bert Zwart.  On an equivalence between loss rates and cycle maxima in queues and dams.  _Probability in the Engineering and Informational Sciences_ , 19(2):241–255, 2005.  doi:10.1017/S0269964805050138.
  * Boxma and Perry [2009] Onno J. Boxma and David Perry.  On the cycle maximum of mountains, dams and queues.  _Communications in Statistics - Theory and Methods_ , 38(16-17):2706–2720, 2009.  doi:10.1080/03610910902936232.  URL https://doi.org/10.1080/03610910902936232.
  * Serfozo [1987] Richard F. Serfozo.  Extreme values of birth and death processes and queues.  _Stochastic Processes and their Applications_ , 27:291–306, 1987.  ISSN 0304-4149.  doi:https://doi.org/10.1016/0304-4149(87)90043-3.  URL https://www.sciencedirect.com/science/article/pii/0304414987900433.
  * Anderson [1970] C. W. Anderson.  Extreme value theory for a class of discrete distributions with applications to some stochastic processes.  _Journal of Applied Probability_ , 7(1):99–113, 1970.  ISSN 00219002.  URL http://www.jstor.org/stable/3212152.
  * Cohen [1982] J. W. Cohen.  _The single server queue_.  North-Holland Pub. Co Amsterdam, 1982.
  * Vervaat [1973] Wim Vervaat.  Limit theorems for records from discrete distributions.  _Stochastic Processes and their Applications_ , 1(4):317–334, 1973.  ISSN 0304-4149.  doi:https://doi.org/10.1016/0304-4149(73)90015-X.  URL https://www.sciencedirect.com/science/article/pii/030441497390015X.
  * de Haan and Resnick [1984] L. de Haan and S. I. Resnick.  Asymptotically balanced functions and stochastic compactness of sample extremes.  _The Annals of Probability_ , 12(2):588–608, 1984\.  ISSN 00911798.  URL http://www.jstor.org/stable/2243489.
  * Foster [1953] F. G. Foster.  On the stochastic matrices associated with certain queuing processes.  _The Annals of Mathematical Statistics_ , 24(3):355–360, 1953.  ISSN 00034851.  URL http://www.jstor.org/stable/2236286.
  * Brumelle [1978] Shelby L. Brumelle.  A generalization of erlang’s loss system to state dependent arrival and service rates.  _Mathematics of Operations Research_ , 3(1):10–16, 1978.  ISSN 0364765X, 15265471.  URL http://www.jstor.org/stable/3689615.
  * Al Hanbali and Boxma [2010] Ahmad Al Hanbali and Onno Boxma.  A busy period analysis for the state dependent M/M/1/K queue.  _Operations research letters_ , 38(1):1–6, 2010\.  ISSN 0167-6377.  doi:10.1016/j.orl.2009.09.012.
  * Leadbetter et al. [1983] M. R. Leadbetter, G. Lindgren, and H. Rootzen.  _Extremes and Related Properties of Random Sequences and Processes_.  Springer Series in Statistics. Springer Verlag, 1983.  ISBN 0387907319.  URL http://www.amazon.de/Extremes-Properties-Sequences-Processes-Statistics/dp/0387907319/ref=sr_1_1?ie=UTF8&qid=1315901112&sr=8-1.
  * Galambos [1987] Janos Galambos.  _The asymptotic theory of extreme order statistics_.  R.E. Krieger Pub. Co., Malabar, Fla., 1987.  ISBN 0898749573 9780898749571.
  * Boucherie and van Dijk [1997] Richard J. Boucherie and Nico M. van Dijk.  On the arrival theorem for product form queueing networks with blocking.  _Performance Evaluation_ , 29(3):155–176, 1997\.  ISSN 0166-5316.  doi:https://doi.org/10.1016/S0166-5316(96)00045-4.  URL https://www.sciencedirect.com/science/article/pii/S0166531696000454.
  * Corless et al. [1996] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth.  On the lambert W function.  _Advances in Computational Mathematics_ , 5(1):329–359, 1996.  doi:10.1007/BF02124750.  URL https://doi.org/10.1007/BF02124750.
  * Boucherie [1998] Richard J. Boucherie.  Norton’s equivalent for queueing networks comprised of quasireversible components linked by state-dependent routing.  _Performance Evaluation_ , 32(2):83–99, 1998\.  ISSN 0166-5316.  doi:https://doi.org/10.1016/S0166-5316(97)00017-5.  URL https://www.sciencedirect.com/science/article/pii/S0166531697000175.
  * Boucherie [1994] Richard J. Boucherie.  On the maximum number of customers simultaneously present in a queue.  _Unpublished report_ , 1994.