| Título: | Mixing and relaxation time for random walk on wreath product graphs |
| Autores: |
Komjáthy, Júlia; Budapest University of Technology and Economics Peres, Yuval; Microsoft Research |
| Fecha: | 2013-01-04 |
| Publicador: | Electronic journal of probability |
| Fuente: |
 |
| Tipo: | Peer-reviewed Article |
| Tema: |
Random Walk, Wreath Product Graphs, Mixing Time, Relaxation Time 60J10, 60D05, 37A25 |
| Descripción: | Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product H\wr G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_{v\in V(G)} is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H. |
| Idioma: | Inglés |
1 Lévy Classes and Self-Normalization por Khoshnevisan, Davar; University of Utah | 6 Time-Space Analysis of the Cluster-Formation in Interacting Diffusions por Fleischmann, Klaus; Weierstrass Institute for Applied Analysis and Stochastics,Greven, Andreas; Universitat Erlangen-Nurnberg |
2 Hausdorff Dimension of Cut Points for Brownian Motion por Lawler, Gregory F.; Duke University and Cornell University | 7 Conditional Moment Representations for Dependent Random Variables por Bryc, Wlodzimierz; University of Cincinnati |
3 Eigenvalue Expansions for Brownian Motion with an Application to Occupation Times por Bass, Richard F.; University of Washington,Burdzy, Krzysztof; University of Washington | 8 Almost Sure Exponential Stability of Neutral Differential Difference Equations with Damped Stochastic Perturbations por Liao, Xiao Xin; University of Strathclyde,Mao, Xuerong; University of Strathclyde |
4 Random Discrete Distributions Derived from Self-Similar Random Sets por Pitman, Jim; University of California, Berkeley,Yor, Marc; Université Pierre et Marie Curie | 9 Quantitative Bounds for Convergence Rates of Continuous Time Markov Processes por Roberts, Gareth O.; University of Cambridge,Rosenthal, Jeffrey S.; University of Toronto |
5 A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences por Seppäläinen, Timo; Iowa State University | 10 Metastability of the Three Dimensional Ising Model on a Torus at Very Low Temperatures por Ben Arous, Gérard; Ecole Normale Supérieure,Cerf, Raphaël; Université Paris Sud |