--- abstract: | Fluid queues are mathematical models frequently used in stochastic modelling. Their stationary distributions involve a key matrix recording the conditional probabilities of returning to an initial level from above, often known in the literature as the matrix $\Psi$. Here, we present a probabilistic interpretation of the family of algorithms known as *doubling*, which are currently the most effective algorithms for computing the return probability matrix $\Psi$. To this end, we first revisit the links described in @ram99 [@soares02] between fluid queues and Quasi-Birth-Death processes; in particular, we give new probabilistic interpretations for these connections. We generalize this framework to give a probabilistic meaning for the initial step of doubling algorithms, and include also an interpretation for the iterative step of these algorithms. Our work is the first probabilistic interpretation available for doubling algorithms.\ : doubling algorithms; stochastic fluid flows; quasi-birth-death processes; stationary distribution author: - 'Nigel Bean[^1]' - 'Giang T. Nguyen' - 'Federico Poloni[^2]' bibliography: - 'interpretation.bib' title: 'Doubling Algorithms for Stationary Distributions of Fluid Queues: A Probabilistic Interpretation' --- Introduction ============ Stochastic fluid queues are two-dimensional Markov processes frequently used for modeling real-life applications. In a fluid queue $\{X_t, \varphi_t\}_{t \geq 0}$, the *phase* $\varphi_t$ is a continuous-time Markov chain on a finite state space $\mathcal{S}$, and the *level* $X_t \in (-\infty,\infty)$ varies linearly at rate $c_{\varphi_t}$. We consider the associated regulated process $\{\overline{X}_t, \varphi_t\}_{t \geq 0}$ that has a boundary at $0$: $$\begin{aligned} \overline{X}_t := X_t - \inf_{0 \leq s \leq t} X_s. \end{aligned}$$ The joint stationary distribution of $\{\overline{X}_t, \varphi_t\}$ has been well-analyzed. Several authors independently derived this distribution using different approaches: time reversal @asmussen95, the theory of generators of Markov processes and Wiener-Hopf factorization @roger94, and partial differential equations @kk95. More recently, Ramaswami @ram99 and da Silva Soares and Latouche @soares02 obtained new representations of the stationary distribution using matrix-analytic methods. The key component for obtaining the stationary distribution is the probability matrix $\Psi$, of which each entry $\Psi_{ij}$ is the probability of the fluid returning, from above, to the initial level $x$ in phase $j$, after starting in phase $i$ and avoiding all levels below $x$. This matrix $\Psi$ is also the minimal nonnegative solution to a *nonsymmetric algebraic Riccati equation* (NARE) of the form $$\begin{aligned} \label{eqn:nare} B - A X - X D + X C X = 0. \end{aligned}$$ These probabilistic and algebraic characterizations of $\Psi$ have led to considerable efforts in developing algorithms for computing the matrix efficiently. Asmussen @asmussen95 presented three iterative schemes, while Guo @guo01 analyzed fixed-point iterations and Newton's method. Following a different path, Ramaswami @ram99 and da Silva Soares and Latouche @soares02 proved that one can approximate fluid processes using Quasi-Birth-Death (QBD) processes, thus allowing quadratically convergent algorithms originally developed for QBDs—such as Logarithmic Reduction @lr93 and Cyclic Reduction @bm09—to be used for solving for $\Psi$. Bean *et al.* @bean05 proposed First-Exit and Last-Entrance and gave probabilistic interpretations for these two algorithms, as well as for Newton's method, one of Asmussen's iterative schemes, and Logarithmic Reduction applied to the QBD version of fluid processes. Probabilistic interpretations are useful as they give an intuitive explanation of how a numerical algorithm works, which in turn allows for shorter and more elegant proofs, as well as for improvements and generalizations of the algorithm. The combination of purely linear-algebraic manipulations and probabilistic understanding has paved ways for many significant theoretical developments, as already seen for QBDs @lr99 [@blm05] and fluid queues @ram99 [@soares02; @bean05]. In this paper, we focus on a family of algorithms for solving known as *doubling*, which include the structure-preserving doubling algorithm (SDA) @glx05, <span>SDA shrink-and-shift</span> (SDA-ss) @bmp, <span>alternating-directional doubling algorithm</span> (ADDA) @wwl, and component-wise accurate doubling algorithm @NguP15. These algorithms are proven to be more computationally efficient than all the ones presented in @asmussen95 [@ram99; @guo01; @bean05; @soares02]. We give these doubling algorithms a probabilistic interpretation, which to the best of our knowledge is the first one available. In order to arrive at this probabilistic interpretation, we revisit the QBD approximations presented in @ram99 and @soares02 and give them a new, unified interpretation. Putting all three families of algorithms—those in @ram99, in @soares02, and doublings—under the same probabilistic light reveals clearly the two reasons why doubling algorithms are more efficient. First of all, they correspond to a QBD with a simpler transition structure, which allows one to reduce the number of matrix blocks that appear in each iteration. Second, they depend on two uniformization parameters instead of one, and these parameters can be chosen suitably to achieve a faster convergence rate. Thus, the aim of this work is twofold. One is to understand doubling algorithms more thoroughly from a probabilistic point of view, with an eye to possible future generalizations. The other is to make these algorithms, which were developed purely from a linear algebra perspective, more accessible to probabilists and practitioners who work on stochastic fluid flows. In Section \[sec:sda\], we describe the doubling algorithms. In Section \[sec:psi\], we present three algebraic representations for the return probability matrix $\Psi$ and their corresponding probabilistic interpretations. Based on the latter, we give in Section \[sec:rei\] three QBDs whose first downward return matrices ${\mathcal{G}}$ contain the matrix $\Psi$ as its sub-block. Two of these QBDs are directly connected to the ones introduced in @ram99 [@soares02]; the third is connected to the QBD in doubling algorithms. In Section \[sec:int\], we give probabilistic meanings for the initial starting point and iterations of doubling algorithms, and discuss their convergence through the analysis of the matrices ${\mathcal{G}}$ and ${\mathcal{R}}$ of these QBDs. Some concluding remarks on the efficiency of these algorithms are in Section \[sec:conclusion\]. Doubling algorithms {#sec:sda} =================== Consider a regulated fluid model $\{\overline{X}_t, \varphi_t\}_{t \geq 0}$, where $\varphi_t$ is a continuous-time Markov chain on a finite state space $\mathcal{S}$, $\overline{X}_t \in [0,\infty)$ and $$\begin{aligned} \frac{{\, \mathrm{d}}}{{\, \mathrm{d}}t} \overline{X}_t = \left\{ \begin{array}{ll} c_{\varphi_t} & \mbox{ for } \overline{X}_t > 0, \\ \vspace*{-0.3cm} \\ \max\{c_{\varphi_t}, 0\} & \mbox{ for } \overline{X}_t = 0. \end{array} \right. \end{aligned}$$ Without loss of generality, we assume all fluid rates to be non-zero, for any given model with zero rates we can censor out those zero-rate states without affecting the return probability matrix $\Psi$ @soares05. We define $C:= \mbox{diag}(c_i)_{i \in \mathcal{S}}$ to be the diagonal rate matrix for the level $\overline{X}_t$, and denote by $T$ the generator of the phase process $\varphi_t$. Let $\mathcal{S}_{+} := \{i \in \mathcal{S}: c_i > 0\}$, $\mathcal{S}_- := \{i \in \mathcal{S}: c_i < 0\}$, $n := |\mathcal{S}|$, $n_{+}: = |\mathcal{S}_{+}|$, and $n_{-}: = |\mathcal{S}_{-}|$. We partition the matrices $C$ and $T$ accordingly into sub-blocks $$\begin{aligned} C = \left[\begin{array}{cc} C_{+} & \\ & C_{-} \end{array} \right], \quad T = \left[\begin{array}{cc} T_{++} & T_{+-} \\ T_{-+} & T_{--} \end{array}\right]. \end{aligned}$$ It is well-established (see e.g. @roger94 [Theorem 2]) that the return probability matrix $\Psi$ is the minimal non-negative solution of the nonsymmetric algebraic Riccati equation $$C_{+}^{-1}T_{+-} + \Psi|C_{-}|^{-1}T_{--} + C_{+}^{-1}T_{++}\Psi + \Psi|C_{-}|^{-1}T_{-+}\Psi = 0. \label{eqn:Psi}$$ In addition to $\Psi$, one can consider the return probability matrix $\widehat{\Psi}$ defined analogously on the process obtained by replacing $C$ with $-C$, i.e., reversing the sign of all rates (*level-reversed* process). Similarly, this matrix $\widehat{\Psi}$ can be characterized as the minimal non-negative solution of the nonsymmetric algebraic Riccati equation $$|C_{-}|^{-1}T_{-+} + \widehat{\Psi}C_{+}^{-1}T_{++} + |C_{-}|^{-1}T_{--}\widehat{\Psi} + \widehat{\Psi} C_{+}^{-1}T_{+-} \widehat{\Psi} = 0. \label{eqn:Psihat}$$ We shall see that the doubling algorithms compute $\widehat{\Psi}$ alongside $\Psi$ without additional work. In the remainder of this section, we describe *operationally* the doubling algorithms, which are numerical methods to compute these two matrices $\Psi$ and $\widehat{\Psi}$. **Initial starting point.** Let $$\begin{aligned} \label{eqn:alphaopt} \alpha_{\mathrm{opt}}:=\min_{i\in\mathcal{S}_-} \abs*{\frac{C_{ii}}{T_{ii}}} \quad \mbox{ and } \quad \beta_{\mathrm{opt}}:=\min_{i\in\mathcal{S}_+} \abs*{\frac{C_{ii}}{T_{ii}}}.\end{aligned}$$ Next, choose two real constants $\alpha,\beta$ with $$\label{eqn:alphabeta} 0 \leq \alpha \leq \alpha_{\mathrm{opt}}, \quad 0 \leq \beta \leq \beta_{\mathrm{opt}}, \quad \text{ $\alpha$, $\beta$ not both zero},$$ and set $$\begin{aligned} Q & := {\begin{bmatrix} C_+-\alpha T_{++} & -\beta T_{+-}\\ -\alpha T_{-+} & \abs{C_-}-\beta T_{--} \end{bmatrix}}, \\ R &:={\begin{bmatrix} C_++\beta T_{++} & \alpha T_{+-}\\ \beta T_{-+} & \abs{C_-}+\alpha T_{--} \end{bmatrix}}. \end{aligned}$$ and compute $$\begin{aligned} \label{eqn:P0} \begin{bmatrix} E & G\\H & F \end{bmatrix}:=Q^{-1}R,\end{aligned}$$ with the same block sizes as above, i.e., $E\in\mathbb{R}^{n_+\times n_+}, F\in\mathbb{R}^{n_-\times n_-}, G\in\mathbb{R}^{n_+\times n_-}, H\in\mathbb{R}^{n_-\times n_+}$. **Iterations.** Define \[eqn:SDA\] $$\begin{aligned} \widehat{E} & := E(I - G H)^{-1}E, \label{eqn:SDA_Ek} \\ \widehat{F} & := F(I - HG)^{-1}F, \label{eqn:SDA_Fk} \\ \widehat{G} & := G + E(I - GH)^{-1}GF, \label{eqn:SDA_Gk} \\ \widehat{H} & := H + F(I - HG)^{-1}HE. \label{eqn:SDA_Hk} \end{aligned}$$ The algorithm replaces at each step $(E,F,G,H)$ with the matrices $(\widehat{E},\widehat{F},\widehat{G},\widehat{H})$ computed according to , repeating until convergence. More formally, the algorithm can be implemented as follows. \[H\] Choose $\alpha,\beta$ according to Compute initial $E,F,G,H$ according to $\Psi = G$ $\widehat{\Psi} = H$ We summarize here the convergence properties of this algorithm, which are described in @bmp [@ChiCGMLX09; @glx05; @wwl]. \[thm:doublingconvergence\] In Algorithm \[algo:doubling\], denoting by $E_k,F_k,G_k,H_k$ the values of the iterates at step $k$, one has: 1. $0 \leq G_0 \leq G_1 \leq G_2 \leq \dots \leq \Psi$, and $\lim_{k\to\infty} G_k = \Psi$. 2. $0 \leq H_0 \leq H_1 \leq H_2 \leq \dots \leq \widehat{\Psi}$, and $\lim_{k\to\infty} H_k = \widehat{\Psi}$. 3. If the fluid queue $\{X_t, \varphi_t\}$ is positive recurrent, then $\lim_{k\to\infty} E_k = 0$. If it is transient, then $\lim_{k\to\infty} F_k = 0$. If it is null recurrent, then both these equalities hold. 4. The convergence rate for these limits is linear if $\{X_t, \varphi_t\}$ is null recurrent, and quadratic otherwise. We speak of *doubling algorithms* in the plural because several variants have appeared in literature, differing only in the choice of the parameters $\alpha$ and $\beta$. The first one to appear, called SDA @glx05, uses $\alpha=\beta=\min(\alpha_{\mathrm{opt}},\beta_{\mathrm{opt}})$. The variant called SDA-ss @bmp uses $\alpha=0$, $\beta=\beta_{\mathrm{opt}}$. The variant called ADDA @wwl uses $\alpha=\alpha_{\mathrm{opt}}$, $\beta=\beta_{\mathrm{opt}}$, and is the most computationally efficient of the three. Our goal in the next sections is to give a probabilistic interpretation of this procedure. The Return Probability Matrix $\Psi$ {#sec:psi} ==================================== We begin by generalizing the algebraic representation and probabilistic interpretation of the return probability matrix $\Psi$ presented in da Silva Soares and Latouche @soares02, in Section \[sec:known\]. New representations of $\Psi$ are presented in Section \[sec:new\]. A known representation {#sec:known} ---------------------- For simplicity, we assume that the level process $\{X_t\}$ has unit fluid rates only, that is, $c_i = \pm 1$ for all $i \in \mathcal{S}$. This assumption is not restrictive, since a fluid model with rates $\pm 1$ can always be obtained by a suitable time rescaling, and has the same return probability matrix $\Psi$. Moreover, we assume that $X_0 = 0$ and $\varphi_0 \in \mathcal{S}_+$. Let $y$ be the time of the first transition into a phase in $\mathcal{S}_-$, which is also the level where the fluid process for the first time stops increasing and starts decreasing, by the assumption of unit rates. Hence $X_y = y$, $\varphi_y \in \mathcal{S}_-$. Let $\tau(-x) := \inf \{t \geq y: X_t = y-x\}$ be the first time the process $\{X_t\}$ returns to level $y-x$. Then, the time-changed phase process $\{\varphi_{\tau(-x)}\}_{x \geq 0}$ is also a Markov chain. Let $U$ be the $|\mathcal{S}_{-}| \times |\mathcal{S}_{-}|$ generator of the phase $\{\varphi_{\tau(-x)}\}$ of the *downward record* process $\{X_{\tau(-x)}, \varphi_{\tau(-x)}\}_{x \geq 0}$. It is known (see e.g. @soares02 [Equation (13)]) that $$\begin{aligned} \label{eqn:U} U = T_{--} +T_{-+} \Psi. \end{aligned}$$ If we condition on $y$, a standard argument gives an expression for the return probability matrix $\Psi$: $$\begin{aligned} \Psi = \int_0^\infty \exp(T_{++}y)T_{+-}\exp(Uy) {\, \mathrm{d}}y. \end{aligned}$$ In @soares02, the authors uniformized the first upward part of the path, from level $0$ to level $y$, and then the remaining part, from level $y$ returning to level $0$, both with the same rate. Here, we reproduce their approach in a more general fashion, in which there are two different uniformization rates, $\lambda$ and $\mu$. Assume that $\varphi_0 \in \mathcal{S}_{+}$. Let $\mathcal{U}_{\lambda} := \{\mathcal{U}_{\lambda}(t)\}_{t \geq 0}$ (for 'upwards') and $\mathcal{D}_{\mu} := \{\mathcal{D}_{\mu}(t)\}_{t \geq 0}$ (for 'downwards') denote two Poisson processes with rates $\lambda$ and $\mu$, respectively. Consider a uniformization of the phase process $\{\varphi_t\}$ using $\mathcal{U}_{\lambda}$. Let $k +1$, $k \geq 0$, be the number of steps it takes until the uniformized process first switches from $\mathcal{S}_{+}$ to $\mathcal{S}_{-}$, at time and level $y$. Thus, there are $k$ events in the time interval $[0,y)$ and an event at time $y$. We use the process $\mathcal{D}_{\mu}$ for uniformizing with rate $\mu$ the downward record process $\{\varphi_{\tau(-x)}\}$. Let $n \geq 0$ be the number of events of $\mathcal{D}_{\mu}$ in $[0,y]$, i.e., until the downward record process reaches level $0$. Summing on $k$ and $n$, we obtain $$\begin{aligned} \label{eqn:Psids} \Psi = \int_0^\infty \left[\sum_{k=0}^\infty {e}^{-\lambda y}\frac{(\lambda y)^k}{k!} P_{\lambda++}^k\right] \lambda P_{\lambda+-}\left[\sum_{n=0}^\infty {e}^{-\mu y}\frac{(\mu y)^n}{n!} V^n_{\mu}\right] {\, \mathrm{d}}y,\end{aligned}$$ with $$\begin{aligned} \label{eqn:Plambda} P_\lambda & := I + \lambda^{-1}T, \\ \label{eqn:Vmu} V_{\mu} & := I + \mu^{-1}U. \end{aligned}$$ Swapping the order of summation and integration gives $$\begin{aligned} \label{latouchesum} \Psi & = \sum_{k,n=0}^{\infty} \gamma_{k,n} P_{\lambda++}^kP_{\lambda+-}V_\mu^n, \\ \intertext{where} \label{eqn:gammakn} \gamma_{k,n} & := \frac{(k+n)!}{k!n!}\frac{\lambda^{k+1}\mu^n}{(\lambda+\mu)^{k+n+1}}. \end{aligned}$$ Figure \[f:times\] gives a sample path of $\{\overline{X}_t\}$, with $k = 3$ and $n = 4$. ![A sample path of $\{\overline{X}_t\}$, with $k = 3$ events $\bullet$ in the time interval $[0,y]$, an event $\diamondsuit$ at time $y$, and $n = 4$ events $\circ$ in the censored time it takes for the downward record process to decrease from $y$ to $0$.<span data-label="f:times"></span>](sample-kn.pdf "fig:") (-265,115)<span>(0,0)\[l\]<span>$y$</span></span> (-265,40)<span>(0,0)\[l\]<span>$0$</span></span> (-3,40)<span>(0,0)\[l\]<span>$t$</span></span> (-259,152)<span>(0,0)\[l\]<span>$\overline{X}_t$</span></span> Da Silva Soares and Latouche @soares02 gave a probabilistic interpretation for the sum in . sample paths of the uniformized processes are decomposed into disjoint sets $\mathcal{A}_{k,n}$; the terms $P_{\lambda++}^kP_{\lambda+-}$ and $V_{\mu}^n$ account for the transitions in the two uniformized processes, while the coefficient $\gamma_{k,n}$ gives the probability to observe $k$ and $n$ events, respectively. To explain the formula , consider the two Poisson process $\mathcal{U}_\lambda$ and $\mathcal{D}_\mu$: they are two independent Poisson processes which take place on two different intervals of time of length $y$: the first is the real time for the fluid process, on its way up to reaching the level $y$ for the first time; the second is the censored time of the downward record process, returning to level $0$ after starting at level $y$. Suppose instead that these two processes are superimposed onto the same time interval $[0,y]$, as in Figure \[f:sum0-dots\]. ![The processes $\mathcal{U}_\lambda$ and $\mathcal{D}_\mu$, superimposed on the same interval $[0,y]$.<span data-label="f:sum0-dots"></span>](superimposed.pdf "fig:") (-180,48)<span>(0,0)\[l\]<span>$u_0$</span></span> (-149,48)<span>(0,0)\[l\]<span>$u_1$</span></span> (-114,48)<span>(0,0)\[l\]<span>$u_2$</span></span> (-88,48)<span>(0,0)\[l\]<span>$u_3$</span></span> (-9,48)<span>(0,0)\[l\]<span>$u_4$</span></span> (-188,36)<span>(0,0)\[l\]<span>$0$</span></span> (2,36)<span>(0,0)\[l\]<span>$y$</span></span> (-188,4)<span>(0,0)\[l\]<span>$0$</span></span> (2,4)<span>(0,0)\[l\]<span>$y$</span></span> Then, $\gamma_{k,n}$ is the probability of observing $n$ events of the second process before the $k+1$st event of the first one. Since the probability of observing an event of the first process before one of the second is $\frac{\lambda}{\lambda+\mu}$, then $\gamma_{k,n}$ is the probability mass function of a negative binomial distribution with $k+1$ successes and probability $\frac{\lambda}{\lambda+\mu}$, which is exactly . New representations {#sec:new} ------------------- Using probabilistic arguments, we consider three different representations for the matrix $\Psi$, each involving only one summation variable. Intuitively, Theorem \[theo:sums\] presents new ways of categorizing returning-to-zero sample paths of a fluid process, relying on two Poisson processes with rates $\lambda$ and $\mu$, respectively. They are the crucial foundation of our new interpretations for the links between QBDs and fluid queues, described in Section \[sec:rei\]. \[theo:sums\] $$\begin{aligned} \label{sum1} \Psi & = \sum_{k=0}^{\infty} P_{\lambda++}^k P_{\lambda+-} \left(I- \lambda^{-1} U\right)^{-k-1} \\ \label{sum2} & = \sum_{n=0}^{\infty} \left(I- \mu^{-1}T_{++}\right)^{-n-1}P_{\mu+-}V_\mu^n, \\ & = \sum_{m=0}^{\infty} Q^m\left(I-\mu^{-1}T_{++}\right)^{-1} \left(P_{\lambda+-}W + P_{\mu+-}\right)W^m, \label{sum3} \end{aligned}$$ where $$\begin{aligned} \label{eqn:W} Q:= \left(I-\mu^{-1}T_{++}\right)^{-1}\left(I+\lambda^{-1}T_{++}\right), \quad W := \left(I + \mu^{-1}U\right)\left(I- \lambda^{-1}U\right)^{-1}, \end{aligned}$$ and $P_{\mu} := I + \mu^{-1}T$, analogously with $P_\lambda$. The spirit of the proof is as follows. We show that - The first representation arises from uniformizing the fluid process on the way up to $y$ with rate $\lambda$. The Poisson process in the uniformization marks a sequence of exponential intervals of rate $\lambda$. We then observe the downward record process on the way down at these exponential epochs. - The second representation comes from the opposite: uniformizing the downward record process with rate $\mu$, and observing the initial upward path at these exponential intervals. - The third one , which leads to the QBD underlying the doubling algorithms, is a mixture of the previous two: alternating between a uniformization step and an observation, all the way up for the level process and then all the way down for the downward record process. The intervals at which we take actions—observing or uniformizing—are created by carefully superimposing the two Poisson processes. **First representation.** To show Equality , we denote by $\{u_i\}_{i = 1, \ldots, k} $ the sequence of time epochs associated with the $k$ Poisson events of $\mathcal{U}_{\lambda}$ in $(0,y)$, where $0 < u_1 < \cdots < u_k < y$, and define $u_0 := 0$ and $u_{k + 1} := y$. Next, let $m_i$, $i = 1, \ldots, k+1$, be the number of events of $\mathcal{D}_{\mu}$ during $[u_{i - 1}, u_i)$. Figure \[f:sum1-dots\] gives a sample path with $k = 3$. ![A sample path with $k = 3$ uniformization events $\bullet$ of $\mathcal{U}_{\lambda}$ in the time interval $[0,y)$, $m_1 = 1$, $m_2 = 2,$ $m_3 = 0$, and $m_4 = 1$.<span data-label="f:sum1-dots"></span>](sum1-dots.pdf "fig:") (-180,48)<span>(0,0)\[l\]<span>$u_0$</span></span> (-149,48)<span>(0,0)\[l\]<span>$u_1$</span></span> (-114,48)<span>(0,0)\[l\]<span>$u_2$</span></span> (-88,48)<span>(0,0)\[l\]<span>$u_3$</span></span> (-9,48)<span>(0,0)\[l\]<span>$u_4$</span></span> (-188,36)<span>(0,0)\[l\]<span>$0$</span></span> (2,36)<span>(0,0)\[l\]<span>$y$</span></span> (-188,4)<span>(0,0)\[l\]<span>$0$</span></span> (2,4)<span>(0,0)\[l\]<span>$y$</span></span> During the first ascent, at each event $u_i$, $i = 1, \ldots, k$, there is a uniformization step $P_{\lambda++}$, which leads to the term $P_{\lambda++}^{k}$ in the sum . At time $y$, there is a uniformization step associated with a transition from $\mathcal{S}_+$ to $\mathcal{S}_-$, which gives the term $P_{\lambda+-}$. Recall that $V_\mu := 1 + \mu^{-1} U$ is the probability transition matrix of the uniformized downward record phase process $\left\{\varphi_{\tau(-x)}\right\}$, and transitions according to $V_{\mu}$ happen at the events of $\mathcal{D}_\mu$. By the same argument used to justify , the probability that there are $m_i$ events of $\mathcal{D}_\mu$ in $[u_{i-1},u_i)$ is $\mu^{m_i}\lambda / (\lambda+\mu)^{m_i+1}$. Let $P_{i}$ be the matrix with elements $ [P_i]_{jk} := \mathds{P}[{\textcolor{black}{\varphi_{\tau( - u_{i})}}} = k | {\textcolor{black}{\varphi_{\tau( - u_{i - 1})}}} = j]$ for $j, k \in \mathcal{S}_{-}.$ Then, $$\begin{aligned} \label{eqn:Pd} P_i & = \sum_{m_i = 0}^{\infty} \frac{\mu^{m_i} \lambda }{(\lambda + \mu)^{m_i + 1}}V_{\mu}^{m_i} = \frac{\lambda}{\lambda + \mu} \left(I - \frac{\mu}{\lambda + \mu} V_{\mu} \right)^{-1} = \left(I - \frac{1}{\lambda}U\right)^{-1}. \end{aligned}$$ Since there are intervals $[u_{i - 1}, u_{i})$, $i = 1, \ldots, k + 1$, this explains the term $(I - \lambda^{-1}U)^{{\textcolor{black}{-k - 1}}}$ in, and completes the proof of, . Note that as $\left(I - {\lambda}^{-1}U\right)^{-1} = \int_0^{\infty} \lambda {e}^{-\lambda x} {e}^{Ux} {\, \mathrm{d}}x$, the matrix $P_i$ contains the conditional probabilities of the downward record process observed at exponential intervals with rate $\lambda$. Thus, the term $(I - \lambda^{-1}U)^{-k - 1}$ can also be seen directly as arising from observing the downward record process at the $(k + 1)$ exponentially distributed intervals marked by the epochs $u_i$, and we could have skipped the construction of $\mathcal{D}_{\mu}$ altogether. However, we need this process to explain the following representations, and both $\mathcal{U}_{\lambda}$ and $\mathcal{D}_{\mu}$ to explain the third, so we maintain both processes throughout the proof. **Second Representation.** Equality comes from grouping the sample paths in a different manner to that in the first representation: according to the number of events, $n$, of the process $\mathcal{D}_{\mu}$ in $[0,y]$. This provides the $n$ uniformizing steps of the downward record process, represented by the term $V_{\mu}^n$ in the sum . Let $\{d_i\}_{i = 1, \ldots, n}$ be the associated sequence of time epochs, and define $d_0 := 0$. ![A sample path with $n = 4$ uniformization events $\circ$ of $\mathcal{D}_{\mu}$.<span data-label="f:sum2-dots"></span>](sum2-dots.pdf "fig:") (-166,-7)<span>(0,0)\[l\]<span>$d_1$</span></span> (-135,-7)<span>(0,0)\[l\]<span>$d_2$</span></span> (-122,-7)<span>(0,0)\[l\]<span>$d_3$</span></span> (-62,-7)<span>(0,0)\[l\]<span>$d_4$</span></span> (-188,36)<span>(0,0)\[l\]<span>$0$</span></span> (2,36)<span>(0,0)\[l\]<span>$y$</span></span> (-188,4)<span>(0,0)\[l\]<span>$0$</span></span> (2,4)<span>(0,0)\[l\]<span>$y$</span></span> By arguments analogous to the ones used for the first representation, the initial upward journey from level $0$ to level $y$ we observe the phase process $\{\varphi_t\}$ at the end of each exponential interval $[d_{i}, d_{i + 1})$, for $i = 0, \ldots, {\textcolor{black}{n - 1}}$. The last interval, $[d_k, y]$, is not an exponential interval with parameter $\mu$, $$\begin{aligned} \sum_{s = 0}^{\infty} \left(\frac{\lambda}{\lambda + \mu}\right)^{s + 1}P_{\lambda ++}^{s} P_{\lambda +-} &= \frac{\lambda}{\lambda+\mu}\left(I- \frac{\lambda}{\lambda+\mu} P_{\lambda++}\right)^{-1} \lambda^{-1} T_{+-} \nonumber\\ &= \left((\lambda+\mu)I - \lambda P_{\lambda++}\right)^{-1} T_{+-} \nonumber\\ &= \left(I - \mu^{-1}T_{++}\right)^{-1}\mu^{-1}T_{+-} \label{endcount} \end{aligned}$$ **Third Representation.** To arrive at , we superimpose $\mathcal{U}_{\lambda}$ and $\mathcal{D}_{\mu}$ and define a new sequence based on $\{u_i\}_{{\textcolor{black}{i \geq 0}}}$ and $\{d_i\}_{{\textcolor{black}{i \geq 0}}}$ as follows $$\begin{aligned} \label{eqn:c0} c_0 & = 0, \\ \label{eqn:codd} c_{2i + 1} & = \min\{d_i: d_i > c_{2i}\}, \\ \label{eqn:ceven} c_{2i + 2} & = \min\{u_i: u_i > c_{2i+1}\} \quad \mbox{for } i \geq 0. \end{aligned}$$ For $c_{2i + 1} < y$, each interval $[c_{2i}, c_{2i + 1}]$ contains an arbitrary number of events of $\mathcal{U}_\lambda$ and exactly one event of $\mathcal{D}_{\mu}$, which lies at its right endpoint, and thus the interval has an exponential length with parameter $\mu$. On the other hand, for $c_{2i + 2} < y$, each interval $[c_{2i +1}, c_{2i + 2}]$ contains an arbitrary number of events of $\mathcal{D}_\mu$ and exactly one event of $\mathcal{U}_{\lambda}$, which lies at its right endpoint, and thus its length is exponentially distributed with parameter $\lambda$. Let $N$ be the number of events $c_j$ in $[0,y)$. There are two possibilities: $N$ is even , and $N$ is odd. We separate the summation in into two sums: $$\begin{aligned} \label{eqn:sum3sep} \Psi & = \sum_{m=0}^{\infty} Q^m\left(I-\mu^{-1}T_{++}\right)^{-1} P_{\lambda+-}W^{m + 1} \nonumber \\ & \;\; + \sum_{m=0}^{\infty} Q^m\left(I-\mu^{-1}T_{++}\right)^{-1} P_{\mu+-}W^m I, \end{aligned}$$ and show that the first sum comes from odd values of $N$, and the second from even ones. We have added an identity matrix as the final factor of the second sum; the reason will be explained later. Suppose that $N = 2m + 1$ for some integer $m \geq 0$. Figure \[f:dots-odd\] gives a sample path for $N = 5$. ![A sample path of $\mathcal{U}_{\lambda}$ and $\mathcal{D}_{\mu}$, where $N = 5$.<span data-label="f:dots-odd"></span>](dots-odd.pdf "fig:") (1,4)<span>(0,0)\[l\]<span>$y$</span></span> (-186,4)<span>(0,0)\[l\]<span>$0$</span></span> (1,34)<span>(0,0)\[l\]<span>$y$</span></span> (-186,34)<span>(0,0)\[l\]<span>$0$</span></span> (1,64)<span>(0,0)\[l\]<span>$y$</span></span> (-186,64)<span>(0,0)\[l\]<span>$0$</span></span> (-165,45)<span>(0,0)\[l\]<span>$d_1$</span></span> (-165,-5)<span>(0,0)\[l\]<span>$c_1$</span></span> (-151,74)<span>(0,0)\[l\]<span>$u_1$</span></span> (-151,-5)<span>(0,0)\[l\]<span>$c_2$</span></span> (-133,45)<span>(0,0)\[l\]<span>$d_2$</span></span> (-133,-5)<span>(0,0)\[l\]<span>$c_3$</span></span> (-112,74)<span>(0,0)\[l\]<span>$u_2$</span></span> (-86,74)<span>(0,0)\[l\]<span>$u_3$</span></span> (-111,-5)<span>(0,0)\[l\]<span>$c_4$</span></span> (-62,45)<span>(0,0)\[l\]<span>$d_4$</span></span> (-62,-5)<span>(0,0)\[l\]<span>$c_5$</span></span> (-172,12)<span>(0,0)\[l\]<span>$\mu$</span></span> (-158,14)<span>(0,0)\[l\]<span>$\lambda$</span></span> (-140,12)<span>(0,0)\[l\]<span>$\mu$</span></span> (-120,14)<span>(0,0)\[l\]<span>$\lambda$</span></span> (-84,12)<span>(0,0)\[l\]<span>$\mu$</span></span> (-34,14)<span>(0,0)\[l\]<span>$\lambda$</span></span> Let $c_{2m + 2} := y$, then the sequence $\{c_i\}_{i = 0, \ldots, 2m + 2}$ mark $(2m + 2)$ exponentially distributed intervals, with rates alternating between $\mu$ and $\lambda$, starting with $\mu$ and ending with $\lambda$. The last interval $[c_{N}, y]$ is exponential with rate $\lambda$ because it contains exactly one event of $\mathcal{U}_{\lambda}$, at time $y$. During the upward path to $y$, for the first $(2m + 1)$ intervals, we alternate between - observing the fluid process at the end of an interval exponentially distributed with rate $\mu$—represented by $(I - \mu^{-1}T_{++})^{-1}$, and - doing a uniformization step at the end of an interval exponentially distributed with rate $\lambda$—represented by $(I + \lambda^{-1}T_{++}) = P_{\lambda++}$. This alternation leads to the product $Q^m\left(I-\mu^{-1}T_{++}\right)^{-1}$ in the sum . Then, at $y$ by definition there is a uniformization step with a switch from the upward direction to downward for the fluid $\{\overline{X}_t\}$, which gives rise to the term $P_{\lambda+-}$. On the other hand, during the time it takes for the downward process to decrease from $y$ to $0$, we alternate between observing the process at the end of an exponential interval $[c_i, c_{i + 1})$, represented by $(I - \lambda^{-1}U)^{-1}$, and doing a uniformization step with $(I + \mu^{-1}U)=V_{\mu}$. This gives the factor $W^{m + 1}$. Thus, the case of $N$ being odd explains the first summation in . Now, suppose $N = 2m$ for some integer $m \geq 0$. The sequence $\{c_i\}_{i =0,\dots,2m}$ mark exponential intervals, with rates alternating between $\mu$ and $\lambda$. Figure \[f:dots-even\] gives a sample path for $N = 4$ and $r = 2$. ![A sample path of $\mathcal{U}_{\lambda}$ and $\mathcal{D}_{\mu}$, where $N = 4$ and $r = 2$.<span data-label="f:dots-even"></span>](dots-even.pdf "fig:") (1,4)<span>(0,0)\[l\]<span>$y$</span></span> (-186,4)<span>(0,0)\[l\]<span>$0$</span></span> (1,34)<span>(0,0)\[l\]<span>$y$</span></span> (-186,34)<span>(0,0)\[l\]<span>$0$</span></span> (1,64)<span>(0,0)\[l\]<span>$y$</span></span> (-186,64)<span>(0,0)\[l\]<span>$0$</span></span> (-165,45)<span>(0,0)\[l\]<span>$d_1$</span></span> (-165,-5)<span>(0,0)\[l\]<span>$c_1$</span></span> (-151,74)<span>(0,0)\[l\]<span>$u_1$</span></span> (-151,-5)<span>(0,0)\[l\]<span>$c_2$</span></span> (-133,45)<span>(0,0)\[l\]<span>$d_2$</span></span> (-133,-5)<span>(0,0)\[l\]<span>$c_3$</span></span> (-112,74)<span>(0,0)\[l\]<span>$u_2$</span></span> (-86,74)<span>(0,0)\[l\]<span>$u_3$</span></span> (-111,-5)<span>(0,0)\[l\]<span>$c_4$</span></span> (-172,12)<span>(0,0)\[l\]<span>$\mu$</span></span> (-158,14)<span>(0,0)\[l\]<span>$\lambda$</span></span> (-140,12)<span>(0,0)\[l\]<span>$\mu$</span></span> (-120,14)<span>(0,0)\[l\]<span>$\lambda$</span></span> Similar to when $N$ is odd, we alternate between observing the fluid process at the end of an exponential interval and doing a uniformization step, contributing a factor $Q^m = \left((I - \mu^{-1}T_{++})^{-1}(I + \lambda^{-1}T_{++})\right)^{m}$. The last interval of the upward path, $[c_{2m}, y]$, contributes a factor $(I - \mu^{-1}T_{++})^{-1}P_{\mu + -}$, by the same computation as in . Then, for the downward record process we also alternate between observing and uniformizing for the first $2m$ intervals, which leads to $W^{m}$. We need an additional factor to account for phase changes in the downward processes between time $c_{2m}$ and time $y$: however, there are no further events of $\mathcal{D}_\mu$ after the one at time $c_{2m}$; hence the downward uniformized process makes no transitions in $[c_{2m},y]$, and the missing factor is simply the identity matrix. Connections between QBDs and Fluid Queues {#sec:rei} ========================================= Recall that a discrete-time Quasi-Birth-Death process $\{Y_n, \kappa_n\}_{n \geq 0}$ is a two-dimensional Markov process, where the phase $\{\kappa_n\}$ is a Markov chain on a finite state space $\mathcal{M}$, the level $Y_n \in \mathds{Z}$ evolves between adjacent levels according to three transition probabilities, $L_-, L_0, L_+$, as follows: $$\begin{aligned} \mathds{P}[Y_n = k - 1, \kappa_{n} = j \mid Y_{n - 1} = k, \kappa_{n - 1} = i] & = [L_-]_{ij}, \\ \mathds{P}[Y_n = k + 1, \kappa_{n} = j \mid Y_{n - 1} = k, \kappa_{n - 1} = i] & = [L_+]_{ij}, \\ \mathds{P}[Y_n = k, \kappa_{n} = j \mid Y_{n - 1} = k, \kappa_{n - 1} = i] & = [L_{0}]_{ij}. \end{aligned}$$ Let $\theta(s) := \inf\{n > 0: Y_n = s\}$ be the first time the QBD hits level $s$. A key matrix of interest for QBDs is the so-called *first downward return* matrix ${\mathcal{G}}$, whose elements $$\begin{aligned} {\mathcal{G}}_{ij} := \mathds{P}\left[\kappa_{\theta(k - 1)} = j,\, \theta(k - 1) < \infty \mid Y_{0} = k,\, \kappa_0 = i\right] \end{aligned}$$ are the probabilities of returning to a level below the initial starting level $k$. For convenience, we refer to this matrix as the ${\mathcal{G}}$-matrix. the phase process takes values in $\mathcal{S} = \mathcal{S}_{+} \cup \mathcal{S}_-$, the same state space as that of the phase process $\varphi_t$ of the fluid model $\{\overline{X}_t, \varphi_t\}$, and we partition the transition matrices between QBD levels into sub-blocks corresponding to states in $\mathcal{S}_+$ and $\mathcal{S}_-$. In this paper, two Quasi-Birth-Death processes are said to be *${\mathcal{G}}$-equivalent* if they share the same ${\mathcal{G}}$-matrix. First, we construct in Section \[subsec:newQBDs\] three Quasi-Birth-Death processes whose ${\mathcal{G}}$-matrices contain the matrix $\Psi$ as one of its blocks, based directly on the new . Then, we show in Section \[subsec:newerQBDs\] that the aforementioned QBDs are respectively ${\mathcal{G}}$-equivalent to three other processes. In particular, the first two QBDs are ${\mathcal{G}}$-equivalent to the QBD constructed in Ramaswami @AhnR03 [Theorem 16] and in da Silva Soares and Latouche @soares02 [Eqn. (17)], respectively. The third QBD—which will be easily seen to reduce to the first QBD, when $\mu \rightarrow \infty$, or to the second QBD, when $\lambda \rightarrow \infty$, and is thus the most general form of the three QBDs—is the underlying QBD of the doubling algorithms. QBDs constructed from new representations of $\Psi$ {#subsec:newQBDs} --------------------------------------------------- \[lem:firstrep\] Consider a Quasi-Birth-Death process $\{Y^{A}_n, \kappa^{A}_n\}_{n \geq 0}$ with the following transition probability matrices: $$\begin{aligned} A_{-1} := \left[\begin{array}{cc} 0 & 0 \\ 0 & \left(I - \lambda^{-1}U\right)^{-1} \end{array} \right], \; A_0 := \left[\begin{array}{cc} 0 & P_{\lambda +-} \\ 0 & 0 \end{array}\right], \; A_1 := \left[\begin{array}{cc} P_{\lambda ++} & 0 \\ 0 & 0 \end{array} \right]. \end{aligned}$$ Then, the ${\mathcal{G}}$-matrix of this QBD is given by $$\begin{aligned} \label{eqn:GA-Ram} {\mathcal{G}}_{A} & =\begin{bmatrix} 0 & \Psi\\ 0 & \left(I- \lambda^{-1}U\right)^{-1} \end{bmatrix}, \end{aligned}$$ where $\Psi$ is the minimal nonnegative solution to $\eqref{eqn:Psi}$, and the generator $U$ is given by . Note that this QBD has a simple dynamic whose paths mimic directly the sum in : starting from a phase in $ \mathcal{S}_{+}$ and level $Y^A_0 = 1$, the process - stays in $\mathcal{S}_{+}$ for a certain number $k \geq 0$ of steps, each time going up one level and making a transition with $P_{\lambda ++}$, which means $Y^A_k = k+1$; - then moves to $\mathcal{S}_{-}$ at the same level with transition matrix $P_{\lambda +-}$, hence $Y^{A}_{k+1} = k+1$; - once having reached $\mathcal{S}_{-}$, the process cannot leave this set of states, and can only go down one level at each step, with stochastic transition matrix $\left(I - \lambda^{-1}U\right)^{-1}$, until it reaches level $0$ after $k+1$ further transitions. Thus, the first passage probability matrix to a lower level, starting from a state in $\mathcal{S}_{+}$, is $\sum_{k \geq 0} P_{\lambda ++}^{k} P_{+-} \left(I - \lambda^{-1}U\right)^{-k - 1}$, which equals $\Psi$ by . Starting from a state in $\mathcal{S}_{-}$, the probability of going to a level lower than the initial one is $\left(I - \lambda^{-1}U\right)^{-1}$, which completes the proof. \[lem:secondrep\] Consider a Quasi-Birth-Death process $\{Y_n^{B}, \kappa_n^{B}\}_{n \geq 0}$ with the transition matrices $$\begin{aligned} B_{-1} & := \left[\begin{array}{cc} 0 & \left(I - \mu^{-1}T_{++}\right)^{-1} P_{\mu +-} \\ 0 & V_{\mu} \end{array} \right], \; B_{0} := 0, \\ B_{1} & := \left[\begin{array}{cc} \left(I - \mu^{-1}T_{++}\right)^{-1} & 0 \\ 0 & 0 \end{array} \right]. \end{aligned}$$ Then, the ${\mathcal{G}}$-matrix of this QBD is given by $$\begin{aligned} \label{eqn:GB-Guy} {\mathcal{G}}_B = \begin{bmatrix} 0 & \Psi\\ 0 & V_{\mu} \end{bmatrix},\end{aligned}$$ where $\Psi$ is the minimal nonnegative solution to , and the transition probability matrix $V_{\mu}$ is given by . Similar to the QBD in Lemma \[lem:firstrep\], the QBD here has a simple dynamic, whose paths mimic directly the sum in . Starting with $\kappa_0^{B} \in \mathcal{S}_{+}$ and $Y_{0}^{B} = 1$, the process - stays in a state in $\mathcal{S}_{+}$ for a certain number $n \geq 0$ of steps, each with probability matrix $(I - \mu^{-1}T_{++})^{-1}$, which means $Y_{n}^{B} = n + 1$; - then moves to a state in $\mathcal{S}_{-}$ and goes down a level (and hence $Y_{n + 1}^{B} = n$), according to $\left(I - \mu^{-1}T_{++}\right)^{-1} P_{\mu +-}$; - from now on, the process stays in $\mathcal{S}_{-}$, going down one level with stochastic transition matrix $V_{\mu}$ at each time step and reaching level $0$ after $n$ further transitions. Thus, the first passage probability matrix to a lower level, starting from a state in $\mathcal{S}_{+}$, is $\sum_{n \geq 0} \left(I - \mu^{-1}T_{++}\right)^{-n - 1}P_{\mu +-} V_{\mu}^n$, which is $\Psi$ by . Starting from a state in $\mathcal{S}_{-}$, the probability of going to a level lower than the initial one is $V_{\mu}$, which completes the proof. \[lem:thirdrep\] Consider a Quasi-Birth-Death process $\{Y_n^{C}, \kappa_n^{C}\}_{n \geq 0}$ with the transition matrices $$\begin{aligned} C_{-1} & := \left[\begin{array}{cc} 0 & {\left(I - \mu^{-1} T_{++}\right)^{-1}P_{\mu {+-}}} \\ 0 & W \end{array}\right], \; C_{0} := \left[\begin{array}{cc} 0 & (I - \mu^{-1}T_{++})^{-1}P_{\lambda +-} \\ 0 & 0 \end{array} \right], \\ C_{1} & := \left[\begin{array}{cc} \left(I - \mu^{-1}T_{++}\right)^{-1}P_{\lambda ++} & 0 \\ 0 & 0 \end{array} \right]. \end{aligned}$$ Then, its ${\mathcal{G}}$-matrix is given by $$\begin{aligned} \label{eqn:GC} {\mathcal{G}}_C = \begin{bmatrix} 0 & \Psi\\ 0 & W \end{bmatrix},\end{aligned}$$ where $W$ is defined in $\eqref{eqn:W}$. The QBD $\{Y_n^{C}, \kappa_n^{C}\}_{n \geq 0}$ has sample paths that mimic the dynamics of the sum . Starting from $\mathcal{S}_{+}$ and level $1$, the process - stays in a state in $\mathcal{S}_+$ for a certain number $m\geq 0$ of steps, each with probability matrix $\left(I - \mu^{-1}T_{++}\right)^{-1}P_{\lambda ++}$, which means that $Y_m^C = m+1$; - then moves to the set $\mathcal{S}_{-}$, either moving down a level, with transition matrix $\left(I - \mu^{-1}T_{++}\right)^{-1}P_{\mu +-}$, or staying in the same level with $\left(I - \mu^{-1}T_{++}\right)^{-1}P_{\lambda +-}$. In the former case, $Y_{m+1}^C=m$, while in the latter $Y_{m+1}^C = m + 1$; - having reached $\mathcal{S}_{-}$, the process stays there and reaches level $0$ after either $m$ or $m + 1$ transitions, depending on the choice made in the previous point. Summing up the contributions of these paths we get the expression for $\Psi$ in . Thus, it is clear that the ${\mathcal{G}}$-matrix for the QBD is given by ${\mathcal{G}}_C$. Connections to existing QBDs and doubling algorithms {#subsec:newerQBDs} ---------------------------------------------------- \[theo:qbd-1\] Consider a Quasi-Birth-Death process $\{Y^{A'}_n, \kappa^{A'}_n\}_{n \geq 0}$ with the following transition probability matrices: $$\begin{aligned} \label{qbdrammod} A'_{-1} & := \frac12\begin{bmatrix} 0 & 0\\ 0 & I \end{bmatrix}, \; A'_0 := \frac12\begin{bmatrix} I & P_{\lambda+-}\\ 0 & P_{\lambda--} \end{bmatrix}, \; A'_1 := \frac12\begin{bmatrix} P_{\lambda++} & 0\\ P_{\lambda-+} & 0 \end{bmatrix}.\end{aligned}$$ We now show that $\{Y_{n}^{A}, \kappa_n^{A}\}_{n \geq 0}$ is ${\mathcal{G}}$-equivalent to a QBD process with transition matrices $$\label{unnamedA} \mbox{Down} := \left[\begin{array}{cr} 0 & 0 \\ 0 & \frac{1}{2} I \end{array} \right], \; \mbox{Same} := \left[\begin{array}{cc} 0 & P_{\lambda +-} \\ 0 & \frac{1}{2} V_{\lambda} \end{array} \right], \; \mbox{Up} := \left[\begin{array}{cc} P_{\lambda ++} & 0 \\ 0 & 0 \end{array} \right],$$ with $V_{\lambda} := I + {\lambda}^{-1} U$. Indeed, the two processes have the same dynamics, apart from their behaviour in $\mathcal{S}_-$. Starting from a state in $\mathcal{S}_-$, the process $\{Y_{n}^A, \kappa_n^{A}\}$ moves one level down immediately, and moves to a state in $\mathcal{S}_-$ with transition matrix $V_{\lambda}$, whereas the process in - makes an arbitrary number $\ell \geq 0$ of same-level transitions within $\mathcal{S}_-$, each with transition matrix $\frac12 V_\lambda$; - then finally moves down one level, again within $\mathcal{S}_-$, with transition matrix $\frac12 I$. However, these dynamics also produce an eventual decrease by one level with transition matrix $V_\lambda$, since $$\begin{aligned} \left(I - \frac{1}{\lambda}U\right)^{-1} = \frac{1}{2}\left(I - \frac{1}{2}V_{\lambda}\right)^{-1} = \sum_{\ell = 0}^{\infty} \left(\frac{1}{2}V_{\lambda}\right)^{\ell} \left(\frac{1}{2}I\right). \end{aligned}$$ Hence the two processes have the same ${\mathcal{G}}$-matrix, since this matrix depends only on the probabilities of reaching a certain level and state, not on the time taken. We now use a similar argument to show that the process with transition matrices is ${\mathcal{G}}$-equivalent to $\{Y_n^{\Delta}, \kappa_n^{\Delta}\}$. Indeed, these two process have the same dynamics, apart from the fact that in the latter a same-level transition with probability $\frac12 V_\lambda$ is replaced by - either a transition to the same level with probability $\frac{1}{2} P_{\lambda --}$, or - a transition to the set $\mathcal{S}_{+}$ and up one level with matrix $\frac{1}{2}P_{\lambda - +}$. However, we have already established that, starting from a state in $\mathcal{S}_+$ at a certain level $\ell$, the process eventually reaches level $\ell-1$ in a state $\mathcal{S}_-$ with transition probability matrix $\Psi$. Hence both dynamics eventually return to the same level (for the first time), in $\mathcal{S}_-$, with the same transition probability matrix, since $V_{\lambda} = P_{\lambda --} + P_{\lambda -+} \Psi$. Again, this change does not affect the value of $\mathcal{G}$. Da Silva Soares and Latouche @soares02 [Eqn. (17)] constructed a Quasi-Birth-Death process $\{Y^{\Theta}_n, \kappa^{\Theta}_n\}_{n \geq 0}$ with the following transition probability matrices: $$\begin{aligned} \label{qbdguy} \Theta_{-1} & := \begin{bmatrix} 0 & \frac12 P_{\mu+-}\\ 0 & P_{\mu--} \end{bmatrix}, \; \Theta_0 := \begin{bmatrix} \frac12P_{\mu++} & 0\\ P_{\mu-+} & 0 \end{bmatrix}, \; \Theta_1 := \frac12\begin{bmatrix} I & 0\\ 0 & 0 \end{bmatrix},\end{aligned}$$ and showed that their ${\mathcal{G}}$-matrix is also given by . \[theo:qbd-2\] Consider a Quasi-Birth-Death process $\{Y^{B'}_n, \kappa^{B'}_n\}_{n \geq 0}$ with transition probability matrices: $$\begin{aligned} \label{qbdguymod} B_{-1}' & := \frac12\begin{bmatrix} 0 & P_{\mu+-}\\ 0 & P_{\mu--} \end{bmatrix}, \; B_0' := \frac12\begin{bmatrix} P_{\mu++} & 0\\ P_{\mu-+} & I \end{bmatrix}, \; B_1' := \frac12\begin{bmatrix} I & 0\\ 0 & 0 \end{bmatrix}.\end{aligned}$$ The process $\{Y^{B'}_n, \kappa^{B'}_n\}_{n \geq 0}$ is equivalent to the QBD $\{Y_n^{\Theta}, \kappa_n^{\Theta}\}_{n \geq 0}$ and to the QBD $\{Y_n^{B}, \kappa_n^{B}\}$ introduced in Lemma \[lem:secondrep\]. This proof follows closely the one of Theorem \[theo:qbd-1\]. For the first part, note that the only difference between the dynamics of the two QBDs is in the transition matrices from a state in $\mathcal{S}_{-}$. With equal probabilities, our QBD $\{Y_{n}^{B'}, \kappa_n^{B'}\}$ either follows the same transition probabilities in their QBD, or makes a transition to the same state and the same level, that is, stays exactly where it is. Intuitively, while this slows down the expected time to go down one level, it does not affect the probability of doing so, and thus does not change the ${\mathcal{G}}$-matrix. We now show that $\{Y_n^{B}, \kappa_n^B\}$ is ${\mathcal{G}}$-equivalent to a QBD process with transition matrices $$\label{unnamedB} \mbox{Down} := \left[\begin{array}{cc} 0 & \frac{1}{2}P_{\mu +-} \\ 0 & V_{\mu} \end{array} \right], \; \mbox{Same} := \left[\begin{array}{cc} \frac{1}{2}P_{\mu ++} & 0 \\ 0 & 0 \end{array} \right], \; \mbox{Up} := \left[\begin{array}{cc} \frac{1}{2} I & 0 \\ 0 & 0 \end{array}\right].$$ Indeed, the two processes have the same dynamics, apart from the fact that (starting from a state in $\mathcal{S}_+$), instead of going one level up into $\mathcal{S}_+$ with transition matrix $\left(I - \mu^{-1}T_{++}\right)^{-1}$, the new process will - make a certain number $\ell \geq 0$ of same-level transitions, each with probability matrix $\frac12 P_{\mu ++}$, and then - make an upward transition with probability matrix $\frac12 I$. Nevertheless, both dynamics produce an increase by one level with the same transition probability matrix, since $$\begin{aligned} \left(I - \mu^{-1}T_{++}\right)^{-1} = \sum_{\ell = 0}^{\infty} \left(\frac{1}{2}P_{\mu ++} \right)^{\ell} \frac{1}{2}I. \end{aligned}$$ Next, we show that the process is ${\mathcal{G}}$-equivalent to $\{Y_n^{\Theta}, \kappa_n^{\Theta}\}$. The only difference between the two is that a downward transition from $\mathcal{S}_-$ to itself with transition matrix $V_{\mu}$ is replaced by - either a transition within $\mathcal{S}_{-}$ and down one level, with $P_{\mu --}$, or, - a transition from $\mathcal{S}_-$ to $\mathcal{S}_{+}$ at the same level, with $P_{\mu - +}$. Again, starting from $\mathcal{S}_+$ the process eventually decreases by one level with transition matrix $\Psi$, so both processes produce a decrease by one level with the same transition matrix, since $V_\mu = P_{\mu--} + P_{\mu-+}\Psi$. This change does not affect the matrix ${\mathcal{G}}$. \[theo:qbd-3\] Consider a Quasi-Birth-Death process $\{Y_n^{C'}, \kappa_n^{C'}\}_{n \geq 0}$ with the following transition matrices: $$\begin{aligned} \label{qbdgen} C_{-1}' & := \frac12\begin{bmatrix} 0 & P_{\mu+-}\\ 0 & P_{\mu--} \end{bmatrix}, \; C_0' := \frac12\begin{bmatrix} P_{\mu++} & P_{\lambda+-}\\ P_{\mu-+} & P_{\lambda--} \end{bmatrix}, \; C_1' := \frac12\begin{bmatrix} P_{\lambda++} & 0\\ P_{\lambda-+} & 0 \end{bmatrix}.\end{aligned}$$ Then, this process is equivalent to the QBD $\{Y_n^C, \kappa_n^C\}$; that is, its ${\mathcal{G}}$-matrix is also given by . In this proof we combine the transformations introduced in the previous ones. We first show that $\{Y_n^{C}, \kappa_n^C\}$ is ${\mathcal{G}}$-equivalent to the QBD with transition matrices $$\label{unnamedC} \mbox{Down}:= \left[\begin{array}{cc} 0 & \frac{1}{2} P_{\mu {+-}} \\ 0 & W \end{array}\right], \; \mbox{Same} := \left[\begin{array}{cc} \frac{1}{2}P_{\mu ++} & \frac{1}{2}P_{\lambda +-} \\ 0 & 0 \end{array} \right], \; \mbox{Up} := \left[\begin{array}{cc} \frac{1}{2} P_{\lambda ++} & 0 \\ 0 & 0 \end{array} \right].$$ We obtain this QBD from $\{Y_n^{C}, \kappa_n^C\}$ with the following modifications: - within the $\mathcal{S}_{+}$, we replace the transition matrix $(I - \mu^{-1} T_{++})^{-1} P_{\lambda ++}$ of increasing a level while remaining in $\mathcal{S}_{+}$ with - staying in the same level and in $\mathcal{S}_{+}$ with transition matrix $1/2P_{\mu++}$ any $n \geq 0$ number of steps, and then - increas a level with $1/2P_{\lambda ++}$; - from $\mathcal{S}_{+}$ to $\mathcal{S}_{-}$ and decreasing a level, we replace the transition matrix $(I - \mu^{-1} T_{++})^{-1} P_{\mu +-}$ with - staying in the same level and in $\mathcal{S}_{+}$ with transition matrix $1/2P_{\mu++}$ for any $n \geq 0$ number of steps, and then - decreasing a level with $1/2P_{\mu +-}$; - from $\mathcal{S}_{+}$ to $\mathcal{S}_{-}$ and staying in the same level, we replace the transition matrix $(I - \mu^{-1} T_{++})^{-1} P_{\lambda +-}$, with - staying in the same level and in $\mathcal{S}_{+}$ with transition matrix $1/2P_{\mu++}$ for any $n \geq 0$ number of steps, and then - transition into a state in $\mathcal{S}_{-}$ in the same level with $1/2P_{\lambda +-}$. All these replacements produce equivalent transitions which do not alter the matrix ${\mathcal{G}}$, since $$\begin{aligned} \left(I - \frac{1}{\mu} T_{++}\right)^{-1}& = \left(I - \frac{1}{2}P_{\mu ++} \right)^{-1}\frac{1}{2} = \sum_{n = 0}^{\infty} \left(\frac{1}{2}P_{\mu++} \right)^n \frac{1}{2} . \end{aligned}$$ Next, with a similar argument we can show that is ${\mathcal{G}}$-equivalent to the QBD with transition matrices $$\label{unnamedC2} \mbox{Down} := \left[\begin{array}{cc} 0 & \frac{1}{2} P_{\mu {+-}} \\ \vspace*{-0.3cm} \\ 0 & \frac{1}{2}V_{\mu} \end{array}\right], \; \mbox{Same} := \left[\begin{array}{cc} \frac{1}{2}P_{\mu ++} & \frac{1}{2}P_{\lambda +-} \\ \vspace*{-0.3cm} \\ 0 & \frac{1}{2}V_{\lambda} \end{array} \right], \; \mbox{Up} := \left[\begin{array}{cc} \frac{1}{2} P_{\lambda ++} & 0 \\ \vspace*{-0.3cm} \\ 0 & 0 \end{array} \right],$$ since $$\begin{aligned} W = (I - \lambda^{-1}U)^{-1}V_{\mu} = \left(I - \frac{1}{2} V_{\lambda}\right)^{-1} \frac{1}{2}V_{\mu} = \sum_{n = 0}^{\infty} \left(\frac{1}{2} V_{\lambda} \right)^n\frac{1}{2}V_{\mu}. \end{aligned}$$ Finally, with the same technique we prove that is ${\mathcal{G}}$-equivalent to $\{Y_{n}^{C'}, \kappa_n^{C'}\}$, since $V_{\mu} = P_{\mu --} + P_{\mu -+} \Psi$ and $V_{\lambda} = P_{\lambda --} + P_{\lambda -+} \Psi.$ Interpretation of Doubling Algorithms {#sec:int} ===================================== We consider for the remainder of the paper the most general Quasi-Birth-Death process $\{Y_{n}^{C'}, \kappa_n^{C'}\}$ only. The same results hold for the other two processes, $\{Y_n^{A'}, \kappa_n^{A'}\}$ and $\{Y_n^{B'}, \kappa_n^{B'}\}$, by setting $\mu^{-1} := 0$ and $\lambda^{-1} := 0$, respectively. Moreover, since $\{Y_n^{A}, \kappa_n^{A}\}$, $\{Y_n^{B}, \kappa_n^{B}\}$ (as well as $\{Y_n^{\Delta}, \kappa_n^{\Delta}\}$ and $\{Y_n^{\Theta}, \kappa_n^{\Theta}\}$) are ${\mathcal{G}}$-equivalent, the results hold for them too. For notational simplicity, we write $\{Y_{n}, \kappa_n\}$ instead of $\{Y_{n}^{C'}, \kappa_n^{C'}\}$, dropping the superscript. We also assume that the time $0$ marks the start of a busy period; hence $Y_0 = 1$, $\kappa_0 \in \mathcal{S}_{+}$. Level, mid-levels, and initial values of ADDA --------------------------------------------- Consider a sequence of integer-valued random variables $\{\tau_k\}_{k \geq 0}$ representing the times at which there is a level change, that is, $$\tau_{0} := 0, \quad \text{and} \quad \tau_{k+1} := \min \{n > \tau_{k} \colon Y_n \neq Y_{\tau_k} \} \text{ for $k > 0$}.$$ We define an associated process $\{M_{\tau_k}, \kappa_{\tau_k}\}_{k \geq 0}$ as follows: $$\label{def:halflevel} M_{\tau_k} := \begin{cases} Y_{\tau_k} - 1/2 & \text{if $\kappa_{\tau_k} \in \mathcal{S}_+$},\\ Y_{\tau_k} + 1/2 & \text{if $\kappa_{\tau_k} \in \mathcal{S}_-$}. \end{cases}$$ To see what the process $\{M_{\tau_k}, \kappa_{\tau_k}\}_{k \geq 0}$ represents in terms of the QBD $\{Y_n,\kappa_n\}$, we define *mid-levels* to be the sequence $\{z + 1/2\}_{z \geq 0}$, and say that the QBD process $\{Y_n,\kappa_n\}$ *crosses* the mid-level $z + 1/2$, at a certain time $n$, if its level changes from $z$ to $z+1$ or from $z+1$ to $z$. Then, the process $\{M_{\tau_k}\}$ has a simple interpretation: it is the mid-level crossed by the process $\{Y_n, \kappa_n\}$ at times $\tau_k$. Moreover, if $Y_n$ has just completed an upward crossing at time $\tau_k$, then $\kappa_{\tau_k} \in \mathcal{S}_+$; if a downward crossing, then $\kappa_{\tau_k} \in \mathcal{S}_-$. ![A sample path of $\{Y_n, \kappa_n\}$, in which $Y_n$ is represented by $\bullet$. By assumption, $\kappa_0 \in \mathcal{S}_+$. We have $\tau_1=1$, $\tau_2=3$, $\tau_3=4$, $\tau_4=5$, $\tau_5=7$, and $\kappa_{\tau_1}, \kappa_{\tau_2}, \kappa_{\tau_4}, \kappa_{\tau_5} \in \mathcal{S}_{+}, \, \kappa_{\tau_3} \in \mathcal{S}_{-}$. The sequence $\{M_{\tau_k}\}_{k \in \{0,\ldots, 5\}}$ is represented by $\circ$. \[fig:halves\] ](Htk.pdf "fig:") (-240,7)<span>(0,0)\[l\]<span>$0$</span></span> (-240,37)<span>(0,0)\[l\]<span>$1$</span></span> (-240,65)<span>(0,0)\[l\]<span>$2$</span></span> (-240,95)<span>(0,0)\[l\]<span>$3$</span></span> (-240,124)<span>(0,0)\[l\]<span>$4$</span></span> (-199, -5)<span>(0,0)\[l\]<span>$1$</span></span> (-171, -5)<span>(0,0)\[l\]<span>$2$</span></span> (-142, -5)<span>(0,0)\[l\]<span>$3$</span></span> (-113, -5)<span>(0,0)\[l\]<span>$4$</span></span> (-85, -5)<span>(0,0)\[l\]<span>$5$</span></span> (-55, -5)<span>(0,0)\[l\]<span>$6$</span></span> (-27, -5)<span>(0,0)\[l\]<span>$7$</span></span> (-230, -19)<span>(0,0)\[l\]<span>$\tau_0$</span></span> (-199, -19)<span>(0,0)\[l\]<span>$\tau_1$</span></span> (-142, -19)<span>(0,0)\[l\]<span>$\tau_2$</span></span> (-113, -19)<span>(0,0)\[l\]<span>$\tau_3$</span></span> (-85, -19)<span>(0,0)\[l\]<span>$\tau_4$</span></span> (-27, -19)<span>(0,0)\[l\]<span>$\tau_5$</span></span> (0,7)<span>(0,0)\[l\]<span>$n$</span></span> (-232,170)<span>(0,0)\[l\]<span>${Y}_n$</span></span> The process $\left\{M_{\tau_k}, \kappa_{\tau_k}\right\}_{k\in\mathbb{N}}$ is on the state space $\{\mathbb{Z} + 1/2\} \times \mathcal{S}$ with transition probability matrices $$\begin{aligned} \label{eq:qbdD} \hspace*{-0.3cm} D_{-1} := \begin{bmatrix} 0 & 0\\ 0 & F \end{bmatrix}, \, D_0 := \begin{bmatrix} 0 & G\\ H & 0 \end{bmatrix}, \, D_1 := \begin{bmatrix} E & 0\\ 0 & 0 \end{bmatrix}, \end{aligned}$$ where $E\in\mathbb{R}^{n_+\times n_+}, F\in\mathbb{R}^{n_-\times n_-}, G\in\mathbb{R}^{n_+ \times n_-}, H\in\mathbb{R}^{n_-\times n_+}$ are given by \[eqn:EGHF\] $$\begin{aligned} \begin{bmatrix} E & G\\ H & F \end{bmatrix} &:= \left( I-\frac12 \begin{bmatrix} P_{\mu++} & P_{\lambda+-}\\ P_{\mu-+} & P_{\lambda--} \end{bmatrix} \right)^{-1} \frac12 \begin{bmatrix} P_{\lambda++} & P_{\mu+-}\\ P_{\lambda-+} & P_{\mu--} \end{bmatrix} \\ &= \begin{bmatrix} I - \mu^{-1}T_{++} & -\lambda^{-1}T_{+-}\\ -\mu^{-1}T_{-+} & I - \lambda^{-1}T_{--} \end{bmatrix}^{-1} \begin{bmatrix} I+\lambda^{-1}T_{++} & \mu^{-1}T_{+-}\\ \lambda^{-1}T_{-+} & I + \mu^{-1}T_{--} \end{bmatrix} . \end{aligned}$$ Note that coincides with in the case of unit rates, after setting $\mu^{-1}=\alpha$, $\lambda^{-1}=\beta$. Let $J_{-1}, J_0,$ and $J_1$ represent the transition probability matrices of $\{Y_{\tau_k}, \kappa_{\tau_k}\}_{k \in \mathds{N}}$, the time-changed QBD obtained by observing the original process $\{Y_n, \kappa_n\}$ only at times at which there are changes of levels. Then, $$\begin{aligned} \label{eqn:Jmatrices} J_{-1} = (I-C_0')^{-1}C_{-1}' = \begin{bmatrix} 0 & G\\ 0 & F \end{bmatrix}, \quad J_0 = 0, \quad J_1 = (I-C_0')^{-1}C_{1}' = \begin{bmatrix} E & 0\\ H & 0 \end{bmatrix}. \end{aligned}$$ In the transitions corresponding to the sub-block $H$, the process $\{Y_{\tau_k}, \kappa_{\tau_k}\}$ moves from $(z, \mathcal{S}_-)$ at time $\tau_{\ell - 1}$ up to $(z+1, \mathcal{S}_+)$ at time $\tau_{\ell}$ for some $\ell \in \mathds{N}$. Hence, the mid-level, as defined in , does not change from the epoch $\tau_{\ell - 1}$ to the epoch $\tau_{\ell}$, that is, $M_{\tau_{\ell - 1}} = M_{\tau_{\ell}} = z + 1/2$. Thus, for the process $\{M_{\tau_k}, \kappa_{\tau_k}\}$, the sub-block $H$ belongs to the bottom-left corner of the transition probability matrix $D_0$. Analogous considerations hold for the other sub-blocks: $E$ corresponds to moving from a mid-level to the one above, $F$ to the one below, and $G$ corresponds to staying in the same mid-level. The ${\mathcal{G}}$-matrix of QBD is $$\label{eqn:GD} {\mathcal{G}}_D = \begin{bmatrix} 0 & \Psi W\\ 0 & W \end{bmatrix},$$ as observed in @bmp. Indeed, decreasing from the mid-level $(z + 1/2)$ to the mid-level $(z - 1/2)$ for $\{M_{\tau_k}, \kappa_{\tau_k}\}$ corresponds to decreasing one level also for QBD $\{Y_n, \kappa_n\}$ if the initial state is in $\mathcal{S}_-$, since it means going from level $z$ to level $(z-1)$. On the other hand, such a decrease of $\{M_{\tau_k}, \kappa_{\tau_k}\}$ corresponds to a decrease of *two* levels if the initial state is in $\mathcal{S}_+$, since it means going from level $(z+1)$ to level $(z-1)$. The fact that this ${\mathcal{G}}$-matrix does not contain $\Psi$ explicitly as a block is not an issue for our computation, since in doubling algorithms we obtain $\Psi$ from the limit $\Psi = \lim_{k\to\infty} G_k$, not as a block of ${\mathcal{G}}_D$. Expanding into blocks the relation $D_{-1}+D_0{\mathcal{G}}_D+D_1{\mathcal{G}}_D^2={\mathcal{G}}_D$, one obtains that $\Psi$ is a solution of the matrix equation $$\label{dare} X = G+EX(I-HX)^{-1}F.$$ Moreover, using the minimality of ${\mathcal{G}}_D$, one can prove that $\Psi$ must be the minimal solution to . Interpretation of the doubling iteration {#subsec:doublingmap} ---------------------------------------- Now that we have a physical interpretation for the QBD with transition matrices $D_{-1},D_0,$ and $D_1$, we consider what it means to apply one step of the iteration to it. Bini *et al.* @bmp showed, via algebraic computations, that applying one step of the Cyclic Reduction (CR) algorithm \[cr\] $$\begin{aligned} \widehat{D}_{-1} &= D_{-1}(I-D_0)^{-1}D_{-1}, \label{cr:-1} \\ \widehat{D}_0 &= D_0 + D_1(I-D_0)^{-1}D_{-1} + D_{-1}(I-D_0)^{-1}D_1,\\ \widehat{D}_1 &= D_{1}(I-D_0)^{-1}D_1 \end{aligned}$$ to the transition matrices in produces a QBD with the same block structure, i.e., $$\begin{aligned} \label{crhat} \hspace*{-0.3cm} \widehat{D}_{-1} := \begin{bmatrix} 0 & 0\\ 0 & \widehat{F} \end{bmatrix}, \, \widehat{D}_0 := \begin{bmatrix} 0 & \widehat{G}\\ \widehat{H} & 0 \end{bmatrix}, \, \widehat{D}_1 := \begin{bmatrix} \widehat{E} & 0\\ 0 & 0 \end{bmatrix}, \end{aligned}$$ with $\widehat{E},\widehat{F},\widehat{G},\widehat{H}$ precisely as in . For more detail on Cyclic Reduction, see @blm05; in particular, note that the full description includes a fourth equation, which is necessary in the general case to recover the matrix $\Psi$, but we shall see that in our case we can do without it. By building on this relation with Cyclic Reduction, we can give a physical interpretation of the doubling iteration and justify the formulas directly. Our starting point is the physical interpretation of Cyclic Reduction @bmr. The matrices $\widehat{D}_{-1},\widehat{D}_0,\widehat{D}_1$ are the transition matrices of the QBD that corresponds to censoring out the odd-numbered levels $(1,3,5,\dots)$ from a QBD with transition matrices $D_{-1}, D_0, D_1$. The QBD resulting from the censoring has level set $2\mathbb{Z} = \{\dots, -4,-2,0,2,4,\dots \}$, so with $\widehat{D}_{-1}$ we mean the probability of moving from level $y$ to level $y-2$, and similarly for the other two matrices. Note that we have already similarly abused the concept of levels when considering the QBD $\{M_n, \kappa_n\}$ which has level set $\mathbb{Z}+1/2 = \{\dots,-3/2,-1/2,1/2,3/2,\dots\}$. It is not difficult to obtain the formulas directly from this interpretation: for instance, the formula for $\widehat{D}_{-1}$ corresponds to the probability (starting from an even-numbered level $\ell$) of descending to level $\ell-1$, spending an arbitrary amount of time there, and then taking a second step down to $\ell-2$. This interpretation tells us that $\widehat{D}_{-1},\widehat{D}_0,\widehat{D}_1$ are the transition matrices of the QBD obtained from $\{M_{\tau_k}, \kappa_{\tau_k}\}$ by censoring out the *odd-numbered* mid-levels, i.e., those of the form $2j+3/2$, and keeping only those of the form $2j+ 1/2$, $j\in\mathbb{Z}$. More formally, define $$\begin{aligned} \widehat{\tau}_0 & =0,\\ \widehat{\tau}_{k+1} & = \min\left\{n > \widehat{\tau}_k : \text{$n=\tau_i$ for some $i$, and $M_n=2j+1/2$ for some $j\in\mathbb{Z}$}\right\}. \end{aligned}$$ Then, $\widehat{D}_{-1},\widehat{D}_0,\widehat{D}_1$ are the transition matrices of $\{M_{\widehat{\tau}_k}, \kappa_{\widehat{\tau}_k}\}$, which is a QBD with level set $2\mathbb{Z}+1/2 = \{\dots,-3/2,1/2,5/2,9/2,\dots\}$. Armed with this physical interpretation, we can justify the formulas directly. To compute the probabilities $\widehat{E}$ (after starting at the mid-level $(y+1/2)$ and in a positive phase) of reaching mid-level $(y+5/2)$ *before* descending to $(y+1/2)$, we condition on the number of visits to the mid-level equidistant between the two, i.e., $y+3/2$: we can visit it either - once (from below, with probability matrix $E^2$), or - three times (from below, then from above, then from below, with probability matrix $EGHE$), or - five times, or - …, leading to the series $$\widehat{E} = E^2 + EGHE + EGHGHE + \dots = E(I-GH)^{-1}E.$$ To compute the complementary probabilities $\widehat{G}$ of returning to mid-level $y+ 1/2$ with taboo level $y+ 5/2$, we condition again on the number of visits to the mid-level $y + 3/2$: we can visit it either - zero times (with probability $G$), or - two times (from below – from above, with probability $EGF$), or - four times, or - …, leading to the series $$\widehat{G} = G + EGF + EGHGF + \dots = G + E(I-GH)^{-1}GF.$$ The formulas for $\widehat{F}$ and $\widehat{H}$ are obtained analogously. Mean number of visits and recurrence ------------------------------------ Another matrix of physical interest for our QBD process $\{M_n,\kappa_n\}$ is the minimal solution ${\mathcal{R}}$ of the matrix equation $$\begin{aligned} {\mathcal{R}}^2D_{-1}+{\mathcal{R}}D_0+D_1={\mathcal{R}}, \end{aligned}$$ which represents the expected number of visits to mid-level $(1+ 1/2)$, starting from mid-level $1/2$ and before returning to the same mid-level (see @blm05 [Section 5] for a description of this matrix in the context of a general QBD). We call it the *${\mathcal{R}}$-matrix* of the QBD, in analogy with the ${\mathcal{G}}$-matrix. This matrix is related to its counterpart for the fluid queue: the matrix $K=T_{++}+\Psi T_{-+}$ such that $\mathrm{e}^{Kx}$ is the expected number of visits to level $x$ of the
{'source': 'arXiv_out/1801'}