Light-tailed behavior of stationary distribution for state-dependent random walks on a strip

We consider the state-dependent reflecting random walk on a half- strip. We provide explicit criteria for （positive） recurrence, and an explicit expression for the stationary distribution. As a consequence, the light-tailed behavior of the stationary distribution is proved under appropriate conditions. The key idea of the method employed here is the decomposition of the trajectory of the random walk and the main tool is the intrinsic branching structure buried in the random walk on a strip, which is different from the matrix-analytic method.     

Explicit Stationary Distribution of the （L, 1）-reflecting Random Walk on the Half Line

In this paper,we consider the（L,1） state-dependent reflecting random walk（RW） on the half line,which is an RW allowing jumps to the left at a maximal size L.For this model,we provide an explicit criterion for（positive） recurrence and an explicit expression for the stationary distribution.As an application,we prove the geometric tail asymptotic behavior of the stationary distribution under certain conditions.The main tool employed in the paper is the intrinsic branching structure within the（L,1）-random walk.     

State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Existence and characterization of product-form invariant distributions for state-dependent stochastic networks in the heavy-traffic diffusion limit

We consider state-dependent stochastic networks in the heavy-traffic diffusion limit represented by reflected jump-diffusions in the orthant ℝ₊ ⁿ with state-dependent reflection directions upon hitting boundary faces. Jumps are allowed in each coordinate by means of independent Poisson random measures with jump amplitudes depending on the state of the process immediately before each jump. For this class of reflected jump-diffusion processes sufficient conditions for the existence of a product-form stationary density and an ergodic characterization of the stationary distribution are provided. Moreover, such stationary density is characterized in terms of semi-martingale local times at the boundaries and it is shown to be continuous and bounded. A central role is played by a previously established semi-martingale local time representation of the regulator processes. F.J. Piera’s research supported in part by CONICYT, Chile, FONDECYT Project 1070797. R.R. Mazumdar’s research supported in part by NSF, USA, Grant 0087404 through Networking Research Program, and a Discovery Grant from NSERC, Canada.     

Chutes and Ladders in Markov Chains

We investigate how the stationary distribution of a Markov chain changes when transitions from a single state are modified. In particular, adding a single directed edge to nearest neighbor random walk on a finite discrete torus in dimensions one, two, or three changes the stationary distribution linearly, logarithmically, or only locally. Related results are derived for birth and death chains approximating Bessel diffusions and for random walk on the Sierpinski gasket.     

本刊英文版Vol.30(2014),No.3论文摘要

<正>Explicit Stationary Distribution of the(L,1)-reflecting Random Walk on the Half Line Wen Ming HONG Ke ZHOU Yi Qiang Q.ZHAO Abstract In this paper,we consider the(L,1)state-dependent reflecting random walk(RW)on the half line,which is an RW allowing jumps to the left at a maximal size L.For this model,we provide an explicit criterion for(positive)recurrence and an explicit expression for the stationary distribution.As an application,we prove the geometric tail asymptotic behavior of the stationary distribution under certain conditions.The main tool employed in the paper is     

Wireless three-hop networks with stealing II: exact solutions through boundary value problems

We study the stationary distribution of a random walk in the quarter plane arising in the study of three-hop wireless networks with stealing. Our motivation is to find exact tail asymptotics (beyond logarithmic estimates) for the marginal distributions, which requires an exact solution for the bivariate generating function describing the stationary distribution. This exact solution is determined via the theory of boundary value problems. Although this is a classical approach, the present random walk exhibits some salient features. In fact, to determine the exact tail asymptotics, the random walk presents several unprecedented challenges related to conformal mappings and analytic continuation. We address these challenges by formulating a boundary value problem different from the one usually seen in the literature.     

Separable solutions for Markov processes in random environments

In this paper we address the problem of efficiently deriving the steady-state distribution for a continuous time Markov chain (CTMC) S evolving in a random environment E. The process underlying E is also a CTMC. S is called Markov modulated process. Markov modulated processes have been widely studied in literature since they are applicable when an environment influences the behaviour of a system. For instance, this is the case of a wireless link, whose quality may depend on the state of some random factors such as the intensity of the noise in the environment. In this paper we study the class of Markov modulated processes which exhibits separable, product-form stationary distribution. We show that several models that have been proposed in literature can be studied applying the Extended Reversed Compound Agent Theorem (ERCAT), and also new product-forms are derived. We also address the problem of the necessity of ERCAT for product-forms and show a meaningful example of product-form not derivable via ERCAT.     

Multivariate polynomial perturbations of algebraic equations

In this note we study multivariate perturbations of algebraic equations. In general, it is not possible to represent the perturbed solution as a Puiseux-type power series in a connected neighborhood. For the case of two perturbation parameters we provide a sufficient condition that guarantees such a representation. Then, we extend this result to the case of more than two perturbation parameters. We motivate our study by the perturbation analysis of a weighted random walk on the Web Graph. In an instance of the latter the stationary distribution of the weighted random walk, the so-called Weighted PageRank, may depend on two (or more) perturbation parameters in a manner that illustrates our theoretical development.     

The limit distribution of the maximum increment of a random walk with dependent regularly varying jump sizes

We investigate the maximum increment of a random walk with heavy-tailed jump size distribution. Here heavy-tailedness is understood as regular variation of the finite-dimensional distributions. The jump sizes constitute a strictly stationary sequence. Using a continuous mapping argument acting on the point processes of the normalized jump sizes, we prove that the maximum increment of the random walk converges in distribution to a Fréchet distributed random variable.     

Quenched invariance principle for simple random walk on discrete point processes

We consider the simple random walk on random graphs generated by discrete point processes. This random walk moves on graphs whose vertex set is a random subset of a cubic lattice and whose edges are lines between any consecutive vertices on lines parallel to each coordinate axis. Under the assumption that the discrete point processes are finitely dependent and stationary, we prove that the quenched invariance principle holds, i.e., for almost every configuration of the point process, the path distribution of the walk converges weakly to that of a Brownian motion.     

On Transience Conditions for Markov Chains and Random Walks

We prove a new transience criterion for Markov chains on an arbitrary state space and give a corollary for real-valued chains. We show by example that in the case of a homogeneous random walk with infinite mean the proposed sufficient conditions are close to those necessary. We give a new proof of the well-known criterion for finiteness of the supremum of a random walk.     

Commutation relations and Markov chains

It is shown that the combinatorics of commutation relations is well suited for analyzing the convergence rate of certain Markov chains. Examples studied include random walk on irreducible representations, a local random walk on partitions whose stationary distribution is the Ewens distribution, and some birth–death chains.     

Numerical solutions for asymmetric Lévy flights

Numerical Algorithms - Lévy flights are generalised random walk processes where the independent stationary increments are drawn from a long-tailed α-stable jump length distribution. We...     

Branching/queueing networks: Their introduction and near-decomposability asymptotics

A new class of models, which combines closed queueing networks with branching processes, is introduced. The motivation comes from MIMD computers and other service systems in which the arrival of new work is always triggered by the completion of former work, and the amount of arriving work is variable. In the variant of branching/queueing networks studied here, a customer branches into a random and state-independent number of offspring upon completing its service. The process regenerates whenever the population becomes extinct. Implications for less rudimentary variants are discussed. The ergodicity of the network and several other aspects are related to the expected total number of progeny of an associated multitype Galton-Watson process. We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution and the throughputs. Closed-form solutions are available for the multi-server single-node model, and for homogeneous networks of infinite-servers. Generally, branching/queueing networks do not seem to have a product-form state distribution. We propose a conditional product-form approximation, and show that it is approached as a limit by branching/queueing networks with a slowly varying population size. The proof demonstrates an application of the nearly complete decomposability paradigm to an infinite state space. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotics of the Stationary Distribution of an Oscillating Random Walk

We obtain some theorems on the asymptotics of the stationary distribution of an oscillating random walk with two levels of switching provided that the distance between the levels tends to infinity.     

Linear and sub-linear growth and the CLT for hitting times of a random walk in random environment on a strip

The main goal of this work is to study the asymptotic behaviour of hitting times of a random walk (RW) in a quenched random environment (RE) on a strip. We introduce enlarged random environments in which the traditional hitting time can be presented as a sum of independent random variables whose distribution functions form a stationary random sequence. This allows us to obtain conditions (stated in terms of properties of random environments) for a linear growth of hitting times of relevant random walks. In some important cases (e.g. independent random environments) these conditions are also necessary for this type of behaviour. We also prove the quenched Central Limit Theorem (CLT) for hitting times in the general ergodic setting. A particular feature of these (ballistic) laws in random environment is that, whenever they hold under standard normalization, the convergence is a convergence with a speed. The latter is due to certain properties of moments of hitting times which are also studied in this paper. The asymptotic properties of the position of the walk are stated but are not proved in this work since this has been done in Goldhseid (Probab. Theory Relat. Fields 139(1):41–64, 2007).      

具有标准发生率的随机SIR传染病模型的建立及平稳分布与疾病灭绝研究

研究了一类具有标准发生率以及考虑随机扰动与系统变量成正比的随机SIR传染病模型.首先,对于任意的正的初值,系统存在唯一的全局正解以及通过构造合适的随机李雅普诺夫函数,得到了模型遍历平稳分布存在的充分条件.其次,给出了疾病灭绝的充分条件,并与模型遍历平稳分布存在的充分条件作对比,得出了在特定条件下随机SIR模型的阈值.最后通过数值模拟验证了结果的正确性.     

Random Walk on Surfaces with Hyperbolic Cusps

We consider the operator associated with a random walk on finite volume surfaces with hyperbolic cusps. We study the spectral gap (upper and lower bound) associated with this operator and deduce some rate of convergence of the iterated kernel towards its stationary distribution.     

Scaling Limit for the Ant in High-Dimensional Labyrinths

We study here a detailed conjecture regarding one of the most important cases of anomalous diffusion, i.e., the behavior of the “ant in the labyrinth.” It is natural to conjecture that the scaling limit for random walks on large critical random graphs exists in high dimensions and is universal. This scaling limit is simply the natural Brownian motion on the integrated super-Brownian excursion. We give here a set of four natural, sufficient conditions on the critical graphs and prove that this set of assumptions ensures the validity of this conjecture. The remaining future task is to prove that these sufficient conditions hold for the various classical cases of critical random structures, like the usual Bernoulli bond percolation, oriented percolation, and spread-out percolation in high enough dimension. In a companion paper, we do precisely that in a first case, the random walk on the trace of a large critical branching random walk. We verify the validity of these sufficient conditions and thus obtain the scaling limit mentioned above in dimensions larger than 14. © 2019 Wiley Periodicals, Inc.