Hitting probabilities of constrained random walks representing tandem networks

Abstract

Let $X$ be the constrained random walk on ${\mathbb{Z}}_{+}^d$ $d>2$, having increments $e_1$, $-e_i+e_{i+1}$ $i=1,2,3,...,d-1$ and $-e_d$ with probabilities $\lambda$, ${\mu }_1$, ${\mu }_2$,...,${\mu }_d$, where $\{e_1,e_2,..,e_d\}$ are the standard basis vectors. The process $X$ is assumed stable, i.e., $\lambda <{\mu }_i$ for all $i=1,2,3,...,d.$ Let ${\tau }_n$ be the first time the sum of the components of $X$ equals $n$. We derive approximation formulas for the probability ${\mathbb{P}}_x({\tau }_n<{\tau }_0)$. For $x\in {\bigcup }_{i=1}^d\{x\in {\mathbb{R}}_{+}^d:{\sum }_{j=1}^{i}x(j)$ $>\left(1-\frac{\log \lambda /\min {\mu }_i}{\log \lambda /{\mu }_i}\right)\}$ and a sequence of initial points $x_n/n\to x$ we show that the relative error of the approximation decays exponentially in $n$. The approximation formula is of the form ${\mathbb{P}}_y(\tau <\infty )$ where $\tau$ is the first time the sum of the components of a limit process $Y$ is $0$; $Y$ is the process $X$ as observed from a point on the exit boundary except that it is unconstrained in its first component (in particular $Y$ is an unstable process); $Y$ and ${\mathbb{P}}_y(\tau <\infty )$ arise naturally as the limit of an affine transformation of $X$ and the probability ${\mathbb{P}}_x({\tau }_n<{\tau }_0).$ The analysis of the relative error is based on a new construction of supermartingales. We derive an explicit formula for ${\mathbb{P}}_y(\tau <\infty )$ in terms of the ratios $\lambda /{\mu }_i$ which is based on the concepts of harmonic systems and their solutions and conjugate points on a characteristic surface associated with the process $Y$; the derivation of the formula assumes ${\mu }_i\ne {\mu }_j$ for $i\ne j.$

Sections 3,4 and 5 are revisions of Sections 5,6 and subsection 8.3 of arXiv:1506.08674. 7 Figures, 37 pages

References in corpus (4)

• Dynamic importance sampling for queueing networks
• Large deviations of a modified Jackson network: stability and rough asymptotics
• Martin boundary of a killed random walk on a quadrant
• Large Deviations Analysis for Distributed Algorithms in an Ergodic Markovian Environment