Abstract
In this paper, we consider (upward skip-free) discrete-time and discrete-space Markov additive chains (MACs) and develop the theory for the so-called \(\widetilde{{\textbf {W}}}\) and \(\widetilde{{\textbf {Z}}}\) scale matrices, which are shown to play a vital role in the determination of a number of exit problems and related fluctuation identities. The theory developed in this fully discrete set-up follows similar lines of reasoning as the analogous theory for Markov additive processes in continuous time and is exploited to obtain the probabilistic construction of the scale matrices, identify the form of the generating function and produce a simple recursion relation for \(\widetilde{{\textbf {W}}}\), as well as its connection with the so-called occupation mass formula. In addition to the standard one- and two-sided exit problems (upwards and downwards), we also derive distributional characteristics for a number of quantities related to the one- and two-sided ‘reflected’ processes.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Exit problems for stochastic processes are a classic topic in applied probability and has received a great deal of attention within the literature. In the continuous setting (time and space), exit problems for so-called upward skip-free processes, known in the literature as ‘spectrally negative Lévy processes’, have been extensively considered in [5] (Chapter VII), [18] (Chapter 8) and references therein, by means of fluctuation theory where semi-explicit expressions are derived in terms of the so-called ‘scale functions’. On the other hand, in the fully discrete setting exit problems for general discrete-time random walks are excellently treated in [10, 13], among others, by means of probabilistic arguments and include, as particular cases, the corresponding upward skip-free random walks. That is, a random walk for which downward jumps are unrestricted but upward jumps are constrained to a magnitude of at most one, emulating the upward ‘drift’ in continuous-time. More recently, [3] implement the ideas underlying the exit problems for continuous spectrally negative Lévy processes for their discrete random walk counterparts and derive exit problems and other fluctuation identities in terms of analogous ‘discrete scale functions’.
A natural generalisation of the above processes are the broad family of Markov additive processes (MAPs), which incorporate an externally influencing Markov environment, providing greater flexibility to the characteristics of the underlying process in terms of its claim frequency and severity distributions, see [1] (Chapter XI). Within this generalised framework, the existence of multidimensional scale functions, known as ‘scale matrices’, was first discussed in [19] and were used to derive fluctuation identities and first passage results for continuous-time MAPs. [14] extended the initial findings of [19] by providing the probabilistic construction of the scale matrices, identifying their transforms and considering an extensive study of exit problems including one-sided and two-sided exits, as well as exits for reflected processes via implementation of the occupation density formula. Further studies on MAPs and their exit/passage times can be found in [4, 8, 9], among others. More recently, [16], derive and compare results for continuous-time MAPs with lattice (discrete-space) and non-lattice support. It is worth noting here that the authors in this work do discuss some of the corresponding results for the fully discrete (time and space) MAP model considered in this paper; however, only a limited number of results are stated and a variety of important steps and proofs were omitted.
This paper bridges the gap between the aforementioned works and provides a theoretical framework for fully discrete, upward skip-free MAPs, in terms of ‘discrete scale matrices’, spelling out the differences in results, methodologies and necessary adjustments for deriving fluctuation identities between discrete and continuous MAPs. In particular, we derive results for the first passage theory, including one and two-sided exit problems as well as the under(over)-shoots upon exit via the associated ‘reflected’ process. The motivation for deriving such a framework comes from the discrete set-up having known advantages over the continuous-time models. For example, it is known that the Wiener–Hopf factorisation can be replaced by a simple Laurent series (see [3]). Moreover, due to the equivalence between a discrete MAP and a Markov-modulated random walk, this paper provides a more flexible random walk model and enriches the numerous applications of random walk theory across a variety of disciplines.
The paper is organised as follows: In Sect. 2, we define the MAP in discrete time and space and derive the so-called occupation mass matrix formula, from which we obtain some useful identities to be used in the following sections. In Sect. 3, we introduce some fundamental matrices associated to the discrete MAP, identify the first of two discrete scale matrices and derive matrix expressions for the one and two-sided upward exit problem. In Sect. 4, we derive results for the corresponding one and two-sided reflected processes, including the over-shoot and under-shoot upon exit which are then used in Sect. 5 to derive expressions for the one and two-sided downward exit problems of the original (non-reflected) discrete MAP.
2 Preliminaries
A fully discrete (time and space) MAP, which we will call a Markov Additive Chain (MAC), is defined as a bivariate discrete-time Markov chain \((X,J) = \{(X_n, J_n)\}_{n \geqslant 0}\), on the product space \({\mathbb {Z}}\times E\), where \(X_n \in {\mathbb {Z}}\) describes the level of the underlying process, whilst \(J_n \in E = \left\{ 1, 2, \ldots , N \right\} \) describes the phase of some external Markov chain (which affects the dynamics of \(X_n\)) having transition probability matrix \({\textbf {P}}\), such that for \(i,j \in E\), \(\left( {\textbf {P}} \right) _{ij} = {\mathbb {P}} \left( J_1 = j | J_{0} =i \right) \). It is assumed throughout this work that the Markov chain \(\{J_n\}_{n \geqslant 0}\) is ergodic such that its stationary distribution \(\varvec{\pi }^\top = \left( \pi _1, \ldots , \pi _N\right) \) exists and is unique. The defining property of the MAC is the conditional independence and stationarity of law governing \(X_n\), given \(J_n\). That is, given that \(\{ J_T = i \}\) for some fixed \(T\in {\mathbb {N}}\), the Markov chain \(\{ (X_{T+n} - X_T, J_{T+n}) \}\) is independent of \({\mathcal {F}}_T\) (the natural filtration to which the bivariate process (X, J) is adapted) and \(\{ (X_{T+n} - X_T, J_{T+n}) \} \overset{d}{=}\ \{ (X_n - X_0, J_n) \}\), given \(\{J_0 = i\}\) for any phase state \(i \in E\). This is known as the Markov additive property, a consequence of which is that the level process \(\{X_n\}_{n \geqslant 0}\) is translation invariant on the lattice.
Intuitively, the MAC is simply a Markov-modulated random walk where \(\{X_n\}_{n \geqslant 0}\) evolves according to the random walk \(X_n = Y_1 + Y_2 + \cdots + Y_n\), where \(\{Y_k\}_{k \geqslant 1}\) is a sequence of conditionally i.i.d. random variables with common, conditional distribution \({\widetilde{q}}_{ij}(y) = {\mathbb {P}}( Y_1 = y | J_1 = j, J_{0}=i),\) and thus, probability mass matrix \(\widetilde{{\textbf {Q}}}(y)\), with i,j-th element \(\bigl (\widetilde{{\textbf {Q}}}(y)\bigr )_{ij} = {\widetilde{q}}_{ij}(y)\). As such, and due to the invariance property, the transition probability matrix of \(\left( X, J\right) \) has a block-like structure with blocks \(\widetilde{{\textbf {A}}}_m\) which represent the (one-step) transition matrix for an increase of m levels in \(\{X_n\}_{n \geqslant 0}\) whilst capturing the phase transitions of \(\{J_n\}_{n \geqslant 0}\), such that
where \(\circ \) denotes entry-wise products (Hadamard multiplication). In the remainder of this paper, we assume that \(X=\{X_n\}_{n\ge 0 }\) may only increase by at most one level per unit time whilst experiencing downward jumps of arbitrary size. That is, for all \(i,j \in E\), we have \({\widetilde{q}}_{ij}(m) = {\mathbb {P}}( Y_1 = m | J_1 = j, J_{0}=i) \geqslant 0\) for \(m \leqslant 1\) and \({\widetilde{q}}_{ij}(m) = 0\) otherwise, which leads to \(\widetilde{{\textbf {Q}}}(m) = {\textbf {0}}\) and thus \(\widetilde{{\textbf {A}}}_m = {\textbf {0}}\) for \(m = 2, 3,. \ldots \). In this sense, we say that X possesses an ‘upward skip-free’ property, an advantage of which is that the value of X is known at stopping time corresponding to ‘upward’ crossing/hitting of a given level (see below). This corresponds to the discrete analogue of a ‘spectrally negative’ MAP in the continuous setting, which have important applications to workload and surplus processes in queuing and risk theory, respectively (see [1, 2] for more details).
2.1 MAC Matrix Generator
It has already been noted that the dynamics of the level process (X) within the MAC depends on the phase transitions of the external Markov chain (J). As such, the majority of quantities and results presented in this paper depend on the initial and final states of \(\{J_n\}_{n \geqslant 0}\) and thus, are given in matrix form. With this in mind, let us define the expectation matrix operator \({\mathbb {E}}_x(\cdot ; J_n)\) which denotes an \(N\times N\) matrix with i, j-th element \(\left( {\mathbb {E}}_x\left( \cdot \,; J_n\right) \right) _{ij}={\mathbb {E}}\left( \cdot \,1_{( J_n = j)} | X_0 = x, J_0 = i \right) \), where \(1_{(\cdot )}\) represents the indicator function, and corresponding probability matrix \({\mathbb {P}}_x( \cdot \,, J_n)\) with elements \(\left( {\mathbb {P}}_x( \cdot \,, J_n)\right) _{ij}={\mathbb {P}}( \cdot \,, J_n = j | X_0 = x, J_0 = i)\). Moreover, we denote \({\mathbb {E}}\left( \cdot \,; J_n\right) \equiv {\mathbb {E}}_0\left( \cdot \,; J_n\right) \), having associated probability measure \({\mathbb {P}}\left( \cdot \,,J_n\right) \equiv {\mathbb {P}}_0\left( \cdot \,, J_n\right) \) and thus, we can define the probability generating matrix (p.g.m.) of the process \(\{X_n\}_{n \geqslant 0}\) with initial level \(X_0=0\), for at least \(|z| \leqslant 1\) and \(z \ne 0\), by \({\mathbb {E}}\left( z^{-X_n}\,; J_n \right) \), which satisfies
and for \(z=1\), we have \(\widetilde{{\textbf {F}}}(1) = {{\textbf {P}}} = \sum _{m=-1}^\infty \widetilde{{\textbf {A}}}_{-m} \).
Remark 1
Note that since the matrices \(\widetilde{{\textbf {A}}}_{-m}\) are probability transition matrices, such that \(\widetilde{{\textbf {A}}}_{-m} \geqslant 0\) (non-negative), it follows that for \(z > 0\), the matrix \(\widetilde{{\textbf {F}}}(z)\) is also non-negative. Hence, by the Perron–Frobenius theorem, \(\widetilde{{\textbf {F}}}(z)\) has a (simple) eigenvalue, denoted \(\kappa (z)\), which is greater than or equal in absolute value than all other eigenvalues with corresponding left and right (column) eigenvectors, denoted \(\mathbf {{{\textbf {v}}}}(z)\) and \(\mathbf {{{\textbf {h}}}}(z)\), respectively, such that \(\mathbf {{\textbf {v}}}(z)^\top \widetilde{{\textbf {F}}}(z) = \kappa (z) \mathbf {{\textbf {v}}}(z)^\top \) and \(\widetilde{{\textbf {F}}}(z) \mathbf {{\textbf {h}}}(z) = \kappa (z) \mathbf {{\textbf {h}}}(z)\). Moreover, since \(\widetilde{{\textbf {F}}}(1) = {\textbf {P}}\) is a stochastic matrix, using standard facts from matrix analysis (see [7]) we have \(\kappa (1) = 1\) and it can be shown that \(\kappa '(1)\) determines the asymptotic drift of the level process \(\{X_n\}_{n \geqslant 0}\) (see Section 1.3 in [11, 22]), given by
Within the theory of continuous-time Lévy processes, it is often desirable to analyse the process prior to some independent exponential ‘killing time’ as this can emulate the role of Laplace transforms or generating functions within the calculations (see [18]). For a MAP, this exponential killing time can alternatively be incorporated via an enlargement to the state space of the Markov chain with the addition of an ‘absorbing’ (killing) state and analysing the process prior to absorption (see [14] for details).
In a similar way, let us enlarge the state space E to \(E \cup \{\dagger \}\), where \(\dagger \) denotes an absorbing state, often called the cemetery state, and we set \(X=\partial \) whenever \(J=\dagger \). Moreover, let us assume that the (one-step) ‘absorption’ probability is the same from all states and denoted by \(1-v = {\mathbb {P}}\left( J_1 = \dagger | J_0 = i \right) \), for all \(i \in E\), such that the corresponding ‘non-absorption’ probability (survival) is given by \(v \in (0,1]\). Now, due to the addition of this cemetery state, it is clear that the probability transition matrix for transitions between the ‘transient’ (when \(v<1\)) states of E is dependent on v. Let us define this by \({\textbf {P}}(v)\equiv v{\textbf {P}}\), where \({\textbf {P}}\) denotes the stochastic probability transition matrix defined in Sect. 2, in the absence of an absorbing state or ‘killing’ (\(v=1\)). Hence, it follows that \({\textbf {P}}(v)\mathbf {{\textbf {e}}} = v{\textbf {P}}\mathbf {{\textbf {e}}} = v\mathbf {{\textbf {e}}}\) and thus, for \(v <1 \), \({\textbf {P}}(v)\) is sub-stochastic and its Perron–Frobenius eigenvalue is less than 1 (see [7]). Finally, it follows that the absorption or ‘killing’ time of the Markov chain, denoted \(g_v=\inf \{n> 0:J_n=\dagger \}\), is geometrically distributed with parameter \(v\in (0,1]\) and we have
where \( \widetilde{{\textbf {F}}}^{v}(z):= {\mathbb {E}}\bigl ( z^{-X_1}; 1 < g_{v},J_1 \bigr ) = {v}\widetilde{{\textbf {F}}}(z)\) with \(\widetilde{{\textbf {F}}}(z)\) denoting the matrix generator of the MAC in the absence of killing, as defined as in Eq. (2.2). The connection between the killed process and transforms/generating functions of the non-killed process is evident when we note that Eq. (2.3) is equivalent to \({\mathbb {E}}\bigl ( v^n z^{-X_n}; J_n \bigr )\) for a ‘non-killed’ MAC. Further advantages of working with the killed process are discussed in more details in later sections. Throughout the remainder of this paper, we generally suppress the explicit notation that absorption has not yet occurred but point out that it is assumed implicitly. As such, the results derived in the following are, in fact, much more general than they appear, with only a handful of these generalisations being stated explicitly.
2.2 Occupation Times
It is well known that occupation times and their densities play an important role within the theory of Lévy processes and their fluctuations. In a continuous environment, the definition of the occupation density/time of a process at a given level has to be treated with some care and detail (see [5, 14]) however, in the fully discrete model considered in this paper, the mathematical definition is intuitive.
Let us define by \({\widetilde{L}}(x, j, n)\), the occupation mass denoting the number of periods the process \(\{(X_n, J_n)\}_{n \ge 0}\) is in state \((x, j)\in {\mathbb {Z}} \times E\), up to and including time \(n \geqslant 0\), such that
Then, for some measurable non-negative function f, we have the so-called discrete occupation mass formula
From the above definition, it is clear that \({\widetilde{L}}(x, j, n)\) is a non-decreasing (monotone) process in \(n \geqslant 0\), which is adapted to the natural filtration \({\mathcal {F}}_n\). Therefore, if we further define the N-dimensional square occupation mass matrix, denoted \(\widetilde{{\textbf {L}}}(x, n)\), with i, j-th element given by \(\bigl (\widetilde{{\textbf {L}}}(x, n)\bigr )_{ij} = {\mathbb {E}}\bigl ( {\widetilde{L}}\left( x, j, n \bigr ) \big | J_0 = i\right) \). Then, by application of the strong Markov property, analogously to Proposition 8 in [14], we have the following proposition.
Proposition 1
Let
denote the first ‘hitting’ time of the level \(x\in {\mathbb {Z}}\). Then, for the occupation mass matrix \(\widetilde{{\textbf {L}}}(x, n)\), it follows that
where \(\left( {\mathbb {P}}\left( \tau _x< \infty , J_{\tau _x} \right) \right) _{ij}={\mathbb {P}}\left( \tau _x<\infty , J_{\tau _x}=j|J_0=i \right) \) and \(\widetilde{{\textbf {L}}}:= \widetilde{{\textbf {L}}}(0, \infty )\) is the occupation mass matrix at the level 0 over an infinite-time horizon, which has strictly positive entries.
Remark 2
Let us point out some of the advantages of working with the killed process at this point:
-
(i)
If we include the implicit killing in the calculations explicitly, then for \(v \in (0,1]\), the probability \( {\mathbb {P}}\left( \tau _x < \infty , J_{\tau _x} \right) \) becomes
$$\begin{aligned} {\mathbb {P}}\bigl ( \tau _x< g_{v} , J_{\tau _x} \bigr )&=\sum _{n=0}^{\infty }{\mathbb {P}}(\tau _x = n, n <g_v, J_{n})\\&=\sum _{n=0}^{\infty }v^n {\mathbb {P}}(\tau _x = n, J_n )= {\mathbb {E}}\bigl ( {v}^{\tau _x};J_{\tau _x}\bigr ), \end{aligned}$$where in the second equality we have used the fact that \({\textbf {P}}(v) = v{\textbf {P}}\). That is, the probability matrix \({\mathbb {P}}(\tau < \infty , J_{\tau _x})\) becomes the generator matrix \({\mathbb {E}}( {v}^{\tau _x};J_{\tau _x})\), if one imposes ‘killing’ explicitly. As mentioned above, throughout this work we will keep killing implicit as it greatly simplifies the presentation but highlight that the above idea holds for all results.
-
(ii)
Similarly, by superimposing killing in Proposition 1, we have that
$$\begin{aligned} \widetilde{{\textbf {L}}}_{v}(x, \infty ) = {\mathbb {E}}\bigl ({v}^{\tau _x}; J_{\tau _x} \bigr ) \widetilde{{\textbf {L}}}_{v}, \end{aligned}$$with \(\widetilde{{\textbf {L}}}_{v}:= \widetilde{{\textbf {L}}}_{v}(0, \infty )\), such that the i, j-th element of \(\widetilde{{\textbf {L}}}_{v}(x, n)\) is given by \(\bigl (\widetilde{{\textbf {L}}}_v(x, n)\bigr )_{ij} = {\mathbb {E}}\bigl ( {\widetilde{L}}_v(x,j,n) \big | J_0=i\bigr )\), where \({\widetilde{L}}_{v}(x,j,n) = \sum _{k=0}^n1_{\left( X_k =x, J_k=j, k<g_{v} \right) }.\) Note that since \({\textbf {P}}\) is sub-stochastic, then \(\{X_k=x\}\) implies that \(\{k<g_v\}\) and thus \({\widetilde{L}}_{v}(x,j,n)\) coincides with \({\widetilde{L}}(x,j,n)\).
The main reason for introducing the theory of occupation times and their associated mass matrices, is due to their relationship with the one-step p.g.m., namely \(\widetilde{{\textbf {F}}}(z)\). This connection is highlighted in the following auxiliary theorem which provides the foundations for many of the results in the following sections.
Theorem 1
For all \(z \in (0,1]\) such that \({\textbf {I}} - \widetilde{{\textbf {F}}}(z)\) is non-singular, it follows that
where \(\tau _x\) is the first hitting time of the level \(x \in {\mathbb {Z}}\).
Proof
First note by the occupation mass formula, that for any \(j\in E\), we have
Taking expectations in the above equation and considering the limit as \(n \rightarrow \infty \), yields
from which, since \(z^{-x}\) is non-negative for \(z > 0\), we can apply the monotone convergence theorem to obtain
Equivalently, in matrix form the above expression can be written as
where the last equality comes from the result of Proposition 1. Finally, we note that the geometric series on the l.h.s. converges to \(({\textbf {I}}-\widetilde{{\textbf {F}}}(z))^{-1}\) as long as \(\kappa (z) < 1\) and the result follows using analytic continuation to extend the domain of convergence to all \(z \in (0,1]\) such that \(({\textbf {I}}-\widetilde{{\textbf {F}}}(z))^{-1}\) exists. \(\square \)
Remark 3
Note that the result of Theorem 1 holds in the presence of killing (\(v < 1\)), since \({\textbf {P}}(v)\) is sub-stochastic and thus \(\kappa ^v(1)<1\), where \(\kappa ^v(z)\) is the Perron–Frobenius eigenvalue of \(\widetilde{{\textbf {F}}}^v(z)\). Hence, by continuity of \(\kappa ^v(z)\), there exists a small interval around \(z =1\) for which \(\kappa ^v(z) < 1\). In addition, \(\widetilde{{\textbf {L}}}\) must have finite entries as under killing the Markov chain is transient and the expected number of visits to any state is finite.
3 Upward Exit Problems
In this section, we discuss and derive results on exit problems for upward skip-free MACs above and below a fixed level or strip. In the first instance, we will utilise the upward skip-free property of the level process, \(\{X_n\}_{n \geqslant 0}\), to determine expressions for upward exit times (one and two-sided), then extend the theory to consider downward exit problems. These expressions are given in terms of so-called fundamental and scale matrices associated to the MAC, where the existence of the latter was first discussed in [19] and extended the notion of scale functions associated to Lévy processes (see [3, 18] for more details).
All the results given in this section are stated from an initial level \(X_0 = 0 \) which, due to the invariance property, can be generalised to an arbitrary level, say \(x_0 \in {\mathbb {Z}}\), via an appropriate shift.
Let us denote by \(\tau _x^{\pm }\), the first time the level process \(\{X_n\}_{n \geqslant 0}\) up(down)-crosses the level \(x \in {\mathbb {Z}}\), such that
We note that in a ‘spectrally negative’ MAC with upward drift of one per unit time, for \(x \geqslant X_0\) the random stopping times \(\tau ^+_x\) (crossing time) and \(\tau _x\) (hitting time) coincide. Moreover, we have that \(X_{\tau ^+_x} = X_{\tau _x} = x\).
3.1 One-Sided Exit Upward
The key observation for the first passage upwards is that the stationary and independent increments as well as the skip-free property provide an embedded Markov structure. To see this, recall that \(X_{\tau _1^+} = X_{\tau _1} = 1\), which together with the strong Markov and Markov additive properties, imply that the process \(\{J_{\tau _n}\}_{n \geqslant 0}\) is a (time-homogeneous) discrete-time Markov chain, given \(X_0 = 0\), with some probability transition matrix \(\widetilde{{\textbf {G}}}\), such that for \(a\ge 0\),
with i, j-th element given by \((\widetilde{{\textbf {G}}})_{ij} = {\mathbb {P}}\left( \tau _1 < \infty , J_{\tau _1} = j \mid J_0 = i\right) \) for \(i,j \in E\).
Remark 4
In the case of no killing, i.e. \(v=1\) and \(\kappa '(1) \leqslant 0\) (non-negative drift), the matrix \(\widetilde{{\textbf {G}}}\) is a stochastic matrix and sub-stochastic otherwise.
The transition probability matrix \(\widetilde{{\textbf {G}}}\) is widely known as the fundamental matrix of the MAC and contains the probabilistic characteristics to determine upward passage times and the corresponding phase state at passage. That is, determining the matrix \(\widetilde{{\textbf {G}}}\) provides the probability of hitting any upper level \(a \geqslant 0\) and the phase of \(\{J_n\}_{n \geqslant 0}\) at this hitting time.
The matrix \(\widetilde{{\textbf {G}}} \) has a long history in the theory of structured stochastic matrices (see for, e.g. Lemma 4.2 in [7]) and can be computed by conditioning on the first time period, i.e.
Multiplying on the right by \(\widetilde{{\textbf {G}}}^{-1}\), assuming it exists (see Remark 7), and using the definition of \(\widetilde{{\textbf {F}}}(z)\) given in Eq. (2.2), it follows that the fundamental matrix, \(\widetilde{{\textbf {G}}}\), is the right solution of \(\widetilde{{\textbf {F}}}(\cdot ) = {\textbf {I}}\), which is a well-known equation established in [21] and further studied in [7, 11, 12, 22], among others.
Remark 5
Let us discuss a few important observations about the fundamental matrix \(\widetilde{{\textbf {G}}}\) and its significance within applied probability:
-
(i)
For the continuous-time (scalar) spectrally negative Lévy process, the fundamental matrix \(\widetilde{{\textbf {G}}}\), corresponds to the of inverse Laplace exponent at zero, namely \(\Phi (0)\), i.e. the solution to \(\psi (\beta ) = 0\), where \(\psi (\beta )\) denotes the Laplace exponent of the Lévy process (see [18]).
-
(ii)
It follows by definition that \({\mathbb {E}}\bigl (\widetilde{{\textbf {G}}}^{-X_n}; J_n \bigr )\) is a martingale. In fact, it is clear that in the matrix setting, there exists another solution (left solution) to \(\widetilde{{\textbf {F}}}(\cdot ) = {\textbf {I}}\), say \(\widetilde{{\textbf {R}}}\), which would also result in the martingale \({\mathbb {E}}\bigl (\widetilde{{\textbf {R}}}^{-X_n}; J_n \bigr )\). It turns out that the matrix \(\widetilde{{\textbf {R}}}\) is actually the counterpart of \(\widetilde{{\textbf {G}}}\) for the ‘time-reversed MAC’ and is considered another fundamental matrix. The time-reversed MAP and the corresponding matrix \(\widetilde{{\textbf {R}}}\) are considered in [15] for the continuous-time (lattice) case and we direct the reader to this paper for more details.
-
(iii)
Superimposing killing in the above produces the transform of the first passage time, namely \({\mathbb {E}}\left( {v}^{\tau _a}; J_{\tau _a} \right) \), such that
$$\begin{aligned} {\mathbb {E}}\bigl ( {v}^{\tau _a}; J_{\tau _a} \bigr ) = \widetilde{{\textbf {G}}}_{v}^{a}, \quad \widetilde{{\textbf {G}}}_{v} = {\mathbb {E}}\bigl ( {v}^{\tau _1}; J_{\tau _1} \bigr ), \end{aligned}$$(3.3)and \(\widetilde{{\textbf {G}}}_{v}\) is the right solution of \(\widetilde{{\textbf {F}}}(\cdot ) = {v}^{-1}{} {\textbf {I}}\).
-
(iv)
As discussed in [15], the right solutions of the above equations cannot be determined analytically except in some special cases. However, there exist a number of numerical algorithms which can be employed, e.g. the iterative algorithm [21], logarithmic reduction [20] and the cyclic reduction [6], to name a few. For further details on the variety of algorithms available for solving such equations, see [7] and references therein.
3.2 Two-Sided Exit Upward - \(\{ \tau _a^+ < \tau _{-b}^-\}\)
Within the literature of spectrally negative Lévy processes and their fully discrete counterparts [3], the common approach to solving two-sided exit problems relies on the introduction of a family of functions, \(W^q\) and \(Z^q\), known as the q-scale functions (see [18] for details). The extension of these auxiliary, one-dimensional scale functions to the multidimensional MAP setting was first proposed in [19], where the existence of the corresponding ‘scale matrices’ was shown and were further investigated in [14] who derived their probabilistic interpretation within the continuous setting.
For \({v} \in (0, 1]\), the discrete \(\widetilde{{\textbf {W}}}_{v}\) scale matrix is defined as the mapping \(\widetilde{{\textbf {W}}}_{v}: {\mathbb {N}} \rightarrow {\mathbb {R}}^{N \times N}\), with \(\widetilde{{\textbf {W}}}_{v}(0) = {\textbf {0}}\) (the matrix of zeros), such that
where we write \(\widetilde{{\textbf {W}}}_1(n) =: \widetilde{{\textbf {W}}}(n)\) for the 1-scale matrix. The definition of the scale matrix above is only unique up to a multiplicative constant and the presence of the infinite-time occupation matrix, \(\widetilde{{\textbf {L}}}_{v}\), is somewhat arbitrary here but is included in order to obtain the most concise form for the p.g.m. of \(\widetilde{{\textbf {W}}}_{v}(\cdot )\), which is derived in Theorem 2 (see also [14]).
In the two-sided exit problem, we are interested in the time of exiting a (fixed) ‘strip’, \([-b,a]\), consisting of an upper and lower level denoted by a and \(-b\), respectively, such that \(a> 0 > -b\). More formally, we are interested in the events \(\{ \tau _a^+ < \tau _{-b}^-\,\}\) and \(\{ \tau _a^+ > \tau _{-b}^-\,\}\), which correspond to the upward and downward exits from the strip \([-b,a]\), respectively. In this section, we are concerned with the former (upward exit). The latter (downward exit) will be discussed in a later section as its derivation depends on alternative methods.
Let us denote by \(\rho (\cdot )\), the spectral radius of a matrix. That is, if \(\Lambda ({\textbf {A}})\) denotes the spectrum of a matrix \({\textbf {A}}\), then \(\rho \left( {\textbf {A}}\right) = \max \{ |\lambda _i|: \lambda _i \in \Lambda ({\textbf {A}})\}\).
3.2.1 Two-Sided Exit Theory for Non-singular \(\widetilde{{\textbf {A}}}_1\)
Theorem 2
Assume that \(\widetilde{{\textbf {A}}}_1\) is non-singular. Then, there exists a matrix \(\widetilde{{\textbf {W}}}: {\mathbb {N}} \rightarrow {\mathbb {R}}^{N\times N}\) with \(\widetilde{{\textbf {W}}}(0) = {\textbf {0}}\), which is invertible and satisfies
where \(\bigl ({\mathbb {P}}\bigl ( \tau ^+_a< \tau ^-_{-b}\,, J_{\tau ^+_a} \bigr )\bigr )_{ij}={\mathbb {P}}\bigl ( \tau ^+_a < \tau ^-_{-b}\,, J_{\tau ^+_a}=j|J_0=i \bigr )\) and \(\widetilde{{\textbf {W}}}(\cdot )\) has representation
Furthermore, it holds that
for \(z \in (0, 1]\) such that \(z\notin \Lambda (\widetilde{{\textbf {G}}})\), and
where \(\widetilde{{\textbf {L}}}^+(n):= {\mathbb {E}}\left[ \widetilde{{\textbf {L}}}\left( 0, \tau _{n}\right) \right] \), denotes the expected number of times the process visits 0 before hitting level \(n \in {\mathbb {N}}^+\).
Proof
Following the same line of logic as in [14], we note that the events \(\{ \tau _a^+ < \tau _{-b}^-\}\) and \(\{ \tau _{ a}< \tau _{- b}\}\) are equivalent due to the upward skip-free property of \(\{X_n\}_{n \geqslant 0}\). This follows from the fact that in order to drop below \(-b\) and then hit a, the process must visit \(-b\) on the way. Thus, conditioning on possible events and employing the Markov additive property, we obtain
and
Now, by recalling that \({\mathbb {P}}\bigl (\tau _a < \infty , J_{\tau _{a}} \bigr )=\widetilde{{\textbf {G}}}^a\), solving the second equation w.r.t. \({\mathbb {P}}\bigl (\tau _{ a}> \tau _{ -b}, J_{\tau _{-b}} \bigr ) \) and substituting the resulting equation into the first, yields
Finally, by multiplying through by \(-\widetilde{{\textbf {G}}}^{-(a+b)}\) on the right, we have
or equivalently
given that \(\widetilde{{\textbf {W}}}(\cdot )^{-1}\) exists (see Remark 7). Note that the above result is derived in the absence of the occupation mass matrix, \(\widetilde{{\textbf {L}}}\), within the definition of \(\widetilde{{\textbf {W}}}(n)\), reinforcing the point that the scale matrix is uniquely defined up to a (matrix) multiplicative constant. The choice for including \(\widetilde{{\textbf {L}}}\) in the definition of \(\widetilde{{\textbf {W}}}(n)\), which is only well defined as long as \(\widetilde{{\textbf {L}}}\) has finite entries (see Remark 3 for conditions), will become apparent in the following.
To prove Eq. (3.7), let us take the transform of the scale matrix and recall the definition given in Eq. (3.6), to obtain
where the first term on the r.h.s. satisfies
for all \(z \in (0, \gamma )\), where \(\gamma := \min \{|\lambda _i|: \lambda _i \in \Lambda (\widetilde{{\textbf {G}}})\}\).
For the second term of Eq. (3.10), under the conditions of Theorem 1, we have
for all \(z \in (0,1]\) such that \(\bigl ({\textbf {I}} - \widetilde{{\textbf {F}}}(z) \bigr ) ^{-1}\) exists. Moreover, for \(z \in (\rho (\widetilde{{\textbf {G}}}), 1]\) (\(\rho (\widetilde{{\textbf {G}}}) < 1 \) is true as long as \(\widetilde{{\textbf {G}}}\) is invertible and this follows from the assumption that the matrix \(\widetilde{{\textbf {A}}}_1\) is non-singular, see also Remark 7 ), the geometric series on the r.h.s. converges and the above equation can be rewritten as
once we prove a common domain of convergence, i.e. \(\bigl ({\textbf {I}} - \widetilde{{\textbf {F}}}(z) \bigr ) ^{-1}\) exists for some \(z \in (\rho (\widetilde{{\textbf {G}}}), 1]\). In fact, for \(\rho (\widetilde{{\textbf {G}}}) < 1 \), see Lemma 4 in [8], it can be shown that the zeros of \(\det [{\textbf {I}} - \widetilde{{\textbf {F}}}(z)]\) coincide with the eigenvalues of \(\widetilde{{\textbf {G}}}\) for \(z \in (0,1]\) and thus, the above holds.
Now, note that if we multiply Eq. (3.12) from the left by \({\textbf {I}} - z \widetilde{{\textbf {G}}}^{-1} \) and from the right by \({\textbf {I}} - \widetilde{{\textbf {F}}}(z)\), then both sides of the resulting equation are analytic for \(z\in (0,1]\). Hence, since the matrices \(\bigl ( {\textbf {I}} - z \widetilde{{\textbf {G}}}^{-1} \bigr )\) and \(\bigl ({\textbf {I}} - \widetilde{{\textbf {F}}}(z)\bigr )\) are invertible as long as \(z \notin \Lambda (\widetilde{{\textbf {G}}})\) and thus for \(z \in (0, \gamma )\), the aforementioned multiplication can be reversed and Eq. (3.12) holds for \(z \in (0,\gamma )\) by analytic continuation. The result follows by substituting the above equation, along with Eq. (3.11), into Eq. (3.10) and using analytic continuation to extend the domain from \(z \in (0,\gamma )\) to \(z \in (0,1]\) such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\).
To prove Eq. (3.8), we use similar arguments to those used for the result of Proposition 1, to show that for \(n \geqslant 0\)
where \(\widetilde{{\textbf {L}}}^+(n): = {\mathbb {E}}\bigl (\widetilde{{\textbf {L}}}(0, \tau _{n})\bigr )\), from which it follows that
Multiplying this expression through by \(\widetilde{{\textbf {G}}}^{-n}\) (on the left) and recalling the form of \(\widetilde{{\textbf {W}}}(n)\) given in Eq. (3.6), the result follows immediately. So far we assume only that \(\rho (\widetilde{{\textbf {G}}}) < 1 \), hence by Remark 4 that either \(v<1\) or that \(v=1\) and \(\kappa ^\prime (0)>0\). To handle the remaining (limiting) case of \(v=1\) and \(\kappa ^\prime (0)\le 0\), we can follow the proof of Theorem 1 in [14]. Namely we can use the representation (3.8) of the scale function, take \( v \rightarrow 1\) and observe that matrices \(\widetilde{{\textbf {G}}}\), \(\widetilde{{\textbf {L}}}^+(n)\) and \(\widetilde{{\textbf {F}}}(z)\) properly converge. \(\square \)
Remark 6
In [15], the authors derive an equivalent result to Theorem 2 for a continuous-time MAP in the lattice and non-lattice case. Although their study focuses purely on the continuous-time case, they do point out the connection for the discrete-time model (Remark 6 in [15]) but do not provide any proof or further details.
Remark 7
(Invertibility of \(\widetilde{{\textbf {L}}}^+(n)\), \(\widetilde{{\textbf {G}}}\) and \(\widetilde{{\textbf {W}}}(n)\)) Throughout the proof of the previous theorem and results earlier in this paper, we required invertibility of the fundamental matrix \(\widetilde{{\textbf {G}}}\) and the scale matrix \(\widetilde{{\textbf {W}}}(n)\). We will now look at under what conditions such invertibility holds:
-
(i)
Following similar arguments as in [15], since the level process starts at \(X_0 =0\), the expected number of visits at 0 before the process reaches level \(n\geqslant 0\), namely \(\widetilde{{\textbf {L}}}^+(n)={\mathbb {E}}\bigl [\widetilde{{\textbf {L}}}(0,\tau _{n})\bigr ]\), satisfies
$$\begin{aligned} \widetilde{{\textbf {L}}}^+(n)={\textbf {I}}+{\varvec{\Pi }}_n\,\widetilde{{\textbf {L}}}^+(n), \end{aligned}$$where \({\varvec{\Pi }}_n\) is a probability matrix with i, j-th element containing the probability of a second visit to level 0 before reaching level n and doing so in phase j, conditioned on the starting point (0, i). Note that \({\varvec{\Pi }}_n\) is clearly a sub-stochastic, non-negative matrix, which implies \(\rho \bigl ({\varvec{\Pi }}_n\bigr )<1\) and thus \({\textbf {I}}-{\varvec{\Pi }}_n\) is invertible. Hence, \(\widetilde{{\textbf {L}}}^+(n)\) is also invertible, since from the above expression it follows that \(\left( {\textbf {I}} - {\varvec{\Pi }}_n\right) \widetilde{{\textbf {L}}}^+(n)={\textbf {I}}\).
-
(ii)
In order to show that \(\widetilde{{\textbf {G}}}\) is invertible, recall that
$$\begin{aligned} \widetilde{{\textbf {G}}} = \sum _{m=-1}^\infty \widetilde{{\textbf {A}}}_{-m} \widetilde{{\textbf {G}}}^{m+1} =\widetilde{{\textbf {A}}}_{1} +\sum _{m=0}^\infty \widetilde{{\textbf {A}}}_{-m} \widetilde{{\textbf {G}}}^{m+1}, \end{aligned}$$from which it follows that
$$\begin{aligned} \widetilde{{\textbf {A}}}_{1} =\widetilde{{\textbf {G}}}- \sum _{m=0}^\infty \widetilde{{\textbf {A}}}_{-m} \widetilde{{\textbf {G}}}^{m+1}&=\Bigl ({\textbf {I}}-\sum _{m=0}^\infty \widetilde{{\textbf {A}}}_{-m} \widetilde{{\textbf {G}}}^{m}\Bigr ){\textbf {G}}=\Bigl ({\textbf {I}}-{\varvec{\Pi }}_1\Bigr ){\textbf {G}} \end{aligned}$$Therefore, since \({\textbf {I}}-{\varvec{\Pi }}_1\) is invertible, \(\widetilde{{\textbf {G}}}\) is invertible provided that \(\widetilde{{\textbf {A}}}_{1}\) is invertible. Finally, since \(\widetilde{{\textbf {L}}}^+(n)\) is invertible and given \(\widetilde{{\textbf {G}}}\) is invertible, then by Eq. (3.8) it is clear that \(\widetilde{{\textbf {W}}}(n)\) is also invertible.
Although Theorem 2 provides a number of representations for \(\widetilde{{\textbf {W}}}\), in the discrete case the scale matrix also satisfies a recursive relation. The recursion below generalises the recursion for the scale function derived in [3] and has also been discussed in [15].
Corollary 1
For \(b\geqslant 1\), the scale matrix \(\widetilde{{\textbf {W}}}(\cdot )\), defined in Theorem 2, satisfies the following recursive equation
with \(\widetilde{{\textbf {W}}}(1)=\widetilde{{\textbf {A}}}_1^{-1}\).
Proof
To prove the recursive relation, consider the two-sided hitting probability \({\mathbb {P}}\bigl (\tau _a^+ < \tau _{-b}^-; J_{\tau ^+_a} \bigr )\) and condition on the first time step. Then, for \(a,b \geqslant 1\), we have
where the last equality follows from the Markov additive property. Further, using Theorem 2 and multiplying on the right by \(\widetilde{{\textbf {W}}}(a+b)\), the above expression can be rewritten as
and the recursive expression given in Eq. (3.14) follows directly after some basic algebraic manipulations. For \(\widetilde{{\textbf {W}}}(1)\), recall Remark 7 that \(\widetilde{{\textbf {L}}}^+(1)=({\textbf {I}}-{\varvec{\Pi }}_1)^{-1} \) and also that \(\widetilde{{\textbf {A}}}_{1}^{-1} =\widetilde{{\textbf {G}}} ^{-1}({\textbf {I}}-{\varvec{\Pi }}_1)^{-1}=\widetilde{{\textbf {G}}} ^{-1}\widetilde{{\textbf {L}}}^+(1)=\widetilde{{\textbf {W}}}(1) \), from Theorem 2. \(\square \)
Remark 8
Under the same line of logic as Remark 5, we recall that the above results are more general than explicitly stated. For example, by superimposing killing Eq. (3.5) is equivalent to
for \(v \in (0,1]\), where \(\widetilde{{\textbf {W}}}_v(\cdot )\) is defined in Eq. (3.4) with the rest of the results amended accordingly.
3.2.2 Two-Sided Exit Theory for Arbitrary \(\widetilde{{\textbf {A}}}_1\)
In Theorem 2, we rely on the fact that \(\widetilde{{\textbf {A}}}_1\) is non-singular, which in turn ensures \(\widetilde{{\textbf {G}}}\) is non-singular by Remark 7. However, it turns out that a similar result can also be derived for arbitrary \(\widetilde{{\textbf {A}}}_1\) in terms of matrices closely related to the \(\widetilde{{\textbf {W}}}\) scale matrix.
To see this, let us define \(\widetilde{{\textbf {L}}}^-(n): = {\mathbb {E}}\bigl (\widetilde{{\textbf {L}}}\left( 0, \tau _{-n}\right) \bigr )\) for \(n \geqslant 0\), \(\widetilde{{\textbf {M}}}(n):={\mathbb {E}}\bigl (\widetilde{{\textbf {L}}}\left( -n, \tau _{-(n+1)}\right) \bigr )\) and recall \(\widetilde{{\textbf {R}}}\) is related to the ‘time-reversed’ counterpart of \(\widetilde{{\textbf {G}}}\) (see Remark 5). Then, we have the following theorem.
Theorem 3
Assume the matrix \(\widetilde{{\textbf {A}}}_{1}\) is singular. Then, there exists a matrix \(\widetilde{{\textbf {V}}}: {\mathbb {N}} \rightarrow {\mathbb {R}}^{N\times N}\) with \(\widetilde{{\textbf {V}}}(0) = {\textbf {I}}\), which is invertible and satisfies
where
Furthermore, it holds that
and for \(z \in (0,1]\) such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\), also
Proof
Assume now that the matrix \(\widetilde{{\textbf {G}}}\) is singular (which, by Remark 7, is equivalent to the requirement that the matrix \(\widetilde{{\textbf {A}}}_{1}\) is singular). Then, from equation (3.9) we can obtain an alternative representation for the two-sided exit probability of the form
where
for \(n\geqslant 0\), as long as this matrix is invertible (see below). Moreover, by similar arguments as in Eq. (3.13), it follows that
or equivalently
Now, although we do not discuss in much details here the definition and probabilistic interpretation of the matrix \(\widetilde{{\textbf {R}}}\), [15] explain that the matrix \(\widetilde{{\textbf {R}}}^n\) comprises of i, j-th elements representing the expected number of visits to level \(n\geqslant 0\) in phase j before the first return to the level 0, given \(X_0=0\) and \(J_0=i\). Hence, using this interpretation, we observe that
and therefore, straightforward calculations show that Eq. (3.16) holds for \(\widetilde{{\textbf {V}}}(n) = \widetilde{{\textbf {L}}}^-(n)\) as long as this matrix is invertible for all \(n\geqslant 0\). Note that this can easily be verified by employing the same argument as in (i) of Remark 7 for \(n \leqslant 0\) and considering \(\varvec{\Pi }_{-n}\) instead of \(\varvec{\Pi }_n\).
To prove Eq. (3.17), we use similar arguments as [15] and employ the Markov property to obtain
and, in particular, \(\widetilde{{\textbf {L}}}^-(1) = \widetilde{{\textbf {M}}}(0)\), from which the result follows directly.
Finally, to prove the transform in Eq. (3.18), we again follow the methodology of [15] and first note that by conditioning on the first time period, for \(n \geqslant 1\), we have
whilst, for \(n=0\), it follows that
Taking transforms on both sides of Eq. (3.19) and noting the above expression for \(\widetilde{{\textbf {M}}}(0)\), after some algebraic manipulations (see Appendix), we obtain
where in the last equality we have use the probabilistic interpretation of \(\widetilde{{\textbf {R}}}\) to note that \(\widetilde{{\textbf {R}}} = \widetilde{{\textbf {A}}}_1 \widetilde{{\textbf {L}}}^-(1) = \widetilde{{\textbf {A}}}_1 \widetilde{{\textbf {M}}}(0)\). The result follows directly by solving the above expression for the transform and holds as long as \({\textbf {I}}-\widetilde{{\textbf {F}}}(z)\) is invertible. \(\square \)
Although the result of Theorem 3 is clearly more general than that of Theorem 2, as it does not require invertibility of \(\widetilde{{\textbf {A}}}_1\), it deviates from the well-known form and methodology of scale matrices (functions) seen throughout the literature. As such, since the purpose of this paper is to demonstrate and derive the fully discrete analogue of the well-known ‘scale theory’ for MACs, we will assume the invertibility of \(\widetilde{{\textbf {A}}}_1\) throughout the rest of this paper but point out that all the following results could also be generalised to the arbitrary case (see [15] for more details of such results in the continuous-time setting).
At this point, it is natural to consider the corresponding downward exit problems (one and two-sided). However, in order to do this we must first discuss some fluctuation problems for the associated ‘reflected’ MAC process which is discussed in the following section.
4 Exit Problems For Reflected MACs
In this section, we deviate from the basic MAC described above and consider the associated two-sided reflection of the process \(\{X_n\}_{n \geqslant 0}\) with respect to a strip \([-d, 0]\) with \(d > 0\). The choice of strip is purely for notational convenience and can easily be converted to the general strip \([-b,a]\) by shifting the process appropriately. The main result of this section is given in Theorem 4 which is interesting in its own right, but is also used to derive the aforementioned downward exit problems of the original (un-reflected) MAC.
Following the same line of logic as in [14], let us define the reflected process by
where \(R^-_n\) and \(R^+_n\) are known as regulators for the reflected process at the barriers \(-d\) and 0, respectively, which ensure that the process \(\{H_n\}_{n \geqslant 0}\) remains within the strip \([-d,0]\) for all \(n \in {\mathbb {N}}\). Note that in continuous-time and space, the reflected process \(\{H_n\}_{n \geqslant 0}\) corresponds to the solution of the so-called Skorohod problem (see [17]). By the construction of \(\{H_n\}_{n \geqslant 0}\), it is clear that \(\{R^-_n\}_{n \geqslant 0}\) and \(\{R^+_n\}_{n \geqslant 0}\) are both non-decreasing processes, with \(R^-_0 = R^+_0 = 0\), when \(X_0\) in \([-d,0]\), which only increase during periods when \(H_n = -d\) and \(H_n = 0\), respectively. Moreover, since \(\{X_n\}_{n \geqslant 0} \) is ‘spectrally negative’ the upward regulator \(\{R^+_n\}_{n \geqslant 0}\) increases by at most one per unit time.
Now, let us denote by \(\rho _k\), the right inverse of the regulator \(\{R^+_n\}_{n \geqslant 0}\), defined by
such that \(R^+_{\rho _k} = k + 1\). Then, since an increase in \(\{R^+_n\}_{n \geqslant 0}\) only occurs whilst \(H_n = 0\), it follows that \(H_{\rho _k} = 0\) and thus, \(R^-_{\rho _k} = (k+1) - X_{\rho _k}\). Hence, by the strong Markov property of \(\{X_n\}_{n \geqslant 0}\), we have that \(\left\{ \left( R^-_{\rho _k}, J_{\rho _k} \right) \right\} _{k \geqslant 0}\) is itself a MAC with random initial position \((R^-_{\rho _0}, J_{\rho _0})\) when \(X_0 \in [-d,0]\) and non-negative jumps within the level process \(\{R^-_{\rho _k}\}_{k \geqslant 0}\). Thus, in a similar way as for the original MAC (X, J), we can define its p.g.m. , given \(X_0 = 0\), by
Remark 9
In the continuous case, \(X_0 = 0\) is a regular point on \((0, \infty )\) and thus, it follows that \(\rho _{_0} = 0\) a.s. and thus \({\mathbb {E}} \bigl ( z^{R^-_{\rho _{_0}}}; J_{\rho _{_0}} \bigr ) = {\textbf {I}}\) (see [14] for details). However, in the fully discrete set-up, we have already mentioned that \(R^-_{\rho _0}\) is random for \(X_0=0\) and is due to the possibility of the process experiencing a negative jump in the first time period such that \(\rho _{_0} \ne 0\). Moreover, the process may drop below the lower level \(-d\) (resulting in a jump in \(\{R^-_n\}_{n \geqslant 0}\)) before the stopping time \(\rho _{_0}\), and justifies the choice of the p.g.m. \({\mathbb {E}} \bigl ( z^{R^-_{\rho _{_0}}}; J_{\rho _{_0}} \bigr )\) above, compared to \({\mathbb {E}} \bigl ( z^{R^-_{\rho _{_1}}}; J_{\rho _{_1}} \bigr )\) in the continuous case (see [14]). On the other hand, we note that if \(X_0=1\), then \({\mathbb {E}} _1\bigl ( z^{R^-_{\rho _{0}}}; J_{\rho _{0}} \bigr )={\textbf {I}}\), since \(R^+_0=1\), and thus \(\rho _0=0\). The latter observation will play a crucial role in analysing the distribution of \((R^-_{\rho _0}, J_{\rho _0})\), which is given in the following theorem in terms of the second v-scale matrix, denoted \(\widetilde{{\textbf {Z}}}_{v}\), and defined for \(z \in (0,1]\) and \(v \in (0,1]\), by
with \(\widetilde{{\textbf {Z}}}_v(z, 0) = {\textbf {I}}\), for all \(z \in (0,1]\) and \(v \in (0,1]\) and \(\widetilde{{\textbf {Z}}}_1(z,n) =: \widetilde{{\textbf {Z}}}(z, n)\).
Theorem 4
For \(z \in (0,1]\), such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\), and \(x \in [-d,1]\) it holds that \(\widetilde{{\textbf {Z}}}(z, d+1)\) is invertible and
where \(\widetilde{{\textbf {Z}}}(z, n)\) is defined by Eq. (4.3).
Proof
The proof of this theorem actually follows a similar line of logic as the proof of Theorem 1; however, due to the nature of the reflected process, the calculations require greater attention.
First note that since \(H_{\rho _{k}} = 0\) for each \(k \in {\mathbb {N}}\), we have \(X_{\rho _{k}} = k+1-R^-_{\rho _{k}}\) and thus \(\{(X_{\rho _k}, J_{\rho _k})\}_{k \geqslant 0}\) is a MAC having unit (upward) drift and downward jumps described by \(\{R^-_{\rho _k}\}_{k \geqslant 0}\) with random ‘initial’ position \(X_{\rho _0} = 1 - R^-_{\rho _0}\). Moreover, its occupation mass in the bivariate state \((y,j) \in {\mathbb {Z}} \times E\) is defined by \({\widetilde{L}}^*(y,j,\infty ) = \sum _{k = 0}^\infty 1_{\left( X_{\rho _k} = y, J_{\rho _k}=j\right) } \) and thus, from the occupation mass formula in Eq. (2.5), we have
Taking expectations on both sides of this expression, conditioned on the initial state \(X_0 = x \in [-d, 1]\), and writing in matrix form yields
where \(\widetilde{{\textbf {L}}}_x^*(m,\infty )\) is the infinite-time occupation matrix with i, j-th element given by
\(\bigl (\widetilde{{\textbf {L}}}_x^*(m,\infty )\bigr )_{ij} = {\mathbb {E}}_x\bigl ( {\widetilde{L}}^*(m,j,\infty ) \mid J_0 = i\bigr )\).
Let us now treat the left-hand side and right-hand side of Eq. (4.5) separately. Firstly, using the fact that \(X_{\rho _{k}} = k+1-R^-_{\rho _{k}}\), along with the strong Markov and Markov additive properties of \(\{R^-_{\rho _k}\}_{k \geqslant 0}\), the l.h.s. of Eq. (4.5) can be rewritten in the form
for all \(z \in (0,1]\) such that \(z > (\rho (\widetilde{{\textbf {F}}}^*(z))\). We note that since \(\{(X_{\rho _k}, J_{\rho _k})\}_{k \geqslant 0}\) is a MAC, it holds that \({\mathbb {E}}(z^{-X_{\rho _k}};J_{\rho _k})=\bigl ({\mathbb {E}}(z^{-X_{\rho _0}};J_{\rho _0})\bigr )^{k+1}\). Now, let us define \({\overline{\tau }}_1=\inf \{ \rho _k\geqslant 0:X_{\rho _k}=1\}\) and \(\overline{{\textbf {G}}}\) to be the probability transition matrix such that \({\mathbb {P}}({\overline{\tau }}_1 < \infty , J_{{\overline{\tau }}_1})=\overline{{\textbf {G}}}\), which is sub-stochastic, (implying \(\rho (\overline{{\textbf {G}}}) < 1\)) in the case of killing or no killing and negative drift. Then, based on similar arguments as those discussed in the proof of Theorem 2, since the eigenvalues of \(\overline{{\textbf {G}}}\) coincide with the roots of \({\textbf {I}}- {\mathbb {E}}(z^{-X_{\rho _0}};J_{\rho _0})=({\textbf {I}} -z^{-1} \widetilde{{\textbf {F}}}^*(z))\), then we conclude that \({\textbf {I}} -z^{-1} \widetilde{{\textbf {F}}}^*(z)\) is invertible for \(z \in (\rho (\overline{{\textbf {G}}}),1]\). In fact, since \(\{X_n\}_{n \geqslant 0}\) is an upward skip-free process, it follows that \({\overline{\tau }}_1=\tau _1\) for \(X_0 \in [-d,1]\), which implies \(\overline{{\textbf {G}}}=\widetilde{{\textbf {G}}}\), and thus \({\textbf {I}} -z^{-1} \widetilde{{\textbf {F}}}^*(z)\) is invertible for \(z \in (\rho (\widetilde{{\textbf {G}}}), 1]\). Hence, by applying the same analytic continuation argument as in Theorem 2, the above expression holds for \(z\in (\rho (\widetilde{{\textbf {G}}}),1)\).
Now, for the r.h.s. of Eq. (4.5), let us introduce the matrix quantity \(\widetilde{{\textbf {C}}}_{-y}\) whose individual i, j-th elements denote the probability of the process \(\{X_n\}_{n \geqslant 0}\) first hitting some level \(-y < 0 \) from initial states \(X_0 = 0\) and \(J_0 = i\), and then hitting the upper level \((d+1) - y\) whilst \(J_n = j\), such that
Using this quantity, it is possible to show that for \(X_0 = x \in [-d,1]\)
To see this, note that \({\widetilde{L}}^*(m,j,\infty )\) corresponds to the (local) time points \(\rho _k\) (increases in \(\{R^+_n\}_{n \geqslant 0}\)) such that \(X_{\rho _k} = m\) and \(J_{\rho _k} = j\), or alternatively, time points \(k \geqslant 0\) for which \(\{R^+_n\}_{n \geqslant 0}\) is increasing and \(X_k = m\) and \(J_k = j\). Then, for \(m > 0\), the first increase of \({\widetilde{L}}^*(m,j,\infty )\) is at \(\tau _m\), otherwise, for \(m \leqslant 0\), \(\{X_n\}_{n \geqslant 0}\) has to first visit the state (level) \(m-(d+1)\) to ensure that at the next time the process \(\{X_n\}_{n \geqslant 0}\) visits the level \(m < 0\), the ‘reflected process’ \(\{H_n\}_{n \geqslant 0}\) was at its upper boundary in the previous time period (\(H_{n-1} = 0\)), resulting in an increase of \(\{R^+_n\}_{n \geqslant 0}\). Every subsequent increase of \({\widetilde{L}}^*(m,j,\infty )\) is obtained in a similar way. Thus, the above equation follows by application of the strong Markov and Markov additive properties.
Taking transforms on both sides of the above equation, it yields
where we have used the fact that \(\sum _{k =0}^\infty \bigl (\widetilde{{\textbf {C}}}_{-(d+1)}\bigr )^k = \bigl ({\textbf {I}} - \widetilde{{\textbf {C}}}_{-(d+1)}\bigr )^{-1}\) in the presence of killing, since \( \widetilde{{\textbf {C}}}_{-(d+1)}\) is a sub-stochastic matrix and thus, its Perron–Frobenius eigenvalue is less than 1. Now, the first term inside the brackets of the last expression is clearly equivalent to \(-\bigl ( {\textbf {I}} - z\widetilde{{\textbf {G}}}^{-1}\bigr )^{-1}\widetilde{{\textbf {G}}}^{-x}\) for all \(z \in (\rho (\widetilde{{\textbf {G}}}), 1]\), whilst by the change of variable \(k = m - (d+1) - x\), the second term within the brackets becomes
and thus, after some algebraic manipulations (see Appendix), Eq.(4.8) can be rewritten as
where \(\widetilde{{\textbf {Z}}}(z, n)\) is defined in Eq. (4.3). Finally, by combining Eqs. (4.6) and (4.9), we obtain for \(z \in (\rho ( \widetilde{{\textbf {G}}}),1)\)
To complete the proof, it remains to determine the form of the matrix \(\widetilde{{\textbf {F}}}^*(z)\). To do this, let \(x = 1\) into the above expression which, after using the fact that \({\mathbb {E}}_1\bigl (z^{R^-_{\rho _{_0}}}; J_{\rho _{_0}} \bigr )={\textbf {I}}\) since in this case \(\rho _0 = 1\) and taking inverses on both sides, gives
Note that this expression shows that \( \widetilde{{\textbf {Z}}}(z, d+1)\) is an invertible matrix as long as \(\widetilde{{\textbf {W}}}(d+1)\) is invertible and after solving w.r.t. \(\widetilde{{\textbf {F}}}^*(z)\) also gives
The result follows by substituting the above expression for \(\widetilde{{\textbf {F}}}^*(z)\) back into Eq. (4.10), re-arranging and employing analytic continuation in a similar way as previous.
\(\square \)
Remark 10
We point out that setting \(X_0=x=0\) in the result of Theorem 4, gives an equivalent representation for \(\widetilde{{\textbf {F}}}^*(z)\) in terms of the \(\widetilde{{\textbf {Z}}}\) scale matrix only, i.e.
Moreover, we note that based on its definition, it is also possible to use the recursive relation of \(\widetilde{{\textbf {W}}}(\cdot )\), given in Corollary 1, to obtain explicit values of \(\widetilde{{\textbf {Z}}}(z, \cdot )\).
Although the result of Theorem 4 is interesting in its own right, its main importance in this paper is as a stepping stone for proving a similar result for the associated one-sided reflected process (see Sect. 4.1 below) and consequently, the two-sided and one-sided (as a limiting case) downward exit problems for the original (non-reflected) MAC.
4.1 One-Sided Reflection
As discussed in the previous section, the downward exit problems can be solved using an auxiliary result for the one-sided (lower) reflected process. As such, let us define
where \(R^{-b}_n = -b-(-b \wedge {\underline{X}}_n)\) with \({\underline{X}}_n = \inf _{k \leqslant n} \{X_k\}\), denotes a lower reflecting barrier at the level \(-b \leqslant 0\). Note that this is equivalent to shifting the two-sided reflected process of the previous section and letting the upper reflecting barrier tend to infinity. Then, by direct application of Theorem 4 we get the following corollary.
Corollary 2
For \(X_0 = 0\), \(z \in (0,1]\) such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\), \(a > 0\) and \(b \geqslant 0\), it holds that
Proof
Note that if we set \(d = (a-1)+b\) in Theorem 4, then \(\{(H_n + (a-1), R^-_n)\}_{n \geqslant 0}\) up to time \(\rho _{_0}\) coincides with \(\{(Y_n, R^{-b}_n)\}_{n \geqslant 0}\) up to time \(\tau _{a}\), given that \(H_0 + (a-1) = Y_0\). Hence, the result follows directly from Theorem 4 with \(x = -(a-1)\). \(\square \)
5 Downward Exit Problems
For the one and two-sided downward exit problems, we are interested in the events \(\{\tau ^-_{-b} < \infty \}\) and \(\{ \tau _{-b}^- < \tau ^+_a\}\), respectively. Unlike the upward exit, due to the possibility of downward jumps in the MAC, the stopping time \(\tau ^-_{-b}\) is not necessarily equivalent to the first hitting time of the level \(-b < 0\), i.e. \(\tau ^-_{-b} \ne \tau _{-b}\). It is for this reason that we cannot employ the Markov type structure seen for the upward exit identities and, instead, rely on the results of the reflected processes of the previous section.
Although it would appear easier to derive in the first instance, it turns out that the one-sided downward exit problem can easily be obtained as a limiting case of the related two-sided case and as such, is considered in the following.
5.1 Two-Sided Exit Downward - \(\{ \tau _{-b}^- < \tau _a^+\}\)
For the two-sided downward exit problem, we are interested in the time of exiting the fixed ‘strip’, \([-b,a]\), such that \(\{ \tau _{-b}^- < \tau ^+_a\}\). Using the result for the transform of the downward regulator for the one-sided reflected process, we obtain the following corollary.
Corollary 3
For \(z \in [0,1]\) such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\), it holds that for any \(a,b > 0\), we have
Proof
Consider the one-sided reflected process of Sect. 4.1. Then, by the strong Markov and Markov additive properties, it follows that for \(b > 0\), we have
Re-arranging this expression and using the identities of Theorem 2 and Corollary 2 the result follows immediately. \(\square \)
5.2 One-Sided Exit Downward
For the one-sided exit problem, we are now interested in the event that of down-crossing the level \(-b < 0\), whilst the upward movement of the MAC is unrestricted, i.e. \(\{\tau ^-_{-b} < \infty \}\) which, as already mentioned, can be viewed as a limiting case of the corresponding two-sided problem as \(a \rightarrow \infty \). In fact, this is the argument used to obtain the following one-sided downward exit identity.
Corollary 4
Assume we are not in the case of no killing and zero drift, i.e. it is not true that both \(v = 1\) and \(\kappa '(1) = 0\). Then, \(\widetilde{{\textbf {L}}}\) is invertible and, for \(z \in (0,1]\) such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\) and \(b > 0\), we have
Proof
Firstly, the invertibility of \(\widetilde{{\textbf {L}}}\) follows from Remark 3, for which it cannot hold that both \(v=1\) and \(\kappa '(1) = 0\). On the other hand, Eq. (5.2) follows from taking the limit of the two-sided case (see Corollary 3) as the upper barrier tends to infinity, i.e. \(a \rightarrow \infty \). In order to evaluate the value of the limit of \(\widetilde{{\textbf {W}}}(b)\widetilde{{\textbf {W}}}(a+b)^{-1}\widetilde{{\textbf {Z}}}(z, a+b-1)\) as \(a \rightarrow \infty \), note that by the definition of the scale matrix \(\widetilde{{\textbf {Z}}}(z, n)\), and using Eq. (3.7), it follows that
Moreover, by using the fact that \(\widetilde{{\textbf {W}}}(n) = \widetilde{{\textbf {G}}}^{-n} \widetilde{{\textbf {L}}}(n)\) (see Theorem 2), multiplication of the above expression by \(\widetilde{{\textbf {W}}}(a+b)^{-1}\) on the left yields
which, after taking \(a \rightarrow \infty \) and using dominated convergence theorem, gives
for \(z \in (0, \gamma )\), where \(\widetilde{{\textbf {L}}}\) is the infinite-time occupation mass matrix defined in Proposition 1. Finally, by analytic continuation, it can be shown that the above holds for all \(z \in (0,1]\) such that \(z \notin \Lambda (\widetilde{{\textbf {G}}})\) and thus, by taking the limit as \(a \rightarrow \infty \) in Corollary 3, using the above expressions and re-arranging, we obtain the result. \(\square \)
Remark 11
We point out once again that by explicitly imposing killing, Corollary 3 and consequently Corollary 4 equivalently yield the following joint transforms for \(v \in (0,1]\)
and
where \(\widetilde{{\textbf {W}}}_v(\cdot )\) and \(\widetilde{{\textbf {Z}}}_v(z, \cdot )\) are defined as in Eqs. (3.4) and (4.3), respectively.
Data availability
Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
References
Asmussen, S.: Applied Probability and Queues. Springer-Verlag, 2nd Edition (2003)
Asmussen, S., Albrecher, H.: Ruin Probabilities. World Scientific, Volume 14 (2010)
Avram, F., Vidmar, M.: First passage problems for upward skip-free random walks via the scale functions paradigm. Adv. Appl. Probab. 51, 408–424 (2019)
Breuer, L.: First passage times for Markov additive processes with positive jumps of phase-type. J. Appl. Probab. 45, 779–799 (2018)
Bertoin, J.: Lévy Processes. Cambridge University Press (1996)
Bini, D., Meini, B.: On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems. Computations with Markov Chains, 21–28. Kluwer Academic Publishers (1995)
Bini, D., Meini, B., Latouche, G.: Numerical Methods for Structured Markov Chains. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford (2005)
D’Auria, B., Ivanovs, J., Kella, O., Mandjes, M.: First passage of a Markov additive process and generalized Jordan chains. J. Appl. Probab. 47(4), 1048–1057 (2016)
Dieker, A.B., Mandjes, M.: Extremes of Markov-additive processes with one-sided jumps, with queueing applications. Methodol. Comput. Appl. Probab. 13(2), 221–267 (2009)
Feller, W.: An Introduction to Probability Theory and its Applications, Vol. II, John Wiley (1971)
Gail, H.R., Hantler, S.L., Taylor, B.A.: Spectral analysis of M/G/1 and G/M/1 type Markov chains. Adv. Appl. Probab. 28(1), 114–165 (1996)
Gail, H.R., Hantler, S.L., Taylor, B.A.: Solutions of the basic matrix equation for M/G/1 and G/M/1 type Markov chains. Commun. Stat. Stoch. Models 10(1), 1–43 (1994)
Jacobsen, M.: Exit times for a class of random walks: exact and distribution results. J. Appl. Probab. 48A, 51–63 (2011)
Ivanovs, J., Palmowski, Z.: Occupation densities in solving exit problems for Markov additive processes and their reflections. Stoch. Process. Appl. 122, 3342–3360 (2012)
Ivanovs, J., Latouche, G., Taylor, P.: One-sided Markov additive processes with lattice and non-lattice increments. Preprint (2019)
Ivanovs, J., Mandjes, M.: First passage of time-reversible spectrally negative Markov additive processes. Oper. Res. Lett. 38(2), 77–81 (2010)
Kruk, Ł., Lehoczky, J., Ramanan, K., Shreve, S.: An explicit formula for the Skorohod map on [0, a]. Ann. Probab., 1740–1768 (2007)
Kyprianou, A.: Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin (2006)
Kypriannou, A., Palmowski, Z.: Fluctuations of Markov-additive processes. Séminaire de Probabilités, Lecture Notes in Mathematics vol,: Springer. Berlin 121–135, 2008 (1934)
Latouche, G., Ramaswami, V.: A logarithmic reduction algorithm for quasi-birth–death processes. J. Appl. Probab. 30(3), 650–674 (1993)
Neuts, M.: Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York (1989)
Neuts, M.: Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. The John Hopkins University Press (1981)
Acknowledgements
This work is partially supported by the National Science Centre under the Grant 2021/41/B/HS4/00599 (2022–2026). The authors are grateful to the anonymous referees for their constructive comments and suggestions that have improved the content and presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no conflicts of interest to declare that are relevant to the content of this article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
Proof of Eq. (3.21)
It follows from the results of Eq. (3.19) and (3.20), that
where, in the last equality, we have used the series definition of \(\widetilde{{\textbf {F}}}(z)\) given in Eq. (2.2). \(\square \)
Proof of Eq. (4.9)
To prove Eq. (4.9), first note that
Then, solving Eq. (3.12) w.r.t. \( \sum _{n=0}^\infty z^n {\mathbb {P}}\bigl (\tau _{-n}<\infty , J_{\tau _{-n}} \bigr )\widetilde{{\textbf {L}}}\) and substituting into the above equation, we have
Now, at this point, consider the definition of the scale matrix, \(\widetilde{{\textbf {W}}}(n)\), given in Eq. (3.6). Multiplying this expression through by \(z^n\) and summing from 0 to k on both sides, gives
and thus by equating the r.h.s. of Eqs. (A.2) and (A.3) and re-arranging, we obtain
which provides an expression for the second term of Eq. (4.8). Thus, letting \(k=d+x\) in the above expression and substituting into Eq. (4.8), we have that
Now, setting \(n=d+1\) in Eq. (3.6) and multiplying from the right by \(\widetilde{{\textbf {L}}}^{-1}\widetilde{{\textbf {G}}}^{d+1}\), yields
by the definition of \(\widetilde{{\textbf {C}}}_{-y}\) given in Eq. (4.7) and thus, it follows that
Finally, substituting the above equation into Eq. (A.5), we get that
where the last equation follows from the definition of the \(\widetilde{{\textbf {Z}}}\) scale matrix given in Eq. (4.3). \(\square \)
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Palmowski, Z., Ramsden, L. & Papaioannou, A.D. Exit Times for a Discrete Markov Additive Process. J Theor Probab 37, 1052–1078 (2024). https://doi.org/10.1007/s10959-024-01322-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10959-024-01322-8