# BEAM–BEAM AND IMPEDANCE††thanks: Work partially supported by Brookhaven
Science Associates, LLC under Contract No. DE-AC02-98CH10886 with the U.S.
Department of Energy, and in part by the U.S. LHC Accelerator Research
Program.

S. White  Brookhaven National Laboratory  Upton  NY  USA
X. Buffat  EPFL  Lausanne  Switzerland; CERN  Geneva  Switzerland

###### Abstract

As two counter-rotating beams interact they can give rise to coherent dipole
modes. Under the influence of impedance these coherent beam–beam modes can
couple to higher order head–tail modes and lead to strong instabilities. A
fully self-consistent approach including beam–beam and impedance was used to
characterize this new coupled mode instability and study possible cures such
as a transverse damper and high chromaticity.

##  1 Introduction

In a high-energy, high-brightness hadron collider, the coherent dynamics of
colliding beams is dominated by beam–beam interactions. The non-linearities of
the beam–beam force introduce a tune spread largely exceeding the one from
other sources, such as non-linear fields, and provide sufficient stability for
any pure impedance instabilities. When they interact with each other, the two
beams will couple, resulting in coherent oscillations. In the case of equal
beams and tunes these coherent oscillations can be described by two
eigenmodes, corresponding to either in-phase or out-of-phase oscillation,
respectively the $\sigma$\- and $\pi$-modes. The frequency of these modes may
be well separated from the incoherent tune spread and consequently they do not
profit from the large intrinsic Landau damping properties of the beam–beam
interactions. Such coherent beam–beam modes are generally not self-excited and
require some external mechanism to become unstable, such as the machine
impedance. When studying the stability of colliding beams, it is therefore
necessary to consider both processes simultaneously.

Past studies have shown that the combination of beam–beam interactions and
impedance could lead to coherent instabilities. However, these studies were
performed either using a linearized model [1] or for very specific cases
applied to the Tevatron [2]. During the 2012 proton run of the LHC, coherent
instabilities were routinely observed [3], triggering a renewed interest to
pursue these studies. In this paper, we present a refined model allowing one
to study the interplay of beam–beam and impedance using the full LHC impedance
model [4]. We will concentrate mostly on single-bunch effects and associated
stabilization techniques and present preliminary results for multibunch
effects.

##  2 Models

Two models were used to characterize the interplay of beam–beam and impedance:

  * •

An analytical model based on the circulant matrix approach used in Ref. [1]

  * •

A fully self-consistent multiparticle tracking model. Single-bunch effects
were studied with the code BeamBeam3D [5] and multibunch effects with the code
COMBI [6]

The circulant matrix model (CMM) allows one to compute the complex tune shift
in the presence of six-dimensional beam–beam interactions, impedance,
chromaticity and transverse damper. The bunches are sliced in the longitudinal
phase space and the beam–beam kicks are computed with the linearized
approximation. Landau damping is not included in this model but the
computation of the eigenmodes is very fast allowing for extensive parameter
scans. This provides an excellent tool for understanding the coherent beam
dynamics in the presence of various physics processes. This approach is very
fast and most appropriate for extensive parameter scans, which provide a good
understanding of the coherent dynamics in the presence of various processes.
While much more demanding in terms of computing power, tracking simulations
are a necessary complement to the CMM. Indeed, the CMM is not a self-
consistent approach, giving rise to differences in the frequencies of
beam–beam coherent modes. In simple cases, the beam–beam parameter can be re-
scaled in order to compensate for the change of frequency of the modes due to
lack of self-consistency. In more complex configurations, this approximation
needs to be tested against a self-consistent model. Also, the CMM is not
suited to study any non-linear effect, in particular Landau damping. Indeed,
even though the complex tune shift can be computed, the dispersion integral
used to derive the stability of a pure impedance mode is not valid for a
beam–beam coherent mode. An analytical derivation of a dispersion integral in
LHC-type configurations promises to be a great challenge, in particular in the
multibunch regime, i.e. in the presence of PACMAN effects. A numerical
approach, by the means of self-consistent multiparticle tracking codes, allows
one to address these issues. Moreover, such approach allows one to treat any
other non-linear effects, e.g. transverse feedback imperfections or external
noise. BeamBeam3D and COMBI (COherent Multi-Bunch Instabilities) are two
similar implementations of such model, based on different multicore
parallelization concepts.

Figure 1: Synchro–betatron modes as a function of the beam–beam parameter for
$Q^{\prime}=0.0$ and $\beta^{*}/\sigma_{s}\approx 100$. Impedance was not
included in this case. The $\sigma$\- and $\pi$-modes are shown in red. Figure
2: Synchro–betatron modes as a function of the beam–beam parameter for
$Q^{\prime}=0.0$ and $\beta^{*}/\sigma_{s}\approx 1$. Impedance was not
included in this case. The $\sigma$\- and $\pi$-modes are shown in red.

Figures 1 and 2 show the tunes of the synchro–betatron modes up to the third
sideband in the presence of a six-dimensional beam–beam interaction. When the
synchro–betatron coupling introduced by the beam–beam interaction is
negligible ($\beta^{*}/\sigma_{s}>>1$), there is no cross talk between higher
order head–tail modes and the coherent beam–beam $\sigma$\- and $\pi$-modes.
The tune of the sidebands is shifted by the coherent beam–beam tune shift,
which is approximately equal to $\xi/2$ in this case. When the
synchro–betatron coupling becomes important ($\beta^{*}/\sigma_{s}\approx 1$),
the synchrotron sidebands are now deflected when their frequency approaches
the frequency of the coherent beam–beam modes, indicating possible coupling
between the coherent beam–beam dipolar modes and higher order head–tail modes.
In both cases, the imaginary part of the tune shifts of all modes is equal to
zero: in the presence of beam–beam interactions only, the system is always
stable.

Figure 3: Synchro–betatron modes as a function of the beam–beam parameter for
$Q^{\prime}=0.0$ and $\beta^{*}/\sigma_{s}\approx 1$. Comparison between the
CMM and BeamBeam3D. Impedance was not included in this case.

Figure 3 shows a comparison between the tracking code BeamBeam3D and the CMM
for $\beta^{*}/\sigma_{s}\approx 1$. The CMM was re-scaled by the Yokoya
factor to match the tracking results. An excellent agreement is observed and
one can see that the frequency of the modes is modified when the beam–beam
coherent modes cross the first sidebands. The frequency components between the
$\sigma$\- and $\pi$-modes observed in the tracking correspond to the
beam–beam tune spread.

The implementation of impedance in BeamBeam3D was fully benchmarked with the
HEADTAIL code [7]. In order to validate the implementation of the LHC
impedance model into the the CMM, we compared the rise times as a function of
chromaticity for an airbag distribution. The results are shown in Fig. 4,
where an excellent agreement is observed. The implementation of the LHC
impedance model in COMBI was also benchmarked against multibunch HEADTAIL [4];
nevertheless, this development is rather recent and only preliminary results
are presented.

Figure 4: Imaginary part of the tune shift as a function of chromaticity for
the CMM and BeamBeam3D. In both models an airbag distribution was used.

##  3 Mode coupling instability of colliding beams

We start by looking at the simple case of two single bunches colliding head-on
in one interaction point (IP). The impedance model used in the following
simulations was derived using the 2012 LHC lattice and collimator settings
[4]. The beam–beam interactions are computed with a full six-dimensional model
taking into account the synchro–betatron effects and eventual non-Gaussian
transverse distributions. In order to estimate the beam stability for a large
number of beam parameters, multiparticle tracking is performed over 10000
turns and each case is analysed using an interpolated FFT algorithm. The beam
stability of any given mode can then be assessed by looking at the amplitude
of its corresponding spectral line.

Figure 5: Synchro–betatron modes as a function of the beam–beam parameter for
$Q^{\prime}=0.0$ and $\beta^{*}/\sigma_{s}\approx 90$. The colours correspond
to the amplitude of the spectral line. Impedance was set to be constant over
the whole scan. Figure 6: Imaginary part of the tune shift of the most
unstable modes as a function of the beam–beam parameter for $Q^{\prime}=0.0$
and $\beta^{*}/\sigma_{s}\approx 90$. Impedance was set to be constant over
the whole scan.

Figures 5 and 6 show a scan in the beam–beam parameter at constant impedance.
As the beam–beam $\pi$-mode approaches the head–tail mode –1 ($\xi\approx
0.003$), they become coupled, leading to a strong instability with similar
rise times and characteristics to the impedance-driven TMCI (Transverse Mode
Coupling Instability). This is observed in both the tracking and CMM with
comparable rise times. The CMM also indicates a coupling between the
$\sigma$-mode and the head–tail mode +1. This is not observed in the tracking
simulations; the reasons for this discrepancy are under investigation but
could be related to Landau damping, which is not taken into account in the
CMM. The strength of this coupling instability and the range in terms of $\xi$
over which the modes couple are determined by the strength of the wake and the
$\beta$-function at the IP.

Figure 7: Synchro–betatron modes as a function of the beam–beam parameter for
$Q^{\prime}=0.0$ and $\beta^{*}/\sigma_{s}\approx 1$. The colours correspond
to the amplitude of the spectral line. Impedance was set to be constant over
the whole scan.

Figure 7 shows a scan in the beam–beam parameter using the same beam
parameters as in Fig. 5 except for the ratio $\beta^{*}/\sigma_{s}$. A ratio
$\beta^{*}/\sigma_{s}\approx 1$ introduces synchro–betatron coupling from the
beam–beam interaction itself. In this case, as was shown in Fig. 2, the
synchrotron sidebands can be deflected by the beam–beam modes. For strong
synchro–betatron coupling the most unstable modes involved in the coupling
instability (shown in green in Figs. 5 and 7) are not overlapping any higher
order head–tail modes. This results in a suppression of the mode coupling
instability observed for higher $\beta^{*}/\sigma_{s}$ ratios.
Synchro–betatron coupling also increases the Landau damping introduced by the
beam–beam interactions. It was shown in Ref. [8] that when the synchrotron
tune is of the order of the beam–beam parameter and significant
synchro–betatron coupling is present, the tune spread of the lower order
sidebands can overlap the $\pi$-mode and damp it. This effect could be
reproduced in simulations [9] and may be useful in the case where coherent
beam–beam mode stability becomes an issue for machines operating at low
$\beta^{*}/\sigma_{s}$ ratio.

Figure 8: Synchro–betatron modes as a function of the transverse separation
for $Q^{\prime}=0.0$ and $\beta^{*}/\sigma_{s}\approx 90$. The colours
correspond to the amplitude of the spectral line. Impedance and beam–beam
parameters were set to be constant over the whole scan.

Colliding with transverse offsets changes the frequency of the beam–beam
coherent modes and modifies the stability diagram [10]. Offset collisions can
occur while bringing the beam into collisions, in the first moments of a
physics store before the luminosity is optimized or when levelling the
luminosity, as was routinely done at the LHC in 2012 [11]. Figure 8
illustrates a scan in separation (only the separation plane is shown)
including coherent beam–beam and impedance. The mode coupling instability is
observed when either the $\pi$-mode overlaps the head–tail mode –1 or the
$\sigma$-mode overlaps the head–tail mode +1 at separations between 1.0 and
2.0 $\sigma$. These instabilities also occur when the stability diagram
reaches its minimum [10]. This was tested in a dedicated experiment [12]
during which instabilities were observed at small separations while the beam
was fully stable when colliding head-on. Weak–strong simulations with single-
plane offset indicate that the stability can be shared between the horizontal
and vertical planes preventing any loss of Landau damping and consequently any
impedance-only-driven instabilities to rise. This experiment, although not
fully conclusive, appears to confirm the existence of the mode coupling
instability involving coherent beam–beam modes. Experimental data and detailed
analysis can be found in Ref. [12].

It is worth mentioning that mode coupling instabilities can also occur for
long-range interactions when the tune shift is sufficiently high. In the case
of the LHC, the $\beta$-functions at the location of the long-range
interactions can reach several kilometers, discarding any benefits from
synchro–betatron coupling, and this therefore represents the worst-case
scenario for this specific mode coupling instability. With the 2012 LHC beam
parameters the tune shift at which the instability occurs is reached for
approximately 10 long-range interactions, as shown in Fig. 9. This number has
to be compared to 16 long-range interactions per IP in the case of nominal LHC
bunches, indicating that PACMAN bunches are the most critical ones. The
instability observed for 15 long-range interactions is originating from the
other plane.

Figure 9: Synchro–betatron modes as a function of the number of long-range
interactions for a single colliding IP. All the long-range interactions were
lumped in one location for which a separation of 10 $\sigma$ was assumed.

Figure 9 represents the simplified case of a single IP colliding, where all
the interactions were lumped in one place. In reality, multibunch effects and
the phase advance between consecutive IPs will modify the situation and should
be considered in any realistic simulations of the LHC.

##  4 Stabilization of single-bunch instabilities

Chromaticity combined with tune spread (to provide Landau damping) is
generally used to cure transverse instabilities. In the specific case of the
LHC, the bunch-by-bunch transverse damper can also be used for this purpose.
In order get a better understanding of how these parameters affect the
coherent beam dynamics, we start with the CMM. All the following simulations
were performed using beam parameters corresponding to the most critical
configuration, where the transverse mode coupling instability is the
strongest.

Figure 10: Real and imaginary parts of the tune shift as a function of the
beam–beam parameters for a single bunch colliding head-on at $Q^{\prime}=0.0$
(top), $Q^{\prime}=2.0$ (middle) and $Q^{\prime}=10.0$ (bottom). Here the
ratio $\beta^{*}/\sigma_{s}\approx 70$.

Figure 10 shows the real and imaginary tune shifts for a single bunch
colliding head-on computed using the CMM for increasing chromaticity. At
$Q^{\prime}=0.0$, the modes are fully coupled and the instability develops
similarly to what was previously shown in Figs. 5 and 6. As the chromaticity
is increased the frequencies of the modes involved in the instability are
separated until they fully decouple for $Q^{\prime}=10.0$. Chromaticity should
therefore help mitigating the mode coupling instability. However, the larger
the ratio $\beta^{*}/\sigma_{s}$, the higher the chromaticity required to
decouple the modes. Operating with too large chromaticity may degrade beam
lifetime. For very large ratio $\beta^{*}/\sigma_{s}$, which is typically the
case for long-range interactions, using chromaticity only may therefore not be
appropriate to cure this instability.

Figure 11: Real and imaginary parts of the tune shift as a function of the
beam–beam parameters for a single bunch colliding head-on at $G=0.0$ (top),
$G=0.001$ (middle) and $G=0.01$ (bottom). Here the ratio
$\beta^{*}/\sigma_{s}\approx 8$. The gain $G$ is specified in 1/turns.

Figure 11 shows the real and imaginary tune shifts for a single bunch
colliding head-on computed using the CMM for increasing transverse damper
gain. The damper is assumed to be an ideal rigid bunch damper for which the
gain is defined in 1/turns. The damper is most efficient on modes with a
significant dipolar component, such as head–tail mode 0. If Landau damping is
sufficient to damp higher order modes, which is generally the case for
colliding beams, the transverse damper should be a very efficient means to
cure the instability without having to run at unrealistically high gain.

Figure 12: Centre of mass motion for a single bunch colliding head-on with
$\beta^{*}/\sigma_{s}\approx 8$ and increasing $Q^{\prime}$. Figure 13:
Instability rise time for a single bunch colliding head-on with
$\beta^{*}/\sigma_{s}\approx 30$ and $\beta^{*}/\sigma_{s}\approx 110$ as a
function of $Q^{\prime}$.

As mentioned before, the CMM does not include Landau damping. In order to
assess beam stability including Landau damping, multiparticle simulations are
required. Figures 12 and 13 show the impact of chromaticity on the mode
coupling instability for a single bunch colliding head-on in one IP. For low
$\beta^{*}/\sigma_{s}$ ratio chromaticity alone is sufficient to damp the
instability. As the ratio is increased, chromaticity alone reduces the rise
time but does not completely cure the instability up to $Q^{\prime}=6.0$.
Comparing the cases with $\beta^{*}/\sigma_{s}\approx 30$ and
$\beta^{*}/\sigma_{s}\approx 110$, it seems that the rise time as a function
of chromaticity converges for large $\beta^{*}/\sigma_{s}$ ratios. This
confirms the results from the CMM and indicates possible issues with long-
range interactions when using chromaticity only as a cure to the mode coupling
instability.

Figure 14: Centre of mass motion for a single bunch colliding head-on with
$\beta^{*}/\sigma_{s}\approx 100$ and $Q^{\prime}=0.0$ as a function of the
damper gain.

Figure 14 shows the impact of the transverse damper on the mode coupling
instability for a single bunch colliding head-on in one IP with
$\beta^{*}/\sigma_{s}\approx 100$ and $Q^{\prime}=0.0$. It is seen that even
for a very low gain of 0.001 the beam is rendered stable by the transverse
damper. This benefit of the transverse damper was experimentally demonstrated
with offset collisions. It was shown that the beams were strongly unstable
when the damper was turned off and stable with the damper on for a separation
of approximately 1.0 $\sigma$ [12] and with $Q^{\prime}\approx 5.0$. This
strong instability with offset collisions and damper off is a good candidate
for the mode coupling instability mentioned before.

Figure 15: Instability rise time as a function of chromaticity for different
damper gains, in the single-bunch approximation of a configuration with 10
long-range interactions separated by 10 $\sigma$.

Although it seems that any instability involving head-on interactions could be
cured with the transverse damper, the situation is more complicated when
looking at offset collisions and even more for long-range interactions. Two
mechanisms can degrade the situation: the reduction of the tune spread and the
absence of synchro–betatron coupling in the case of long-range interactions.
Figure 15 shows the instability rise time as a function of transverse damper
gain and chromaticity in the case of long-range interactions. All the
interactions are lumped in one location and the tune shift was set to be
equivalent to 10 long-range interactions with a separation of 10 $\sigma$. In
this case, either chromaticity or damper only is not sufficient to damp the
instability. There is however a correlated dependence: the higher the gain the
lower the chromaticity required to stabilize the beams and inversely. In 2012,
the LHC was operated with both high gain and chromaticity. Both these
parameters are known to degrade beam lifetime and emittance; these results
indicate that there should be room for optimization of these parameters which
should be considered during LHC recommissioning in 2015.

Adding a full head-on interaction significantly increases the tune spread and
consequently damps all long-range types of instabilities. This is consistent
with experimental observations [3] and indicates that operating the transverse
damper during physics stores may not be required as long as sufficient tune
spread is provided and tune shifts at which the coupled mode instability
occurs are avoided.

##  5 Multibunch effects

Previous results were produced using the single-bunch approximation. In the
LHC, the filling pattern, long-range interactions and symmetry of the
collision points should be considered to give a more realistic picture of the
coherent beam dynamics. In such configuration, each bunch encounters a
different set of beam–beam interactions, leading to significantly different
incoherent and coherent effects. In particular, the coupling between bunches
along a single beam through the machine impedance and to bunches of the other
beam through beam–beam interactions becomes different for each bunch. The CMM
was extended to multibunch in order to properly take into account the real
beam–beam configuration and coupled bunch impedance.

Figure 16: Real and imaginary parts of the tune shift as a function of the
beam–beam parameter. In this case only long-range interactions in a single IP
were considered. The top plot is for two bunches in each beam, the middle plot
for three bunches in each beam and the bottom plot for eight bunches in each
beam colliding only on one side of the IP to enhance PACMAN effects. The modes
of all bunches are shown in these plots.

Figure 16 shows how the complexity of the collision pattern can modify the
coherent beam dynamics. In these cases only long-range interactions in a
single IP were considered. The top plot shows the case of two bunches per
beam, each bunch colliding only once on either side of the IP, and is
therefore similar to the single-bunch case. The only difference between the
bunches comes from the coupled bunch impedance. The coupled mode instabilities
are clearly observed when the beam–beam modes cross the head–tail modes
$\pm$1\. Although much weaker, this instability is also observed when the
beam–beam modes cross the head–tail modes $\pm$2\. This is an interesting
feature which deserves further investigation, as the effect of the damper on
such higher order mode coupling instabilities is unclear. As the number of
bunches is increased, and hence the complexity of the collision pattern, a lot
of modes with different frequencies appear and consequently mode coupling
instabilities occur for most beam–beam parameters. In particular, the
different modes do not necessarily involve the whole beam, but only a subset
of bunches, as also shown by self-consistent simulations in Fig. 18. It is
rather clear from this picture that PACMAN effects and the overall complexity
of the LHC collision pattern cannot be neglected when looking at coherent beam
dynamics.

Figure 17 shows a comparison of simulations with the CMM and COMBI in an
identical configuration (nominal 2012 LHC running condition with
$Q_{s}=0.002$), indicating a good agreement between the models. In particular,
mode coupling instabilities are observed for separations from 11 to 16
$\sigma$ at frequencies around the horizontal tune, 0.31. The separation at
which the instabilities occur depends on the beam–beam parameter and
synchrotron tune. The instabilities observed in the tracking code only, at
frequencies between 0.316 and 0.325, originate from the vertical plane and
therefore do not appear in the CMM, which models one plane only. It is
foreseen to further extend the CMM to take this into account.
The complex tune shift of each mode is evaluated by singular value
decomposition of the turn-by-turn position of each bunch. The singular vectors
associated with the most unstable mode at separations of 9 and 10 $\sigma$ are
shown in Fig. 18. In particular, one observes that, in the configuration with
10 $\sigma$ separation, bunches at the edge of the train are stable, while the
bunches at the centre of the train are unstable. The opposite is true at 9
$\sigma$. Moreover, the rise time associated with these two modes are
significantly different, respectively 1800 and 3800 turns. This observation
provides another indication of the importance of PACMAN effects on the
coherent dynamics and therefore motivates further studies of the effect of the
different stabilization techniques in configurations as close as possible to
the real LHC.

Figure 17: Coherent mode frequencies and rise times (colour) as a function of
the normalized separation in the horizontal plane at the long-range location
for two trains of 36 bunches colliding in one IP with 16 long-range
interactions. The upper plot shows the result from CMM and the lower from
COMBI. The synchrotron tune in this case was set to 0.002.

Figure 18: Oscillation amplitude of each bunch of the two beams for an
unstable mode in the presence of impedance and 16 long-range beam–beam
interactions in one IP with separations of 10 $\sigma$ (upper plot) and 9
$\sigma$ (lower plot).

##  6 Summary and outlook

During the 2012 proton run of the LHC, coherent instabilities were routinely
observed in the LHC at the end of the squeeze and with beams colliding with a
transverse offset, triggering a renewed interest to pursue studies of the
interplay of beam–beam and impedance. For this purpose two models were
developed:

  * •

An analytical model based on the circulant matrix approach used in Ref. [1]

  * •

A fully self-consistent multiparticle tracking model. Single-bunch effects
were studied with the code BeamBeam3D [5] and multibunch effects with the code
COMBI [6]

A full benchmarking campaign with existing code was done to validate the
implementation of impedance in these different models and excellent agreement
was reached for both the analytical model and tracking codes.

Single-bunch effects were studied in detail for various cases. It was shown
that the coherent beam–beam modes can couple with higher order head–tail modes
giving rise to strong instabilities with similar characteristics to the
impedance-driven TMCI. Possible cures were considered and it was demonstrated
that, in the case of the single-bunch approximation, a combination of
chromaticity and transverse damper should stabilize the beams in all cases.
Specific cases should be studied in detail to optimize the values of the gain
and chromaticity. Nevertheless, due to its complex collision pattern, the LHC
beams can hardly be approximated with a single bunch. PACMAN effects and
coupled bunch impedance have to be considered in any attempt to realistically
model the LHC. Both analytical and tracking models were developed to study
multibunch effects. Preliminary results show good agreement and tend to
confirm the invalidity of the single-bunch approximation for the case of the
LHC. Further efforts should be pursued in this direction to provide a better
understanding of LHC observations.

##  7 Acknowledgments

The authors would like to thank T. Pieloni and N. Mounet for their help and
support regarding these studies.

## References

  * [1] E.A. Perevedentsev and A.A. Valishev, Phys. Rev. Spec. Top. Accel. Beams 4 (2001) 024403.
  * [2] E. Stern et al., Phys. Rev. Spec. Top. Accel. Beams 13 (2010) 024401.
  * [3] G. Papotti, “Observation of Beam–Beam Effects in the LHC,” these proceedings.
  * [4] N. Mounet, PhD thesis, CERN-THESIS-2012-055, (2012).
  * [5] J. Qiang et al., Phys. Rev. Spec. Top. Accel. Beams 5 (2002) 104402.
  * [6] T. Pieloni, PhD thesis, CERN-THESIS-2010-056 (2010).
  * [7] G. Rumolo et al., Phys. Rev. Spec. Top. Accel. Beams 5 (2002) 121002.
  * [8] Y. Alexahin, Nucl. Instrum. Methods A 480 (2002) 253.
  * [9] S. White et al., “Synchro–Betatron Effects in the Presence of Large Piwinski Angle and Crab Cavities at the HL-LHC,” Proceedings of IPAC12, Shanghai, China, (2012).
  * [10] X. Buffat, “Stability Diagrams of Colliding Beams,” this workshop.
  * [11] B. Muratori and T. Pieloni, “Luminosity Leveling Techniques: Implications for Beam–Beam Interactions,” this workshop.
  * [12] X. Buffat, “Coherent Beam–Beam Modes in the LHC,” this workshop.


# Stability of a cascade system with two stations and its extension for
multiple stations

Masakiyo Miyazawa**footnotemark: * Evsey Morozov††footnotemark: †

(July 9, 2023)

###### Abstract

We consider a two-station cascade system in which waiting or externally
arriving customers at station $1$ move to the station $2$ if the queue size of
station $1$ including an arriving customer itself and a customer being served
is greater than a given threshold level $c_{1}\geq 1$ and if station $2$ is
empty. Assuming that external arrivals are subject to independent renewal
processes satisfying certain regularity conditions and service times are
$i.i.d.$ at each station, we derive necessary and sufficient conditions for a
Markov process describing this system to be positive recurrent in the sense of
Harris. This result is extended to the cascade system with a general number
$k$ of stations in series. This extension requires certain traffic intensities
of stations $2,3,\ldots,k-1$ for $k\geq 3$ to be defined. We finally note that
the modeling assumptions on the renewal arrivals and $i.i.d.$ service times
are not essential if the notion of the stability is replaced by a certain
sample path condition. This stability notion is identical with the standard
stability if the whole system is described by the Markov process which is a
Harris irreducible $T$-process.

11footnotetext: Department of Information Sciences, Tokyo University of
Science, Noda, Chiba, Japan & School of Data Science, Chinese University of
Hong Kong, Shenzhen, China.22footnotetext: Institute of Applied Mathematical
Research of Karelian Research Centre, Russian Academy of Sciences,
Petrozavodsk, Karelia, Russia; Petrozavodsk State University, Petrozavodsk,
185910; Moscow Center for Fundamental and Applied Mathematics, Moscow State
University, Moscow 119991, Russia.

##  1 Introduction

We are interested in the stability of a service system with two single server
stations, numbered as $1,2$, where the stability means that a Markov process
describing this system is positive recurrent in the sense of Harris (see
Definition 2.1). We assume the following system dynamics for this queueing
model. Each station has renewal arrivals and $i.i.d.$ service times. Both
stations have single servers, which are independently working in parallel, but
waiting or exogenously just arriving customers at station $1$ moves to the
station $2$ if the queue size of station $1$ including a customer being served
is greater than a given threshold level $c_{1}\geq 1$ and if station $2$ is
empty, where an exogenously arriving customer is counted in the queue. The
customer arriving from station 1 immediately starts its service at station 2,
and gets service only when no other customer is in station 2. We refer to this
queuing system as a 2-station cascade system. Since this system naturally
arises in practice but its analysis is not easy, its stability is attracting
researchers of queueing systems

For station $i=1,2$, let $\lambda_{i}$ be the arrival rate of exogenously
arriving customers, and let $\mu_{i}$ is the service rate of those customers.
Let $\rho_{i}=\lambda_{i}/\mu_{i}$. Since some of arriving customers at
station 1 may move to station 2, $\rho_{1}$ is not an actual traffic intensity
(the mean amount of service processed per unit time), so it is nominal. We
define $\rho^{*}_{1}(\xi)$ as the time average of the probability that the
station $1$ is not empty for an arbitrarily given initial distribution $\xi$
of the system at time $0$, which is formally defined as (3.11) in Section 3.
We refer to $\rho^{*}_{1}(\xi)$ as an effective traffic intensity at station
$1$ given $\xi$.

In this setting, it is expected that the system is stable if and only if
$\rho^{*}_{1}(\xi)<1$ for some $\xi$ and $\rho_{2}<1$. We prove this
characterization of the stability in our framework (see Lemma 3.3), but it is
less tractable because $\rho^{*}_{1}(\xi)$ is hard to compute. In the
literasture, a computable condition has been studied (e.g., see [13]), but the
stability is not fully answered. For the cascade system with more than two
stations, necessary and sufficient conditions are separately considered in
[6], but there are gaps between those conditions.

In this paper, we solve this stability problem for the 2-station cascade
system, assuming certain regularity conditions on the inter-arrival time
distributions of exogenous customers at each station. This extends the known
results. For example, Morozov and Steyaert [13] obtain tractable sufficient
conditions for the stability under the extra assumption that the 1st station
has Poisson arrivals. We show that, not assuming Poisson arrivals, those
conditions are necessary and sufficient. We further extend this result for a
$k$-station cascade system for a general integer $k\geq 3$ using the effective
traffic intensities $\rho^{*}_{1}(\xi)$ for $i=2,3,\ldots,k-1$. As those
traffic intensities are hard to compute, it is preferable to have tractable
stability conditions. Such conditions are conjectured in [11], but they are
disproved by [7].

Both papers of those papers [7, 11] are based on Theorem 3.1 of the preprint
[12]. This theorem is correct, but some arguments in [11] are not accurate.
These motivate us to write the present paper updating [11] taking Kim and Kim
[7] into account.

Thus, main contributions of this paper are a proof technique for the stability
problem and the full characterization of the stability for $k=2$. The proof
technique is a combination of sample path analysis similar to fluid
approximation and the characterization of the stability based on the so-called
Harris irreducibility of a Markov $T$-process with a general state space (see
Proposition 2.2). This approach is different from the method of Morozov and
Steyaert [13], which is based on a regenerative process, so is restrictive in
applications. Another typical approach to stability problems is to use fluid
approximation and Lyapunov functions (see, e.g. [4]). The fluid approximation
largely depends on strong law of large numbers, strong LLN for short. However,
it may have certain limitations. For example, Tezcan [14] shows insufficiency
for studying stability through fluid approximation (see also Chernova et al.
[3]). We encounter a similar situation because the stability condition for
$k\geq 3$ requires $\rho^{*}_{j}(\xi)$ for downward stations, which can not be
obtained from the fluid approximation. The counterexamples of [7] supports
this situation.

This paper is made up by six sections. In Section 2, we introduce the well-
known framework for a Markov process to be positive Harris recurrent, which
provides a base for our analysis. In Section 3, the 2-station cascade system
is detailed, and its stability conditions are presented in Theorem 3.1, which
are proved in Section 4. The general $k$-station cascade system is considered
in Section 5. Finally, Section 6 remarks the possibility to relax the renewal
assumptions on the 2-station cascade system concerning its stability. The
proofs for some auxiliary results are given in the appendix.

##  2 Markov process and Harris recurrence

Our main concern is the stability of the $2$-station cascade system, which
will be described by a Markov process. For formally discussing it, we use the
following basic notations. Let $(\Omega,{\mathcal{F}},\mathbb{P})$ be a
probability space on which a continuous-time stochastic process
$X(\cdot)\equiv\\{X(t);t\geq 0\\}$ with state space $S$ is defined, where $S$
is a separable and locally compact metric state space. We assume that its
sample path is right-continuous and has left-limits, and $X(\cdot)$ is adapted
to a filtration $\mathbb{F}\equiv\\{{\mathcal{F}}_{t};t\geq 0\\}$, that is,
$X(t)$ is ${\mathcal{F}}_{t}$-measurable for all $t\geq 0$. Assume that
$X(\cdot)$ is a strong Markov process with respect to $\mathbb{F}$.

For this Markov process $X(\cdot)$, we briefly introduce Harris irreducibility
and (null and positive) recurrence. Let ${\mathcal{B}}(S)$ be the Borel field
on $S$, that is, the $\sigma$-field on $S$ generated by all open sets of $S$,
and let $\mathbb{P}_{x}(A)=\mathbb{P}(A|X(0)=x)$ for $x\in S$ and
$A\in{\mathcal{F}}$. The following definitions are taken from Meyn and Tweedie
[10] (for their discrete counterparts, see Section 8.3 of Meyn and Tweedie
[8]). In what follows, a measure $\varphi$ on $S$ means that it is defined on
measurable space $(S,{\mathcal{B}}(S))$, and it is said to be non-trivial if
$\varphi(S)>0$.

######  Definition 2.1 (Irreducibility and recurrence).

For the Markov process $X(\cdot)$, let

$\displaystyle\tau_{A}=\inf\\{t\geq 0;X(t)\in
A\\},\qquad\eta_{A}=\int_{0}^{\infty}1(X(u)\in A)du,\qquad
A\in{\mathcal{B}}(S),$

where $1(\cdot)$ denotes the indicator function of proposition “$\cdot$”.
Then, $X(\cdot)$ is called Harris irreducible, Harris recurrent, positive
Harris recurrent if the following conditions (a), (b) and (c) are satisfied,
respectively.

  * (a)

There is a non-trivial $\sigma$-finite measure $\varphi$ on $S$, called an
irreducibility measure, such that, for $\forall B\in{\mathcal{B}}(S)$,
$\varphi(B)>0$ implies that $\mathbb{E}_{x}(\eta_{B})>0$, for $\forall x\in
S$. In this case, $X(\cdot)$ is called $\varphi$-irreducible if $\varphi$ is
specified.

  * (b)

There is a non-trivial $\sigma$-finite measure $\varphi$ on $S$ such that
$\varphi(B)>0$ implies that $\mathbb{P}_{x}(\eta_{B}=\infty)=1$ for $\forall
x\in S$, which is equivalent to that there is a non-trivial $\sigma$-finite
measure $\varphi$ on $S$ such that $\varphi(B)>0$ implies that
$\mathbb{P}_{x}(\tau_{B}<\infty)=1$ for $\forall x\in S$. In this case, there
exists a unique invariant measure on $S$ up to a multiplication constant,
where $\sigma$-finite measure $\nu$ on $S$ is called an invariant measure if

$\displaystyle\nu(A)=\int_{S}\nu(dx)\mathbb{P}_{x}(X(t)\in A),\qquad\forall
A\in{\mathcal{B}}(S),\forall t>0.$

  * (c)

$X(\cdot)$ is Harris recurrent, and there is an invariant probability measure
on $S$, that is, $\nu$ of (b) is a probability measure.

In particular, we call $X(\cdot)$ and the stochastic model described by it to
be stable if $X(\cdot)$ is positive Harris recurrent.

######  Definition 2.2 ($K$-chain and $T$-process).

(i) For a probability measure $a$ on
$(\mathbb{R}_{+},{\mathcal{B}}(\mathbb{R}_{+}))$, define kernel $K_{a}$ as

$\displaystyle K_{a}(x,A)=\int_{0}^{\infty}\mathbb{P}_{x}(X(t)\in
A)a(dt),\qquad x\in S,A\in{\mathcal{B}}(S),$

then $K_{a}$ is called a $K$-chain with sampling distribution $a$.
(ii) The Markov process $X(\cdot)$ is called a $T$-process if there is a
kernel $T(x,A)$ for $x\in S$ and $A\in{\mathcal{B}}(S)$ such that $T$ is non-
trivial, that is, $T(x,S)>0$ for $\forall x\in S$, $T(x,A)$ is lower semi-
continuous in $x\in S$, that is, $T(x,A)\leq\liminf_{y\to x}T(y,A)$, and the
following inequality holds for some probability measure $a$ on
$\mathbb{R}_{+}$.

$\displaystyle K_{a}(x,A)\geq T(x,A),\qquad\forall x\in S,\forall
A\in{\mathcal{B}}(S).$

We first note some basic facts for a Harris recurrent Markov process. They are
not only used in our proofs, but also helpful to better understand our
arguments.

######  Lemma 2.1.

[The continuous-time counterpart of Proposition 3.4 of [15]] Assume that the
Markov process $X(\cdot)$ is a Harris recurrent $T$-process. Denote its
$\sigma$-finite invariant measure by $\nu$. Then, $\nu(C)$ is finite for each
compact set $C$ of $S$.

This lemma can be proved in the exactly same way as Proposition 3.4 in [15]
for a discrete-time Markov process. This is because the $K$-chains play the
exactly same role in both cases. The essence here is that $\\{x\in
S;T(x,A)>0\\}$ is an open set of $S$ because $T(x,A)$ is lower semi-continuous
in $x\in S$ for each $A\in{\mathcal{B}}(S)$.

The next fact is known as the ratio limit (or ergodic) theorem.

######  Proposition 2.1 (Remark 1 for Theorems II.1 and II.2 of [1]).

Assume that the Markov process $X(\cdot)$ is Harris recurrent, and denote its
$\sigma$-finite invariant measure on $S$ by $\nu$. Let $L^{1}_{+}(\nu)$ be the
set of all nonnegative measurable functions $f$ on $S$ such that
$\langle\nu,f\rangle\equiv\int_{S}f(y)\nu(dy)<\infty$, then, for $f,g\in
L^{1}_{+}(\nu)$ satisfying $\langle\nu,g\rangle>0$,

$\displaystyle\lim_{t\to\infty}\frac{\int_{0}^{t}f(X(u))du}{\int_{0}^{t}g(X(u))du}=\frac{\langle\nu,f\rangle}{\langle\nu,g\rangle},\qquad
a.s.\;\mathbb{P}_{x},\forall x\in S.$ (2.1)

######  Remark 2.1.

(i) If $X(\cdot)$ is positive recurrent, then $\nu(S)<\infty$, so, for any
compact set $C\subset S$, $\nu(C)\leq\nu(S)<\infty$. Hence, normalizing $\nu$
as $\nu(S)=1$, the dominated convergence theorem and (2.1) with $f(x)=1(x\in
C)$ and $g(x)=1$ for $x\in S$ yield

$\displaystyle\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{x}(X(u)\in
C)du=\mathbb{E}_{x}\left(\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}1(X(u)\in
C)du\right)=\nu(C).$ (2.2)

(ii) If $X(\cdot)$ is null recurrent, then $\nu(S)=\infty$. Since $\nu$ is
$\sigma$-finite, there is a sequence of sets
$\\{S_{i}\in{\mathcal{B}}(S);i\geq 1\\}$ such that $\nu(S_{i})<\infty$ for
each $i\geq 1$, $S_{i}\uparrow S$ and $\nu(S_{i})\to\infty$ as $i\to\infty$.
Since, for any compact set $C\subset S$, $\nu(C)<\infty$ by Lemma 2.1, we
have, by (2.1), under $\mathbb{P}_{x}$,

$\displaystyle\limsup_{t\to\infty}$
$\displaystyle\frac{1}{t}\int_{0}^{t}1(X(u)\in
C)du\leq\lim_{t\to\infty}\frac{\int_{0}^{t}1(X(u)\in
C)du}{\int_{0}^{t}1(X(u)\in S_{i})du}=\frac{\nu(C)}{\nu(S_{i})}\to 0,\mbox{ as
}i\to\infty.$

This implies that $\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}1(X(u)\in C)du=0$
$a.s.$ $\mathbb{P}_{x}$. Hence, by the dominated convergence theorem,
$\lim_{t\to\infty}\mathbb{E}_{x}\left(\frac{1}{t}\int_{0}^{t}1(X(u)\in
C)du\right)=0$. Since this limit can be replaced by limit supremum,

$\displaystyle\limsup_{t\to\infty}$
$\displaystyle\frac{1}{t}\int_{0}^{t}\mathbb{P}_{x}(X(u)\in
C)du=\limsup_{t\to\infty}\mathbb{E}_{x}\left(\frac{1}{t}\int_{0}^{t}1(X(u)\in
C)du\right)=0.$ (2.3)

The following proposition is obtained in [10], which will be a key for our
approach.

######  Proposition 2.2 ((ii) of Theorem 3.2 and the second half of (iv) of
Theorem 3.4 of [10]).

Assume that the Markov process $X(\cdot)$ is a $T$-process and Harris
irreducible, then the following three conditions are equivalent.

  * (a)

$X(\cdot)$ is positive Harris recurrent.

  * (b)

For any $x\in S$ and any $\varepsilon>0$, there is a compact set $C\subset S$
such that

$\displaystyle\liminf_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{x}(X(u)\in
C)du\geq 1-\varepsilon.$ (2.4)

  * (c)

For some $x\in S$ and some compact set $C\subset S$,

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{x}(X(u)\in
C)du>0.$ (2.5)

######  Remark 2.2.

The condition (b) is called bounded in probability in [10], but we call it
tight on average.

This proposition is a subset of Theorems 3.2 and 3.4 of [10], and follows from
Proposition 2.1. However, the equivalence of (a) and (c) is not fully proved
in [10]. We prove this equivalence in Appendix A.1 because it is particularly
important for this research.

##  3 Two-station cascade system

We focus on the two-station cascade system. This is a queueing system with
single-server stations 1, 2 and infinite-buffers. The servers are working in
parallel, and, for $i=1,2$, exogenous customers arrive at station $i$, and are
called class-$i$ customers. Let $\\{t_{e,i}(n);n\geq 1\\}$ be the arriving
times of class-$i$ customers, which are assumed to be a renewal process with
$i.i.d.$ interarrival times $\tau_{e,i}(n)=t_{e,i}(n)-t_{e,i}(n-1)>0$, $n\geq
1$, where $t_{e,i}(0)=0$. Denote the generic element of $\tau_{e,i}(n)$ by
$\tau_{e,i}$, and the arrival rate by

$\displaystyle\lambda_{i}\equiv 1/\mathbb{E}(\tau_{e,i})\in(0,\,\infty),\qquad
i=1,2.$

This convention $\tau_{e,i}$ for $\tau_{e,i}(n)$ will be used for other random
variables indexed by $n$. Class-$i$ customers are served in the first-come-
first-served manner, and their service times $\\{\tau_{s,i}(n),n\geq 1\\}$ are
$i.i.d.$, and the service rate is denoted by $\mu_{i}\equiv
1/\mathbb{E}(\tau_{s,i})>0$ for $i=1,2$.

Let $Q_{1}(t)$ be the number of class-$1$ customers at station $1$ including
customers being served at time $t$. There is a switching rule for a class-$1$
customer in such a way that, if a class-$1$ customer who is waiting for
service or just arrives from the outside observes queue size including itself
to be greater than $c_{1}\geq 1$ (a given threshold) and if station $2$ is
empty, then it immediately goes to station $2$ as a class-${1|2}$ customer,
and gets service immediately with $i.i.d.$ service times
$\\{\tau_{s,1|2}(n);n\geq 1\\}$ with rate $\mu_{{1|2}}\equiv
1/\mathbb{E}(\tau_{s,{1|2}})$. We assume that class-${1|2}$ customer is always
preempted in service by class-$2$ customers and resumes its service when no
class $2$ customer is in station 2. Thus, there is at most one class-${1|2}$
customer in station $2$ who can get service only when there is no class-$2$
customer. All customers who completed their service leave the system.

To consider the stability, we describe the 2-station cascade system by a
Markov process. For $v=1,2,{1|2}$, let $Q_{v}(t)$ be the number of class-$v$
customers in the system at time $t$, which is called a queue $v$ at time $t$.
Define $L_{i}(t)$ for $i=1,2$ as

$\displaystyle L_{1}(t)=Q_{1}(t),\qquad L_{2}(t)=Q_{2}(t)+Q_{{1|2}}(t),\qquad
t\geq 0.$

Thus, $L_{i}(t)$ is the total number of customers in station $i$ at time $t$
for $i=1,2$. For time $t\geq 0$, let $R_{e,i}(t)$ and $R_{s,i}(t)$ be the
remaining arrival and service times, respectively, of class-$i$ customers for
$i=1,2$, and let $R_{s,{1|2}}(t)$ be the remaining service time of a
class-${1|2}$ customer, where the remaining service times vanish if there is
no customer of the corresponding class in the system. Let
$S=\mathbb{Z}_{+}^{2}\times\\{0,1\\}\times\mathbb{R}_{+}^{5}$, which can be
considered as a separable complete metric space, where the discrete topology
is taken on $\mathbb{Z}_{+}^{2}\times\\{0,1\\}$. Define
${\boldsymbol{X}}(\cdot)=\\{X(t);t\geq 0\\}$ as

$\displaystyle{\boldsymbol{X}}(t)=({\boldsymbol{Q}}(t),{\boldsymbol{R}}_{e}(t),{\boldsymbol{R}}_{s}(t),R_{s,{1|2}}(t))\in
S,$ (3.6)

where ${\boldsymbol{Q}}(t)=(Q_{1}(t),Q_{2}(t),Q_{1|2}(t))$,
${\boldsymbol{R}}_{e}(t)=(R_{e,1}(t),R_{e,2}(t))$ and
${\boldsymbol{R}}_{s}(t)=(R_{s,1}(t),R_{s,2}(t))$. We take the natural
filtration $\mathbb{F}\equiv\\{{\mathcal{F}}_{t};t\geq 0\\}$ for
${\boldsymbol{X}}(\cdot)$. Namely, ${\mathcal{F}}_{t}$ is defined as

$\displaystyle{\mathcal{F}}_{t}=\sigma(\\{{\boldsymbol{X}}(u);u\in[0,t]\\}),\qquad
t\geq 0,$

where $\sigma(\cdot)$ is the minimal $\sigma$-field including all events in
${\mathcal{F}}$ generated by “$\cdot$”. Then, clearly
${\boldsymbol{X}}(\cdot)$ is a continuous-time Markov process with respect to
$\mathbb{F}$. Since its sample paths are piecewise deterministic,
${\boldsymbol{X}}(\cdot)$ is a strong Markov processes with respect to
$\mathbb{F}$ (e.g., see [5]). This process fully describes the 2-station
cascade system, and we refer to it as a 2-station cascade process. Similarly,
we define

$\displaystyle{\boldsymbol{X}}_{2}(\cdot)=\\{(Q_{2}(t),R_{e,2}(t),R_{s,2}(t);t\geq
0\\},$ (3.7)

which is a strong Markov process describing the queue of class-$2$ customers.

For the Markov process ${\boldsymbol{X}}(\cdot)$, we apply the framework
introduced in Section 2. The following assumption enables
${\boldsymbol{X}}(\cdot)$ to be a $T$-process and Harris irreducible.

######  Assumption 3.1.

For $i=1,2$, (a) $\mathbb{P}(\tau_{e,i}>x)>0$ for all $x>0$, and (b) there is
a function $p_{i}(x)\geq 0$ such that $\int_{0}^{\infty}p_{i}(x)dx>0$ and, for
some integer $j_{i}\geq 1$,

$\displaystyle\mathbb{P}\Big{(}a\leq\sum_{n=1}^{j_{i}}\tau_{e,i}(n)\leq
b\Big{)}\geq\int_{a}^{b}p_{i}(x)dx,\qquad\forall a,b\mbox{ satisfying }\;0\leq
a<b.$

The following lemmas are easy consequences of this assumption.

######  Lemma 3.1.

Under Assumption 3.1, (i) the Markov process ${\boldsymbol{X}}(\cdot)$ is a
$T$-process, and any
${\boldsymbol{x}}^{*}\in\\{(0,0,0,{\boldsymbol{r}}_{e},0,0,0)\in
S;{\boldsymbol{r}}_{e}\in\mathbb{R}_{+}^{2}\\}$ is reachable from any
${\boldsymbol{x}}\in S$, that is,
$\int_{0}^{\infty}\mathbb{P}_{{\boldsymbol{x}}}({\boldsymbol{X}}(u)\in G)du>0$
for any ${\boldsymbol{x}}\in S$ and any open set $G$ containing
${\boldsymbol{x}}^{*}$,
(ii) ${\boldsymbol{X}}(\cdot)$ is $\varphi$-irreducible for $\varphi(B)\equiv
T({\boldsymbol{x}}^{*},B)$ for $B\in{\mathcal{B}}(S)$.

The part (i) of this lemma is similarly proved as Lemma 3.7 of [9], while (ii)
is the continuous-time counterpart of Proposition 6.2.1 of [8], and can be
similarly proved. Nevertheless, we prove (ii) in Appendix A.2 for the
completeness.

######  Lemma 3.2.

Under Assumption 3.1, the Markov process ${\boldsymbol{X}}(\cdot)$ is positive
Harris recurrent if and only if, for each $i=1,2$, there exist
${\boldsymbol{x}}_{i}\in S$ and $\ell_{i}\geq 0$ such that

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}_{i}}(Q_{i}(u)\leq\ell_{i})du>0,\qquad
i=1,2.$ (3.8)

This lemma is proved in Appendix A.3. We are ready to answer to the stability
of the 2-station cascade system.

######  Theorem 3.1.

Under Assumption 3.1, the Markov process ${\boldsymbol{X}}(\cdot)$ is positive
recurrent if and only if

$\displaystyle\widetilde{\rho}_{1}\equiv\frac{\lambda_{1}}{\mu_{1}+\mu_{{1|2}}(1-\rho_{2})}<1,$
(3.9) $\displaystyle\rho_{2}<1.$ (3.10)

######  Remark 3.1.

Morozov and Steyaert [13, Theorem 3] show that the essentially same condition
is sufficient for the stability under the assumption that station $1$ has
$m_{1}$ $(\geq 1)$ servers and Poisson arrivals and the switching level
$c_{1}=m_{1}$. The extension from a single server to multiple servers at
stations is not hard in our arguments (see Section 4.3). Thus, the sufficiency
of (3.9) and (3.10) is essentially known under the assumption that
${\boldsymbol{X}}(\cdot)$ is a regenerative process, but their necessity is
only considered in some cases in [13]. For the general $k$-station cascade
system at least for the Poisson arrivals, Delgado and Morozov [6] study its
stability, assuming $c_{i}=1$. They use a fluid approximation, and their
sufficient conditions for $k=2$ agree with ours. They also derive the
necessary conditions, which are different from the sufficient ones. Namely,
there is a gap in those conditions even for $k=2$.

One may interpret $\widetilde{\rho}_{1}$ of (3.9) as a kind of the traffic
intensity of exogenously arriving customers at station 1 provided station 1 is
saturated (permanently busy). Hence, it is different from the actual traffic
intensity which agrees with the stationary probability that station 1 is not
empty when the system is stable. Thus, it may be interesting to compare
$\widetilde{\rho}_{1}$ with $\rho^{*}_{1}(\xi)$, which is intuitively
introduced as the effective traffic intensity in Section 1. We now formally
define it for a distribution $\xi$ on $S$ for $i=1,2$ by

$\displaystyle\rho^{*}_{i}(\xi)=\liminf_{t\to\infty}\frac{1}{t}\int_{0}^{t}\Big{(}\int_{S}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)\geq
1)\xi(d{\boldsymbol{x}})\Big{)}du,$ (3.11)

which is called an effective traffic intensity of $Q_{i}(\cdot)$. We note the
following basic facts on $\rho^{*}_{i}(\xi)$. They may look intuitively
obvious, but have the important message that the stability problem on
${\boldsymbol{X}}(\cdot)$ can be answered by the effective traffic
intensities.

######  Lemma 3.3.

Under Assumption 3.1, (i) if ${\boldsymbol{X}}(\cdot)$ is positive recurrent,
then, for any distribution $\xi$ on $S$,

$\displaystyle\rho_{i}^{*}(\xi)=1-\mathbb{P}_{\nu}(Q_{i}(0)=0),\qquad i=1,2,$
(3.12)

where $\nu$ is the stationary distribution of ${\boldsymbol{X}}(\cdot)$, and
$\mathbb{P}_{\nu}(A)=\int_{S}\mathbb{P}_{{\boldsymbol{x}}}(A)\nu(dx)$ for
$A\in{\mathcal{F}}$. Hence, $\rho^{*}_{i}(\xi)$ is independent of $\xi$ when
${\boldsymbol{X}}(\cdot)$ is positive recurrent, (ii)
${\boldsymbol{X}}(\cdot)$ is positive recurrent if and only if
$\rho^{*}_{i}(\xi)<1$ for $i=1,2$ and some distribution $\xi$ on $S$.

This lemma is proved in Appendix A.4, independently of Theorem 3.1, and will
be used to prove the necessity of (3.9) in Theorem 3.1. Thus,
$\rho^{*}_{1}(\xi)$ is hard to compute, but still useful.

##  4 System dynamics and proof of Theorem 3.1

To prove Theorem 3.1, we first detail the dynamics of the Markov process
${\boldsymbol{X}}(\cdot)$.

###  4.1 Dynamics of the $2$-station cascade system

Recall that $t_{e,i}(n)$ is the $n$-th arriving time of class-$i$ customer at
station $i$ for $i=1,2$, and let $t_{e,1|2}(n)$ be the $n$-th arriving time of
class-$1|2$ customer at station $2$ from station $1$. For $v=1,2,{1|2}$,
define $A_{v}(\cdot)=\\{A_{v}(t);t\geq 0\\}$ as

$\displaystyle A_{v}(t)=\sum_{n=1}^{\infty}1(0<t_{v}(n)\leq t).$

That is, $A_{v}(\cdot)$ is the counting process of arrivals of class-$v$
customers.

We similarly introduce notations for departures. Let $\\{t_{d,i}(n);n\geq
1\\}$ be departure instants of class-$i$ customers to the outside for $i=1,2$,
and let $\\{t_{d,1|2}(n);n\geq 1\\}$ be departure instants of class-$1|2$
customers at station 2. We denote the corresponding counting processes by
$D_{v}(\cdot)\equiv\\{D_{v}(t);t\geq 0\\}$ for $v=1,2,{1|2}$, that is

$\displaystyle D_{v}(t)=\sum_{n=1}^{\infty}1(0<t_{v}(n)\leq t).$

Note that $A_{v}(0)=D_{v}(0)=0$ by those definitions. Since there is at most
one class-${1|2}$ customer at station $2$, we have

$\displaystyle D_{{1|2}}(t)\leq A_{{1|2}}(t)\leq D_{{1|2}}(t)+1,\qquad t\geq
0.$ (4.1)

We also have the following flow balance equations.

$\displaystyle Q_{1}(t)=Q_{1}(0)+A_{1}(t)-(D_{1}(t)+A_{{1|2}}(t)),$ (4.2)
$\displaystyle Q_{1|2}(t)=Q_{1|2}(0)+A_{{1|2}}(t)-D_{{1|2}}(t),$ (4.3)
$\displaystyle Q_{2}(t)=Q_{2}(0)+A_{2}(t)-D_{2}(t).$ (4.4)

To describe departures by service times, we introduce the following notations.

$\displaystyle B_{i}(t)=\int_{0}^{t}1(Q_{i}(u)>0)du,\qquad t\geq 0,i=1,2,$
$\displaystyle B_{1|2}(t)=\int_{0}^{t}1(Q_{1|2}(u)>0,Q_{2}(u)=0)du$

and let $I_{2}(t)=t-B_{2}(t)$. We also introduce

$\displaystyle J_{{1|2}}(t)=\int_{0}^{t}1(Q_{1}(u)>c_{1},Q_{2}(u)=0)du,\qquad
t\geq 0,$

where $c_{1}$ is the threshold for switching from station 1 to station 2.
Obviously,

$\displaystyle J_{{1|2}}(t)\leq B_{{1|2}}(t)\leq I_{2}(t),\qquad t\geq 0.$
(4.5)

Denote by $N_{v}(t)$ the counting processes for potential numbers of class-$v$
customers served up to time $t$, namely,

$\displaystyle N_{v}(t)=\sup\left\\{n\geq
0;\sum_{\ell=1}^{n}\tau_{s,v}(\ell)\leq t\right\\},\qquad t\geq
0,v=1,2,{1|2},$ (4.6)

where $\tau_{s,1|2}(0)=0$ and $\tau_{s,1|2}(n)=t_{s,1|2}(n)-t_{s,1|2}(n-1)$
for $n\geq 1$. Since $D_{v}(t)=N_{v}(B_{v}(t))$ and

$\displaystyle\\{Q_{1}(u)>c_{1},Q_{2}(u)=0\\}=\\{Q_{1}(u)>c_{1},Q_{2}(u)=0,Q_{1|2}(u)>0\\},\qquad
u\geq 0,$

it follows from (4.5) that

$\displaystyle N_{{1|2}}(J_{{1|2}}(t))\leq D_{{1|2}}(t)\leq
N_{{1|2}}(I_{2}(t)),\qquad t\geq 0.$ (4.7)

###  4.2 Auxiliary lemmas

Recall the definition (3.7) of ${\boldsymbol{X}}_{2}(\cdot)$. Under the
Assumption 3.1, ${\boldsymbol{X}}_{2}(\cdot)$ is a Harris irreducible Markov
process with state space $\mathbb{Z}_{+}\times\mathbb{R}_{+}^{2}$, and
describes the $GI/G/1$ queue with traffic intensity
$\rho_{2}=\lambda_{2}/\mu_{2}$. As is well known,
${\boldsymbol{X}}_{2}(\cdot)$ is positive recurrent if and only if
$\rho_{2}<1$. Assume that $\rho_{2}<1$, then, by Little’s law for a customer
in service,

$\displaystyle\mathbb{P}_{\nu_{2}}(Q_{2}(0)\geq
1)=\lambda_{2}/\mu_{2}=\rho_{2},$

where $\mathbb{P}_{\nu_{2}}(Q_{2}(0)\geq
1)=\int_{\mathbb{Z}_{+}\times\mathbb{R}_{+}^{2}}\mathbb{P}(Q_{2}\geq
1|{\boldsymbol{X}}_{2}={\boldsymbol{y}})\nu_{2}(d{\boldsymbol{y}})$ for the
stationary distribution $\nu_{2}$ of ${\boldsymbol{X}}_{2}(\cdot)$, and
therefore (i) of Remark 2.1 yields

$\displaystyle\lim_{t\to\infty}\frac{1}{t}I_{2}(t)=\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}1(Q_{2}(u)=0)du=1-\rho_{2},\qquad
w.p.1.$ (4.8)

######  Lemma 4.1.

If $\rho_{2}=\lambda_{2}/\mu_{2}<1$, then

$\displaystyle\overline{D}_{{1|2}}\equiv\limsup_{t\to\infty}\frac{1}{t}D_{{1|2}}(t)\leq\mu_{{1|2}}(1-\rho_{2}),\qquad
w.p.1,$ (4.9)

and therefore

$\displaystyle\lambda_{1|2}\equiv\mathbb{E}\left(\overline{D}_{{1|2}}\right)\leq\mu_{{1|2}}(1-\rho_{2}).$
(4.10)

###### Proof.

Since

$\sum_{\ell=1}^{N_{{1|2}}(t)}\tau_{s,1|2}(\ell)\leq
t<\sum_{\ell=1}^{N_{{1|2}}(t)+1}\tau_{s,1|2}(\ell),$

strong LLN yields

$\displaystyle\lim_{t\to\infty}\frac{1}{t}N_{{1|2}}(t)=\mu_{{1|2}},\qquad
w.p.1.$ (4.11)

Combing this with (4.7) and (4.8), we have

$\displaystyle\overline{D}_{{1|2}}(t)\leq\limsup_{t\to\infty}\frac{I_{2}(t)}{t}\frac{1}{I_{2}(t)}N_{{1|2}}(I_{2}(t))=\mu_{{1|2}}(1-\rho_{2}),\qquad
w.p.1,$

which proves (4.9). ∎

We will prove Theorem 3.1 by applying Lemmas 3.2 and 3.3. For the sufficiency
of the conditions (3.9) and (3.10), we will use the following lemma.

######  Lemma 4.2.

Assume that $\rho_{2}=\lambda_{2}/\mu_{2}<1$ and

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}}(Q_{1}(u)\leq\ell)du=0,\qquad\forall{\boldsymbol{x}}\in
S,\forall\ell\geq 0.$ (4.12)

Then, there exists a nonnegative sequence $\\{s_{n};n\geq 1\\}$ such that
$s_{n}\uparrow\infty$ and, under $\mathbb{P}_{x}$,

$\displaystyle\liminf_{t\to\infty}\frac{1}{s_{n}}D_{{1|2}}(s_{n})\geq\mu_{{1|2}}(1-\rho_{2}),\qquad
w.p.1.$ (4.13)

###### Proof.

In what follow, we fix ${\boldsymbol{X}}(0)={\boldsymbol{x}}$. Define
$K_{1}(t)$ as

$\displaystyle K_{1}(t)=\int_{0}^{t}1(Q_{1}(u)\leq c_{1})du,\qquad t\geq 0.$

Then, from the Markov inequality, for each $\varepsilon>0$,

$\displaystyle\mathbb{P}(K_{1}(t)>t\varepsilon)\leq\frac{1}{\varepsilon}\mathbb{E}\Big{(}\frac{1}{t}K_{1}(t)\Big{)},$

so (4.12) implies that

$\displaystyle\limsup_{t\to\infty}\mathbb{P}\Big{(}\frac{1}{t}K_{1}(t)>\varepsilon\Big{)}\leq\frac{1}{\varepsilon}\limsup_{t\to\infty}\mathbb{E}\Big{(}\frac{1}{t}K_{1}(t)\Big{)}=\limsup_{t\to\infty}\frac{1}{\varepsilon
t}\int_{0}^{t}\mathbb{P}(Q_{1}(u)\leq c_{1})du=0.$

Hence, $\frac{1}{t}K(t)$ converges to $0$ in probability as $t\to\infty$.
Then, as is well known (e.g., see Corollary 6.1.2 of [2]), we can choose a
subsequence $\\{s_{n};n\geq 1\\}$ from $\mathbb{R}_{+}$ such that
$s_{n}\to\infty$ as $n\to\infty$ and

$\displaystyle\lim_{n\to\infty}\frac{1}{s_{n}}K_{1}(s_{n})=0,\qquad w.p.1.$
(4.14)

Since

$\displaystyle
J_{{1|2}}(t)=\int_{0}^{t}1(Q_{2}(u)=0)du-\int_{0}^{t}1(Q_{1}(u)\leq
c_{1},Q_{2}(u)=0)du$

and $\int_{0}^{t}1(Q_{1}(u)\leq c_{1},Q_{2}(u)=0)du\leq K_{1}(t)$, (4.8) and
(4.14) yield

$\displaystyle\lim_{n\to\infty}\frac{1}{s_{n}}J_{{1|2}}(s_{n})=\lim_{n\to\infty}\frac{1}{s_{n}}\int_{0}^{s_{n}}1(Q_{2}(u)=0)du=1-\rho_{2},\qquad
w.p.1,$

because ${\boldsymbol{X}}_{2}(\cdot)$ is positive Harris recurrent by
$\rho_{2}<1$. Hence, this together with (4.7) and (4.11) imply that

$\displaystyle\liminf_{n\to\infty}\frac{1}{s_{n}}D_{{1|2}}(s_{n})$
$\displaystyle\geq\liminf_{n\to\infty}\frac{J_{{1|2}}(s_{n})}{s_{n}}\frac{1}{J_{{1|2}}(s_{n})}N_{{1|2}}(J_{{1|2}}(s_{n}))$
$\displaystyle=(1-\rho_{2})\liminf_{t\to\infty}\frac{1}{J_{{1|2}}(s_{n})}N_{{1|2}}(J_{{1|2}}(s_{n)})$
$\displaystyle=(1-\rho_{2})\mu_{{1|2}},\qquad w.p.1,$

where the last equality is obtained by (4.11). Thus, we have proved (4.13). ∎

###  4.3 The proof of Theorem 3.1

We now start to prove Theorem 3.1. We first prove the sufficiency of (3.9) and
(3.10). We apply reduction to the absurdity. For this assume (4.12) for all
${\boldsymbol{x}}\in S$ and $\ell\geq 0$. Since $\rho_{2}<1$, it follows from
Lemmas 4.1 and 4.2 that, for the nonnegative sequence $\\{s_{n};n\geq 1\\}$
obtained in Lemma 4.2,

$\displaystyle\lim_{n\to\infty}\frac{1}{s_{n}}A_{{1|2}}(s_{n})=\lim_{n\to\infty}\frac{1}{s_{n}}D_{{1|2}}(s_{n})=\mu_{{1|2}}(1-\rho_{2}),\qquad
w.p.1.$ (4.15)

Since $B_{1}(t)=t-\int_{0}^{t}1(Q_{1}(u)=0)du$, we have, by (4.14),

$\displaystyle\lim_{n\to\infty}\frac{1}{s_{n}}B_{1}(s_{n})=1-\lim_{n\to\infty}\frac{1}{s_{n}}\int_{0}^{s_{n}}1(Q_{1}(u)=0)du=1,\qquad
w.p.1.$ (4.16)

Furthermore, because $D_{v}(t)=N_{v}(B_{v}(t))$, strong LLN and (4.16) yield

$\displaystyle\lim_{n\to\infty}\frac{1}{s_{n}}A_{1}(s_{n})=\lambda_{1},\qquad
w.p.1,$ (4.17)
$\displaystyle\lim_{n\to\infty}\frac{1}{s_{n}}D_{1}(s_{n})=\lim_{n\to\infty}\frac{1}{s_{n}}B_{1}(s_{n})\frac{1}{B_{1}(s_{n})}N_{1}(B_{1}(s_{n}))=\mu_{1},\qquad
w.p.1.$ (4.18)

Hence, (4.2) yields

$\displaystyle\lambda_{1}-\mu_{1}-\mu_{{1|2}}(1-\rho_{2})=\lim_{n\to\infty}\frac{1}{s_{n}}Q_{1}(s_{n})\geq
0,\qquad w.p.1,$ (4.19)

which implies that

$\displaystyle\lambda_{1}\geq\mu_{1}+\mu_{{1|2}}(1-\rho_{2}).$ (4.20)

Consequently, (4.12) for all ${\boldsymbol{x}}\in S$ and $\ell>0$ implies
(4.20). Thus, taking the contraposition of this implication,

$\displaystyle\lambda_{1}<\mu_{1}+\mu_{{1|2}}(1-\rho_{2})$ (4.21)

implies that (4.12) does not hold, that is, for some ${\boldsymbol{x}}\in S$
and some $\ell\geq 0$,

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}}(Q_{1}(u)\leq\ell)du>0.$
(4.22)

Hence, ${\boldsymbol{X}}(\cdot)$ is positive Harris recurrent by Lemma 3.2.

For the necessity of (3.9) and (3.10), assume that ${\boldsymbol{X}}(\cdot)$
is positive Harris recurrent. As noted at the beginning of Section 4.2, this
implies that $\rho_{2}<1$. So, we only need to show the necessity of (3.9).
From the positive recurrence of ${\boldsymbol{X}}(\cdot)$, we have
$\rho^{*}_{1}(\xi)=1-\mathbb{P}_{\nu}(Q_{1}(0)=0)<1$ by Lemma 3.3. By Lemma
4.1, $\overline{D}_{{1|2}}\leq\mu_{{1|2}}(1-\rho_{2})$. Hence, applying
Little’s law to the class-1 customers who are served at station 1 and their
mean number in service, which is $\rho^{*}_{1}(\xi)$, we have

$\displaystyle\mu_{1}\rho^{*}_{1}(\xi)=\lambda_{1}-\lambda_{{1|2}}\geq\lambda_{1}-\mu_{{1|2}}(1-\rho_{2}).$
(4.23)

On the other hand, from the definition (3.9) of $\widetilde{\rho}_{1}$,

$\mu_{{1|2}}(1-\rho_{2})\widetilde{\rho}_{1}=\lambda_{1}-\mu_{1}\widetilde{\rho}_{1}.$

Hence, it follows from (4.23) that

$\displaystyle\mu_{1}\rho^{*}_{1}(\xi)\widetilde{\rho}_{1}\geq\lambda_{1}\widetilde{\rho}_{1}-\mu_{{1|2}}(1-\rho_{2})\widetilde{\rho}_{1}=\lambda_{1}\widetilde{\rho}_{1}-\lambda_{1}+\mu_{1}\widetilde{\rho}_{1},$

which is equivalent to
$\lambda_{1}(1-\widetilde{\rho}_{1})\geq\mu_{1}\widetilde{\rho}_{1}(1-\rho^{*}_{1}(\xi))$.
Thus, $\rho^{*}_{1}(\xi)<1$ implies $\widetilde{\rho}_{1}<1$. This proves that
(3.9) is necessary for the stability, and the proof of Theorem 3.1 is
completed.

##  5 General $k$-station cascade system

We next consider an extension of Theorem 3.1 to a cascade system with
$k$-stations, which are numbered as $1,2,\ldots,k$ from top to bottom. Each
station $i$ has exogenous arrivals, called class-$i$ customers, and served in
the manner of first come first served. If the number of class-$i$ customers is
greater than $c_{i}$ and if station $i+1$ is empty, then one class-$i$
customer not in service immediately moves to station $i+1$ as a
class-$i|(i+1)$ customer at station $i+1$ for $i\leq k-1$, where $c_{i}$ is a
positive integer. It is assumed that a class-$i|(i+1)$ customer is only served
when there is no class-$(i+1)$ customer, and its service is resumed when
class-$(i+1)$ customers vanish at station $i+1$. All customers leave the
system when their service is completed. We refer to this system as a
$k$-station cascade system.

Note that the system is stochastically independent of which class-$i$ customer
not in service moves to station $i+1$ as a class-$i|(i+1)$ customer.
Furthermore, an exogenously arriving class-$(i+1)$ customer preempts
class-$i|(i+1)$ customer when the latter is being served at station $(i+1)$.
Hence, the stability of station $i$ is independent of the dynamics of stations
$1,2,\ldots,i-1$, but it is influenced from downward stations
$i+1,i+2,\ldots,k$. Let $Q_{i}(t)$ be the number of class-$i$ customers in
station $i$ at time $t\geq 0$ and let $Q_{i-1|i}(t)$ the number of
class-$(i-1)|i$ customers in station $i$ at time $t$. The remaining times
$R_{e,i}(t)$, $R_{s,i}(t)$ for $i=1,2,\ldots,k$ and $R_{s,i|(i+1)}(t)$ for
$i=1,2,\ldots,k-1$ are defined for each time $t\geq 0$ similarly to the case
of $k=2$.

As for the regularity condition, we need to replace Assumption 3.1 by its
$k$-station version. Namely,

######  Assumption 5.1.

For $i=1,2,\ldots,k$, the conditions (a) and (b) of Assumption 3.1 hold.

Similarly to the case of $k=2$, we can construct the Markov process
${\boldsymbol{X}}(\cdot)\equiv\\{{\boldsymbol{X}}(t);t\geq 0\\}$ by using the
remaining arrival and service times, where

$\displaystyle{\boldsymbol{X}}(t)=({\boldsymbol{Q}}_{1,k}(t),{\boldsymbol{R}}_{e,1,k}(t),{\boldsymbol{R}}_{s,1,k}(t),{\boldsymbol{R}}_{s,1,k}^{+}(t))\in
S\equiv\mathbb{Z}_{+}^{2k}\times\\{0,1\\}^{k-1}\times\mathbb{R}_{+}^{3k-1},$
(5.1)

where, for $i=1,2,\ldots,k$,

$\displaystyle{\boldsymbol{Q}}_{i,k}(t)=(Q_{i}(t),Q_{i+1}(t),\ldots,Q_{k}(t),Q_{i|(i+1)}(t),Q_{(i+1)|(i+2)}(t),\ldots,Q_{(k-1)|k}(t)),$
$\displaystyle{\boldsymbol{R}}_{e,i.k}(t)=(R_{e,i}(t),R_{e,i+1}(t),\ldots,R_{e,k}(t)),\quad{\boldsymbol{R}}_{s,i,k}(t)=(R_{s,i}(t),R_{s,i+1}(t),\ldots,R_{s,k}(t)),$
$\displaystyle{\boldsymbol{R}}_{s,i,k}^{+}(t)=(R_{s,i|(i+1)}(t),R_{s,(i+1)|(i+2)}(t),\ldots,R_{s,(k-1)|k}(t)).$

To describe the system dynamics, we also introduce counting processes. For
$v=i$ and $v=(i-1)|i$, let $A_{v}(t)$ be the number of the arrivals of
class-$v$ customers up to time $t\geq 0$, and let $N_{v}(t)$ be the number of
potential service completions of class-$v$ customers by time $t$ for
$v=1,2,\ldots,k$ and $v=1|2,2|3,\ldots,(k-1)|k$. It is assumed that
$A_{i}(\cdot)$ and $N_{i}(\cdot)$ for $i=1,2,\ldots,k$ and
$N_{(i-1)|i}(\cdot)$ for $i=2,3,\ldots,k$ are independent renewal processes.
Their rates are denoted by $\lambda_{i}$, $\mu_{i}$ and $\mu_{(i-1)|i}$,
respectively.

Let $D_{v}(t)$ be the number of departures of class-$v$ customers by time
$t\geq 0$. Let

$\displaystyle L_{i}(t)=Q_{i}(t)+Q_{(i-1)|i}(t)1(i\geq 2),\qquad
i=1,2,\ldots,k.$

Note that class-$i$ and class-$(i-1)|i$ customers have different service time
distributions for $i\geq 2$. From the modeling assumptions, we have, for
$i=1,2,\ldots,k$,

$\displaystyle Q_{i}(t)=Q_{i}(0)+A_{i}(t)-(D_{i}(t)+A_{i|i+1}(t)),\quad t\geq
0,$ (5.2) $\displaystyle
Q_{(i-1)|i}(t)=Q_{(i-1)|i}(0)+A_{(i-1)|i}(t)-D_{(i-1)|i}(t),\quad t\geq 0,$
(5.3)

where $A_{0|1}(t)=A_{k|(k+1)}(t)=0$. Note that the term
$A_{(i-1)|i}(t)-D_{(i-1)|i}(t)$ has no influence on the stability of
$Q_{i}(t)$ because the assumption on class-$(i-1)|i$ customers implies

$\displaystyle 0\leq A_{(i-1)|i}(t)-D_{(i-1)|i}(t)\leq 1,\qquad t\geq 0.$
(5.4)

Let $\rho_{i}=\frac{\lambda_{i}}{\mu_{i}}$ for $i=1,2,\ldots,k$. Similar to
(3.11), we define $\rho^{*}_{i}(\xi)$ for a distribution $\xi$ as

$\displaystyle\rho^{*}_{i}(\xi)\equiv\liminf_{t\to\infty}\frac{1}{t}\int_{0}^{t}\Big{(}\int_{S}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)\geq
1)\xi(d{\boldsymbol{x}})\Big{)}du,\qquad i=2,3,\ldots,k.$ (5.5)

We also define a Markov process describing the last $k-i+1$ stations by

$\displaystyle{\boldsymbol{X}}_{i,k}(\cdot)\equiv\\{({\boldsymbol{Q}}_{i,k}(t),{\boldsymbol{R}}_{e,i,k}(t),{\boldsymbol{R}}_{s,i,k}(t),{\boldsymbol{R}}^{+}_{s,i,k}(t));t\geq
0\\},\qquad i=1,2,\ldots,k.$

Then, the following lemma is proved in the exactly same way as Lemmas 3.3 and
4.1.

######  Lemma 5.1.

Under Assumption 5.1, for each $i=1,2,\ldots,k$,
${\boldsymbol{X}}_{i,k}(\cdot)$ is positive Harris recurrent if and only if
$\rho^{*}_{j}(\xi)<1$ for $j=i,i+1,\ldots,k$ for some distribution $\xi$ on
$S$. Furthermore, particularly when this is the case: for $i\geq 2$,

$\displaystyle\overline{D}_{{(i-1)|i}}\equiv\limsup_{t\to\infty}\frac{1}{t}D_{{(i-1)|i}}(t)\leq\mu_{{(i-1)|i}}(1-\rho^{*}_{i}(\xi)),\qquad
w.p.1,$ (5.6)
$\displaystyle\lambda_{(i-1)|i}\equiv\mathbb{E}\left(\overline{D}_{{(i-1)|i}}\right)\leq\mu_{{(i-1)|i}}(1-\rho^{*}_{i}(\xi)).$
(5.7)

Then, we have the following result similar to Theorem 3.1.

######  Theorem 5.1.

Under Assumption 5.1, the Markov process ${\boldsymbol{X}}(\cdot)$ which
describes the $k$-station cascade system is positive recurrent if and only if
the following conditions hold for some distribution $\xi$ on $S$.

$\displaystyle\widetilde{\rho}_{i}(\xi)\equiv\frac{\lambda_{i}}{\mu_{i}+\mu_{{i|(i+1)}}(1-\rho^{*}_{i+1}(\xi))}<1,\qquad
i=1,2,\ldots,k-1,$ (5.8)
$\displaystyle\widetilde{\rho}_{k}(\xi)\equiv\rho_{k}<1.$ (5.9)

This theorem is proved in the exactly same way as Theorem 3.1 using the
induction on $i$ from $i=k-1$ to $1$. We outline this proof below.

The necessity of (5.8) and (5.9) can be proved in the same way as the proof of
Theorem 3.1 using Lemma 5.1 instead of Lemma 3.3. To see their sufficiency,
suppose that $\widetilde{\rho}_{i}(\xi)<1$ and $\rho^{*}_{j}(\xi)<1$ for
$j=i+1,i+2,\ldots,k$, then ${\boldsymbol{X}}_{i,k}(\cdot)$ is positive
recurrent by a similar proof in Theorem 3.1 and Lemma 5.1. Hence,
$\rho^{*}_{i}(\xi)<1$ by Lemma 5.1. Inductively repeating this argument from
$i=k-1$ to $i=1$, we can conclude that
${\boldsymbol{X}}_{1,k}(\cdot)(={\boldsymbol{X}}(\cdot))$ is positive
recurrent.

######  Remark 5.1.

Theorem of [7] formulates the stability problem in a slightly different way
that the stability condition is checked backward induction from $k$ to $1$.
Then, Theorem 1 of [7] says that ${\boldsymbol{X}}_{i,k}(\cdot)$ is stable if
and only if $\widetilde{\rho}_{i}(\xi)<1$ and
${\boldsymbol{X}}_{i+1,k}(\cdot)$ is stable. Obviously, this is essentially
rephrasing Theorem 3.1 of [12] (also of this paper). Theorem 5.1 is a little
more than it due to Lemma 5.1.

##  6 Concluding remarks

We have assumed that the exogenous arrival processes $A_{i}(\cdot)$ at station
$i$ are independent renewal processes with finite arrival rates and the
service times of each class of customers are $i.i.d.$. However, from the proof
of Theorem 3.1, those assumptions can be relaxed in proving that (3.9) implies
(4.22) under the assumption $\rho_{2}<1$, which is the core part in the proof
of Theorem 3.1. Namely, this implication is valid as long as the following
conditions hold.

$\displaystyle\lim_{t\to\infty}\frac{1}{t}A_{i}(t)=\lambda_{i},\qquad
i=1,2,\;w.p.1,$ (6.1)
$\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum_{\ell=1}^{n}\tau_{s,v}(\ell)=\mu_{v},\qquad
v=1,2,{1|2},\;w.p.1,$ (6.2)
$\displaystyle\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}1(Q_{2}(s)=0)ds=\max(0,1-\rho_{2}),\qquad
w.p.1,$ (6.3)

where $\rho_{2}=\lambda_{2}/\mu_{2}$.

The condition (4.22) is much weaker than the existence of the stationary
distribution of $Q_{1}(\cdot)$, but it may be interpreted as a certain
stability property of the process $Q_{1}(\cdot)$. Hence, it may be interesting
to investigate the stability of the 2-station cascade system in a weaker sense
for more general exogenous arrival processes based on the conditions (6.1),
(6.2) and (6.3).

## Acknowledgements

After the submission of this paper, we have learned that Kim and Kim [7]
disproves the conjecture of [11]. We thanks the Editor-in-chief for allowing
us to revise the original submission taking [7] into account. We are grateful
to the anonymous referee for pointing out various errors in the revised
submissions and helpful suggestions for correcting them.

## Appendix

###  A.1 The equivalence of (a) and (c) in Proposition 2.2

We prove that (a) is equivalent to (c) in Proposition 2.2. We first note that,
under the assumption that $X(\cdot)$ is a Harris irreducible $T$-process,
$X(\cdot)$ is either Harris recurrent or $\sigma$-transient by the
irreducibility and the Doeblin decomposition (see Theorem 3.1 of [16]), where
$X(\cdot)$ is said to be $\sigma$-transient if $S$ is a countable union of
measurable sets $A_{i}$ for $i\geq 1$ such that
$\mathbb{E}_{x}(\eta_{A_{i}})<\infty$ for all $x\in S$ and for all $i\geq 1$,
in which case each $A_{i}$ is said to be uniformly transient. If $X(\cdot)$ is
positive Harris recurrent, then it has an invariant probability measure.
Denote it by $\nu$. Then, (2.5) is immediate from (2.2) in Remark 2.1 because
there exists a compact set $C\subset S$ such that $\nu(C)>0$ by the tightness
of $\nu$ on $S$.
Conversely, if (2.5) holds, then $\mathbb{E}_{x}(\eta_{C})=\infty$ for the
compact set $C$. Hence, $X(\cdot)$ can not be $\sigma$-transient, and
therefore it is Harris recurrent by the Doeblin decomposition. Thus, there is
a unique invariant measure. Suppose that this $X(\cdot)$ is null recurrent,
then it follows from (2.3) in Remark 2.1 that, for all $x\in S$ and any
compact set $C\subset S$,

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{x}(X(u)\in
C)du=0.$ (A.1)

This contradicts (2.5), so $X(\cdot)$ must be positive Harris recurrent.

###  A.2 Proof of (ii) of Lemma 3.1

By (i) of Lemma 3.1 ${\boldsymbol{X}}(\cdot)$ is a $T$-process. Let
$\varphi(B)=T({\boldsymbol{x}}^{*},B)$, then $T({\boldsymbol{x}}^{*},B)>0$
implies that $T({\boldsymbol{y}},B)>0$ for $\forall{\boldsymbol{y}}$ in some
open set $V({\boldsymbol{x}}^{*})$ containing ${\boldsymbol{x}}^{*}$ by the
lower semi-continuity of $T(\cdot,B)$. Furthermore, let $e$ be the exponential
distribution with unit mean, then
$K_{e}({\boldsymbol{x}},V({\boldsymbol{x}}^{*}))=\int_{0}^{\infty}\mathbb{P}_{{\boldsymbol{x}}}({\boldsymbol{X}}(u)\in
V({\boldsymbol{x}}^{*}))e^{-u}du>0$ for $\forall{\boldsymbol{x}}\in S$ since
${\boldsymbol{x}}^{*}$ is reachable from any ${\boldsymbol{x}}\in S$. Hence,
for the sampling distribution $a$ by which ${\boldsymbol{X}}(\cdot)$ is a
$T$-process,

$\displaystyle
K_{e*a}({\boldsymbol{x}},B)\geq\int_{V_{\varepsilon}({\boldsymbol{x}}^{*})}K_{e}({\boldsymbol{x}},d{\boldsymbol{y}})K_{a}({\boldsymbol{y}},B)\geq\int_{V_{\varepsilon}({\boldsymbol{x}}^{*})}K_{e}({\boldsymbol{x}},d{\boldsymbol{y}})T({\boldsymbol{y}},B)>0,\quad\forall{\boldsymbol{x}}\in
S,$

where $e*a$ is the convolution of distributions $e$ and $a$ on
$\mathbb{R}_{+}$, and $K_{e*a}(\cdot,\cdot)$ is $e*a$-sampling $K$-chain. This
proves that ${\boldsymbol{X}}(\cdot)$ is $\varphi$-irreducible because
distribution $e*a$ has an absolutely continuous component with respect to
Lebesgue measure on $\mathbb{R}_{+}$.

###  A.3 Proof of Lemma 3.2

Obviously, (2.5) implies (3.8) for $X(\cdot)={\boldsymbol{X}}(\cdot)$, so we
only need to prove that (3.8) implies (2.5). Recall that
${\boldsymbol{X}}_{2}(\cdot)$ is the Markov process describing the queue of
class-2 customers. We first show that ${\boldsymbol{X}}_{2}(\cdot)$ is a
positive Harris recurrent if (3.8) holds for $i=2$. Since $R_{e,2}(\cdot)$ is
a regenerative process with cycles $\tau_{e,2}(\cdot)$ and $R_{s,2}(\cdot)$ is
dominated by such a regenerative process $Y(\cdot)$ with cycles
$\tau_{s,2}(\cdot)$ in the sense that

$\displaystyle\int_{0}^{t}1(R_{s,2}(u)\leq x)du\leq\int_{0}^{t}1(Y(u)\leq
x)du,\qquad x\geq 0,t\geq 0.$

both of $R_{e,2}(\cdot)$ and $R_{s,2}(\cdot)$ are tight on average. Hence, by
Proposition 2.2, for any ${\boldsymbol{x}}_{2}\in S$, any $\varepsilon>0$ and
$v=e,s$, there is a compact subset $C_{v,2}\subset\mathbb{R}_{+}$ such that

$\displaystyle\liminf_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}_{2}}(R_{v,2}(u)\in
C_{v,2})du\geq 1-\varepsilon.$ (A.2)

Let $\widetilde{C}_{2}=C_{2,e}\times C_{2,s}$, then

$\displaystyle\mathbb{P}_{{\boldsymbol{x}}_{2}}({\boldsymbol{X}}_{2}(u)\in\\{0\\}\times\widetilde{C}_{2})$
$\displaystyle\geq\mathbb{P}_{{\boldsymbol{x}}_{2}}(Q_{2}(u)=0)-\mathbb{P}_{{\boldsymbol{x}}_{2}}(R_{e,2}(u),R_{s,2}(u))\not\in\widetilde{C}_{2})$
$\displaystyle\geq\mathbb{P}_{{\boldsymbol{x}}_{2}}(Q_{1}(u)=0)-\big{(}\mathbb{P}_{{\boldsymbol{x}}_{2}}(R_{e,2}(u)\not\in
C_{e,2})+\mathbb{P}_{{\boldsymbol{x}}}(R_{s,2}(u)\not\in C_{s,2})\big{)}$
$\displaystyle\geq\mathbb{P}_{{\boldsymbol{x}}_{2}}(Q_{1}(u)=0)-2\varepsilon.$

Integrating this inequality for $u\in[0,t]$, it follows from (3.8) for $i=2$
that there is some ${\boldsymbol{x}}^{\prime}_{2}\in S$,

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}^{\prime}_{2}}({\boldsymbol{X}}_{2}(u)\in\\{0\\}\times\widetilde{C}_{2})du>0.$

By Proposition 2.2, this proves that ${\boldsymbol{X}}_{2}(\cdot)$ is positive
recurrent. Furthermore, it is tight on average by (b) of Proposition 2.2.
Since $Q_{1|2}(t)\leq 1$ for $\forall t\geq 0$, $\\{Q_{1|2}(t);t\geq 0\\}$ is
obviously tight on average. Similar to $R_{e,2}(\cdot)$ and $R_{s,2}(\cdot)$,
$R_{e,1}(\cdot)$, $R_{s,1}(\cdot)$ and $R_{s,1|2}(\cdot)$ are also tight on
average. Hence, by a similar argument to ${\boldsymbol{X}}_{2}(\cdot)$, (3.8)
for $i=1$ implies (2.5) for $X(\cdot)={\boldsymbol{X}}(\cdot)$.

###  A.4 Proof of Lemma 3.3

Note that, under Assumption 3.1, ${\boldsymbol{X}}(\cdot)$ is
$\varphi$-irreducible $T$-process by Lemma 3.1. (i) Since
${\boldsymbol{X}}(\cdot)$ is positive Harris recurrent, it has the stationary
distribution $\nu$, and, by (2.2) in Remark 2.1,

$\displaystyle\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)\geq
1)du=\mathbb{P}_{\nu}(Q_{i}\geq 1),\qquad\forall{\boldsymbol{x}}\in S,i=1,2.$

Integrating both sides of this equation by $\xi$ and applying the dominated
convergence theorem, we have

$\displaystyle\lim_{t\to\infty}\frac{1}{t}\int_{0}^{t}\Big{(}\int_{S}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)\geq
1)\xi(d{\boldsymbol{x}})\Big{)}du=1-\mathbb{P}_{\nu}(Q_{i}(0)=0).$

This and the definition of $\rho^{*}_{i}(\xi)$ prove (3.12).
(ii) By Lemma 3.2, we only need to show that $\rho^{*}_{i}(\xi)<1$ for $i=1,2$
is equivalent to (3.8) for some ${\boldsymbol{x}}\in S$ and some $\ell\geq 0$.
Assume that $\rho^{*}_{i}(\xi)<1$ for $i=1,2$. Because, by Fatou’s lemma,

$\displaystyle\rho^{*}_{i}(\xi)\geq\int_{S}\Big{(}\liminf_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)\geq
1)du\Big{)}\xi(d{\boldsymbol{x}}),$

we have

$\displaystyle\int_{S}\Big{(}\limsup_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)=0)du\Big{)}\xi(d{\boldsymbol{x}})$
$\displaystyle=\int_{S}\Big{(}1-\liminf_{t\to\infty}\frac{1}{t}\int_{0}^{t}\mathbb{P}_{{\boldsymbol{x}}}(Q_{i}(u)\geq
1)du\Big{)}\xi(d{\boldsymbol{x}})\geq 1-\rho^{*}_{i}(\xi)>0.$

Hence, (3.8) holds for $i=1,2$, $\ell=0$ and some ${\boldsymbol{x}}_{i}\in S$.

Conversely, assume (3.8) for $i=1,2$ and some ${\boldsymbol{x}}_{i}\in S$ and
some $\ell=0$. Then, ${\boldsymbol{X}}(\cdot)$ is positive Harris recurrent by
Lemma 3.2. Hence, (3.12) holds by (i) of Lemma 3.3, and therefore we only need
to show that $\mathbb{P}_{\nu}(Q_{i}(0)=0)>0$ for $i=1,2$. To prove this, we
first note that ${\boldsymbol{X}}(\cdot)$ is Harris $\varphi$-irreducible for
$\varphi(B)=T({\boldsymbol{x}}^{*},B)$ by Lemma 3.1. Hence, $\varphi(B)>0$
implies $K_{a}({\boldsymbol{x}},B)>0$ for $\forall{\boldsymbol{x}}\in S$ for
some sampling distribution $a$ by Definition 2.2. Then, for the stationary
distribution $\nu$ of ${\boldsymbol{X}}(\cdot)$, for any sampling distribution
$a$ on $\mathbb{R}_{+}$,

$\displaystyle\nu(B)\geq\int_{S}\nu(d{\boldsymbol{x}})K_{a}({\boldsymbol{x}},B)>0.$

Hence, $\varphi(B)>0$ implies $\nu(B)>0$ for any $B\in{\mathcal{B}}(S)$. From
the definition of $\varphi$, $\varphi(G)>0$ for any open set $G$ containing
${\boldsymbol{x}}^{*}$ of Lemma 3.1. As this $G$, we choose $G_{0}$ defined by

$\displaystyle
G_{0}=\\{0\\}\times\mathbb{Z}_{+}\times\\{0,1\\}\times\mathbb{R}_{+}^{5}\subset
S,$

which obviously contains ${\boldsymbol{x}}^{*}$. Since the discrete topology
is taken on $\mathbb{Z}_{+}^{2}\times\\{0,1\\}$, $G_{0}$ is an open set.
Hence, $\varphi(G_{0})>0$, which implies that
$\mathbb{P}_{\nu}(Q_{1}(0)=0)=\nu(G_{0})>0$. This proves that
$\rho_{1}^{*}(\xi)<1$. Similarly, $\rho^{*}_{2}(\xi)<1$ is proved.

## References

  * Azema et al. [1967] Azema, J., Kaplan-Duflo, M. and Revuz, D. (1967).  Mesure invariante surles classes récurrentes des processus de Markov.  Z. Wahrscheinlichkeitstheorie verw. Gebjete, 8 157–181.
  * Borovkov [2013] Borovkov, A. A. (2013).  Probability Theory.  Springer.
  * Chernova et al. [2013] Chernova, N., Foss, S. and Kim, B. (2013).  A polling system whose stability region depends on the whole distribution of service times.  Operations Research Letters, 41 188–190.
  * Dai [1995] Dai, J. G. (1995).  On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models.  Annals of Applied Probability, 5 49–77.
  * Davis [1993] Davis, M. H. A. (1993).  Markov Models and Optimization.  Monographs on Statistics and Applied Probability 49, Chapman & Hall.
  * Delgado and Morozov [2014] Delgado, R. and Morozov, E. (2014).  Stability analysis of cascade networks via fluid models.  Performance Evaluation, 82 39–54.
  * Kim and Kim [2023] Kim, B. and Kim, J. (2023).  Stability of a cascade system with multiple stations.  Queueing Systems, 104, 53–64.
  * Meyn and Tweedie [2009] Meyn, S. and Tweedie, R. L. (2009).  Markov chains and stochastic stability.  2nd ed. Cambridge University Press, Cambridge.
  * Meyn and Down [1994] Meyn, S. P. and Down, D. (1994).  Stability of generalized Jackson networks.  Annals of Applied Probability, 4 124–148.
  * Meyn and Tweedie [1993] Meyn, S. P. and Tweedie, R. L. (1993).  Stability of Markovian processes II: Continuous time processes and sampled chains.  Adv. Appl. Probab., 25 487–517.
  * Miyazawa and Morozov [2022a] Miyazawa, M. and Morozov, E. (2022a).  Stability condition of a cascade system with a general number of stations.  Queueing Systems, 100 225–227.
  * Miyazawa and Morozov [2022b] Miyazawa, M. and Morozov, E. (2022b).  Stability of a cascade system with two stations and its extension for multiple stations.  ArXiv e-prints, https://doi.org/10.48550/arXiv.2203.14294.
  * Morozov and Steyaert [2013] Morozov, E. and Steyaert, B. (2013).  Stability analysis of a two-station cascade queueing network.  Annals of Operations Research, 202 135–160.
  * Tezcan [2013] Tezcan, T. (2013).  Stability analysis of N-model systems under a static priority rule.  Queueing Systems, 73 235–259.
  * Tuominen and Tweedie [1979a] Tuominen, P. and Tweedie, R. L. (1979).  Markov chains with continuous components.  Proceedings of London Mathematical Society, 38 89–114.
  * Tuominen and Tweedie [1979b] Tuominen, P. and Tweedie, R. L. (1979).  The recurrence structure of general Markov process,  Proceedings of London Mathematical Society, 38 554–576.