text:
\begin{document}
\title{\documenttitle}
\author{Sonja Otten, Ruslan Krenzler, Hans Daduna, Karsten Kruse}

\maketitle

\begin{abstract}
Exponential single server queues with state dependent arrival and service rates are considered which evolve under influences of external environments.
The transitions of the queues are influenced by the environment's state and the movements of the environment depend on the status of the queues (bi-directional interaction).
The structure of the environment is constructed in a way to encompass various models from the recent Operation Research literature, where a queue is coupled e.g. with an inventory or with reliability issues.
With a Markovian joint queueing-environment process we prove separability for a large class of such interactive systems, i.e. the steady state distribution is of product form and explicitly given: The queue and the environment processes decouple asymptotically and in steady state.\\
For non-separable systems we develop ergodicity criteria via Lyapunov functions. By examples we show principles for bounding throughputs of non-separable systems by throughputs of two separable systems as upper and lower bound.
\end{abstract}

{\it Key Words}: Queues; interactive random environment;
separable systems; product form steady state; Lyapunov functions;
throughput bounds; queueing-inventory systems

\section{Introduction and literature review}\label{sect:intro}
Queueing systems which evolve under influences from external sources have found interest for long times. Today's emerging complex technological and/or logistic systems revived interest in such structures which are used to model various features in service and related systems:
Services of different quality are provided to individual customers, or to general differentiated demand, even to data sets (messages in sensor networks), etc., under side-constraints of limited and shared resources and further restrictions which are external from the point of view of the service system.
The need for understanding the behaviour of these systems revived  investigations of queueing systems in a dedicated environment. Moreover, because in real life situations service systems are subject to random interarrival and service time requests and the environments are usually non-deterministic as well, the area of queues in random environments is today a field of active research in applied probability.

The model of a queue in a random environment studied in this note summarizes and unifies various models from different research areas, especially in Operations Research, which emerged over the last two decades. Representative examples are e.g.:
\begin{enumerate}
\item
Supply chains of production facilities (modeled as  a queue) with an attached inventory.
This model was seemingly investigated first in \cite{sigman;simchi-levi:92} and \cite{melikov;molchanov:92}, where demand in case of stock-out at the inventory is backordered. Intense
research on this model started with a series of papers by Berman and his coauthors, e.g.~\cite{berman;kim:99,berman;sapna:00,berman;sapna:02}. The first explicit results on stationary behaviour for such integrated production-inventory models seem to be \cite{schwarz;sauer;daduna;kulik;szekli:06}, where demand in case of stock-out at the inventory is lost. It was shown that the associated queueing-inventory process is separable. A review on separable systems is \cite{krishnamoorthy;lakshmy;manikandan:11}. More recent contributions which focus on product form steady states are \cite{saffari;haji;hassanzadeh:11,saffari;asmussen;haji:13,vineetha:08} and recently \cite{otten:18}.
\item
Sensor networks, where a dedicated node  (test node, referenced node) featuring an internal message queue which
interacts with a complex environment. The environment  incorporates especially location and status of
neighboured sensor nodes and  geographical conditions, as well as internal status information of the referenced node, e.g.~activity level or sleep mode.
A detailed study is \cite{krenzler;daduna:14},  where a compilation of related literature can be found in Section 1.
\item
Queues where the availability of service capacity  depends on external
conditions and/or control decisions, e.g.~for preventive maintenance. This has been topic of continuous research over decades, a review paper is \cite{krishnamoorthy;pramod;chakravarthy:14}.
 Explicit formulas for the stationary distribution of such system, even for networks of service systems were derived in \cite{sauer;daduna:03}.
A recent study of performability for a randomly degrading queue
with maintenance options in the spirit of our present research is \cite{krenzler;daduna:15a}.
\item
Queueing networks where a node of special interest is embedded in the ``environment'' constituted by the set of the other nodes,
are investigated e.g. in \cite[Section 4.5.1]{dijk:93} and \cite{krenzler;daduna:15}.
\item
Queues in a random environment as an example for application of matrix-analytical methods in the framework of quasi-birth-death-processes. Typical  examples are Markov-arrival processes (MAPs) with queue-length dependent service mechanisms, and related structures, see e.g.\ \cite[Sections 3 and 6]{neuts:81} for general principles. A control problem in the realm of queues in a random environment is \cite{helm;waldmann:84}.
The general feature of all these
quasi-birth-death-process models is: The queue length process is the level process while the environment process is the phase process.
A note in the spirit of the present paper is \cite{economou:03a} where criteria for the existence of a  stationary distribution of product form are provided.
\item  Closely related to our present research on queues which are subject to external side constraints  with accessible stationary distribution are \cite{falin:96} and  \cite{krenzler;daduna:15}.
\end{enumerate}

All these examples can be described by a model which incorporates  a queue and its environment.
We are interested in the common structural properties of a unified Markovian description for the interacting queueing-environment system. A careful study of the above examples reveals a general principle: {\bf(i)} The evolution of the system is of rather general structure but in any case some special environment conditions interrupt the dynamics of the queueing system, and the server is stalled as long as these conditions hold on.
{\bf(ii)} The environment is non-autonomous with respect to the queueing system, i.e. its dynamics depend on the status of the associated queueing system (interactive random environment \cite{pang;sarantsev;belopolskaya;suhov:20}). This ``bi-directional interaction'' is different from most work in the literature but reflects many real situations, as shown in the examples above.

Special emphasis will be given in this note to
\begin{itemize}
\item separable models with  product form steady state,
i.e.~asymptotically and in equilibrium  the queue and the environment as components
(in space) of the 1-dimensional marginals in time decouple:
The steady state distributions of the queue and the environment are independent. This usually allows to determine ergodicity conditions directly, and
\item  non-separable models where ergodicity conditions via construction of Lyapunov function will be  proven. In this case usually the infinite system of global balance equations of the joint queueing-environment process are not explicitly solvable.
\end{itemize}

\underline{Related models.}\\
 A Markovian queueing-environment process can be considered as a birth-death process in random environment.
We note that there exists a bulk of literature on that subject.
Classical birth-death processes in random environment found in the literature in general are not separable, see \cite{cogburn:80}, \cite{cogburn:84},
\cite{cogburn;torrez:81}, \cite{cornez:87}, \cite{yechiali:73},
\cite{prabhu;zhu:89}, \cite{prabhu;zhu:95}.
Typical problems with computing stationary distributions and performance metrics which occur even with finite (non-separable) birth-death processes in a random environment are described in \cite{gaver;jacobs;latouche:84}.\\
In \cite{gannon;pechersky;suhov;yambartsev:16} a reversible Jacksonian queueing network is the environment for a random walker (a distinguished customer) on the network lattice. This work was extended in \cite{daduna:16}, where the random walker was substituted by a ``moving queue'' on the network. This was motivated by modeling a referenced mobile sensor node with an internal message queue (test node) in a network of mobile sensor nodes. Although the stationary distributions occurring in \cite{daduna:16} are separable, the transition mechanism of the system does not fit exactly in the class of models considered here in Section \ref{sect:Separable}.\\
A recent study on an $M/M/1$ queue in  abstract ``interactive'' environments is \cite{pang;sarantsev;belopolskaya;suhov:20}, where the environment is either diffusive (continuous environment space) or a jump environment (discrete environment space).\\
Our approach here is with environment state spaces with discrete structure, and the infinitesimal generators of our processes are different from those in \cite{pang;sarantsev;belopolskaya;suhov:20}[Section 2].\\
A related class of models are random walks on $\bf{Z}$ in a random medium, see for an introduction Part I of \cite{sznitman:02}. Our research in this paper is on different problems than those described there and our methods are different from those used generally in that field.

\underline{Structure and main results of the paper.}\\
In Section \ref{sect:model} we describe the general model of a queueing system in a non-autonomous random environment.
In Section \ref{sect:Separable} we characterize separability of the queueing-environment process and derive ergodicity conditions and the stationary distribution.
In Section \ref{sect:Non-separable} we start with an application from production-inventory theory where separability does not hold.
In Section \ref{sect:ergodicity-necessary} we prove a necessary condition for ergodicity of non-separable queueing systems in a random environment, which is trivially valid in the separable case.
In Section \ref{sect:ergodicity-Lyapunov} we provide sufficient conditions for ergodicity by constructing a Lyapunov function which indicates negative drift of the queueing-environment process.
In Section \ref{sect:BoundingNPF} we combine our findings on separable and non-separable systems by showing that it is in many cases possible to find for a non-separable system related separable partner systems such that performance indices of the former (which are not explicitly computable) can be bounded by the respective indices of the separable partner.

As a running example we investigate several variants of a production system, modeled as a queueing system with an associated inventory which holds items needed in the production process and a replenishment system which generates new items on request of the inventory.
The combined inventory-replenishment system constitutes the environment of the queueing system.

\underline{Notations and Conventions.}
\begin{itemize}
\item $\mathbb{R}_{0}^{+}:= [0,\infty)$, $\mathbb{R}^{+}:= (0,\infty)$, $\mathbb{N}$:= \{1,2,3,\dots\},
$\mathbb{N}_{0}:= \{0\}\cup\mathbb{N}$
\item Empty sums are 0, and empty products are 1.
\item $1_{\left\{ expression\right\} }$ is the indicator function which
is $1$ if $expression$ is true and $0$ otherwise.
\item We write $C=A\uplus B$ to
emphasize that $C$ is the union of disjoint sets $A$ and $B$.
\item For $a\in \mathbb{R}$ we set  $a_{+}:=\max(0,a)$.
\item All random variables and processes occurring henceforth are defined
on a common underlying probability space $(\Omega,{\cal F},P)$.
\item
The models for queueing systems in a random environment in the paper are described by homogeneous Markov processes with discrete state space.
We assume throughout that all these processes are regular, i.e.
all states are stable (i.e. all diagonal elements of the transition intensity matrices are finite), the intensity matrices are conservative (i.e. row sums are zero), and the process is non-explosive (i.e. the sequence of jump times of the process diverges almost surely), and we have a version of the process with cadlag paths (i.e. each path of a process is right-continuous and has left limits every-where).\\
Furthermore, the processes posess the strong Markov property.
\end{itemize}

\section{The model: Queue in a random environment}\label{sect:model}

Our starting point is the classical M/M/1/$\infty$-queue with queue-length-dependent intensities, i.e. an
exponential single server under first-come-first-served regime (FCFS).
We assume that customers are indistinguishable. If the queue length (i.e.~number of customers either waiting or in service) is $n\geq 0$, customers arrive at the system with intensity $\lambda(n)>0,$
and if $n\geq 1$, service is provided to the customer at the head of the line with intensity $\mu(n)>0$. We set formally $\mu(0)\coloneqq 0$.

Setting in force the usual (conditional) independence assumptions, the queue length process  $X\coloneqq (X(t):t\geq 0)$ with state space $\mathbb{N}_0$ is Markov. It is the simplest example of a birth-death process which in case of ergodicity has stationary distribution
$\xi\coloneqq (\xi(n):n\in\mathbb{N}_0)$ with
\beq\label{eq:queue-xi}
\xi(n) =C^{-1} \cdot \prod_{k=0}^n\frac{\lambda(k)}{\mu(k+1)},\quad n\in\mathbb{N}_0,
\eeq
where $C$ is the normalization constant.

We consider the situation where the service system  and the arrival stream are subject to external random influences which disturb  the queueing process, see \prettyref{fig:queue-env}.

\begin{figure}[H]
\centering{}\includegraphics[width=0.6\textwidth]{figure-queue-environment-sw.pdf}\caption{\label{fig:queue-env}Supply chain with base stock policy}
\end{figure}

The states of the environment are summarized as
countable environment state space $K\neq \emptyset$ and the environment process is denoted by
$Y\coloneqq (Y(t):t\geq 0)$.

The joint queueing-environment process is
$Z=(X,Y)=((X(t),Y(t)):t\geq 0)$ on state space $E\coloneqq \mathbb{N}_0\times K$, i.e.~$Z(t)\coloneqq (X(t),Y(t))=(n,k)$ indicates that at time $t$  the queue length is $n$ and the environment's state is $k$.

In most investigations found in the literature (e.g.~\cite{foss;shneer;tyurlikov:12}, \cite{zhu:94},  \cite{economou:05})  an autonomous environment is considered:\\
This means that the environment process $Y=(Y(t):t\geq 0)$  on $K$ is Markov of its own, and the
state of the environment influences arrival and service rates of the queue. Consequently in this
situation  there is only a "one-way interaction".\\
We shall consider in this note mainly the case of non-autonomous environments:\\
Then the environment process $Y=(Y(t):t\geq 0)$  on $K$ is not Markov of its own.
The state of the environment and state of the queue influence transitions of the other component of the system
vice-versa, which results in a "two-way interaction".
In case of birth-death processes in a random environment this is often termed "feedback property of the environment",  see e.g.~\cite{cornez:87}.

In all applications mentioned, for the  joint queueing-environment process $Z=(X,Y)$ on  $E=\mathbb{N}_0\times K$ we observe that
the environment space  $K$ is partitioned  as a disjoint union $K = K_W \uplus K_B$ with the  following meaning and consequences:
\begin{itemize}
\item$Y(t)\in K_{B}$ $ :\Longleftrightarrow$ at time  $t$ no service is provided and no arrivals occur,
i.e.~the queue length process $X$ is frozen (= {server is {\bf B}locked}).
\item$Y(t)\in K_{W}$ $:\Longleftrightarrow$  at time  $t$ the server is functioning, new arrivals
are admitted (= {server  {\bf W}orks}).
\end{itemize}

The dynamics of the environment are as follows: If the queue length is $n$, then
\begin{itemize}
\item a generator matrix $V_n\coloneqq (v_n(k,m):k,m\in K)$ governs continuous changes
of  the environment, $n=0, 1, \dots$, and
\item a stochastic matrix $R_n\coloneqq (R_n{(k,m)}:k,m\in K)$ governs instantaneous jumps of the environment
triggered by service  completions (downward jumps of the queue),
 $n=1, 2, \dots$.
\end{itemize}

We henceforth assume that
$Z=(X,Y)=((X(t),Y(t)):t\geq 0)$  is a Markov process on $E = \mathbb{N}_{0}\times K$.
The characterizing data for the system's development are the given  $\lambda(n)$, $\mu(n)$, the
countable  environment {$K=K_W \uplus K_B$}, and the driving components for the environment $R_n=(R_n({k,m}):k,m\in K)$, $V_n=(v_n(k,m):k,m\in K)$.

The generator $\mathbf{Q}\coloneqq ({q}(z,\tilde z):z, \tilde z\in E)$ of the Markov process
$Z$ is with generic state $(n,k)\in E$:
\begin{align}
q\left((n,k);(n+1,k)\right) & \coloneqq \lambda(n)\cdot{1_{\left\{ k\in K_{W}\right\} }}, \label{generator1}\\
q\left((n,k);(n-1,\ell)\right) & \coloneqq \mu(n)\cdot {R_{n}(k,\ell)}\cdot1_{\left\{ n>0\right\} }\cdot
{1_{\left\{ k\in K_{W}\right\} }},& \ell\in K,\nonumber\\
q\left((n,k);(n,\ell)\right) & \coloneqq {v_{n}(k,\ell)}, & \ell\in K,\ k\neq\ell,\nonumber
\end{align}
and $q(z;\tilde{z})\coloneqq 0$ for  other $z\neq\tilde{z}$,
and
$q\left(z;z\right)\coloneqq -\sum_{\substack{\tilde{z}\in E,\\
z\neq\tilde{z}} }q\left(z;\tilde{z}\right)$ for all $z\in E.$

We note that such processes can be considered as quasi-birth-death  processes with level-dependent phase-dynamics.
To clarify the connection of our model to that in Section 2 of \cite{pang;sarantsev;belopolskaya;suhov:20}, we rewrite $\mathbf{Q}$ for  $(n,k)\in E$ as:
\begin{align}
q\left((n,k);(n+1,k)\right) & \eqqcolon \lambda(n,k)
\label{generator11}\\
q\left((n,k);(n-1,\ell)\right) & \eqqcolon \mu(n,k,\ell),
& \ell\in K,\nonumber\\
q\left((n,k);(n,\ell)\right) & \eqqcolon {v_{n}(k,\ell)}, & \ell\in K,\ k\neq\ell.\nonumber
\end{align}
The generator $\mathbf{R} \coloneqq (R(n,k;n',k'):(n,k),(n',k')\in E)$ in \cite[(2.1)]{pang;sarantsev;belopolskaya;suhov:20} does not allow the $\lambda(\cdot)$ or $\mu(\cdot)$ in \eqref{generator11} to depend on $n$ and allows only  one of the coordinates to change at a time instant, i.e.
$\mu(n,k,\ell)\neq 0$ only for $k=\ell$.
 On the other side our $\lambda(n,k)$ and $\mu(n,k,\ell)$ are of specific structure guided by the motivating examples.
\bass\label{ass:irreducible}
We assume throughout that $Z=(X,Y)$, resp. $\mathbf{Q}$ is irreducible on $E$.
\eass

\bremark Although $Z=(X,Y)$ is a Markov process, neither $X$ nor $Y$ is in general Markov. Moreover, even under Assumption \ref{ass:irreducible}
neither the $R_n$ nor the $V_n$ need to be irreducible, or ergodic.
\eremark

\section{Separable queueing-environment systems}\label{sect:Separable}

Separability means roughly that the state vector of a multi-dimensional Markov process in
equilibrium has for
a fixed time instant independent coordinates. The classical examples are Jackson networks of queues
\cite{jackson:57} and their generalizations as BCMP networks
\cite{baskett;chandy;muntz;palacios:75}, resp.~Kelly networks \cite{kelly:76}.
We are interested in conditions which guarantee this asymptotic independence for the pair $Z=(X,Y)$.
A characterization theorem for the case when the  dynamics of the environment is independent
of queue length, i.e.~$V_n=V$, $R_n=R$ for all $n$ is proved in \cite[Theorem 2]{krenzler;daduna:12}.
We provide a characterization for the general case here.

\btheorem\label{theorem:Separable1}
{\bf (a)} For $n\in \mathbb N_0$ define ``reduced generators''  $\widetilde{\mathbf{Q}}_{red}^{(n)}\coloneqq (\widetilde{q}_{red}^{(n)}(k,m):k,m\in K)$
on the environment space $K$ via $\mathbf{Q}$ by
\begin{eqnarray*}
\widetilde{q}_{red}^{(n)}(k,m) & \coloneqq & \lambda{(n)}\cdot R_{n+1}(k,m)\cdot 1_{\{k\in K_{W}\}}+v_n(k,m),\qquad k\neq m,\\
\widetilde{q}_{red}^{(n)}(k,k) & \coloneqq & -[1_{\{k\in K_{W}\}}\cdot \lambda{(n)}\cdot
(1-R_{n+1}(k,k))+\sum_{m\in K\backslash\{k\}}v_n(k,m)].
\end{eqnarray*}
The ``reduced generators'' $\widetilde{\mathbf{Q}}_{red}^{(n)}$ are generators for  Markov processes on $K$.

{\bf (b)} The following properties are equivalent:\\
\noindent
{\bf (i)} $Z=(X,Y)$ is ergodic with product form steady state $\pi = \xi \times \theta$, with $\xi$ from \eqref{eq:queue-xi}, i.e.
\begin{equation}
\pi(n,k)= C^{-1}\cdot \left(\prod_{i=0}^{n-1}\frac{\lambda(i)}{\mu{(i+1)}}\right) \cdot \theta(k),\quad
(n,k)\in E,
\end{equation}\label{eq:LS-product-form}
where $\theta\coloneqq (\theta(k):k\in K)$ is a probability distribution on $K$.\\
\noindent
{\bf (ii)} The summability condition
$ C  := \sum_{n=0}^{\infty}\prod_{i=0}^{n-1}\frac{\lambda{(i)}}{\mu{(i+1)}} <\infty$
holds, and  the equation
\begin{equation}\label{eq:LS-q-tilde-0-conditon}
    \theta\cdot\widetilde{\mathbf{Q}}_{red}^{(0)}=0
\end{equation}
 admits a stochastic solution $\theta\coloneqq (\theta(k):k\in K)$ which solves also
\begin{equation}\label{eq:LS-q-tilde-n-conditon}
\forall n\in \mathbb N:\theta\cdot\widetilde{\mathbf{Q}}_{red}^{(n)}=0 .
\end{equation}
\etheorem

\begin{proof}
\textbf{(a)} By definition  $\widetilde{q}_{red}^{(n)}(k,m)\geq 0$,
and $\widetilde{q}_{red}^{(n)}(k,k)\leq 0$ for $k,m\in K$, $k\neq m$. Direct summation shows that the row sums of all
$\widetilde{\mathbf{Q}}_{red}^{(n)}, n\in\mathbb{N}_0,$ are zero.

\textbf{(b)} \textbf{(ii)} $\mathbf{\Rightarrow}$ \textbf{(i):}
By assumption (\ref{eq:LS-q-tilde-0-conditon}) there exists a stochastic
solution to $\theta\cdot \widetilde{\mathbf{Q}}_{red}^{(0)}=0$, which according to requirement
(\ref{eq:LS-q-tilde-n-conditon}) is a solution of $\theta\cdot \widetilde{\mathbf{Q}}_{red}^{(n)}=0$ too.
Due to the summability condition $C<\infty$ we can use our $\theta$ and $C$ to define $\pi(n,k)$ by the right-hand side of (\ref{eq:LS-product-form}). Next, we show that $\pi$ fulfills the global balance  $\pi\cdot \mathbf{Q}=\mathbf{0}$ of the Markov process $(X,Y)$ which are for
$(n,k)\in E$
\begin{eqnarray}
 &  & \pi(n,k)\cdot \Big(1_{\{k\in K_{W}\}}\cdot \lambda(n)+\sum_{m\in K\backslash\{k\}}\myv_n(k,m)+1_{\{k\in K_{W}\}}\cdot 1_{\{n\intpositive\}}\cdot \mu(n)\Big)\nonumber \\
 & = & \pi(n-1,k)\cdot 1_{\{k\in K_{W}\}}1_{\{n\intpositive\}}\cdot \lambda(n-1)+\sum_{m\in K_{W}}\pi(n+1,m)\cdot \Rentry mk{n+1}\cdot \mu(n+1)\nonumber \\
 &  & +\sum_{m\in K\backslash\{k\}}\pi(n,m)\cdot \myv_n(m,k).\label{eq:LS-lba-general-2-2}
\end{eqnarray}

Inserting the proposed product form solution (\ref{eq:LS-product-form})
for the stationary distribution into the global balance
equations (\ref{eq:LS-lba-general-2-2}), canceling $C^{-1}$
and multiplying with $\prod_{i=0}^{n-1}\left(\frac{\lambda(i)}{\mu(i+1)}\right)^{-1}$
yields
\begin{eqnarray*}
 &  & \theta(k)\cdot \Big(1_{\{k\in K_{W}\}}\cdot \lambda(n)+\sum_{m\in K\backslash\{k\}}\myv_n(k,m)+
 \underbrace{1_{\{k\in K_{W}\}}\cdot 1_{\{n\intpositive\}}\cdot \mu(n)}_{(*)}\Big)\\
 & = & \underbrace{\theta(k)\cdot \frac{\mu(n)}{\lambda(n-1)}\cdot 1_{\{k\in K_{W}\}}\cdot 1_{\{n\intpositive\}}\cdot \lambda(n-1)}_{(**)}
 +\sum_{m\in K_{W}}\theta(m)\cdot \frac{\lambda(n)}{\mu(n+1)}\cdot \Rentry mk{n+1}\cdot \mu(n+1)\\
 &  & +\sum_{m\in K\backslash\{k\}}\theta(m)\cdot \myv_n(m,k).
\end{eqnarray*}
Canceling for $n\geq 1$ the expressions $(\theta(k)\cdot (*))$ and $(**)$, yields for all $n\geq0$
\begin{eqnarray*}
 &  & \theta(k)\cdot \Big(1_{\{k\in K_{W}\}}\cdot \lambda(n)+\sum_{m\in K\backslash\{k\}}\myv_n(k,m)\Big)\\
 & = & \sum_{m\in K_{W}}\theta(m)\cdot {\lambda(n)}\cdot \Rentry mk{n+1}
 +\sum_{m\in K\backslash\{k\}}\theta(m)\cdot \myv_n(m,k).
\end{eqnarray*}
This implies
\begin{eqnarray*}
 &  & \theta(k)\cdot \Big(1_{\{k\in K_{W}\}}\cdot \lambda(n)\cdot (1- \Rentry kk{n+1})
 +\sum_{m\in K\backslash\{k\}}\myv_n(k,m)\Big)\\
 & = & \sum_{m\in K\setminus\{k\}}\theta(m)\cdot 1_{\{m\in K_{W}\}}\cdot {\lambda(n)}\cdot \Rentry mk{n+1}
 +\sum_{m\in K\backslash\{k\}}\theta(m)\cdot \myv_n(m,k)
\end{eqnarray*}
and
\begin{eqnarray}
 &  & \theta(k)\cdot \underbrace{\Big(1_{\{k\in K_{W}\}}\cdot \lambda(n)\cdot (1- \Rentry kk{n+1})
 +\sum_{m\in K\backslash\{k\}}\myv_n(k,m)\Big)}_{= - \widetilde q_{red}^{(n)}(k,k)}\nonumber\\
 & = & \sum_{m\in K\setminus\{k\}}\theta(m)\cdot \underbrace{\left(
 1_{\{m\in K_{W}\}}\cdot {\lambda(n)}\cdot \Rentry mk{n+1} +\myv_n(m,k)\right)}_{=\widetilde q_{red}^{(n)}(m,k)},
 \label{eq:LS-equal-solution}
\end{eqnarray}
which is for all $n\geq 0$ the condition \eqref{eq:LS-q-tilde-0-conditon},
respectively \eqref{eq:LS-q-tilde-n-conditon}, i.e.~$\theta\cdot \widetilde{\mathbf{Q}}_{red}^{(n)}=0$.
Hence we conclude  that \eqref{eq:LS-q-tilde-0-conditon}, and \eqref{eq:LS-q-tilde-n-conditon} guarantee that (\ref{eq:LS-product-form}) solves (\ref{eq:LS-lba-general-2-2}).

Therefore, the global balance equations of $Z$ admit the stochastic solution
$\pi= \xi\times \theta$, which is unique by Assumption \ref{ass:irreducible},
and so $Z$ is ergodic.

\textbf{(b)} \textbf{(i)} $\mathbf{\Rightarrow}$ \textbf{(ii):}
 Because $\pi$ is stochastic and is of product form, summability
holds. Insert the stochastic vector of product form \eqref{eq:LS-product-form}
into \eqref{eq:LS-lba-general-2-2}. As shown in the part \textbf{(ii)}
$\mathbf{\Rightarrow}$ \textbf{(i)} of the proof, this leads to \eqref{eq:LS-equal-solution}
and we have found a stochastic solution $\theta$
which solves \eqref{eq:LS-q-tilde-0-conditon} and
 \eqref{eq:LS-q-tilde-n-conditon} for all $n\in\mathbb{N}$. \end{proof}
\bremark\label{rem:Tn}
The reduced generators $\widetilde{\mathbf{Q}}_{red}^{(n)}=(\widetilde{q}_{red}^{(n)}(k,m):k,m\in K)$ can be considered as generalization of the generators
$\mathbf{T}_n, n\in \mathbb{N}_0,$ in the construction of the Markovian jump generators in \cite[Section 2]{pang;sarantsev;belopolskaya;suhov:20}.
$\widetilde{\mathbf{Q}}_{red}^{(n)}$ takes into consideration the
possibility of jumps in two dimension for $\mathbf{Q}$.
The property that $\theta$ is the common solution of the equations
\eqref{eq:LS-q-tilde-0-conditon} and
\eqref{eq:LS-q-tilde-n-conditon}
is therefore in parallel to Assumption 2.1 in \cite{pang;sarantsev;belopolskaya;suhov:20} put on the $\mathbf{T}_n, n\in \mathbb{N}_0,$ there.
\eremark

\bex[Queueing-inventory system, see Figure~\ref{fig:BS-PER-figure-base-stock-model}]\label{ex:QueueInventory1}
The production system  with an attached inventory considered here
is a special case of queueing systems in a random environment: The exponential server ($=$ production system) interacts with an environment which consists of an inventory and an associated replenishment subsystem.

\begin{figure}[h]
\centering{}\includegraphics[width=0.95\textwidth]{bs-perishable-env-1-sw.pdf}\caption{\label{fig:BS-PER-figure-base-stock-model}Supply chain with base stock policy}
\end{figure}

The production system consists
of a single server (machine) with infinite waiting room that serves
 customers' demand on a make-to-order basis under a FCFS regime.
To satisfy a customer's demand the production system needs exactly
one item of raw material from the associated inventory.

Arriving customers join the queue unless the inventory is depleted (``lost sales'').
If $n\geq 0$, customers are present and the inventory is not depleted, the customer at the head of the line (if any) is served with intensity $\mu(n)>0$, and new arrivals occur with intensity $\lambda(n)>0$.\\
A customer departs from the system immediately after  service and the associated consumed raw material is formally removed from the inventory at this time instant.

If the server is ready to serve a customer, and the inventory is not depleted, service immediately
starts. Otherwise, the service starts  when the next replenishment arrives.\\
If the inventory is depleted no service is possible, customers in the waiting line stay on and wait, newly arriving customers are lost.

The inventory is controlled according to base stock policy, i.e.~each item taken from the inventory triggers  an immediate order for one item of raw material at the supplier. The base stock level
$b\geq1$ is the maximal size of the inventory.\\
The supplier consists of a single server  with waiting room of size $b-1$
under FCFS. Service times to produce one item of raw material at the supplier are exponentially distributed with parameter $\nu>0$.
A finished item of raw material departs immediately from the supplier and is added to the inventory.

This queueing-inventory system  fits into the definition of the queueing system in a random environment described by a Markov process $Z=(X,Y)=\text{(queue-length,\ inventory size)}$ on state space $E=\mathbb{N}_0\times K$ with $K\coloneqq \{0,1,\dots,b\}$ and
\[
K_{B}\coloneqq \left\{0\right\} ,\qquad K_{W}\coloneqq \left\{ 1,\ldots,b\right\} ,
\]
where $Y(t)\in K_{W}$ indicates for the inventory that there is
stock on hand for production, and $Y(t)\in K_{B}$ indicates stock-out. Note, that the physical environment of the production system includes the replenishment system. The status of the replenishment server at time $t$ is uniquely determined by the size of the inventory as $b-Y(t)$.

The dynamics of $Z$ are determined by the infinitesimal generator $\mathbf{Q}=\left(q(z;\widetilde{z}):z,\widetilde{z}\in E\right)$ with the following transition rate for $(n,k)\in E =\mathbb{N}_{0}\times K$:

\begin{align*}
q\left((n,k);(n+1,k)\right) & \coloneqq \lambda(n)\cdot{1_{\left\{k\in\left\{ 1,\ldots,b\right\}\right\}}},\\
q\left((n,k);(n-1,k-1)\right) & \coloneqq \mu(n) \cdot 1_{\left\{ n>0\right\} }\cdot
{1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} }},\\
q\left((n,k);(n,k+1)\right) & \coloneqq \nu \cdot 1_{\left\{ k\in\left\{ 0,\ldots,b-1\right\}\right\}},
\end{align*}
and $q(z;\tilde{z})\coloneqq 0$ for  other $z\neq\tilde{z}$,
and
$q\left(z;z\right)\coloneqq -\sum_{\substack{\tilde{z}\in E,\\
		z\neq\tilde{z}} }q\left(z;\tilde{z}\right)$ for all $z\in E.$\\

The queue-length dependent dynamics of the inventory process are determined by
\[
R_{n}(0,0)\coloneqq 1,\qquad R_{n}(k,k-1)\coloneqq 1,\quad k\in\left\{ 1,\ldots,b\right\},\ n\in\mathbb{N},
\]
\begin{align*}
v_{n}(k,\ell) & \coloneqq \begin{cases}
\nu, & \text{if }k\in\left\{ 0,\ldots,b-1\right\},\ \ell=k+1,\\
0, & \text{otherwise for }k\neq\ell,\qquad\quad n\geq0.
\end{cases}
\end{align*}

If $\lambda(n)=\lambda$ for all $n\in \mathbb{N}$ and some $\lambda \in \mathbb{R}$ and the queueing-inventory process is ergodic, then the stationary distribution $\pi$ is given by

\begin{equation}\label{eq:QueueingInventoryPF}
\pi(n,k)\coloneqq  \xi(n)\cdot \theta (k), \quad (n,k)\in E,
\end{equation}
with
\begin{align*}
\xi(n)\coloneqq C^{-1} \cdot \prod_{i=0}^{n-1}\frac{\lambda}{\mu{(i+1)}},  \  n\in \mathbb{N}_{0},\qquad
\theta(k)\coloneqq C_{\theta}^{-1}\cdot \left(\frac{\nu}{\lambda}\right)^{k}, \  k\in K,
\end{align*}

and normalization constants $C$ and $C_{\theta}$.

For this model $\theta$ is steady state of classical inventory (without service system) with demand rate $\lambda$.
\eex

In Section \ref{sect:BoundingNPF} we present further examples of  separable queueing-environment systems.

\bex[Examples with queue-length dependent environment dynamics]
\label{ex:QueueInventory1A}
We describe two examples which are related to case 3. (``Availability'') of the list in the Introduction.\\
Consider an ergodic $M/M/1/\infty$ with arrival rate $\lambda(n)$ and service rate $\mu(n)$.\\
The availability of the server is governed by an alternating exponential renewal process (on-off process) with queue-length dependent rates $\eta(\cdot), \gamma(\cdot)$. The state space of the environment is $K\coloneqq \{0,1\}$, where $0 \equiv$off and  $1 \equiv$on.

In terms of our general model we have $K_B=\{0\}$ and $K_W=\{1\}$. The dynamics of the environment are queue-length dependent governed by the generator matrices $V_n$ and jump matrices $R_n$ as follows:\\
In both cases we take the generators $V_n$ as
\beq\label{eq:Vn}
v_n(0,1)\coloneqq \eta\cdot (n+1),\quad v_n(1,0)\coloneqq \gamma\cdot (n+1),\qquad n\geq 0.
\eeq
\textbf{(a)} The jump matrices are taken trivial
$R_n\coloneqq  [1_{\{i=j\}}:i,j\in\{0,1\}]$.
Then it follows $\widetilde{\mathbb Q}^n_{red} = V_n$
and the common probability solution $\theta$ of
\[
\theta\cdot \widetilde{\mathbb Q}^n_{red} =0, \qquad n\geq 0,
\]
is
\[
\theta =\left(\frac{\gamma}{\gamma +\eta},\frac{\eta}{\gamma +\eta} \right).
\]
\textbf{(b)} The jump matrices are taken as
$R_{n+1}(1,0)=1,\ R_{n+1}(0,0)=1,$
and we assume the arrival rates to be linear
$\lambda(n):=\lambda\cdot(n+1)$ for $n\geq 0$. It follows that
 the common probability solution $\theta$ of
\[
\theta\cdot \widetilde{\mathbb Q}^n_{red} =0, \qquad n\geq 0,
\]
is
\[
\theta =\left(\frac{\lambda+\gamma}{\lambda+\gamma +\eta},\frac{\eta}{\lambda+\gamma +\eta} \right).
\]

Consequently, by Theorem 3.1 {\bf (b)} we have shown that both unreliable service systems  are separable although the transition regimes of the environment are queue-length dependent.
\eex

\section{Non-separable queueing-environment systems}\label{sect:Non-separable}

Ergodicity in case of separable queueing-environment systems is in most cases easy to detect because of the product structure for the solution of the global balance equations. This solution  is not accessible
in the next example which is a slight modification of Example  \ref{ex:QueueInventory1}.

\bex[Queueing-inventory system with perishable items]\label{ex:QueueInventory2}

Products like  foodstuffs, human blood, chemicals, etc.~often have a maximum life time, i.e. when they are hold in  inventories they may either perish,
deteriorate, are subject to ageing, or become obsolete.

We consider the queueing-inventory system of Example \ref{ex:QueueInventory1}  with the additional restriction that
 the life time of raw material in the inventory is exponentially
distributed with ``ageing rate'' $\gamma>0$.
In the literature, it is often assumed that an item of raw material, being already in the production process does not perish any longer
(e.g.~\cite{manuel;sivakumar;arivarignan:07},~\cite{manuel;sivakumar;arivarignan:08},~\cite{jeganathan:14},~\cite{yadavalli;anbazhagan;jeganathan:15a}). More complex systems with additional features are found in \cite{koroliuk;melikov;ponomarenko;rustamov:17,koroliuk;melikov;ponomarenko;rustamov:18},
where ``stock that is already at distribution stage cannot perish'':

We  consider a standard queueing-inventory system incorporating this form of perishing here, which implies:
\begin{itemize}
	\item [\textbf{-}]If $n>0$ and there are $k>0$ items of raw material  in the inventory,
	then  one piece of raw material is in production and does not perish. Consequently, the total loss rate of inventory due to perishing is $\gamma\cdot\left(k-1\right)\cdot1_{\left\{ n>0\right\} }$.
	\item [\textbf{-}]If $n=0$ and there are $k>0$ items of raw material in the inventory, then the total loss rate
	of inventory due to perishing is $\gamma\cdot k\cdot1_{\left\{ n=0\right\} }$.
\end{itemize}
We call the functions $k\mapsto\gamma\cdot k\cdot1_{\left\{ n=0\right\} }$ resp.\ $k\mapsto\gamma\cdot(k-1)_{+}\cdot1_{\left\{ n>0\right\} }$
ageing regimes which determine the  queue-length-dependent overall loss rates of inventory due to perishing.\\

This queueing-inventory system  fits into the definition of the queueing system in a random environment described by a Markov process $Z=(X,Y)=$(queue-length, inventory size) on state space $E=\mathbb{N}_0\times K$ with $K\coloneqq \{0,1,\dots,b\}$ and
\[
K_{B}=\left\{0\right\} ,\qquad K_{W}=\left\{ 1,\ldots,b\right\} ,
\]
where $Y(t)\in K_{W}$  indicates for the inventory that there is stock on hand for production, and $Y(t)\in K_{B}$ indicates stockout. Note, that the physical environment of the production system includes the replenishment system. The status of the replenishment server at time $t$ is uniquely determined by the size of the inventory as $b-Y(t)$.

The dynamics of $Z$ are determined by the infinitesimal generator $\mathbf{Q}=\left(q(z;\widetilde{z}):z,\widetilde{z}\in E\right)$ with the following transition rates for $(n,k)\in E =\mathbb{N}_{0}\times K$:

\begin{align*}
q\left((n,k);(n+1,k)\right) & \coloneqq \lambda(n) \cdot1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} },\\
q\left((n,k);(n,k-1)\right) & \coloneqq \left(\gamma\cdot(k-1)\cdot1_{\left\{ n>0\right\} }+\gamma\cdot k\cdot1_{\left\{ n=0\right\} }\right)\cdot1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} },\\
q\left((n,k);(n-1,k-1)\right) & \coloneqq \mu(n) \cdot1_{\left\{ n>0\right\} }\cdot1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} },\\
q\left((n,k);(n,k+1)\right) & \coloneqq \nu\cdot1_{\left\{k \in\left\{ 0,\ldots,b-1\right\}\right\} },
\end{align*}
and $q(z;\tilde{z})\coloneqq 0$ for  other $z\neq\tilde{z}$,
and
$q\left(z;z\right)\coloneqq -\sum_{\substack{\tilde{z}\in E,\\
		z\neq\tilde{z}} }q\left(z;\tilde{z}\right)$ for all $z\in E.$

The queue-length dependent dynamics of the inventory process is determined by
\[
R_{n}(0,0)\coloneqq 1,\qquad R_{n}(k,k-1)\coloneqq 1,\quad k\in\left\{ 1,\ldots,b\right\},\ n\in\mathbb{N},
\]

\begin{align*}
v_{0}(k,\ell) & \coloneqq \begin{cases}
\nu, & \text{if }k\in\left\{ 0,\ldots,b-1\right\},\ \ell=k+1,\\
\gamma\cdot k, & \text{if }k\in\left\{ 1,\ldots,b\right\},\ \ell=k-1\\
0, & \text{otherwise for }k\neq\ell,
\end{cases}\\
\\
v_{n}(k,\ell) & \coloneqq \begin{cases}
\nu, & \text{if } k\in\left\{ 0,\ldots,b-1\right\},\ \ell=k+1,\\
\gamma\cdot(k-1), & \text{if }k\in\left\{ 1,\ldots,b\right\},\ \ell=k-1,\\
0, & \text{otherwise for }k\neq\ell,\qquad\quad n\geq1.
\end{cases}
\end{align*}
\eex

\bcor\label{cor:QueueInventory-NonPF}
In the queueing-inventory system of Example \ref{ex:QueueInventory2} (with state-independent arrival rates) the stationary distribution is in general not of product form.
\ecor

\bproof
Details are provided in~\cite[Proposition 4.2.29, p.~96]{otten:18}.
\eproof

Under additional restrictions separability is possible. The proof of the next corollary is by direct computation.
\bcor\label{cor:QueueInventoryPerishable-PF}
Consider the queueing-inventory system of Example \ref{ex:QueueInventory2} with state-independent rates
$\lambda(n)=\lambda$ and $\mu(n)=\mu$ for all $n$ and some $\lambda,\ \mu \in \mathbb{R}$
and base stock level $b=1$.
If $\lambda<\mu$ the queueing-inventory process is ergodic, and the stationary distribution $\pi$ is given by

\begin{align*}
&\pi(0,0) \coloneqq C^{-1} \cdot \frac{\lambda + \gamma }{\nu },\quad \\
&\pi(n,0) \coloneqq C^{-1} \cdot \left(\frac{\lambda}{\mu }\right)^{n}\cdot \frac{\lambda}{\nu },\   n>0,\qquad
\pi(n,1) \coloneqq C^{-1} \cdot \left(\frac{\lambda}{\mu }\right)^{n}, \  n\geq 0,
\end{align*}

with normalization constant
\begin{align*}
C \coloneqq \frac {\mu}{\mu - \lambda}\cdot \left(1+\frac{\lambda}{\nu}\right)+\frac{\gamma}{\nu}.
\end{align*}
\ecor

We  continue with proving necessary condition for ergodicity in Proposition \ref{prop:random-abh-notw}.
Furthermore, in case of finite environment space,  sufficient conditions for positive recurrence are proved in \prettyref{thm:BS-PER-GER-pos-rec} and Corollary \ref{cor:BS-PER-GER-pos-rec-2}.

\subsection{A necessary condition for ergodicity}\label{sect:ergodicity-necessary}

We start with a proposition which is of independent interest because it underpins the importance of
the environment's structure and its stalling feature for the queueing system.

\begin{prop}
\label{prop:random-prop-1}If the queueing-environment process $Z$
is ergodic, then the solution $\mathbf{x}\coloneqq \left(x\left(z\right):z\in E\right)$
of the global balance equations $\mathbf{x}\mathbf{\cdot Q=0}$ fulfills
for all $n\in\mathbb{N}_{0}$\textup{
\begin{equation}
\sum_{k\in K_{W}}x(n,k)=\sum_{k\in K_{W}}x(n+1,k)\cdot\frac{\mu(n+1)}{\lambda(n)}\label{eq:BS-PER-GEN-PXnY>0(2)-1a}
\end{equation}
and consequently we have a geometrical structure
\begin{equation}
\sum_{k\in K_{W}}x(n,k)=\sum_{k\in K_{W}}x(0,k)\cdot\prod_{m=1}^{n}\frac{\lambda(m-1)}{\mu(m)},
\quad n\in\mathbb{N}_{0}.\label{eq:BS-PER-GEN-PXnY>0(1)-1a}
\end{equation}
}\end{prop}

\begin{proof}
By ergodicity  there exists a unique
strictly positive stationary probability distribution
$\mathbf{x}\coloneqq \left(x\left(z\right):z\in E\right)$,  as  solution
of the global balance equations $\mathbf{x}\mathbf{\cdot Q=0}$
(cf.~\cite[Theorem 4.2,  p. 51]{asmussen:03}).
$\mathbf{x}$ is subject to the cut-criterion \cite[Lemma 1.4]{kelly:79} and
\eqref{eq:BS-PER-GEN-PXnY>0(2)-1a} can be proven by equalizing the probability flows between the sets
\[
\Big\{(m,k):m\in\{0,1,\ldots,n\},\: k\in K\Big\}
~\text{and}~
\left\{ (\widetilde{m},\widetilde{k}):\widetilde{m}\in\mathbb{N}_{0}\setminus\{0,1,\ldots,n\},\:\widetilde{k}\in K\right\} ,~~ n\in\mathbb{N}_{0}.
\]
These flow equations are
\begin{align*}
 & \sum_{m=0}^{n}\sum_{k\in K}\ \sum_{\widetilde{m}=n+1}^{\infty}\sum_{\widetilde{k}\in K}x(m,k)\cdot q((m,k);(\widetilde{m},\widetilde{k}))\\
 & =\sum_{\widetilde{m}=n+1}^{\infty}\sum_{\widetilde{k}\in K}\ \sum_{m=0}^{n}\sum_{k\in K}x(\widetilde{m},\widetilde{k})\cdot q((\widetilde{m},\widetilde{k});(m,k))
\end{align*}
and simplify to
\begin{align*}
& \sum_{k\in K_{W}}x(n,k)\cdot\lambda(n)=
\sum_{\widetilde{k}\in K_{W}}x(n+1,\widetilde{k})\cdot\mu(n+1)\cdot
\underbrace{\sum_{\ell\in K}R_{n+1}(\widetilde{k},\ell)}_{=1},
\end{align*}
which  is \eqref{eq:BS-PER-GEN-PXnY>0(2)-1a}. \eqref{eq:BS-PER-GEN-PXnY>0(1)-1a} follows directly.
\end{proof}

The next result shows that it is impossible to stabilize a non-ergodic (isolated) queue by embedding it into a suitably constructed environment.

\begin{prop}
\label{prop:random-abh-notw}If the queueing-environment process $Z$
is ergodic, it holds
\beq\label{eq:birth-death-constant-finite}
\sum_{n=0}^{\infty}\prod_{m=1}^{n}\frac{\lambda(m-1)}{\mu(m)}<\infty.
\eeq
\end{prop}

\begin{proof}
Ergodicity implies that any solution $\mathbf{x}\coloneqq \left(x\left(z\right):z\in E\right)$
of the global balance equations
fulfils $\sum_{n=0}^{\infty}\sum_{k\in K}x(n,k)<\infty.$
It holds
\beqaro
  \sum_{n=0}^{\infty}\sum_{k\in K}x(n,k) &{=}&\sum_{n=0}^{\infty}\sum_{k\in K_{W}}x(n,k)+\sum_{n=0}^{\infty}\sum_{k\in K_{B}}x(n,k)\\
 &{=}&\sum_{n=0}^{\infty}\underbrace{\sum_{k\in K_{W}}x(0,k)}_{=:\widetilde{W}}\cdot\prod_{m=1}^{n}\frac{\lambda(m-1)}{\mu(m)}+\sum_{n=0}^{\infty}\sum_{k\in K_{B}}x(n,k)\\
 &{=}&\widetilde{W}\cdot\sum_{n=0}^{\infty}\prod_{m=1}^{n}\frac{\lambda(m-1)}{\mu(m)}+\sum_{n=0}^{\infty}\sum_{k\in K_{B}}x(n,k).
\eeqaro
By ergodicity, $\widetilde{W}\in\left(0,\infty\right)$ and
$\sum_{n=0}^{\infty}\sum_{k\in K_{B}}x(n,k)<\infty$.
Hence, $\sum_{n=0}^{\infty}\sum_{k\in K}x(n,k)<\infty$ implies
$\sum_{n=0}^{\infty}\prod_{m=1}^{n}\frac{\lambda(m-1)}{\mu(m)}<\infty$.
\end{proof}

\subsection{Ergodicity via Lyapunov functions}\label{sect:ergodicity-Lyapunov}
We follow a standard approach in searching for ergodicity conditions by constructing Lyapunov functions to apply Foster's criterion, see \cite[Proposition D.3]{kelly;yudovina:14}.
\bass\label{ass:K-finite}
We assume henceforth that the environment space $K$ is finite.
\eass
We start with three preparatory lemmas. The proof of the first one is by direct evaluation.

\begin{lemma}
\label{lem:BS-PER-GEN-Lemma1}For an $M/M/1/\infty$ queue with queue-length-dependent
arrival intensities $\lambda(n)>0$ and service intensities $\mu(n)>0$
let there exist a Lyapunov function $\widetilde{\mathcal{L}}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{0}^{+}$ with finite exception set $\widetilde{F}$ and constant $\widetilde{\varepsilon}>0$ which satisfies the Foster-Lyapunov
stability criterion. Then, the following inequalities are satisfied:
\begin{align}
 & \lambda(0)\cdot\left(\widetilde{\mathcal{L}}(1)-\widetilde{\mathcal{L}}(0)\right)\leq-\widetilde{\varepsilon}, &  & \text{if }0\notin\widetilde{F},\label{eq:random-mm1-eq1}\\
 & \lambda(n)\cdot\left(\widetilde{\mathcal{L}}(n+1)-\widetilde{\mathcal{L}}(n)\right)+\mu(n)\cdot\left(\widetilde{\mathcal{L}}(n-1)-\widetilde{\mathcal{L}}(n)\right)\leq-\varepsilon, &  & \text{if }n\notin\widetilde{F},\ n>0.\label{eq:random-mm1-eq2}
\end{align}
\end{lemma}

For the Markovian queueing-environment process $Z=(X,Y)$ of Section \ref{sect:model} with generator
$\mathbf{Q}=({q}(z,\tilde z):z, \tilde z\in E)$ from \eqref{generator1} we define in the following  for every
$n\in \mathbb{N}_{0}$ an artificial Markov process
$Y^{(n)}\coloneqq (Y^{(n)}(t):t\geq 0)$ on $K$ with generator $V_n=(v_n(k,\ell):k,\ell\in K)$.
The processes $Y^{(n)}$ are in general neither irreducible, nor recurrent.

By definition the stochastic behaviour of $Y^{(n)}$ when started in $Y^{(n)}_0\coloneqq  k\in K_B$ until the first entrance into
$K_W$ is identical to the behaviour of  the $Y$-component of  $Z= (X,Y)$ on $\{n\}\times K$ when started in
$(X_0,Y_0)= (n,k)\in E$ until first entrance into $\{n\}\times K_W$. Especially, until this first entrance of $(X,Y)$ the first coordinate of $(X,Y)$ is constant $n$.

We define the function $\tau_{n}:K\rightarrow\mathbb{R}_{0}^{+}$
for $n\in\mathbb{N}_{0}$, where $\tau_{n}(k)$ for $k\in K_{B}$
is the mean first entrance time of $Y^{(n)}$ in $K_{W}$ when starting in $k\in K_{B}$ (conditional mean absorption time in $K_B$).
For $\ell\in K_{W}$ we set $\tau_{n}(\ell)\coloneqq 0$, indicating that absorption has already happened.

\begin{lemma}\label{lem:BS-PER-GEN-Lemma2}
For all $n\in \mathbb N_0$ holds $0< \tau_{n}(k) < \infty$ for $k\in K_{B}$ and we have a set of first-entrance equations
\[
\tau_{n}(k)=\frac{1}{-v_{n}(k,k)}+\sum_{\ell\in K_{B}\setminus\{k\}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\tau_{n}(\ell),
\]
which are equivalent to
\begin{equation}
-1=\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot\left(\tau_{n}(\ell)-\tau_{n}(k)\right)-\sum_{\ell\in K_{W}}v_{n}(k,\ell)\cdot\tau_{n}(k),\qquad n\in\mathbb{N}_{0}.\label{eq:BS-PER-GEN-eins}
\end{equation}
\end{lemma}

\begin{proof}
Positivity of $\tau_{n}$ on $K_B$ is due to the regularity of the $Y^{(n)}$ which follows from regularity of $(X,Y)$.\\
Irreducibility of $(X,Y)$ implies that for any $(n,k)\in \{n\}\times K_B$ there must exist some
state $(n,\ell)\in \{n\}\times K_W$ which can be reached in a finite number of jumps. This implies that $Y^{(n)}$ can be considered as a finite state process with attached single absorbing state $a$. Consequently, time to absorption  of $Y^{(n)}$ in $a$ has  finite mean for any initial state.\\
The set $\left(\tau_{n}(k):k\in K_{B}\right)$ satisfies the following
set of first entrance equations:
\begin{align}
\tau_{n}(k) & \overset{\phantom{(\star)}}{=}\sum_{\ell\in K_{B}\setminus\{k\}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\left(\frac{1}{-v_{n}(k,k)}
+\tau_{n}(\ell)\right) +\sum_{\ell\in K_{W}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\left(\frac{1}{-v_{n}(k,k)}+\tau_{n}(\ell)\right)\nonumber \\
 & \overset{\phantom{(\star)}}{=}\sum_{\ell\in K\setminus\{k\}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\frac{1}{-v_{n}(k,k)}\nonumber
+\sum_{\ell\in K_{B}\setminus\{k\}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\tau_{n}(\ell)+\sum_{\ell\in K_{W}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\underbrace{\tau_{n}(\ell)}_{=0}\nonumber \\
 & \overset{(\star)}{=}\frac{1}{-v_{n}(k,k)}+\sum_{\ell\in K_{B}\setminus\{k\}}\frac{v_{n}(k,\ell)}{-v_{n}(k,k)}\cdot\tau_{n}(\ell),\qquad\qquad\qquad n\in\mathbb{N}_{0}.\label{eq:rand-lemma-taunk}
\end{align}
$(\star)$ holds because $V_{n}=\left(v_{n}(k,\ell):k,\ell\in K\right)$ is conservative.
\eqref{eq:rand-lemma-taunk} is equivalent to
\begin{align*}
-1 & =\left(\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot\tau_{n}(\ell)\right)+v_{n}(k,k)\cdot\tau_{n}(k)\\
& =\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot\tau_{n}(\ell)-\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot\tau_{n}(k)\\
 & =\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot\left(\tau_{n}(\ell)-\tau_{n}(k)\right)-\sum_{\ell\in K_{W}}v_{n}(k,\ell)\cdot\tau_{n}(k),\qquad n\in\mathbb{N}_{0}.
\end{align*}
\end{proof}

\begin{lemma}
{\label{lem:random-cn}}We define for $n\in\mathbb{N}_{0}$
\begin{align}
\widehat{c}_{n} & \coloneqq \left[\min\left\{ \frac{1}{\max_{k\in K_{W}}\left\{ \mu(n+1)\cdot\sum_{\ell\in K_{B}}R_{n+1}(k,\ell)\cdot\tau_{n}(\ell)\right\} },\right.\right.\nonumber \\
 & \hphantom{=\left\{ \min\ \ \ \right.}\left.\left.\qquad\ \:\frac{1}{\max_{k\in K_{W}}\left\{ \sum_{\ell\in K_{B}}v_{n}(k,\ell)\cdot\tau_{n}(\ell)\right\} }\right\} \right].\label{eq:BS-PER-GEN-cn}
\end{align}
The $\widehat{c}_{n}$ are well-defined, i.e.~it holds $0 < \widehat{c}_{n}<\infty$ for
$n\in\mathbb{N}_{0}$.
\end{lemma}

\begin{proof}\label{rem:cn-kleiner}
First, we show $\widehat{c}_{n}>0$. Because of $0<\mu(n+1) <\infty$ this is equivalent to
\[
  \frac{1}{\max_{k\in K_{W}}\left\{\sum_{\ell\in K_{B}}R_{n+1}(k,\ell)\cdot\tau_{n}(\ell)\right\} }>0
  ~ \wedge ~\frac{1}{\max_{k\in K_{W}}\left\{ \sum_{\ell\in K_{B}}v_{n}(k,\ell)\cdot\tau_{n}(\ell)\right\} }>0.
\]
In Lemma \ref{lem:BS-PER-GEN-Lemma2} we have shown that the mean first entrance times $\tau_{n}(\ell)$
for $\ell\in K_{B}$ are positive and finite.  Hence, it holds $\widehat{c}_{n}>0$.

Second, we show that $\widehat{c}_{n}<\infty$. This is equivalent to
\[
 \max_{k\in K_{W}}\left\{\mu(n+1)\sum_{\ell\in K_{B}}R_{n+1}(k,\ell)\cdot\tau_{n}(\ell)\right\} \neq0 ~
  \vee~\max_{k\in K_{W}}\left\{ \sum_{\ell\in K_{B}}v_{n}(k,\ell)\cdot\tau_{n}(\ell)\right\} \neq0.
  \]
Because $\mu(n)>0$ and $\tau_{n}(\ell)>0$
for $\ell\in K_{B}$ this holds iff
\[\exists\ k\in K_{W},\ \ell\in K_{B}:\quad R_{n+1}(k,\ell)\neq0\quad\vee\quad v_{n}(k,\ell)\neq0.\]

To show this, note that because of irreducibility any state $(n,\ell)\in E$ with $\ell\in K_{B}$ must
be reachable from some state $(\widetilde{n},k)\in E$ with $k\in K_{W}$
in a finite number of steps.

If the environment is in state $\ell\in K_{B}$, no service is provided
to customers in the queue and newly arriving customers are lost.  Hence, no transitions from the states $(n+1,\ell)$ or
$(n-1,\ell)$ into state $(n,\ell)$ are possible.

Furthermore, a transition from state $(n-1,k)$ with $k\in K_{W}$
to state $(n,\ell)$ with $\ell\in K_{B}$ for all $n\in\mathbb{N}$
is not possible since changes of the environment's status can not occur concurrently with an arrival.
The only remaining possible transitions are
\begin{itemize}
\item transitions from $K_{W}$ to $K_{B}$ \\
with $v_{n}(k,\ell)>0$ from some state $(n,k)\in\mathbb{N}_{0}\times K_{W}$
to state $(n,\ell)\in\mathbb{N}_{0}\times K_{B}$ \\
or with $\mu(n+1)\cdot R_{n+1}(k,\ell)>0$ from some state $(n+1,k)\in\mathbb{N}_{0}\times K_{W}$
to state $(n,\ell)\in\mathbb{N}_{0}\times K_{B}$
\item or transitions  inside of $K_{B}$ \\
with $v_{n}(\widetilde{\ell},\ell)>0$ from some state $(n,\widetilde{\ell})\in\mathbb{N}_{0}\times K_{B}$
to state $(n,\ell)\in\mathbb{N}_{0}\times K_{B}$.
\end{itemize}
Hence, because of irreducibility any state
$(n,\ell)\in\mathbb{N}_{0}\times K_{B}$ must be reachable from a
state $(\widetilde{n},k)\in E$ with $\widetilde{n}\in\{n,n+1\}$
and $k\in K_{W}$ in a finite number of steps, i.e.~on a finite path
in $E$,
$
\left((\widetilde{n},k)=(n_{0},k_{0}),\;(n_{1},k_{1}),\;(n_{2},k_{2}),\ldots,
\;(n_{m-1},k_{m-1}),\;(n_{m},k_{m})=(n,\ell)\right),
$
where for all $i\in\left\{ 0,1,\ldots,m\right\}$ holds
$
q\left((n_{i},k_{i});(n_{i+1},k_{i+1})\right)>0.
$
$m$ is the length of the path.\\
Let $m^{*}\geq1$ be the minimal length.

Because of irreducibility and the above mentioned ``only remaining
possible transitions'' there must exist a minimal path from a state $(\widetilde{n},k)=(n_{0},k_{0})$
in $\{n,n+1\}\times K_{W}$ to state $(n_{m},k_{m})=(n,\ell)\in\mathbb{N}_{0}\times K_{B}$
of length $m^{*}\geq1$.

{\bf If$\ m^{*}=1$}, the state $(n,\ell)\in\mathbb{N}_{0}\times K_{B}$
is reachable directly from a state in $\{n,n+1\}\times K_{W}$ in
one step.
Consequently, for $\ell\in K_{B}$ there exists $k\in K_{W}$ such
that $R_{n+1}(k,\ell)>0$ or $v_{n}(k,\ell)>0$ holds because these
are the only possible transitions to reach the state $(n,\ell)\in\mathbb{N}_{0}\times K_{B}$
from $\{n,n+1\}\times K_{W}$ in one step.\\
{\bf If$\ m^{*}>1$}, the state $(n,\ell)\in\mathbb{N}_{0}\times K_{B}$
is reachable from a state in $\{n,n+1\}\times K_{W}$ in $m^{*}$
steps.
Hence, there exists a minimal path of length $m^{*}$, where the state
$(n,\ell_{1})\in\mathbb{N}_{0}\times K_{B}$ of the path is reachable directly
from a state in $\{n,n+1\}\times K_{W}$ in one step. \\
So, for $\ell_{1}\in K_{B}$ there exists $k\in K_{W}$ so
that $R_{n+1}(k,\ell_{1})>0$ or $v_{n}(k,\ell_{1})>0$ holds.
\end{proof}

\btheorem\label{thm:BS-PER-GER-pos-rec}
Consider the queueing-environment process $Z$ with finite environment set $K$. Assume that
\[
\widetilde{\mathcal{L}}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{0}^{+}
\]
is a Lyapunov function with finite exception set $\widetilde{F}$ and constant $\widetilde{\varepsilon}>0$ for the $M/M/1/\infty$
process with queue-length-dependent arrival intensities $\lambda(n)>0$ and service intensities $\mu(n)>0$.
Assume further that
\[
\inf_{n\in\mathbb{N}_{0}}\widehat{c}_{n}>0,
\]
holds, where $\widehat{c}_{n}$ is defined in  Lemma \ref{lem:random-cn}.
Then
\begin{equation}
\mathcal{L}:E\rightarrow\mathbb{R}_{0}^{+}~~\text{with}~~ \mathcal{L}(n,k)\coloneqq \widetilde{\mathcal{L}}(n)+1_{\left\{ k\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(k)\label{eq:rand-lyap}
\end{equation}
is a Lyapunov function for $Z$ with
finite exception set $F\coloneqq \widetilde{F}\times K$
and constant
\[
\varepsilon\coloneqq \min\left(\frac{\widetilde{\varepsilon}}{2}\ ,\ \inf_{n\in\mathbb{N}_{0}} c_{n}\right)>0,
~~\text{where}~~
c_{n}:=\frac{\widetilde{\varepsilon}}{4}\cdot\widehat{c}_{n},
\]
and $Z$ is ergodic.
\etheorem

\begin{proof}
We construct the Lyapunov function

\begin{equation}
\mathcal{L}:E\rightarrow\mathbb{R}_{0}^{+}~~\text{with}~~ \mathcal{L}(n,k)=\widetilde{\mathcal{L}}(n)+1_{\left\{ k\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(k)\label{eq:rand-lyap}
\end{equation}

and finite exception set $F=\widetilde{F}\times K$
and constant
\[
\varepsilon=\min\left(\frac{\widetilde{\varepsilon}}{2}\ ,\ \inf_{n\in\mathbb{N}_{0}} c_{n}\right)>0,
~~\text{where}~~
c_{n}:=\frac{\widetilde{\varepsilon}}{4}\cdot\widehat{c}_{n}.
\]

\noindent First, because  the jumps of $X$ are of hight $1$, and because $|K|<\infty$, to check $\left(\mathbf{Q\cdot\mathcal{L}}\right)\left(n,k\right)<\infty$
for $(n,k)\in F=\widetilde{F}\times K$ is by direct evaluation.

\noindent Second, we will check $\left(\mathbf{Q\cdot\mathcal{L}}\right)\left(n,k\right)\leq-\varepsilon$ for $(n,k)\notin F=\widetilde{F}\times K$.\\
 $\blacktriangleright$ For $k\in K_{B}$ and $n\notin F$, $n\geq0$, holds

\begin{align*}
 & \left(\mathbf{Q\cdot\mathcal{L}}\right)\left(n,k\right)

  =\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot\left(\mathcal{L}(n,\ell)-\mathcal{L}(n,k)\right)\\
 & =\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot\left(\left(\widetilde{\mathcal{L}}(n)+1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(\ell)\right)-\left(\widetilde{\mathcal{L}}(n)+1_{\left\{ k\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(k)\right)\right)\\
 & =\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(\ell)-\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=1}c_{n}\cdot\tau_{n}(k)\\
 & =\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot c_{n}\cdot\tau_{n}(\ell)-\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot c_{n}\cdot\tau_{n}(k)\\
 & =\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot\left(c_{n}\cdot\tau_{n}(\ell)-c_{n}\cdot\tau_{n}(k)\right)-\sum_{\ell\in K_{W}}v_{n}(k,\ell)\cdot c_{n}\cdot\tau_{n}(k)\\
 & =c_{n}\cdot\underbrace{\Bigg[\sum_{\ell\in K_{B}\setminus\{k\}}v_{n}(k,\ell)\cdot\left(\tau_{n}(\ell)-\tau_{n}(k)\right)-\sum_{\ell\in    K_{W}}v_{n}(k,\ell)\cdot\tau_{n}(k)\Bigg]}_{{=}-1, {~~\text{by}~ \eqref{eq:BS-PER-GEN-eins}}}\\

 & =-c_{n}\leq-\varepsilon=-\min\left(\frac{\widetilde{\varepsilon}}{2}\ ,\ \inf_{m\in\mathbb{N}_{0}} c_{m}\right).\end{align*}

 $\blacktriangleright$ For $k\in K_{W}$ and $n=0\notin F$ holds
\begin{align*}
 & \phantom{\leq}\left(\mathbf{Q\cdot\mathcal{L}}\right)\left(n,k\right)

 =\lambda(0)\cdot\left(\mathcal{L}(1,k)-\mathcal{L}(0,k)\right)
+\sum_{\ell\in K\setminus\{k\}}v_{0}(k,\ell)
\cdot\left(\mathcal{L}(0,\ell)-\mathcal{L}(0,k)\right)\\
 & =\lambda(0)\cdot\Bigg(\Bigg(\widetilde{\mathcal{L}}(1)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{1}\cdot\tau_{1}(k)\Bigg)-\Bigg(\widetilde{\mathcal{L}}(0)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{0}\cdot\tau_{0}(k)\Bigg)\Bigg)\\
 & \phantom{\leq}+\sum_{\ell\in K\setminus\{k\}}v_{0}(k,\ell)\cdot\Bigg(\Bigg(\widetilde{\mathcal{L}}(0)+1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{0}\cdot\tau_{0}(\ell)\Bigg)-\Bigg(\widetilde{\mathcal{L}}(0)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{0}\cdot\tau_{0}(k)\Bigg)\Bigg)\\
 & =\lambda(0)\cdot\left(\widetilde{\mathcal{L}}(1)-\widetilde{\mathcal{L}}(0)\right)+\sum_{\ell\in K\setminus\{k\}}v_{0}(k,\ell)\cdot 1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{0}\cdot\tau_{0}(\ell)\\
 & =\underbrace{\lambda(0)\cdot\left(\widetilde{\mathcal{L}}(1)-
 \widetilde{\mathcal{L}}(0)\right)}_{{\leq}-\widetilde{\varepsilon}~~{(\diamondsuit)}}+\sum_{\ell\in K_{B}}v_{0}(k,\ell)\cdot c_{0}\cdot\tau_{0}(\ell)\\
 & \leq-\widetilde{\varepsilon}+\underbrace{\sum_{\ell\in K_{B}}v_{0}(k,\ell)\cdot c_{0}\cdot\tau_{0}(\ell)}_{\overset{\eqref{eq:BS-PER-GEN-cn}}{\leq}\frac{\widetilde{\varepsilon}}{4}}\leq-\frac{3}{4}\cdot\widetilde{\varepsilon}\leq-\varepsilon=-\min\left(\frac{\widetilde{\varepsilon}}{2}\ ,\ \inf_{m\in\mathbb{N}_{0}} c_{m}\right).
\end{align*}

$(\diamondsuit)$ holds because of \eqref{eq:random-mm1-eq1}
since $\widetilde{\mathcal{L}}:E\rightarrow\mathbb{R}_{0}^{+}$ is
a Lyapunov function for the $M/M/1/\infty$ queue with queue-length-dependent
arrival and service intensities with constant $\widetilde{\varepsilon}$.

 $\blacktriangleright$ For $k\in K_{W}$ and $n\notin F$, $n>0$, holds
\begin{align*}
 & \phantom{\leq}\left(\mathbf{Q\cdot\mathcal{L}}\right)\left(n,k\right)

  =\lambda(n)\cdot\left(\mathcal{L}(n+1,k)-\mathcal{L}(n,k)\right)\\
 & \phantom{\leq}+\sum_{\ell\in K}\mu(n)\cdot R_{n}(k,\ell)\cdot\left(\mathcal{L}(n-1,\ell)-\mathcal{L}(n,k)\right)
+\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot\left(\mathcal{L}(n,\ell)-\mathcal{L}(n,k)\right)\\
 & =\lambda(n)\cdot\Bigg(\Bigg(\widetilde{\mathcal{L}}(n+1)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{n+1}\cdot\tau_{n+1}(k)\Bigg)-\Bigg(\widetilde{\mathcal{L}}(n)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{n}\cdot\tau_{n}(k)\Bigg)\Bigg)\\
 & \phantom{\leq}+\sum_{\ell\in K}\mu(n)\cdot R_{n}(k,\ell)\cdot\Bigg(\Bigg(\widetilde{\mathcal{L}}(n-1)+1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{n-1}\cdot\tau_{n-1}(\ell)\Bigg)\\
 & \hphantom{+\sum_{\ell\in K}\mu(n)\cdot R_{n}(k,\ell)\cdot\Bigg(\quad}-\Bigg(\widetilde{\mathcal{L}}(n)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{n}\cdot\tau_{n}(k)\Bigg)\Bigg)\\
 & \phantom{\leq}+\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot\Bigg(\Bigg(\widetilde{\mathcal{L}}(n)+1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(\ell)\Bigg)-\Bigg(\widetilde{\mathcal{L}}(n)+\underbrace{1_{\left\{ k\in K_{B}\right\} }}_{=0}\cdot c_{n}\cdot\tau_{n}(k)\Bigg)\Bigg)\\
 & =\lambda(n)\cdot\left(\widetilde{\mathcal{L}}(n+1)-\widetilde{\mathcal{L}}(n)\right)+\mu(n)\cdot\underbrace{\sum_{\ell\in K}R_{n}(k,\ell)}_{=1}\cdot\left(\widetilde{\mathcal{L}}(n-1)-\widetilde{\mathcal{L}}(n)\right)\\
 & \phantom{\leq}+\mu(n)\cdot\sum_{\ell\in K}R_{n}(k,\ell)\cdot1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{n-1}\cdot\tau_{n-1}(\ell)+\sum_{\ell\in K\setminus\{k\}}v_{n}(k,\ell)\cdot 1_{\left\{ \ell\in K_{B}\right\} }\cdot c_{n}\cdot\tau_{n}(\ell)\\
 & =\underbrace{\lambda(n)\cdot\left(\widetilde{\mathcal{L}}(n+1)-\widetilde{\mathcal{L}}(n)\right)+\mu(n)
 \cdot\left(\widetilde{\mathcal{L}}(n-1)-
 \widetilde{\mathcal{L}}(n)\right)}_{{\leq}-\widetilde{\varepsilon}~~{(\triangle)}}\\
 & \phantom{\leq}+\mu(n)\cdot\sum_{\ell\in K_{B}}R_{n}(k,\ell)\cdot c_{n-1}\cdot\tau_{n-1}(\ell)+\sum_{\ell\in K_{B}}v_{n}(k,\ell)\cdot c_{n}\cdot\tau_{n}(\ell)\\
 & \leq-\widetilde{\varepsilon}+\underbrace{\mu(n)\cdot\sum_{\ell\in K_{B}}R_{n}(k,\ell)\cdot c_{n-1}\cdot\tau_{n-1}(\ell)}_{{\leq}
 \frac{\widetilde{\varepsilon}}{4}~~{\eqref{eq:BS-PER-GEN-cn}}}+\underbrace{\sum_{\ell\in K_{B}}v_{n}(k,\ell)\cdot c_{n}\cdot\tau_{n}(\ell)}_{{\leq}\frac{\widetilde{\varepsilon}}{4}~~{\eqref{eq:BS-PER-GEN-cn}}}\\
 & \leq-\frac{\widetilde{\varepsilon}}{2}\leq-\varepsilon=-\min\left(\frac{\widetilde{\varepsilon}}{2}\ ,\ \inf_{m\in\mathbb{N}_{0}} c_{m}\right).
\end{align*}

$(\triangle)$ holds because of \eqref{eq:random-mm1-eq2} since
$\widetilde{\mathcal{L}}:E\rightarrow\mathbb{R}_{0}^{+}$ is a Lyapunov
function for the $M/M/1/\infty$ queue with queue-length-dependent
arrival and service intensities with constant $\widetilde{\varepsilon}$.
\end{proof}

\bremark\label{rem:inf-c-n}
The positivity condition in Theorem \ref{thm:BS-PER-GER-pos-rec},
\[
\inf_{n\in\mathbb{N}_{0}}\widehat{c}_{n}>0,
\]
says roughly that the mean passage times through $K_B$ are uniformly (over all queue lengths $n\geq 0$) bounded.
Any such passage through $K_B$, initiated when the environment is on leave  from some $k\in K_W$ by entering some $\ell\in K_B$,
originates either from a jump movement (service completion which triggers an immediate jump)  $k\to\ell$
governed by $R_{n+1}(k,\cdot)$, or from a continuous movement
from some $k\in K_W$ to some $\ell\in K_B$
driven by $v_{n}(k,\cdot)$.
In both cases the resulting queue length during the passage is $n$. Rewriting \eqref{eq:BS-PER-GEN-cn} as
\begin{align*}
\widehat{c}_{n} & =\left[\min\left\{ \frac{1}{\max_{k\in K_{W}}\left\{ \mu(n+1)\cdot\sum_{\ell\in K_{B}}R_{n+1}(k,\ell)\cdot\tau_{n}(\ell)\right\} },\right.\right.\nonumber \\
& \hphantom{=\left\{ \min\ \ \ \right.}\left.\left.\qquad\ \:\frac{1}{\max_{k\in K_{W}}
	\left\{ - v_{n}(k,k)\sum_{\ell\in K_{B}}\frac{v_{n}(k,\ell)}{- v_{n}(k,k)}\cdot\tau_{n}(\ell)\right\} }\right\} \right],
\end{align*}
we observe that the mean passage times through $K_B$ are in both cases weighted by the entrance probabilities into $K_B$.\\
Including the departure intensities $ \mu(n+1)$, resp. $- v_{n}(k,k)$ out of $k\in K_W$ ensures that the queueing-environment system resides in $K_W$ sufficiently long.
\eremark

\bcor\label{cor:BS-PER-GER-pos-rec-2}
Consider the queueing-environment process $Z$ with finite environment set $K$ and queue-length-dependent
arrival intensities $\lambda(n)>0$ and service intensities $\mu(n)>0$.
If \beq \label{eq:birth-death-constant-finite-1}
\sum_{n=0}^{\infty}\prod_{m=1}^{n}\frac{\lambda(m-1)}{\mu(m)}<\infty
\eeq
holds, and if with $\widehat{c}_{n}$ from  Lemma \ref{lem:random-cn}, it holds
\[
\inf_{n\in\mathbb{N}_{0}}\widehat{c}_{n}>0,
\]
then  $Z$ is ergodic.
\ecor

\bproof
The Markovian queue length process $X$ of the $M/M/1/\infty$ queue with rates $\lambda(n)>0$ and  $\mu(n)>0$ is ergodic under \eqref{eq:birth-death-constant-finite-1}.
A Lyapunov function can be determined as follows:\\
Take $\widetilde{F} \coloneqq \{0\}$ as exception set and for $n\geq 1$
define $\widetilde{\mathcal{L}}(n)$ as the mean first entrance time of $X$ into $\{0\}$ given $X(0)=n$, and set formally
$\widetilde{\mathcal{L}}(0)\coloneqq 0$. For $n\geq 1$ we have the mean first-entrance-equations
\[
\widetilde{\mathcal{L}}(n)= \frac{1}{\lambda(n)+\mu(n)} +
\left(\frac{\lambda(n)}{\lambda(n)+\mu(n)}
\widetilde{\mathcal{L}}(n+1)+
\frac{\mu(n)}{\lambda(n)+\mu(n)}
\widetilde{\mathcal{L}}(n-1)\right),
\]
which is
\beq\label{eq:LyapunovGuT-1}
\sum_{m\in\{n-1,n+1\}}q(n,m)\left[\widetilde{\mathcal{L}}(m) -
\widetilde{\mathcal{L}}(n)
\right] = -1, \qquad n\in \widetilde{F}^c,
\eeq
and it holds furthermore for some $b> 0$
\beq\label{eq:LyapunovGuT-2}
q(n,n+1)\left[\widetilde{\mathcal{L}}(n+1) -
\widetilde{\mathcal{L}}(n)
\right] = \lambda(1) \widetilde{\mathcal{L}}(1) \leq b-1 , \qquad n=0\in \widetilde{F},
\eeq
which says that
$\widetilde{\mathcal{L}}$ constitutes by \eqref{eq:LyapunovGuT-1} and \eqref{eq:LyapunovGuT-1} is a Lyapunov function for $X$ in the sense of \cite[Proposition D.3]{kelly;yudovina:14}.
Because of \eqref{eq:birth-death-constant-finite-1} it holds
$\widetilde{\mathcal{L}}(n)\in (0,\infty)$ for all $n\geq 1$,
see \cite[Corollary of Theorem 2 on p. 214]{chung:67}.
We therefore can apply Theorem \ref{thm:BS-PER-GER-pos-rec}
to finish the proof.
\eproof

\bremark\label{rem:FossEtal}
It is interesting to compare the result of Corollary \ref{cor:BS-PER-GER-pos-rec-2}, especially the condition
\eqref{eq:birth-death-constant-finite-1}, with the structure of the results in \cite{foss;shneer;tyurlikov:12}, although the two-dimensional Markov processes there are discrete time models on a general state space. For simplicity we concentrate on \cite[Section 2]{foss;shneer;tyurlikov:12}. The process
$Z=(X,Y)$ there constitutes a non-Markovian chain $Y$ in a random environment described by a Markov chain $X$. We note that $X$ is an autonomous environment, i.e.~$X$ is Markov (on a general state space) for its own which is ergodic due to a given Lyapunov function. The evolution of $Y$ depends on $X$ via the $X$-dependent transition probabilities.\\
If in our running example of the queueing-inventory system, see Example \ref{ex:QueueInventory1}, we consider the queue, i.e.~$X$,  as the environment of the inventory, i.e. $Y$, then the condition
\eqref{eq:birth-death-constant-finite-1} seems to fix ergodicity for $X$ via the Lyapunov function $\widetilde{\mathcal{L}}$ as in the model of \cite{foss;shneer;tyurlikov:12}.\\
The point is: Although $\widetilde{\mathcal{L}}$ guarantees in some sense a drift condition for $X$, the standard approach of Markov theory is not possible because our environment $X$ is not Markov as in \cite{foss;shneer;tyurlikov:12}. Our theorems deal with a completely different situation.
\eremark

The following corollary and example shed some light on the range of possible classes of models subsumed in Theorem \ref{thm:BS-PER-GER-pos-rec} and Corollary \ref{cor:BS-PER-GER-pos-rec-2}.

\begin{cor}
\label{cor:random-cor-mm1-bsp}The queueing-environment process $Z$
is ergodic if there exists $N\in\mathbb{N}_{0}$ such that $\inf_{n\geq N}\left(\mu(n)-\lambda(n)\right)>0$
and
\[
\inf_{n\in\mathbb{N}_{0}}\widehat{c}_{n}>0,
\]
where $\widehat{c}_{n}$ is defined in \prettyref{lem:random-cn}.\end{cor}
\begin{proof}
Let there be $N\in\mathbb{N}_{0}$ such that $\inf_{n\geq N}\left(\mu(n)-\lambda(n)\right)>0$.
Then, for every $M/M/1/\infty$ queue with queue-length-dependent
arrival intensities $\lambda(n)>0$ and service intensities $\mu(n)>0$
is $\widetilde{\mathcal{L}}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{0}^{+}$ with $\widetilde{\mathcal{L}}(n)\coloneqq n$, finite exception set $\widetilde{F}\coloneqq \{0,\ldots,N-1\}$ and constant $\widetilde{\varepsilon}\coloneqq \inf_{n\geq N}\left(\mu(n)-\lambda(n)\right)>0$
a Lyapunov function, which satisfies the Foster-Lyapunov stability
criterion. Hence, we can apply \prettyref{thm:BS-PER-GER-pos-rec}.
\end{proof}

\bex\label{ex:random-bsp-perish} If $\sup_{n\in \mathbb{N}_{0}}\mu(n)<\infty$, then in the following examples holds  $\inf_{n\in\mathbb{N}_{0}}\widehat{c}_{n}>0$. It should be noted that $\widehat{c}_{n}$ is only defined by $\mu(n+1)$, the generator $V_n$ and the stochastic matrix $R_n$ (since $\tau_n$ is defined by the generator $V_n$).
\begin{itemize}
\item [\textbf{(a)}]For the generator $V_{n}=\left(v_{n}(k,\ell):k,\ell\in K\right)$
holds
\[
V_{2n-1}\coloneqq V_{1}\quad\text{and}\quad V_{2n}\coloneqq V_{2},\qquad n\in\mathbb{N},
\]
and for the stochastic matrix $R_{n}=(R_{n}(k,\ell):k,\ell\in K$)
holds
\[
R_{2n-1}\coloneqq R_{1}\quad\text{and}\quad R_{2n}\coloneqq R_{2},\qquad n\in\mathbb{N}.
\]
A similar structure is found in birth-and-death processes with alternating
rates which are considered e.g.~by Di Crescenzo et al.\ (\cite{dicrescenzo:12},
\cite{dicrescenzo:14}).
\item [\textbf{(b)}]Let $N_{0}\in \mathbb{N}$. For the generator $V_{n}=\left(v_{n}(k,\ell):k,\ell\in K\right)$
holds
\[
V_{n}\coloneqq V\quad\forall n\geq N_{0},
\]
and for the stochastic matrix $R_{n}=(R_{n}(k,\ell):k,\ell\in K$)
holds
\[
R_{n}\coloneqq R\quad\forall n\geq N_{0}.
\]
Then, $\widehat{c}_{n}$ can be arbitrarily until $N_{0}-1$ and
from $N_{0}$ it is bounded below by a $\widehat{c}_{\min}>0$. \\
A similar  structure is found in multi-server models ($M/M/s$ queue)
which are studied e.g.\ by Neuts~\cite[Section 6.2, Section 6.5]{neuts:81}.
\\
Moreover, such a structure is found in a queue with $N$ servers subject
to breakdowns and repairs. This is studied by Neuts and Lucantoni~\cite{neuts;lucantoni:79}.\\
Furthermore, this structure can be found in the study of Neuts and
Rao~\cite{neuts;rao:90}. Since an analytic solution for their
multi-server retrial model is difficult, they make a simplifying approximation,
which yields an infinitesimal generator with a modified matrix-geometric
steady state vector which can be efficiently computed.
\item [\textbf{(c)}]The queueing-inventory system with perishable items in Example \ref{ex:QueueInventory2} is a special case of \textbf{(b)}  with $N_{0}=1$.
\end{itemize}
\eex

\section{Bounding performance  of non-separable systems}\label{sect:BoundingNPF}
Standard performance metrics (e.g.~throughput, mean delay, mean queue lengths) of complex systems are often directly accessible if the system is separable as described in Section \ref{sect:Separable}. This relies on the fact that the mentioned metrics can be computed when the stationary distribution is explicitly at hand.
On the other side, computing these performance metrics for non-separable systems as that in Section \ref{sect:Non-separable} is often difficult.
Van Dijk reviews literature on methods for bounding performance metrics of stochastic systems when  values of the metric of
interest  are not explicitly available (cf.~\cite[Section 1.7, pp.~62f.]{dijk:11b},~\cite[pp.~311ff.]{dijk:98},~\cite{dijk;koreuioglu:92},~\cite{dijk;wal:92}).
He developed among other methods a principle to bound performance metrics of ``non-product form systems''
by the respective metrics of related ``product form systems'', and provided many examples.
Closely related to our systems and the topic of the present section are the ``queueing systems in random environment'' with unknown stationary distribution in \cite[Theorem 3]{economou:03a}.
The generator of the environment process which is Markov of its own in the original system is ``perturbed'' in such a way that there are bi-directional interactions in the modified system which then shows a stationary distribution of a special ``product form''
which is of slightly different form as those developed here.

Our results in Sections \ref{sect:Separable} and \ref{sect:Non-separable} suggest to develop approximation principles for queues in a random environment when separability does not hold. The main idea is to manipulate the environment in a suitable way. These principles should provide approximation methods
for the application examples described in the introduction when separability fails here. We concentrate on queueing-inventory systems.

As we have stated in Corollary \ref{cor:QueueInventory-NonPF}, the stationary distribution of the queueing-inventory system in Example \ref{ex:QueueInventory2} is in general  not of product form and therefore  closed form expressions are not available for the production-inventory system with perishable items when the total ageing rate  depends on whether an item from inventory is already in usage for production (in case of base stock levels $b \geq  2$).

In the next example we show that we get product form results for related systems which are slight modifications of Example \ref{ex:QueueInventory2}.
For simplicity we consider arrival rates $\lambda$ and service rates $\mu$ independent of the queue lengths.

\bex[Separable queueing-inventory system with perishable items]\label{ex:QueueInventory3}
We consider  the queueing-inventory system of Example \ref{ex:QueueInventory1} with perishable items in the inventory where the ageing regimes are different from that in
 Example \ref{ex:QueueInventory2}:
Ageing is \emph{independent} of whether an item from inventory is already in usage by production.\\
If there are $k>0$ items of raw material in the inventory, then the total loss rate
of inventory due to perishing is $\gamma\cdot d(k)$ independent of the queue length. We call the function $k\mapsto\gamma\cdot d(k)$ ageing regime.\\
The queueing-inventory process $Z$ has  generator $\mathbf{Q}=\left(q(z;\tilde{z}):z,\tilde{z}\in E\right)$
with the following  transition rates for $(n,k)\in E$.

\begin{align*}
q\left((n,k);(n+1,k)\right) & \coloneqq \lambda \cdot1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} },\\
q\left((n,k);(n,k-1)\right) & \coloneqq \gamma\cdot d(k) \cdot 1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} },\\
q\left((n,k);(n-1,k-1)\right) & \coloneqq \mu \cdot1_{\left\{ n>0\right\} }\cdot1_{\left\{ k\in\left\{ 1,\ldots,b\right\}\right\} },\\
q\left((n,k);(n,k+1)\right) & \coloneqq \nu\cdot1_{\left\{ \in\left\{ 0,\ldots,b-1\right\}\right\} },
\end{align*}
and $q(z;\tilde{z})\coloneqq 0$ for other $z\neq\tilde{z}$,
and
$q\left(z;z\right)\coloneqq -\sum_{\substack{\tilde{z}\in E,\\
		z\neq\tilde{z}} }q\left(z;\tilde{z}\right)$ for all $z\in E.$

This queueing-inventory system with exponentially distributed
life times of the items in the inventory fits
into the definition of the queueing system in a random environment
by setting
$
K\coloneqq \left\{0,1,\ldots,b\right\},
K_{B}\coloneqq \left\{0\right\}, K_{W}\coloneqq \left\{1,\ldots,b\right\},
$
and
\[
R_{n}(0,0)\coloneqq 1,\qquad R_{n}(k,k-1)\coloneqq 1,\quad1\leq k\leq b,\ n\in\mathbb{N},
\]

\begin{align}\label{eq:v-perish-separable}
v_{n}(k,\ell) & \coloneqq \begin{cases}
\nu, & \text{if } k\in\left\{ 0,\ldots,b-1\right\},\ \ell=k+1,\\
\gamma\cdot d(k), & \text{if }k\in\left\{ 1,\ldots,b\right\},\ \ell=k-1,\\
0, & \text{otherwise for }k\neq\ell,\qquad\quad n\geq0.
\end{cases}
\end{align}

If $\lambda<\mu$ the queueing-inventory process is ergodic, and the stationary distribution $\pi$ is

\begin{equation}\label{eq:perish-separableSteadyState-1}
\pi(n,k)\coloneqq \xi(n)\cdot \theta (k), \ (n,k)\in E,
\end{equation}
with
\begin{align}\label{eq:perish-separableSteadyState-2}
\xi(n)\coloneqq \left( 1- \frac{\lambda}{\mu}\right) \cdot \left(\frac{\lambda}{\mu}\right)^n
\  n\in \mathbb{N}_{0},\qquad
\theta(k)\coloneqq C_{\theta}^{-1} \cdot \prod_{\ell =0}^{k-1} \frac{\nu}{\lambda + d(\ell +1 )}, \  k\in K,
\end{align}

and normalisation constant $C_{\theta}$.
\eex
We will show that (with varying ageing function $d(\cdot)$)
this product form result can  be used to bound throughputs for the systems with (unknown) non-product form stationary distribution of Example \ref{ex:QueueInventory2}.

For simplicity we consider an ergodic queueing-inventory system according to  Example \ref{ex:QueueInventory2} with queue length independent rates $\lambda, \mu$.
We construct bounding systems according to Example \ref{ex:QueueInventory3} with the same rates $\lambda, \mu$, environment $K=\left\{0,1,\ldots,b\right\},
K_{B}=\left\{0\right\}, K_{W}=\left\{1,\ldots,b\right\},$ and
jump matrices $R_n$ and two new specifications of $d(\cdot)$ in the rate matrices \eqref{eq:v-perish-separable}.
These systems are ergodic because of \eqref{eq:perish-separableSteadyState-1} and \eqref{eq:perish-separableSteadyState-2}.

\underline{A lower bound ``$-$''-system} where the  ageing regime in state $(m,k)\in E$ is $k\mapsto d(k) := \gamma\cdot k$. This means:
All items are perishable - even
the one already reserved for production.

\underline{An upper bound ``$+$''-system} where the  ageing regime in state $(m,k)\in E$ is $k\mapsto d(k) := \gamma\cdot(k-1)_{+}$.
This means:
One item in the inventory (if there is any) is not subject
to ageing - even if the server is idling and no item is reserved for production.

\underline{The target  ``$o$''-system,} i.e.~queueing-inventory system with unknown non-product form
stationary distribution from  Example \ref{ex:QueueInventory2}.
Perishing of items depends on whether an item
from inventory is in usage by production (i.e.~the server
is busy, or if the server is idling and the inventory is not   empty). The ageing regime in
state $(m,k)\in E$ is $k\mapsto(\gamma\cdot k)\cdot1_{\left\{ n=0\right\} }+(\gamma\cdot(k-1))\cdot1_{\left\{ n>0\right\} }.$
This system is ergodic from Corollary \ref{cor:BS-PER-GER-pos-rec-2} and Example \ref{ex:random-bsp-perish}\textbf{(b)}.

In the following we write ``$\star$''-system for one of the systems specified by ``+'', ``-'', or ``o''.
In all cases is with stationary distribution $\pi^{\star}\coloneqq (\pi^{\star}(m,k):(m,k)\in E)$ the throughput
\begin{equation}
TH^{\star}\coloneqq \sum_{(m,k)\in E}\pi^{\star}(m,k)\cdot\mu\cdot1_{\left\{ m>0\right\} }\cdot1_{\left\{ k>0\right\} }.\label{eq:THo-1-1-Star}
\end{equation}

Denote by $v^\star_n(m,k)$ the number of departures from the $\star$-system up to the time of the $n$-the jump of the process given the initial state is $(m,k)\in E$.
So $v^\star_n(m,k)/n$ is the finite time throughput up to the time of the $n$-the jump of the process started in  $(m,k)\in E$.
It holds for all initial states $(m,k)\in E$ \cite[Lemma 2]{vanderwal:89}
\begin{equation}
TH^{\star}= \lim\limits_{n\to\infty} \frac{1}{n} v^\star_n(m,k).
\label{eq:THo-1-1-StarInfty}
\end{equation}

Our starting point is the observation that for all $(n,k)\in E$ the ageing regimes are ordered:
\[
\gamma\cdot(k-1)_{+}\leq(\gamma\cdot k)\cdot1_{\left\{ n=0\right\} }+(\gamma\cdot(k-1))\cdot1_{\left\{ n>0\right\} }\leq\gamma\cdot k.
\]

Intuitively we expect that the throughputs of the respective
systems are ordered the other way round.
The intuitive explanation of this throughput ordering is:
If we have either more inventory and at least the same number of customers
in system, or more customers in system and at least the same stock
size of the inventory, then the system should be able to produce more output.

This leads to the following conjecture.
\begin{conjecture}[Monotonicity of throughputs]Consider three (exponential) ergodic
	queueing-inventory systems with the same arrival rate $\lambda$,
	service rate $\mu$, replenishment rate $\nu$, individual ageing
	rate $\gamma$ for items in the inventory which are subject to ageing.

	Then the following monotonicity property for the throughputs holds
	\[
	TH^{-}\leq TH^{o}\leq TH^{+}.
	\]
\end{conjecture}

This conjecture is supported by the following results:\\
\textbf{R1.} In~\cite[Section 4.3.3.1, pp.~112ff.]{otten:18}, we computed explicitly the throughputs of the systems with base stock level $b=1$ and showed that the monotonicity property holds.
This is based on explicit stationary distributions in Corollary \ref{cor:QueueInventoryPerishable-PF} (for "o"-system) and in Example \ref{ex:QueueInventory3} (for "$-$"- and "$+$"-system).

\textbf{R2.} We say that $v^\star_n$ is isotone with respect to the product order on $\mathbb{N}_0\times\{0,1,\dots,b\}$ if
\beq\label{eq:order}
\forall (m,k), (m',k')\in E:[m\leq m' \wedge k\leq k']~\text{implies}~ [v^\star_n(m,k)\leq  v^\star_n(m',k')].
\eeq
The proof of the following proposition is tedious and rather lengthy and can be found in \cite[Appendix D.2]{otten:18}.

\bprop\label{prop:isotone}
Consider the three exponential ergodic queueing-inventory systems ``+'', ``-'', and ``o'' with perishable items  described above
with identical rates $\lambda, \mu, \nu$ and the different ageing regimes. Then the following holds \cite[Proposition 4.3.11]{otten:18}:

\textbf{(a)} If $v^-_n$ is isotone, then for all $ (m,k)\in E$ holds
\[
v^-_n(m,k)\leq  v^o_n(m,k)\quad \forall n\in\mathbb{N},
\]
and consequently $TH^-\leq TH^o$.

\textbf{(b)} If $v^+_n$ is isotone, then for all $ (m,k)\in E$ holds
\[
v^o_n(m,k)\leq  v^+_n(m,k)\quad \forall n\in\mathbb{N},
\]
and consequently $TH^o\leq TH^+$.

\textbf{(c)} If $v^o_n$ is isotone, then for all $ (m,k)\in E$ holds
\[
v^-_n(m,k)\leq  v^o_n(m,k)\leq  v^+_n(m,k)\quad \forall n\in\mathbb{N},
\]
and consequently $TH^-\leq TH^o\leq TH^+$.
\eprop

Exploiting the monotonicity results of Proposition \ref{prop:isotone}, it can be shown that for all base stock levels
in~\cite[Section 4.3.3.2, pp.~114ff.]{otten:18}   the following results  hold:
\begin{itemize}
\item If in the "$-$"-system we have $\lambda\leq \gamma$, then it holds $TH^{-}\leq TH^{o}$.
\item If in the "$o$"-system we have $\mu=\gamma$, then it holds $TH^{-}\leq TH^{o}\leq TH^{+}$.
\end{itemize}

\bproof
Utilizing ideas of van der Wal \cite{vanderwal:89}, monotonicity is shown under both conditions in \cite[pages 354--373]{otten:18}.
Thereafter Proposition \ref{prop:isotone} is applied.
\eproof
\section{Conclusion}\label{sect:Conclusion}
For a large class of queueing-environment systems with bi-directional interaction we have obtained product form steady state distributions. These explicit steady state distributions open the possibility to compute performance metrics of the systems explicitly.\\
If this is not possible we developed ergodicity criteria using Lyapunov functions and demonstrated by an example of a coupled queueing-inventory system how to compute two-sided bounds for the throughput. This indicates how to procede in case of general queueing-environment systems to obtain explicit bounds  for performance indices which are not directly accessible.
Another direction of research on non-separable queueing-environment systems is to modify the transition intensity matrix of the system suitably (possibly only the environment coordinate-process) to obtain a product form approximation of the stationary distribution.
This is part of our ongoing research.

\bibliographystyle{alpha}

config: arxiv


TITLE: Why is humanity investing so little on fusion research?
QUESTION [1 upvotes]: Optimists expect fusion industry to be a reality in 2080 to 2100. Fusion means clean and unlimited amount of energy, it is the fuel of the universe. Fusion will solve most of our time problems including climate change and clear water supply.
However the humanity global investment on research on fusion is around 40B\$ (around 20B\$ just for the ITER project). Beijing Olympic Game alone costed 40B\$ and the global wealth created per year is around 82.000B\$. Apple, Amazon, Microsoft and Google are worth each 1.000B\$+.
I understand that obtaining energy from fusion is, after 60 years of research, still a major scientific and industrial challenge with uncertainty. But last decade progress have been real.
2080 is far too late. Why not invest say 1.000B\$ on 20 years and get a real chance to counter climate change before it is too late? Why not consider fusion as the new man-on-the-moon challenge? Most of us feel concerned by climate change, why so few realize the potential of fusion?

REPLY [6 votes]: There are a long list of reasons why more generous funding is not forthcoming; I will recount some of them here.
First, there is a general distrust of nuclear energy, following the long history of disappointments surrounding atomic fission reactors. In a sense, fusion has a bad reputation because of fission, at least in the eyes of the public and most of the people they elect to high office.
Second, as long as the USA is awash in fossil fuels (specifically, fracked natural gas and tar sands) there is little short-term economic advantage to funding a full-court press for fusion power. Getting the people who control funding to think long-term has always been and will continue to be a big problem.
Third, there are many problems related to making fusion power feasible that our best efforts for over 60 years have not solved- not because we haven't spent enough money, but because physics conspires against us. One such problem for example is how to convert the kinetic energy of the neutrons given off by fusion into heat that can boil water and drive turbines in what is called the "first wall" of a hypothetical fusion reactor, without destroying the integrity of the material forming the first wall with the neutron flux.
Finally, note that when governments subsidize sports into international spectacle, it makes sports enthusiasts happy quickly relative to the timescale of the expenditure. Those same sports enthusiasts cannot be made happy with progress in achieving breakeven in demonstration-scale fusion reactors, and until we can figure out some way to accomplish that, this situation in unlikely to change.


TITLE: Formalities of the variational integral
QUESTION [2 upvotes]: Usually when the variational principle is introduced one starts by defining a Lagrangian density
$${\mathscr L}(x,\phi(x),\partial_{\mu}\phi(x))$$
and an action
$$S[\phi]=\int_R d(x) {\mathscr L}$$
Then one tries to find the form of $\phi(x)$ that makes the value of $S$ be an extremum (either maximum or minimum). To solve this problem one applies a "small" perturbation to $x$ and $\phi$ to see how the value of $S$ is modified. Thus by "taking the limit" to smaller and smaller perturbations results in an infinitesimal change $\delta S$ which is set to zero.
Now there are several ways to implement the "small" perturbation. One is to construct the homotopy between two functions that contains the solution. This means that we have a family of functions $\phi(x;\epsilon)$ parametrized continuously by $\epsilon$. However, one can argue that the homotopy cannot contain all possible variations because it only contains the "intermediate" functions of the deformation of the initial function to the final one.
Another way, which is contained in most physics textbooks, is to consider the transformations:
$$x^\mu\to x'^\mu=x^\mu+\delta x^\mu$$
$$\phi(x)\to \phi'(x)=\phi(x)+\delta \phi(x)$$
Where both $\delta x^\mu$ and $\delta \phi(x)$ are arbitrary small functions of $x$. Now, the lagrangian density also depends on $\partial_\mu \phi(x)$ so it is straightforward to take another small function, say $\delta \partial_\mu\phi(x)$, and consider
$$\partial_\mu \phi(x) \to \partial_\mu \phi'(x) = \partial_\mu \phi(x)+ \delta\partial_\mu \phi(x)$$
However, taking the derivative of the fourth equation gives
$$\partial_\mu \phi(x)\to \partial_\mu \phi'(x)=\partial_\mu \phi(x)+\partial_\mu (\delta \phi(x))$$
Then it is tempting to identify
$$\delta \partial_\mu\phi(x)=\partial_\mu (\delta \phi(x))$$
But here is the question: how can we guarantee that the identification is correct? i.e. that $\partial_\mu (\delta \phi(x))$ is small.
For example I can think of a variation of the kind
$$\delta \phi(x)=\epsilon \sin\left(\frac{1}{x-a}\right)$$
where $\epsilon$ is a small number and $a$ a constant. Then obviously even when $\delta \phi(x)$ is small,
$$\partial_\mu (\delta \phi(x))=-\frac{\epsilon}{(x-a)^2}\cos\left(\frac{1}{x-a}\right)$$
so we cannot guarantee that this variation is small close to $a$.

REPLY [0 votes]: Let us for simplicity discuss this in the context of point mechanics with variables $q^i(t)$ [rather than field theory with variables $\phi^{\alpha}({\bf x},t)$].
We have the following short comments to the question (v1):

One is not necessarily looking for an extremal (=minimal or maximal) configurations. We are looking for stationary configurations.
When deriving the Euler-Lagrange equations, one doesn't make horizontal variation $\delta t=\ldots$. Only vertical variations $\delta q^i=\ldots$
(Horizontal variations, on the other hand, are used in the context of (off-shell) symmetry of the action, cf. Noether's Theorem.)
Let us consider OP's example. By redefining time $t\to t+a$, we may assume that $a=0$. Then OP's example reads
$$\delta q(t)~=~\epsilon \sin\frac{1}{t}.$$
Now the Lagrangian is a function $L(q,\dot{q},t)$. The action $S[q]$ is therefore a priori only well-defined for differential$^1$ paths $q$.
The variation $\delta S$ is by definition $S[q+\delta q] - S[q]$. We must therefore demand that $q+\delta q$ is also a differential path, and hence the variation $\delta q$ is a differential path. This means that the problematic instant $t=0$ cannot belong to the physical time domain $[t_i,t_f]$, and thus OP's example is not a problem.

--
$^1$ Let us ignore for simplicity that it is possible to extend the definition of $S[q]$ to include e.g. continuous, piecewise differentiable paths $q$, etc.


TITLE: Meaning of numerals in partial differential equation notation
QUESTION [2 upvotes]: Could someone please explain this notation for a partial differential equation?

The example is from encyclopedia of mathematics.
I'm familiar with the notation $u_x=\frac{\delta{u}}{\delta{x}}$.
But I do not understand what the numeral 4 represents in $u_{x^4}$.
Is it the fourth derivate perhaps?
This type of notation is not explained on the wikipedia page for PDE notation.

REPLY [2 votes]: It means the fourth derivative with respect to the same  variable. It is written like that just to avoid long indices. For example :
$$u_{x^4} = u_{xxxx}, \; u_{y^4} = u_{yyyy}, \; u_{z^4} = u_{zzzz}$$


TITLE: Very basic special relativity (relative velocities)
QUESTION [1 upvotes]: My question involves broadly why calculating different (Einstein) relative velocities give different answers:
Say we have car 1 traveling in front of car 2. Car 1 goes at velocity $3c/4$, while car 2 goes at velocity $c/2$, both relative to the ground. Now, car 2 launches a projectile at car 1, with velocity $c/3$ relative to car 2. The question is, whether this projectile will reach car 1.
This is a relative velocity with special relativity problem, though I  am very confused why different approaches give different conclusions:
I. Compute $v_{p1}$, or the relative velocity of the projectile relative to car 1.
Using the formula for relative velocities with Einstein correction, we can write
$$v_{p1}=\frac{v_{p2}+v_{21}}{1+v_{p2}\cdot v_{21}/c^2}.$$ Plug in the numbers (classical relative velocities), we have $v_{p2}=c/3$, $v_{21}=-c/4$, so numerator is positive, (denominator clearly also positive), so $v_{p1}>0$, in other words the projectile hits car 1.
II. Compute $v_{pg}$, or the velocity of the projectile relative to the ground. Following the above formalism, $$v_{pg}=\frac{v_{p1}+v_{1g}}{1+v_{p1}\cdot v_{1g}/c^2}.$$ Here, we have $v_{p1}=c/3$ and $v_{1g}=c/2$ as givens in the problem. Evaluating the whole fraction, we have $v_{pg}=5c/7$, which is less than the velocity of car 1 relative to the ground $3c/4$, so projectile never hits car 1.
I just can't see what's wrong with either approach, though clearly the results are contradictory... Some guidance would be much appreciated!

REPLY [3 votes]: UPDATE:
I had a chance to look at your problem more carefully.

As @BillN said, there are some errors in your velocities.
Part of the problem is that velocities are not additive in special relativity.
I think your second equation should have labels $v_{p2}$ (not $v_{p1}$) and $v_{2g}$ (not $v_{1g}$).

I'll use "A" instead of "1", and "B" instead of "2".
I've drawn a spacetime diagram [to scale] centered at the projectile launch event. I translated $A$'s worldline back to make the velocity comparisons easier.
Graphically, we see that worldline-of-$P$ has a lab-frame velocity less than that of $A$, and so worldline-$P$ will never meet worldline-$A$.
Let's do the calculation.
I have shaded in sectors that mark the given "rapidities" (the signed Minkowski angle, whose hyperbolic-tangent gives the relative velocity between the worldlines).

Unlike velocities, rapidities are additive.
Note that (for example)
$$
v_{PA}=\tanh{\theta_{PA}}\equiv\tanh(\theta_{PB}+\theta_{BA})\equiv
\frac{\tanh\theta_{PB}+\tanh\theta_{BA}}
{1+\tanh\theta_{PB}\tanh\theta_{BA}}
=\frac{ v_{PB}+v_{BA} }{1+ v_{PB}v_{BA} }
$$

To find $v_{PA}=\tanh\theta_{PA}$,
use an expression involving $\theta_{PA}$.

\begin{align}\theta_{PA}
&=\stackrel{\checkmark}{\theta_{PB}}+\stackrel{?}{\theta_{BA}}\\
&={\theta_{PB}}+(\theta_{BG}-
\theta_{AG})
=\mbox{arctanh}\displaystyle\frac{1}{3}
+\left(\mbox{arctanh}\displaystyle\frac{1}{2}
-\mbox{arctanh}\displaystyle\frac{3}{4}\right)\approx -0.0770753
\end{align}
So, $v_{PA}=\tanh\theta_{PA}=-\displaystyle\frac{1}{13} \approx -0.076923 \quad <\quad 0$. Worldline-$P$ won't meet worldline-$A$.

To find $v_{PG}=\tanh\theta_{PG}$,
use an expression involving $\theta_{PG}$.

\begin{align}\theta_{PG}
&=\theta_{PB}+\theta_{BG}\\
&=\mbox{arctanh}\displaystyle\frac{1}{3}+\mbox{arctanh}\displaystyle\frac{1}{2}=0.8958 \qquad\mbox{note: }\mbox{arctanh}\displaystyle\frac{3}{4}\approx 0.972955
\end{align}
So, $v_{PG}=\tanh\theta_{PG}= \displaystyle\frac{5}{7} \approx 0.714 \quad < \quad 0.75 $. Worldline-$P$ won't meet worldline-$A$.

One could work solely with the velocity-composition formula.
However, making reference to rapidity allows one to use aspects of Euclidean geometry that carry over into Minkwoskian geometry.

[original version of my answer]
This notation suggests "velocity addition" or "velocity composition"
$$v_{p1}=\frac{v_{p2}+v_{21}}{1+v_{p2}\cdot v_{21}/c^2}.$$
Think about walking forward on a train that is also moving forward.
What is your velocity with respect to the ground?
Here's an analogue with angles,
$$(\theta_p-\theta_1)=
(\theta_p-\theta_2)+(\theta_2-\theta_1).$$

"Relative velocity" is expressed as
$$v_{p1}=\frac{v_{p2}-v_{12}}{1-v_{p2}\cdot v_{12}/c^2},$$
Think differences from a common frame.
Think about both you and train moving forward with respect to the ground.
What is the relative velocity of you with respect to the train?
Here's an analogue with angles,
$$(\theta_p-\theta_1)=
(\theta_p-\theta_2)-(\theta_1-\theta_2).$$

REPLY [0 votes]: Your relative velocity formula is incorrect. Also, you must transform (via Lorentz) the velocity of the projectile from ref. frame 1 to ref. frame 2. It is not merely subtraction. In your second approach, the velocities $v_{p1}$ and $v_{1g}$ are incorrect.
You need to be extremely careful with negative signs and relative velocity symbols. Those are the sources of most mistakes in Lorentz transformations.


TITLE: Let $M$ be the only maximal ideal of the local ring $\Bbb{Z}_{(p)}$, show that $\Bbb{Z}_{(p)}/M$ is isomorphic to $\Bbb{Z}/(p)$.
QUESTION [1 upvotes]: Question: Let $M$ be the only maximal ideal of the local ring $\Bbb{Z}_{(p)}$, show that $\Bbb{Z}_{(p)}/M$ is isomorphic to $\Bbb{Z}/(p)$.
I have proved that $M=\{\dfrac a b\in\Bbb{Z}_{(p)}:p|a\}$ is only maximal ideal of $\Bbb{Z}_{(p)}$. So $\Bbb{Z}_{(p)}/M$ is a field. I saw somewhere that, this field is isomorphic to $\Bbb{Z}/(p)$, but the proof is not trivial. Can any one give an outline of the proof of this? Thank you.

REPLY [1 votes]: Let $S:=\mathbb{Z}\setminus (p)$. Thus, $\mathbb{Z}_{(p)}=S^{-1}\mathbb{Z}$ and $M=S^{-1}(p)$. Hence, $\mathbb{Z}_{(p)}/M= S^{-1}\mathbb{Z}/S^{-1}(p)\cong S^{-1}(\mathbb{Z}/(p))=S^{-1}\mathbb{Z}_{(p)}$. Now since the elements of $S$ are unite in the ring $\mathbb{Z}_{(p)}$ we have $S^{-1}\mathbb{Z}_{(p)}=\mathbb{Z}_{(p)}$, and so $\mathbb{Z}_{(p)}/M\cong \mathbb{Z}_{(p)}$.


TITLE: Kernel of linear operator with functions having Fourier transform supported in $[0,\infty)$
QUESTION [0 upvotes]: A bounded linear operator $ T: L^2 \to L^2$ with this properties :
1. Commutes with translation
2. Commutes with dilation
3. Has in its kernel functions $ f $ such that support $\hat {f} \subseteq [0,\infty) $
I already can prove that $T= f* \mu$ where $\mu $ is a tempered distribution.
Then $\int_{-\infty}^0\hat {f}(s)e^{2i\pi s x} ds =c Tf (x)$ where $ c $ is s constant. How to prove this ?

REPLY [0 votes]: Take the fourier transform of $Tf=f*\mu$
$\hat{Tf}=m(s)\hat{f}$ where $m(s)$ is the fourier transform of $\mu$
So $m(s)$ must be zero on the positive real line and non zero on the negative real line. Combining this with the dilation property implies the result you asked.