Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHitting probabilities of constrained random walks representing tandem networks
274
0
0.0
(
0
)
Authors
Ali Devin Sezer
Ask ChatGPT about the research
No Arabic 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 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.$
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.
We present a novel application of the HHL (Harrow-Hassidim-Lloyd) algorithm -- a quantum algorithm solving systems of linear equations -- in solving an open problem about quantum random walks, namely computing hitting (or absorption) probabilities of a general (not only Hadamard) one-dimensional quantum random walks with two absorbing boundaries. This is achieved by a simple observation that the problem of computing hitting probabilities of quantum random walks can be reduced to inverting a matrix. Then a quantum algorithm with the HHL algorithm as a subroutine is developed for solving the problem, which is faster than the known classical algorithms by numerical experiments.
We prove new results on lazy random walks on finite graphs. To start, we obtain new estimates on return probabilities $P^t(x,x)$ and the maximum expected hitting time $t_{rm hit}$, both in terms of the relaxation time. We also prove a discrete-time version of the first-named authors ``Meeting time lemma~ that bounds the probability of random walk hitting a deterministic trajectory in terms of hitting times of static vertices. The meeting time result is then used to bound the expected full coalescence time of multiple random walks over a graph. This last theorem is a discrete-time version of a result by the first-named author, which had been previously conjectured by Aldous and Fill. Our bounds improve on recent results by Lyons and Oveis-Gharan; Kanade et al; and (in certain regimes) Cooper et al.
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.
In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Further, we prove that for any reversible ergodic Markov chain $P$, the quantum hitting time of the quantum analogue of $P$ has the same order as the square root of the classical hitting time of $P$. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem for the 2D grid. Extending his result, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
