Abstract:
This paper develops the theory of the Extrapolated Successive Overrelaxation (ESOR) method as introduced by Sisler in [1], [2], [3] for the numerical solution of large sparse linear systems of the form Au=b, when A is a consistently ordered 2-cyclic matrix with non-vanishing diagonal elements and the Jacobi iteration matrix B possesses only real eigenvalues. The region of convergence for the ESOR method is described and the optimum values of the involved parameters are also determined. It is shown that if the minimum of the moduli of the eigenvalues of B, ˉ does not vanish, then ESOR attains faster rate of convergence than SOR when 1 ￠ ’ ˉ2<(1 ￠ ’ ˉ2)12, where ˉ denotes the spectral radius of B.

Abstract:
We construct the conditional version of $k$ independent and identically distributed random walks on $\R$ given that they stay in strict order at all times. This is a generalisation of so-called non-colliding or non-intersecting random walks, the discrete variant of Dyson's Brownian motions, which have been considered yet only for nearest-neighbor walks on the lattice. Our only assumptions are moment conditions on the steps and the validity of the local central limit theorem. The conditional process is constructed as a Doob $h$-transform with some positive regular function $V$ that is strongly related with the Vandermonde determinant and reduces to that function for simple random walk. Furthermore, we prove an invariance principle, i.e., a functional limit theorem towards Dyson's Brownian motions, the continuous analogue.

Abstract:
The quantum walks in the lattice spaces are represented as unitary evolutions. We find a generator for the evolution and apply it to further understand the walks. We first extend the discrete time quantum walks to continuous time walks. Then we construct the quantum Markov semigroup for quantum walks and characterize it in an invariant subalgebra. In the meanwhile, we obtain the limit distributions of the quantum walks in one-dimension with a proper scaling, which was obtained by Konno by a different method.

Abstract:
The rotor walk is a derandomized version of the random walk on a graph. On successive visits to any given vertex, the walker is routed to each of the neighboring vertices in some fixed cyclic order, rather than to a random sequence of neighbors. The concept generalizes naturally to Markov chains on a countable state space. Subject to general conditions, we prove that many natural quantities associated with the rotor walk (including normalized hitting frequencies, hitting times and occupation frequencies) concentrate around their expected values for the random walk. Furthermore, the concentration is stronger than that associated with repeated runs of the random walk, with discrepancy at most C/n after n runs (for an explicit constant C), rather than c/sqrt n.

Abstract:
We consider the discrete time unitary dynamics given by a quantum walk on $\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 $\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 stationnary 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 posesses a drift proportional to the time and its centered counterpart displays a diffusive behavior with a diffusion matrix we compute. Moderate and large deviations 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 whose law we compute. We complete the picture by presenting an uncorrelated example.

Abstract:
This note continues paper of Denisov and Wachtel (2010), where we have constructed a $k$-dimensional random walk conditioned to stay in the Weyl chamber of type $A$. The construction was done under the assumption that the original random walk has $k-1$ moments. In this note we continue the study of killed random walks in the Weyl chamber, and assume that the tail of increments is regularly varying of index $\alpha

Abstract:
In a recent paper of Eichelsbacher and Koenig (2008) the model of ordered random walks has been considered. There it has been shown that, under certain moment conditions, one can construct a k-dimensional random walk conditioned to stay in a strict order at all times. Moreover, they have shown that the rescaled random walk converges to the Dyson Brownian motion. In the present paper we find the optimal moment assumptions for the construction of the conditional random walk and generalise the limit theorem for this conditional process.

Abstract:
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 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.

Abstract:
In this paper, we investigate the properties of recurrent planar Markov random walks. More precisely, we study the set of recurrent 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 the (standard or non-standard) central limit theorem holds.

Abstract:
Despite of the extreme success of the spectral graph theory, there are relatively few papers applying spectral analysis to hypergraphs. Chung first introduced Laplacians for regular hypergraphs and showed some useful applications. Other researchers treated hypergraphs as weighted graphs and then studied the Laplacians of the corresponding weighted graphs. In this paper, we aim to unify these very different versions of Laplacians for hypergraphs. We introduce a set of Laplacians for hypergraphs through studying high-ordered random walks on hypergraphs. We prove the eigenvalues of these Laplacians can effectively control the mixing rate of high-ordered random walks, the generalized distances/diameters, and the edge expansions.