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.     

On a Fluctuation Identity for Random Walks and Levy Processes

In this paper, some identities in laws involving ladder processesfor random walks and Lévy processes are extended andunified. 2000 Mathematics Subject Classification 60G50, 60G51(primary), 60G17 (secondary).     

On the Recurrence Set of Planar Markov Random Walks

In this paper, we investigate properties of recurrent planar Markov random walks. More precisely, we study the set of recurrence points with the use of local limit theorems. The Nagaev–Guivarc’h spectral method provides several examples for which these local limit theorems are satisfied as soon as some (standard or non-standard) central limit theorem and some non-sublattice assumption hold.     

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.     

Factorization Representations in the Boundary Crossing Problems for Random Walks on a Markov Chain

Let τ be some stopping time for a random walk S _n defined on transitions of a finite Markov chain and let τ(t) be the first passage time across the level t which occurs after τ. We prove a theorem that establishes a connection between the dual Laplace-Stieltjes transforms of the joint distributions of (τ, S _τ) and (τ(t), S _τ(t)). This result applies to the study of the number of crossings of a strip by sample paths of a random walk.Original Russian Text Copyright © 2005 Lotov V. I. and Orlova N. G.The authors were partially supported by the Russian Foundation for Basic Research (Grant 05-01-00810) and the Grant Council of the President of the Russian Federation (Grant NSh-2139.2003.1).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 833–840, July–August, 2005.     

Random Walks with Stochastically Bounded Increments: Renewal Theory

Summary. This paper develops renewal theory for a rather general class of random walks S_N including linear submartingales with positive drift. The basic assumption on S_N is that their conditional increment distribution functions with respect to some filtration ?_? are bounded from above and below by integrable distribution functions. Under a further mean stability condition these random walks turn out to be natural candidates for satisfying Blackwell-type renewal theorems. In a companion paper [2], certain uniform lower and upper drift bounds for S_N, describing its average growth on finite remote time intervals, have been introduced and shown to be equal in case the afore-mentioned mean stability condition holds true. With the help of these bounds we give lower and upper estimates for H * U(B), where U denotes the renewal measure of S_N, H a suitable delay distribution and B a Borel subset of IR. This is then further utilized in combination with a coupling argument to prove the principal result, namely an extension of Blackwell's renewal theorem to random walks of the previous type whose conditional increment distribution additionally contain a subsequence with a common component in a certain sense. A number of examples are also presented.     

Correlated Markov Quantum Walks

We consider the discrete time unitary dynamics given by a quantum walk on ${\mathbb {Z}^d}$ performed by a particle with internal degree of freedom, called coin state, according to the following iterated rule: a unitary update of the coin state takes place, followed by a shift on the lattice, conditioned on the coin state of the particle. We study the large time behavior of the quantum mechanical probability distribution of the position observable in ${\mathbb {Z}^d}$ for random updates of the coin states of the following form. The random sequences of unitary updates are given by a site-dependent function of a Markov chain in time, with the following properties: on each site, they share the same stationary Markovian distribution and, for each fixed time, they form a deterministic periodic pattern on the lattice. We prove a Feynman–Kac formula to express the characteristic function of the averaged distribution over the randomness at time n in terms of the nth power of an operator M. By analyzing the spectrum of M, we show that this distribution possesses a drift proportional to the time and its centered counterpart displays a diffusive behavior with a diffusion matrix we compute. Moderate and large deviation principles are also proven to hold for the averaged distribution and the limit of the suitably rescaled corresponding characteristic function is shown to satisfy a diffusion equation. An example of random updates for which the analysis of the distribution can be performed without averaging is worked out. The random distribution displays a deterministic drift proportional to time and its centered counterpart gives rise to a random diffusion matrix, the law of which we compute. We complete the picture by presenting an uncorrelated example.     

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

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

一类非标准随机游动及其在风险理论中的应用

考虑一类非标准的随机游动Sn=X1 … Xn,其中Xi(i≥1)为一列独立的随机变量序列,X1的分布函数为G,Xi(i≥2)具有共同的分布函数F.本文主要研究了F与G属于S(γ)族时,非标准随机游动的尾等价式和局部等价式,并给出在风险理论中的一些应用.     

Large Deviations for Intersections of Random Walks

We prove a large deviations principle for the number of intersections of two independent infinite-time ranges in dimension 5 and greater, improving upon the moment bounds of Khanin, Mazel, Shlosman, and Sinaï [9]. This settles, in the discrete setting, a conjecture of van den Berg, Bolthausen, and den Hollander [15], who analyzed this question for the Wiener sausage in the finite-time horizon. The proof builds on their result (which was adapted in the discrete setting by Phetpradap [12]), and combines it with a series of tools that were developed in recent works of the authors [2, 3, 5]. Moreover, we show that most of the intersection occurs in a single box where both walks realize an occupation density of order 1. © 2022 Wiley Periodicals, Inc.     

随机环境中广义随机游动的灭绝概率

随机环境中广义随机游动(GRWRE)是随机环境中随机游动(RWRE)的推广．该文构造了非负整数集上的GRWRE,证明了这种模型的存在性,并计算了灭绝概率．     

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.     

有向图上的随机游动

设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 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.     

Strong Laws of Large Numbers for Random Walks in Random Sceneries

In this paper, we study strong laws of large numbers for random walks in random sceneries. Some mild sufficient conditions for the validity of strong laws of large numbers are obtained.     

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 .