On random walks arising in queueing systems: ergodicity and transience via quadratic forms as lyapounov functions — Part I

A simple and quite general approach is proposed to derive criteria for transience and ergodicity of a certain class of irreducibleN-dimensional Markov chains in ₊ ^N assuming a boundedness condition on the second moment of the jumps. The method consists in constructing convenient smooth supermartingales outside some compact set. The Lyapounov functions introduced belong to the set of quadratic forms in ₊ ^N and do not always have a definite sign. Existence and construction of these forms is shown to be basically equivalent to finding vectors satisfying a system of linear inequalities.Part I is restricted toN=2, in which case a complete characterization is obtained for the type of random walks analyzed by Malyshev and Mensikov, thus relaxing their condition of boundedness of the jumps. The motivation for this work is partly from a large class of queueing systems that give rise to random walks in ₊ ^N      

The Martin boundary and completion of Markov chains

Summary In this paper we treat a time-symmetrical Martin boundary theory for continuous parameter Markov chains. This is done by reversing the time sense of a Markov chainX _t in such a way as to obtain a dual Markov chain , and considering the two chains together. Various relations between the Martin exit boundaries and of these processes are studied. The exit boundary of , is in a sense an entrance boundary forX _t and vice versa. After a natural identification of certain points in and one can topologizeI in such a way thatboth X _t and have standard modifications in this space which are right continuous, have left limits, and are strongly Markov.Research supported in part at Stanford University, Stanford, California under AFOSR 0049.     

Semigroups, Rings, and Markov Chains

We analyze random walks on a class of semigroups called left-regular bands. These walks include the hyperplane chamber walks of Bidigare, Hanlon, and Rockmore. Using methods of ring theory, we show that the transition matrices are diagonalizable and we calculate the eigenvalues and multiplicities. The methods lead to explicit formulas for the projections onto the eigenspaces. As examples of these semigroup walks, we construct a random walk on the maximal chains of any distributive lattice, as well as two random walks associated with any matroid. The examples include a q-analogue of the Tsetlin library. The multiplicities of the eigenvalues in the matroid walks are generalized derangement numbers, which may be of independent interest.     

Wave distribution in a variable medium with random inhomogeneities

We consider the behavior of a solution of the wave equation u_tt (t, x) – a² (t) u_xx (t, x)=f (t, x) with initial conditions u (0, x)=u₀, /t6t u (t, x) ¦_t=0 =u₁ (x), a andf being random functions; a(t) characteristizes the variable character of the medium;f(t, x) is the inhomogeneity, having the character of random walks.Translated from Teoriya Sluchainykh Protsessov, No. 16, pp. 75–78, 1988.     

Local times on curves and uniform invariance principles

Summary Sufficient conditions are given for a family of local times |L _t ^µ | ofd-dimensional Brownian motion to be jointly continuous as a function oft and . Then invariance principles are given for the weak convergence of local times of lattice valued random walks to the local times of Brownian motion, uniformly over a large family of measures. Applications included some new results for intersection local times for Brownian motions on ² and ².Research partially supported by NSF grant DMS-8822053     

Random walks generated by affine mappings

This article is concerned with Markov chains on ^m constructed by randomly choosing an affine map at each stage, and then making the transition from the current point to its image under this map. The distribution of the random affine map can depend on the current point (i.e., state of the chain). Sufficient conditions are given under which this chain is ergodic.     

Isoperimetry for wreath products of Markov chains and multiplicity of selfintersections of random walks

We prove an isoperimetric inequality for wreath products of Markov chains with variable fibers. We use isoperimetric inequalities for wreath products to estimate the return probability of random walks on infinite groups and graphs, drift of random loops, the expected value E(exp(−tR _n )), where R _n is the number of distinct sites, visited up to the moment n, and, more generally, (where L _z,n is the number of visits of z up to the moment n and F(x, y) is some non-negative function).     

LU-Factorization Versus Wiener-Hopf Factorization for Markov Chains

Our initial motivation was to understand links between Wiener-Hopf factorizations for random walks and LU-factorizations for Markov chains as interpreted by Grassman (Eur. J. Oper. Res. 31(1):132–139, 1987). Actually, the first ones are particular cases of the second ones, up to Fourier transforms. To show this, we produce a new proof of LU-factorizations which is valid for any Markov chain with a denumerable state space equipped with a pre-order relation. Factors have nice interpretations in terms of subordinated Markov chains. In particular, the LU-factorization of the potential matrix determines the law of the global minimum of the Markov chain. For any matrix, there are two main LU-factorizations according as you decide to enter 1 in the diagonal of the first or of the second factor. When we factorize the generator of a Markov chain, one factorization is always valid while the other requires some hypothesis on the graph of the transition matrix. This dissymmetry comes from the fact that the class of sub-stochastic matrices is not stable under transposition. We generalize our work to the class of matrices with spectral radius less than one; this allows us to play with transposition and thus with time-reversal. We study some particular cases such as: skip-free Markov chains, random walks (this gives the WH-factorization), reversible Markov chains (this gives the Cholesky factorization). We use the LU-factorization to compute invariant measures. We present some pathologies: non-associativity, non-unicity; these can be cured by smooth assumptions (e.g. irreductibility).     

Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

On an extremal property of Markov chains and sufficiency of Markov strategies in Markov decision processes with the Dubins-Savage criterion

An inequality regarding the minimum ofP(lim inf(X _n D _n )) is proved for a class of random sequences. This result is related to the problem of sufficiency of Markov strategies for Markov decision processes with the Dubins-Savage criterion, the asymptotical behaviour of nonhomogeneous Markov chains, and some other problems.     

Markov chains on hypercubes: Spectral representations and several majorization relations

Various Markov chains on hypercubes ??are considered and their spectral representations are presentend in terms of Kronecker products. Special attention is given to random walks on the graphs ??(l = 1,n ? 2), where the vertex set is ?? and two vertices are connected if and only if their Hamming distance is at most l. It is shown that λ(??₁)>λ(??₁)>λ(??_n?1)>λ(??_n),l=2,…,n?2, where λ (??_I) is the specturum of the random walk on ??I, and > denotes the majorization ordering. A similar majorization relation is established for graphs V₁ where two veritces are connected if and only if their Hamming distance is exactly l. Some applications to mean times of these random walks are given. © 1993 John Wiley & Sons, Inc.     

On the lower Markov spectrum

C. Hightower found two infinite sequences of gaps in the Markov spectrum, ( _n , _n ) and ( _n , _n ) with _n and _n both Markov elements, converging to . This paper exhibits Markov elements _n ^* and _n ^* such that, for alln 1, ( _n ^* , _n ) and ( _{n n} ^* ) are gaps in the Markov spectrum. Other results include showing that, for alln 1, _n is completely isolated, while the other endpoints of the gaps are limit points in the Markov spectrum.     

A random wave process

The parabolic or forward scattering approximation to the equation describing wave propagation in a random medium leads to a stochastic partial differential equation which has the form of a random Schrödinger equation. Existence, uniqueness and continuity of solutions to this equation are established. The resulting process is a Markov diffusion process on the unit sphere in complex Hilbert space. Using Markov methods a limiting Markov process is identified in the case of a narrow beam limit; this limiting process corresponds to a simple random translation of the beam known as spot-dancing.Research supported by the Natural Sciences and Engineering Research Council of Canada.Research supported by the Air Force Office of Scientific Research under Grant number AFOSR-80-0228.     

On the Local Time of Random Walks Associated with Gegenbauer Polynomials

The local time of random walks associated with Gegenbauer polynomials \(P_{n}^{(\alpha)}(x)\), x∈[?1,1], is studied in the recurrent case: \(\alpha\in [-\frac{1}{2},0]\). When α is nonzero, the limit distribution is given in terms of a Mittag-Leffler distribution. The proof is based on a local limit theorem for the random walk associated with Gegenbauer polynomials. As a by-product, we derive the limit distribution of the local time of some particular birth-and-death Markov chains on ?.     

Strong laws of large numbers for random walks associated with a class of one-dimensional convolution structures

We derive strong laws of large numbers for birth and death random walks and random walks on polynomial hypergroups for which the coefficients of the three-term-recurrence formula of the associated orthogonal polynomials satisfy lim _n n ^a (a _n-c_n)= wherea]0, 1[ and >0. We also present these laws for random walks on Sturm-Liouville hypergroups on ₊ for which a corresponding asymptotic condition holds. Our paper supplements articles ofVoit [9] andZeuner [14] in which the casesa=0 anda=1 are considered.This paper was written at Murdoch University in Western Australia while the author held a Feodor Lynen fellowship of the Alexander von Humboldt foundation.     

A class of path-valued Markov processes and its applications to superprocesses

Summary Let ( _s ) be a continuous Markov process satisfying certain regularity assumptions. We introduce a path-valued strong Markov process associated with ( _s ), which is closely related to the so-called superprocess with spatial motion ( _s ). In particular, a subsetH of the state space of ( _s ) intersects the range of the superprocess if and only if the set of paths that hitH is not polar for the path-valued process. The latter property can be investigated using the tools of the potential theory of symmetric Markov processes: A set is not polar if and only if it supports a measure of finite energy. The same approach can be applied to study sets that are polar for the graph of the superprocess. In the special case when ( _s ) is a diffusion process, we recover certain results recently obtained by Dynkin.     

Random Walks on Trees and an Inequality of Means

We define trees generated by bi-infinite sequences, calculate their walk-invariant distribution and the speed of a biased random walk. We compare a simple random walk on a tree generated by a bi-infinite sequence with a simple random walk on an augmented Galton-Watson tree. We find that comparable simple random walks require the augmented Galton-Watson tree to be larger than the corresponding tree generated by a bi-infinite sequence. This is due to an inequality for random variables with values in [1, [ involving harmonic, geometric and arithmetic mean.     

Markov processes of infinitely many nonintersecting random walks

Consider an N-dimensional Markov chain obtained from N one-dimensional random walks by Doob h-transform with the q-Vandermonde determinant. We prove that as N becomes large, these Markov chains converge to an infinite-dimensional Feller Markov process. The dynamical correlation functions of the limit process are determinantal with an explicit correlation kernel. The key idea is to identify random point processes on ${\mathbb Z}$ with q-Gibbs measures on Gelfand–Tsetlin schemes and construct Markov processes on the latter space. Independently, we analyze the large time behavior of PushASEP with finitely many particles and particle-dependent jump rates (it arises as a marginal of our dynamics on Gelfand–Tsetlin schemes). The asymptotics is given by a product of a marginal of the GUE-minor process and geometric distributions.