
























Let $X$ be the constrained random walk on ${\mathbb Z}_+^2$ taking the steps $(1,0)$, $(-1,1)$ and $(0,-1)$ with probabilities $λ< (μ_1\neq μ_2)$; in particular, $X$ is assumed stable. Let $τ_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( τ_n < τ_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 $τ$ be the first time that the components of $Y$ equal each other. We derive the following explicit formula for $P_y(τ< \infty)$: \[ P_y(τ< \infty) = W(y)= ρ_2^{y(1)-y(2)} + \frac{μ_2 - λ}{μ_2 - μ_1} ρ_1^{ y(1)-y(2)} ρ_1^{y(2)} + \frac{μ_2-λ}{μ_1 -μ_2} ρ_2^{y(1)-y(2)} ρ_1^{y(2)}, \] where, $ρ_i = λ/μ_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\nearrow \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}(τ_n < τ_0)$ to $P_y(τ< \infty)$; 2) construct a basis of harmonic functions of $Y$ and use it to apply the superposition principle to compute $P_y(τ< \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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。