Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximation of the Exit Probability of a Stable Markov Modulated Constrained Random Walk
85
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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).$
rate research
Read More
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.
In order to approximate the exit time of a one-dimensional diffusion process, we propose an algorithm based on a random walk. Such an algorithm so-called Walk on Moving Spheres was already introduced in the Brownian context. The aim is therefore to generalize this numerical approach to the Ornstein-Uhlenbeck process and to describe the efficiency of the method.
We view the classical Lindeberg principle in a Markov process setting to establish a universal probability approximation framework by It^{o}s formula and Markov semigroup. As applications, we consider approximating a family of online stochastic gradient descents (SGDs) by a stochastic differential equation (SDE) driven by additive Brownian motion, and obtain an approximation error with explicit dependence on the dimension which makes it possible to analyse high dimensional models. We also apply our framework to study stable approximation and normal approximation and obtain their optimal convergence rates (up to a logarithmic correction for normal approximation).
We consider random walk on dynamical percolation on the discrete torus $mathbb{Z}_n^d$. In previous work, mixing times of this process for $p<p_c(mathbb{Z}^d)$ were obtained in the annealed setting where one averages over the dynamical percolation environment. Here we study exit times in the quenched setting, where we condition on a typical dynamical percolation environment. We obtain an upper bound for all $p$ which for $p<p_c$ matches the known lower bound.
Consider a discrete-time one-dimensional supercritical branching random walk. We study the probability that there exists an infinite ray in the branching random walk that always lies above the line of slope $gamma-epsilon$, where $gamma$ denotes the asymptotic speed of the right-most position in the branching random walk. Under mild general assumptions upon the distribution of the branching random walk, we prove that when $epsilonto 0$, the probability in question decays like $exp{- {beta + o(1)over epsilon^{1/2}}}$, where $beta$ is a positive constant depending on the distribution of the branching random walk. In the special case of i.i.d. Bernoulli$(p)$ random variables (with $0<p<{1over 2}$) assigned on a rooted binary tree, this answers an open question of Robin Pemantle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
