Hitting probabilities of constrained random walks representing tandem networks

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 Big{x in {mathbb R}^d_+: sum_{j=1}^{i} x(j)$ $> left(1 - frac{log lambda/min mu_i}{log lambda/mu_i}right) Big}$ and a sequence of initial points $x_n/n rightarrow 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 eq mu_j$ for $i eq j.$

Backward Stochastic Differential Equations with Non-Markovian Singular Terminal Conditions with General Driver and Filtration

We consider a class of Backward Stochastic Differential Equations with superlinear driver process $f$ adapted to a filtration supporting at least a $d$ dimensional Brownian motion and a Poisson random measure on ${mathbb R}^m- {0}.$ We consider the following class of terminal conditions $xi_1 = infty cdot 1_{{tau_1 le T}}$ where $tau_1$ is any stopping time with a bounded density in a neighborhood of $T$ and $xi_2 = infty cdot 1_{A_T}$ where $A_t$, $t in [0,T]$ is a decreasing sequence of events adapted to the filtration ${mathcal F}_t$ that is continuous in probability at $T$. A special case for $xi_2$ is $A_T = {tau_2 > T}$ where $tau_2$ is any stopping time such that $P(tau_2 =T) =0.$ In this setting we prove that the minimal supersolutions of the BSDE are in fact solutions, i.e., they attain almost surely their terminal values. We further show that the first exit time from a time varying domain of a $d$-dimensional diffusion process driven by the Brownian motion with strongly elliptic covariance matrix does have a continuous density; therefore such exit times can be used as $tau_1$ and $tau_2$ to define the terminal conditions $xi_1$ and $xi_2.$ The proof of existence of the density is based on the classical Greens functions for the associated PDE.

Approximation of the Exit Probability of a Stable Markov Modulated Constrained Random Walk

Let $X$ be the constrained random walk on ${mathbb Z}_+^2$ having increments $(1,0)$, $(-1,1)$, $(0,-1)$ with jump probabilities $lambda(M_k)$, $mu_1(M_k)$, and $mu_2(M_k)$ where $M$ is an irreducible aperiodic finite state Markov chain. The process $X$ represents the lengths of two tandem queues with arrival rate $lambda(M_k)$, and service rates $mu_1(M_k)$, and $mu_2(M_k)$. We assume that the average arrival rate with respect to the stationary measure of $M$ is less than the average service rates, i.e., $X$ is assumed stable. Let $tau_n$ be the first time when the sum of the components of $X$ equals $n$ for the first time. Let $Y$ be the random walk on ${mathbb Z} times {mathbb Z}_+$ having increments $(-1,0)$, $(1,1)$, $(0,-1)$ with probabilities $lambda(M_k)$, $mu_1(M_k)$, and $mu_2(M_k)$. Let $tau$ be the first time the components of $Y$ are equal. For $x in {mathbb R}_+^2$, $x(1) + x(2) < 1$, $x(1) > 0$, and $x_n = lfloor nx rfloor$, we show that $P_{(n-x_n(1),x_n(2)),m)}( tau < infty)$ approximates $P_{(x_n,m)}(tau_n < tau_0)$ with exponentially vanishing relative error as $nrightarrow infty$. For the analysis we define a characteristic matrix in terms of the jump probabilities of $(X,M).$ The $0$-level set of the characteristic polynomial of this matrix defines the characteristic surface; conjugate points on this surface and the associated eigenvectors of the characteristic matrix are used to define (sub/super) harmonic functions which play a fundamental role both in our analysis and the computation / approximation of $P_{(y,m)}(tau < infty).$

Excessive Backlog Probabilities of Two Parallel Queues

Let $X$ be the constrained random walk on ${mathbb Z}_+^2$ with increments $(1,0)$, $(-1,0)$, $(0,1)$ and $(0,-1)$; $X$ represents, at arrivals and service completions, the lengths of two queues working in parallel whose service and interarrival times are exponentially distributed with arrival rates $lambda_i$ and service rates $mu_i$, $i=1,2$; we assume $lambda_i < mu_i$, $i=1,2$, i.e., $X$ is assumed stable. Without loss of generality we assume $rho_1 =lambda_1/mu_1 ge rho_2 = lambda_2/mu_2$. Let $tau_n$ be the first time $X$ hits the line $partial A_n = {x in {mathbb Z}^2:x(1)+x(2) = n }$. Let $Y$ be the same random walk as $X$ but only constrained on ${y in {mathbb Z}^2: y(2)=0}$ and its jump probabilities for the first component reversed. Let $partial B ={y in {mathbb Z}^2: y(1) = y(2) }$ and let $tau$ be the first time $Y$ hits $partial B$. The probability $p_n = P_x(tau_n < tau_0)$ is a key performance measure of the queueing system represented by $X$ (probability of overflow of a shared buffer during systems first busy cycle). Stability of $X$ implies $p_n$ decays exponentially in $n$ when the process starts off $partial A_n.$ We show that, for $x_n= lfloor nx rfloor$, $x in {mathbb R}_+^2$, $x(1)+x(2) le 1$, $x(1) > 0$, $P_{(n-x_n(1),x_n(2))}( tau < infty)$ approximates $P_{x_n}(tau_n < tau_0)$ with exponentially vanishing relative error. Let $r = (lambda_1 + lambda_2)/(mu_1 + mu_2)$; for $r^2 < rho_2$ and $rho_1 eq rho_2$, we construct a class of harmonic functions from single and conjugate points on a characteristic surface of $Y$ with which $P_y(tau < infty)$ can be approximated with bounded relative error. For $r^2 = rho_1 rho_2$, we obtain $P_y(tau < infty) = r^{y(1)-y(2)} +frac{r(1-r)}{r-rho_2}left( rho_1^{y(1)} - r^{y(1)-y(2)} rho_1^{y(2)}right).$

Approximation of Excessive Backlog Probabilities of Two Tandem Queues

Let $X$ be the constrained random walk on ${mathbb Z}_+^2$ taking the steps $(1,0)$, $(-1,1)$ and $(0,-1)$ with probabilities $lambda < (mu_1 eq mu_2)$; in particular, $X$ is assumed stable. Let $tau_n$ be the first time $X$ hits $partial A_n = {x:x(1)+x(2) = n }$ For $x in {mathbb Z}_+^2, x(1) + x(2) < n$, the probability $p_n(x)= P_x( tau_n < tau_0)$ is a key performance measure for the queueing system represented by $X$. Let $Y$ be the constrained random walk on ${mathbb Z} times {mathbb Z}_+$ with increments $(-1,0)$, $(1,1)$ and $(0,-1)$. Let $tau$ be the first time that the components of $Y$ equal each other. We derive the following explicit formula for $P_y(tau < infty)$: [ P_y(tau < infty) = W(y)= rho_2^{y(1)-y(2)} + frac{mu_2 - lambda}{mu_2 - mu_1} rho_1^{ y(1)-y(2)} rho_1^{y(2)} + frac{mu_2-lambda}{mu_1 -mu_2} rho_2^{y(1)-y(2)} rho_1^{y(2)}, ] where, $rho_i = lambda/mu_i$, $i=1,2$, $y in {mathbb Z}times{ mathbb Z}_+$, $y(1) > y(2)$, and show that $W(n-x_n(1),x_n(2))$ approximates $p_n(x_n)$ with relative error {em exponentially decaying} in $n$ for $x_n = lfloor nx rfloor$, $x in {mathbb R}_+^2$, $0 < x(1) + x(2) < 1$. The steps of our analysis: 1) with an affine transformation, move the origin $(0,0)$ to $(n,0)$ on $partial A_n$; let $n earrow infty$ to remove the constraint on the $x(2)$ axis; this step gives the limit {em unstable} /{em transient} constrained random walk $Y$ and reduces $P_{x}(tau_n < tau_0)$ to $P_y(tau < infty)$; 2) construct a basis of harmonic functions of $Y$ and use it to apply the superposition principle to compute $P_y(tau < infty).$ The construction involves the use of conjugate points on a characteristic surface associated with the walk $X$. The proof that the relative error decays exponentially uses a sequence of subsolutions of a related HJB equation on a manifold.

Stationary analysis of a single queue with remaining service time dependent arrivals

We study a generalization of the $M/G/1$ system (denoted by $rM/G/1$) with independent and identically distributed (iid) service times and with an arrival process whose arrival rate $lambda_0f(r)$ depends on the remaining service time $r$ of the current customer being served. We derive a natural stability condition and provide a stationary analysis under it both at service completion times (of the queue length process) and in continuous time (of the queue length and the residual service time). In particular, we show that the stationary measure of queue length at service completion times is equal to that of a corresponding $M/G/1$ system. For $f > 0$ we show that the continuous time stationary measure of the $rM/G/1$ system is linked to the $M/G/1$ system via a time change. As opposed to the $M/G/1$ queue, the stationary measure of queue length of the $rM/G/1$ system at service completions differs from its marginal distribution under the continuous time stationary measure. Thus, in general, arrivals of the $rM/G/1$ system do not see time averages. We derive formulas for the average queue length, probability of an empty system and average waiting time under the continuous time stationary measure. We provide examples showing the effect of changing the reshaping function on the average waiting time.

Backward Stochastic Differential Equations with Nonmarkovian Singular Terminal Values

We solve a class of BSDE with a power function $f(y) = y^q$, $q > 1$, driving its drift and with the terminal boundary condition $ xi = infty cdot mathbf{1}_{B(m,r)^c}$ (for which $q > 2$ is assumed) or $ xi = infty cdot mathbf{1}_{B(m,r)}$, where $B(m,r)$ is the ball in the path space $C([0,T])$ of the underlying Brownian motion centered at the constant function $m$ and radius $r$. The solution involves the derivation and solution of a related heat equation in which $f$ serves as a reaction term and which is accompanied by singular and discontinuous Dirichlet boundary conditions. Although the solution of the heat equation is discontinuous at the corners of the domain the BSDE has continuous sample paths with the prescribed terminal value.

Exit Probabilities and Balayage of Constrained Random Walks

Let $X$ be the constrained random walk on ${mathbb Z}_+^d$ representing the queue lengths of a stable Jackson network and $x$ its initial position. Let $tau_n$ be the first time the sum of the components of $X$ equals $n$. $p_n doteq P_x(tau_n < tau_0)$ is a key performance measure for the queueing system represented by $X$, stability implies $p_nrightarrow 0$ exponentially. Currently the only analytic method available to approximate $p_n$ is large deviations analysis, which gives the exponential decay rate of $p_n$. Finer results are available via rare event simulation. The present article develops a new method to approximate $p_n$ and related expectations. The method has two steps: 1) with an affine transformation, move the origin onto the exit boundary of $tau_n$, take limits to remove some of the constraints on the dynamics, this yields a limit unstable constrained walk $Y$ 2) Construct a basis of harmonic functions of $Y$ and use them to apply the classical superposition principle of linear analysis. The basis functions are linear combinations of $log$-linear functions and come from solutions of harmonic systems, which are graphs whose vertices represent points on the characteristic surface of $Y$, the edges between the vertices represent conjugacy relations between the points, the loops represent membership in the boundary characteristic surfaces. Using our method we derive explicit, simple and almost exact formulas for $P_x(tau_n < tau_0)$ for $d$-tandem queues, similar to the product form formulas for the stationary distribution of $X$. The same method allows us to approximate the Balayage operator mapping $f$ to $x rightarrow {mathbb E}_x left[ f(X_{tau_n}) 1_{{tau_n < tau_0}} right]$ for a range of stable constrained random walks in $2$ dimensions. We indicate how the ideas of the paper relate to more general processes and exit boundaries.

Analysis of Push-type Epidemic Data Dissemination in Fully Connected Networks

Consider a fully connected network of nodes, some of which have a piece of data to be disseminated to the whole network. We analyze the following push-type epidemic algorithm: in each push round, every node that has the data, i.e., every infected node, randomly chooses $c in {mathbb Z}_+$ other nodes in the network and transmits, i.e., pushes, the data to them. We write this round as a random walk whose each step corresponds to a random selection of one of the infected nodes; this gives recursive formulas for the distribution and the moments of the number of newly infected nodes in a push round. We use the formula for the distribution to compute the expected number of rounds so that a given percentage of the network is infected and continue a numerical comparison of the push algorithm and the pull algorithm (where the susceptible nodes randomly choose peers) initiated in an earlier work. We then derive the fluid and diffusion limits of the random walk as the network size goes to $infty$ and deduce a number of properties of the push algorithm: 1) the number of newly infected nodes in a push round, and the number of random selections needed so that a given percent of the network is infected, are both asymptotically normal 2) for large networks, starting with a nonzero proportion of infected nodes, a pull round infects slightly more nodes on average 3) the number of rounds until a given proportion $lambda$ of the network is infected converges to a constant for almost all $lambda in (0,1)$. Numerical examples for theoretical results are provided.

Joint Hitting-Time Densities for Finite State Markov Processes

For a finite state Markov process and a finite collection ${ Gamma_k, k in K }$ of subsets of its state space, let $tau_k$ be the first time the process visits the set $Gamma_k$. We derive explicit/recursive formulas for the joint density and tail probabilities of the stopping times ${ tau_k, k in K}$. The formulas are natural generalizations of those associated with the jump times of a simple Poisson process. We give a numerical example and indicate the relevance of our results to credit risk modeling.