A note on the Poisson boundary of lamplighter random walks

The main goal of this paper is to determine the Poisson boundary of lamplighter random walks over a general class of discrete groups Γ endowed with a “rich” boundary. The starting point is the Strip Criterion of identification of the Poisson boundary for random walks on discrete groups due to Kaimanovich (Ann. Math. 152:659–692, 2000). A geometrical method for constructing the strip as a subset of the lamplighter group ${\mathbb {Z}_{2}\wr \Gamma}$ starting with a “smaller” strip in the group Γ is developed. Then, this method is applied to several classes of base groups Γ: groups with infinitely many ends, hyperbolic groups in the sense of Gromov, and Euclidean lattices. We show that under suitable hypothesis the Poisson boundary for a class of random walks on lamplighter groups is the space of infinite limit configurations.     

A note on the Poisson boundary of lamplighter random walks

The main goal of this paper is to determine the Poisson boundary of lamplighter random walks over a general class of discrete groups Γ endowed with a “rich” boundary. The starting point is the Strip Criterion of identification of the Poisson boundary for random walks on discrete groups due to Kaimanovich (Ann. Math. 152:659–692, 2000). A geometrical method for constructing the strip as a subset of the lamplighter group \mathbb Z₂\wr G{\mathbb {Z}_{2}\wr \Gamma} starting with a “smaller” strip in the group Γ is developed. Then, this method is applied to several classes of base groups Γ: groups with infinitely many ends, hyperbolic groups in the sense of Gromov, and Euclidean lattices. We show that under suitable hypothesis the Poisson boundary for a class of random walks on lamplighter groups is the space of infinite limit configurations.     

空间随机行走比对问题的动态规划算法

受计算生物学中两个蛋白质结构比对问题的启发,定义了三维空间随机步以及两个随机步同构等的概念.研究了步长为k的随机步非同构意义下的个数.最后提出了两个非同构随机步对齐的优化问题,通过研究随机步的同构,采用动态规划给出了将一个随机步对齐到另一个随机步所需最少的操作步数的算法.     

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.     

Edgeworth Expansions for Centered Random Walks on Covering Graphs of Polynomial Volume Growth

Edgeworth expansions for random walks on covering graphs with groups of polynomial volume growths are obtained under a few natural assumptions. The coefficients appearing in this expansion depend on not only geometric features of the underlying graphs but also the modified harmonic embedding of the graph into a certain nilpotent Lie group. Moreover, we apply the rate of convergence in Trotter’s approximation theorem to establish the Berry–Esseen-type bound for the random walks.

     

Quasimorphisms,random walks,and transient subsets in countable groups

We study the interrelations between the theory of quasimorphisms and the theory of random walks on groups, and establish the following transience criterion for subsets of groups: if a subset of a countable group has bounded images under any three linearly independent homogeneous quasimorphisms on the group, the this subset is transient for all nondegenerate random walks on the group. From this it follows, by results of M. Bestvina, K. Fujiwara, J. Birman, W. Menasco, and others, that, in a certain sense, generic elements in the mapping class groups of surfaces are pseudo-Anosov, generic braids in Artin’s braid groups represent prime links and knots, generic elements in the commutant of every nonelementary hyperbolic group have large stable commutator length, etc. Bibliography: 20 titles.     

The central limit theorem for stationary Markov processes with normal generator—with applications to hypergroups

We extend the central limit theorem for additive functionals of a stationary, ergodic Markov chain with normal transition operator due to Gordin and Lif?ic, 1981 [A remark about a Markov process with normal transition operator, In: Third Vilnius Conference on Probability and Statistics 1, pp. 147–48] to continuous-time Markov processes with normal generators. As examples, we discuss random walks on compact commutative hypergroups as well as certain random walks on non-commutative, compact groups.     

Gaussian Estimates for Random Walks on Some Unimodular p-adic Groups

It is shown in this paper that the transition kernels corresponding to simple random walks on certain unimodular solvable p-adic groups admit upper Gaussian estimates.      

Khintchine–Pollaczek formula for random walks whose steps have one geometric tail

We derive a Khinchine–Pollaczek formula for random walks whose steps have a geometric left tail. The construction rests on the memory-less property of the geometric distribution. An example from a tandem queue modeling dynamic isnstability for microtubules is given.     

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.     

Random walks on random coset spaces with applications to Furstenberg entropy

We determine the range of Furstenberg entropy for stationary ergodic actions of nonabelian free groups by an explicit construction involving random walks on random coset spaces.     

Optimal placement in a limit order book: an analytical approach

This paper proposes and studies an optimal placement problem in a limit order book. Under a correlated random walk model with mean-reversion for the best ask/bid price, optimal placement strategies for both static and dynamic cases are derived. In the static case, the optimal strategy involves only the market order, the best bid, and the second best bid; the optimal strategy for the dynamic case is shown to be of a threshold type depending on the remaining trading time, the market momentum, and the price mean-reversion factor. Critical to the analysis is a generalized reflection principle for correlated random walks, which enables a significant dimension reduction.     

Liouville property for groups and manifolds

We introduce a method to estimate the entropy of random walks on groups. We apply this method to exhibit the existence of compact manifolds with amenable fundamental groups such that the universal cover is not Liouville. We also use the criterion to prove that a finitely generated solvable group admits a symmetric measure with non-trivial Poisson boundary if and only if this group is not virtually nilpotent. This, in particular, shows that any polycyclic group admits a symmetric measure such that its boundary does not readily interprete in terms of the ambient Lie group. As another application we get a series of examples of amenable groups such that any finite entropy non-degenerate measure on them has non-trivial Poisson boundary. Since the groups in question are amenable, they do admit measures such that the corresponding random walks have trivial boundary; the above shows that such measures on these groups have infinite entropy. Mathematics Subject Classification (1991) 60B15, 60J50, 28D20, 20P05, 43A07, 60J65, 43A85, 20f16     

Data structures with dynamical random transitions

We present a (non‐standard) probabilistic analysis of dynamic data structures whose sizes are considered dynamic random walks. The basic operations (insertion, deletion, positive and negative queries, batched insertion, lazy deletion, etc.) are time‐dependent random variables. This model is a (small) step toward the analysis of these structures when the distribution of the set of histories is not uniform. As an illustration, we focus on list structures (linear lists, priority queues, and dictionaries) but the technique is applicable as well to more advanced data structures. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On growth,recurrence and the Choquet-Deny Theorem for <Emphasis Type="Italic">p</Emphasis>-adic Lie groups

We first study the growth properties of p-adic Lie groups and its connection with p-adic Lie groups of type R and prove that a non-type R p-adic Lie group has compact neighbourhoods of identity having exponential growth. This is applied to prove the growth dichotomy for a large class of p-adic Lie groups which includes p-adic algebraic groups. We next study p-adic Lie groups that admit recurrent random walks and prove the natural growth conjecture connecting growth and the existence of recurrent random walks, precisely we show that a p-adic Lie group admits a recurrent random walk if and only if it has polynomial growth of degree at most two. We prove this conjecture for some other classes of groups also. We also prove the Choquet-Deny Theorem for compactly generated p-adic Lie groups of polynomial growth and also show that polynomial growth is necessary and sufficient for the validity of the Choquet-Deny for all spread-out probabilities on Zariski-connected p-adic algebraic groups. Counter example is also given to show that certain assumptions made in the main results can not be relaxed.     

Synchronization and functional central limit theorems for interacting reinforced random walks

We obtain Central Limit Theorems in Functional form for a class of time-inhomogeneous interacting random walks. Due to a reinforcement mechanism and interaction, the walks are strongly correlated and converge almost surely to the same, possibly random, limit. We study random walks interacting through a mean-field rule and compare the rate they converge to their limit with the rate of synchronization, i.e. the rate at which their mutual distances converge to zero. We show that, under certain conditions, synchronization is faster than convergence. Even if our focus is on theoretical results, we propose as main motivations two contexts in which such results could directly apply: urn models and opinion dynamics in a random network evolving via preferential attachment.     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

Degrees of Transience and Recurrence and Hierarchical Random Walks

The notion of degree and related notions concerning recurrence and transience for a class of Lévy processes on metric Abelian groups are studied. The case of random walks on a hierarchical group is examined with emphasis on the role of the ultrametric structure of the group and on analogies and differences with Euclidean random walks. Applications to separation of time scales and occupation times of multilevel branching systems are discussed. Mathematics Subject Classifications (2000) 60G50, 60B15, 60F05, 60J80.D.A. Dawson: Research supported by NSERC (Canada) and a Max Planck Award for International Cooperation.L.G. Gorostiza: Research supported by CONACYT grant 37130-E (Mexico).A. Wakolbinger: Research supported by DFG (SPP 1033) (Germany).     

Random walks and the effective resistance of networks

In this article we present an interpretation ofeffective resistance in electrical networks in terms of random walks on underlying graphs. Using this characterization we provide simple and elegant proofs for some known results in random walks and electrical networks. We also interpret the Reciprocity theorem of electrical networks in terms of traversals in random walks. The byproducts are (a) precise version of thetriangle inequality for effective resistances, and (b) an exact formula for the expectedone-way transit time between vertices.     

Random walks on Baumslag–Solitar groups

We consider random walks on non-amenable Baumslag–Solitar groups BS(p, q) and describe their Poisson–Furstenberg boundary. The latter is a probabilistic model for the long-time behaviour of the random walk. In our situation, we identify it in terms of the space of ends of the Bass–Serre tree and the real line using Kaimanovich’s strip criterion.