Eigenvalues of Quantum Walks of Grover and Fourier Types

A necessary and sufficient conditions for a certain class of periodic unitary transition operators to have eigenvalues are given. Applying this, it is shown that Grover walks in any dimension has both of \(\pm \, 1\) as eigenvalues and it has no other eigenvalues. It is also shown that the lazy Grover walks in any dimension has 1 as an eigenvalue, and it has no other eigenvalues. As a result, a localization phenomenon occurs for these quantum walks. A general conditions for the existence of eigenvalues can be applied also to certain quantum walks of Fourier type. It is shown that the two-dimensional Fourier walk does not have eigenvalues and hence it is not localized at any point. Some other topics, such as Grover walks on the triangular lattice, products and deformations of Grover walks, are also discussed.

     

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.

     

Analysis of Bidirectional Ballot Sequences and Random Walks Ending in Their Maximum

Consider non-negative lattice paths ending at their maximum height, which will be called admissible paths. We show that the probability for a lattice path to be admissible is related to the Chebyshev polynomials of the first or second kind, depending on whether the lattice path is defined with a reflective barrier or not. Parameters like the number of admissible paths with given length or the expected height are analyzed asymptotically. Additionally, we use a bijection between admissible random walks and special binary sequences to prove a recent conjecture by Zhao on ballot sequences.     

Walks and paths in trees

Recently Csikvári [Combinatorica 30(2) 2010, 125–137] proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend this theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negative. Finally we consider an analogous question for paths rather than walks. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On exactness and isoperimetric profiles of discrete groups

We introduce a quasi-isometry invariant related to Property A and explore its connections to various other invariants of finitely generated groups. This allows to establish a direct relation between asymptotic dimension on one hand and isoperimetry and random walks on the other. We apply these results to reprove sharp estimates on isoperimetric profiles of some groups and to answer some questions in dimension theory.     

Total progeny in killed branching random walk

We consider a branching random walk for which the maximum position of a particle in the n??th generation, R _n , has zero speed on the linear scale: R _n /n ?? 0 as n ?? ??. We further remove (??kill??) any particle whose displacement is negative, together with its entire descendence. The size Z of the set of un-killed particles is almost surely finite (Gantert and Müller in Markov Process. Relat. Fields 12:805?C814, 2006; Hu and Shi in Ann. Probab. 37(2):742?C789, 2009). In this paper, we confirm a conjecture of Aldous (Algorithmica 22:388?C412, 1998; and Power laws and killed branching random walks) that E [Z]?<??? while ${{\mathbf E}\left[Z\,{\rm log}\, Z\right]=\infty}$ . The proofs rely on precise large deviations estimates and ballot theorem-style results for the sample paths of random walks.     

The number of lattice paths below a cyclically shifting boundary

We count the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope. Our main result can be viewed as an extension of well-known enumerative formulae concerning lattice paths dominated by lines of integer slope (e.g. the generalized ballot theorem). Its proof is bijective, involving a classical “reflection” argument. Moreover, a straightforward refinement of our bijection allows for the counting of paths with a specified number of corners. We also show how the result can be applied to give elegant derivations for the number of lattice walks under certain periodic boundaries. In particular, we recover known expressions concerning paths dominated by a line of half-integer slope, and some new and old formulae for paths lying under special “staircases.”     

On Matrix Rings and Subhereditary Radicals

Abstract

We study some one-sided ideals of row bounded and of column bounded matrix rings over free algebras. Obtained results are applied to answer several open problems on subhereditary radicals of associative rings. In particular we show that the right strongly prime radical is not left subhereditary and that the lattice of left (right) subhereditary radicals is not complete.     

Persistent Random Walks. I. Recurrence Versus Transience

We consider a walker on the line that at each step keeps the same direction with a probability which depends on the time already spent in the direction the walker is currently moving. These walks with memories of variable length can be seen as generalizations of directionally reinforced random walks introduced in Mauldin et al. (Adv Math 117(2):239–252, 1996). We give a complete and usable characterization of the recurrence or transience in terms of the probabilities to switch the direction and we formulate some laws of large numbers. The most fruitful situation emerges when the running times both have an infinite mean. In that case, these properties are related to the behaviour of some embedded random walk with an undefined drift so that these features depend on the asymptotics of the distribution tails related to the persistence times. In the other case, the criterion reduces to a null-drift condition. Finally, we deduce some criteria for a wider class of persistent random walks whose increments are encoded by a variable length Markov chain having—in full generality—no renewal pattern in such a way that their study does not reduce to a skeleton RW as for the original model.     

On the distribution of range for tree-indexed random walks

We study tree-indexed random walks as introduced by Benjamini, Häggström, and Mossel, i.e., labelings of a tree for which adjacent vertices have labels differing by 1. It is a conjecture of those authors that the distribution of the range for any such tree is dominated by that of a path on the same number of edges. The two main variants of this conjecture considered in the literature are the standard walks, in which adjacent vertices must have labels differing by exactly 1, and lazy walks, in which adjacent vertices must have labels differing by at most 1. We confirm this conjecture for all trees in the lazy case and provide some partial results in the standard case.     

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.     

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.     

A combinatorial result with applications to self-interacting random walks

We give a series of combinatorial results that can be obtained from any two collections (both indexed by Z×N) of left and right pointing arrows that satisfy some natural relationship. When applied to certain self-interacting random walk couplings, these allow us to reprove some known transience and recurrence results for some simple models. We also obtain new results for one-dimensional multi-excited random walks and for random walks in random environments in all dimensions.     

The peak and descent statistics over ballot permutations

A ballot permutation is a permutation π such that in any prefix of π the descent number is not more than the ascent number. By using a reversal-concatenation map, we (i) give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, (ii) connect this distribution and the joint distribution (pk, des) over ordinary permutations in terms of generating functions, and (iii) confirm Spiro's conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.     

A law of the iterated logarithm for a class of polynomial hypergroups

We consider stationary ₀-valued Markov chains whose transition probabilities are associated with convolution structures of measures which are induced by linearization formulas of orthogonal polynomials. The best known examples are random walks on polynomial hypergroups and generalized birth and death random walks. Using central limit theorems derived in a recent paper by the author and some martingale arguments, we here prove a law of the iterated logarithm for a class of such Markov chains.     

RESULTS AND CONJECTURES ON COVERING METRIC SPACES

Abstract

A semi-quantitative theory of covering metric spaces is studied; the theory, involving the concept of a ‘fine cover’, has proved useful in complex analysis. We obtain general results on fine covers, and put forward some conjectures. Most of these remain unanswered (and indeed seem most difficult to answer) for subsets of the real line.     

On square roots of isometries

Abstract

In various normed spaces we answer the question of when a given isometry is a square of some isometry. In particular, we consider (real and complex) matrix spaces equipped with unitarily invariant norms and unitary congruence invariant norms, as well as some infinite dimensional spaces illustrating the difference between finite and infinite dimensions.     

A generalized central limit theorem in infinite ergodic theory

We prove a generalized central limit theorem for dynamical systems with an infinite ergodic measure which induce a Gibbs–Markov map on some subset, provided the return time to this subset has regularly varying tails. We adapt a method designed by Csáki and Földes for observables of random walks to show that the partial sums of some functions of the system—the return time and the observable—are asymptotically independent. Some applications to random walks and Pomeau–Manneville maps are discussed.     

Poisson approximation for non-backtracking random walks

Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. The authors of [3] studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1)))log n/log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun’s sieve with some extensions of the ideas in [3]. Let N _t denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g = ω(1), then for any fixed t, N _t /n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then N _t /n is typically 1+o(1)/et! niformly on all t ≤ (1 − o(1)) log n/log log n and 0 for all t ≥ (1 + o(1)) log n/log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.