Isoperimetric Inequalities for Random Walks

In this paper some isoperimetric problems are studied, particularly the extremal property of the mean exit time of the random walk from finite sets. This isoperimetric problem is inserted into the set of equivalent conditions of the diagonal upper estimate of transition probability of random walks on weighted graphs.     

Strategic Purely Nonatomic Random Walks

In this note we describe a class of Random Walks on integers in the finitely additive setup which are purely nonatomic in contrast to the countably additive setup where all random walks are simply atomic, a result of David Blackwell.     

Boundaries and Harmonic Functions for Random Walks with Random Transition Probabilities

The usual random walk on a group (homogeneous both in time and in space) is determined by a probability measure on the group. In a random walk with random transition probabilities this single measure is replaced with a stationary sequence of measures, so that the resulting (random) Markov chains are still space homogeneous, but no longer time homogeneous. We study various notions of measure theoretical boundaries associated with this model and establish an analogue of the Poisson formula for (random) bounded harmonic functions. Under natural conditions on transition probabilities we identify these boundaries for several classes of groups with hyperbolic properties and prove the boundary triviality (i.e., the absence of non-constant random bounded harmonic functions) for groups of subexponential growth, in particular, for nilpotent groups.     

Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.     

Random Walks Associated with Non-Divergence Form Elliptic Equations

This paper is concerned with the study of the diffusion process associated with a nondivergence form elliptic operator in d dimensions, d2. The authors introduce a new technique for studying the diffusion, based on the observation that the probability of escape from a d–1 dimensional hyperplane can be explicitly calculated. They use the method to estimate the probability of escape from d–1 dimensional manifolds which are C ^1, , and also d–1 dimensional Lipschitz manifolds. To implement their method the authors study various random walks induced by the diffusion process, and compare them to the corresponding walks induced by Brownian motion.     

有向图上的随机游动

设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.     

Fastest Coupling of Random Walks

A new coupling of one-dimensional random walks is describedwhich tries to control the coupling by keeping the separationof the two random walks of constant sign. It turns out thatamong such monotone couplings there is an optimal one-step couplingwhich maximises the second moment of the difference (assumingthis is finite), and this coupling is ‘fast’ inthe sense that for a random walk with a unimodal step distributionthe coupling time achieved by using the new coupling at eachstep is stochastically no larger than any other coupling. Thisis applied to the case of symmetric unimodal distributions.     

Random Walks on Dihedral Groups

In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p ² steps are necessary for the walk to become close to uniformly distributed on all of D _2p where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p ^2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D _2p . We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D _2p .     

Asymptotics for Random Walks with Dependent Heavy-Tailed Increments

We consider a random walk {S _n} with dependent heavy-tailed increments and negative drift. We study the asymptotics for the tail probability P{sup _n S _n >x} as x. If the increments of {S _n} are independent then the exact asymptotic behavior of P{sup _n S _n >x} is well known. We investigate the case in which the increments are given as a one-sided asymptotically stationary linear process. The tail behavior of sup _n S _n turns out to depend heavily on the coefficients of this linear process.     

一类随机环境中的随机游动

在Solomn的模型的基础上对一类随机环境中随机游动进行了讨论，并得出了一个常返性准则和一些极限性质。     

一类随机环境中的随机游动

研究了在环境平稳遍历时,右半直线上可逗留的随机环境中的随机游动的常返性和非常返性,给出非常返、正常返、零常返的充要条件,并讨论了极限性质.作为推论,给出P独立同分布时的相应结论.     

Survival of Branching Random Walks in Random Environment

We study survival of nearest-neighbor branching random walks in random environment (BRWRE) on ℤ. A priori there are three different regimes of survival: global survival, local survival, and strong local survival. We show that local and strong local survival regimes coincide for BRWRE and that they can be characterized with the spectral radius of the first moment matrix of the process. These results are generalizations of the classification of BRWRE in recurrent and transient regimes. Our main result is a characterization of global survival that is given in terms of Lyapunov exponents of an infinite product of i.i.d. 2×2 random matrices.     

Lamplighter Random Walks on Fractals

We consider on-diagonal heat kernel estimates and the laws of the iterated logarithm for a switch-walk-switch random walk on a lamplighter graph under the condition that the random walk on the underlying graph enjoys sub-Gaussian heat kernel estimates.     

半直线上的独立随机环境中可逗留的随机游动

主要研究了在随机环境独立的情况下,右半直线上随机环境中可逗留的随机游动的常返性和非常返性.     

一维随机风景中的随机游动的中偏差

本文研究一维独立同分布随机风景中的随机游动的中偏差.通过给出一些有用的高阶矩估计并结合G(a)rtner-Ellis定理,得到主要结果.     

Random Walks on Trees with Finitely Many Cone Types

This paper is devoted to the study of random walks on infinite trees with finitely many cone types (also called periodic trees). We consider nearest neighbour random walks with probabilities adapted to the cone structure of the tree, which include in particular the well studied classes of simple and homesick random walks. We give a simple criterion for transience or recurrence of the random walk and prove that the spectral radius is equal to 1 if and only if the random walk is recurrent. Furthermore, we study the asymptotic behaviour of return probabilitites and prove a local limit theorem. In the transient case, we also prove a law of large numbers and compute the rate of escape of the random walk to infinity, as well as prove a central limit theorem. Finally, we describe the structure of the boundary process and explain its connection with the random walk.     

Minimal Position of Branching Random Walks in Random Environment

We consider branching random walks in random environment (BRWRE) on ? with only one particle starting at the origin. Particles reproduce according to offspring distribution (which depends on its locations) and move one step to the right (with a probability in (0,1] which may depend on the location) or stay in the same site. We give an estimate to the minimal displacement of BRWRE at time n in the case where the essential supremum of mean number of offsprings which stay in the same place is equal to 1.