Lower bounds for covering times for reversible Markov chains and random walks on graphs

For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant. This is deduced from a more general result about stationary finite-state reversible Markov chains. Under weak conditions, the covering time for such processes is at leastc times the covering time for the corresponding i.i.d. process.     

Certain boundary functionals for Markov random walks

The asymptotic behavior of the moments of reaching the domain and exit from the domain (the boundaries of the domains going to infinity) of a multidimensional discrete random walk, defined on a Markov chain, is investigated.Translated from Matematicheskie Zametki, Vol. 23, No. 2, pp. 315–326, February, 1978.     

Large deviations for random walks in a mixing random environment and other (non‐Markov) random walks

We extend a recent work by S. R. S. Varadhan [8] on large deviations for random walks in a product random environment to include more general random walks on the lattice. In particular, some reinforced random walks and several classes of random walks in Gibbs fields are included. © 2004 Wiley Periodicals, Inc.     

Local approximations of Markov random walks by diffusions

We consider triangular arrays of Markov random walks that can be approximated by an accompanying sequence of diffusion processes. We give uniform bounds for approximation of scaled transition probabilities by transition densities of the diffusion process. In particular, we state local limit theorems for the case that the Markov random walks converge weakly to a diffusion process.     

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.     

Some Hecke algebra products and corresponding random walks

Let i=1+q+???+q ^i?1. For certain sequences (r ₁,…,r _l ) of positive integers, we show that in the Hecke algebra ? _n (q) of the symmetric group \(\mathfrak{S}_{n}\), the product \((1+\boldsymbol{r}_{\boldsymbol{1}}T_{r_{1}})\cdots (1+\boldsymbol{r}_{\boldsymbol{l}}T_{r_{l}})\) has a simple explicit expansion in terms of the standard basis {T _w }. An interpretation is given in terms of random walks on \(\mathfrak{S}_{n}\).     

Markov chains in random environments and random iterated function systems

We consider random iterated function systems giving rise to Markov chains in random (stationary) environments. Conditions ensuring unique ergodicity and a ``pure type' characterization of the limiting ``randomly invariant' probability measure are provided. We also give a dimension formula and an algorithm for simulating exact samples from the limiting probability measure.

     

Statistical estimation in the scheme of continuous Markov random walks

A constructive method of obtaining unbiased estimates of the unknown parameters and characteristics of a continuous finite Markow chain (CMC) ν(t), t≥0, with states 1, 2, ..., k and constant transition intensitiesλ _i,j<∞, i≠j, i, j=1, 2,..., k; $$\lambda _{i,i} = 0,\quad q_i = \sum\limits_{j = 1}^k {\lambda _{i,j} } ,\quad i = 1, 2,..., k,$$ is considered in the present paper for a wide class of stopping rules.     

随机环境中马氏链状态的常返性与暂留性

给出了随机环境中马氏链状态必然是弱常返或强暂留的几个充分条件,引入了状态周期的概念,得到类似于经典马氏链状态周期的几个性质.引入了随机环境中马氏链状态的几个数字特征,给出了随机环境中马氏链状态是弱常返与强常返等价的充分条件,利用这一条件可以说明相关文献所出现的错误结论.     

Zonal polynomials for wreath products

The pair of groups, symmetric group S _2n and hyperoctohedral group H _n , form a Gelfand pair. The characteristic map is a mapping from the graded algebra generated by the zonal spherical functions of (S _2n ,H _n ) into the ring of symmetric functions. The images of the zonal spherical functions under this map are called the zonal polynomials. A wreath product generalization of the Gelfand pair (S _2n ,H _n ) is discussed in this paper. Then a multi-partition versions of the theory is constructed. The multi-partition version of zonal polynomials are products of zonal polynomials and Schur functions and are obtained from a characteristic map from the graded Hecke algebra into a multipartition version of the ring of symmetric functions. Dedicated to Professor Eiichi Bannai on his 60th birthday.     

Generators and relations for wreath products

Generators and defining relations for wreath products of groups are given. Under a certain condition (conormality of generators), they are minimal. Published in Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 7, pp. 997–999, July, 2008.     

Limit theorems for Markov random walks with a fixed number of certain transitions

The limit behavior of Markov chains with discrete time and a finite number of states (MCDT) depending on the number n of its steps has been almost completely investigated [1–4]. In [5], MCDT with forbidden transitions were investigated, and in [6], the sum of a random number of functionals of random variables related by a homogeneous Markov chain (HMC) was considered. In the present paper, we continue the investigation of the limit behavior of the MCDT with random stopping time which is determined by a Markov walk plan II with a fixed number of certain transitions [7, 8]. Here we apply a method similar to that of [6], which allows us to obtain, together with some generalizations of the results of [6], a number of new assertions. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 119–130, Perm, 1990.     

p-Sets for random walks

Summary Let (,,P) be a probability space and let {itX _n ()} _n=1 be a sequence of i.i.d. random vectors whose state space isZ ^m for some positive integerm, where Z denotes the integers. Forn = 1, 2,... letS _n () be the random walk defined by . ForxZ ^m andU ^m, them-dimensional torus, let . Finally let be the characteristic function of the X's.In this paper we show that, under mild restrictions, there exists a set withP{ ₀ } = 1 such that for ₀ we have for all aU ^m,le0.As a consequence of this theorem, we obtain two corollaries. One is concerned with occupancy sets form-dimensional random walks, and the other is a mean ergodic theorem.Research supported by N.S.F. Grant # MCS 77-26809     

随机环境中马氏链状态的各种常返性与暂留性

考虑到随机环境中马氏链的状态在受到环境因素各种条件的影响下,引入了随机环境中马氏链状态的各种常返性与暂留性概念,讨论了这些常返性与暂留性的相互关系,从而说明随机环境中马氏链状态的常返性与暂留性和经典马氏链状态的常返性与暂留性有着显著的区别.     

Large deviations for Markov processes with discontinuous statistics,II: random walks

Summary Let ¹ and ² be Borel probability measures on ^d with finite moment generating functions. The main theorem in this paper proves the large deviation principle for a random walk whose transition mechanism is governed by ¹ when the walk is in the left halfspace ¹ = {x ^d :x ₁0} and whose transition mechanism is governed by ² when the walk is in the right halfspace ² = {x ^d :x ₁>0}. When the measures ¹ and ² are equal, the main theorem reduces to Cramér's Theorem.This research was supported in part by a grant from the National Science Foundation (NSF-DMS-8902333)This research was supported in part by a grant from the National Science Foundation (NSF-DMS-8901138) and in part by a Lady Davis Fellowship while visiting the Faculty of Industrial Engineering and Management at the Technion during the spring semester of 1989