Markovian linearization of random walks on groups

2020/11/28 by Charles Bordenave, Bordenave, Charles, Bastien Dubail +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #FOS: Mathematics #Geometric and Algebraic Topology #Probability (math.PR) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2011.14127

openalex publication_date 2020/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In operator algebra, the linearization trick is a technique that reduces the study of a non-commutative polynomial evaluated at elements of an algebra A to the study of a polynomial of degree one, evaluated on the enlarged algebra A x M r (C), for some integer r. We introduce a new instance of the linearization trick which is tailored to study a finitely supported random walk on a group G by studying instead a nearest-neighbor colored random walk on G x 1,. .. , r, which is much simpler to analyze. As an application we extend well-known results for nearest-neighbor walks on free groups and free products of finite groups to colored random walks, thus showing how one can obtain explicit formulas for the drift and entropy of a finitely supported random walk.

Cited by

• Sparse graphs and their Benjamini-Schramm limits: a spectral tour

Related

• Random walks on free products of cyclic groups
• Algebraically recurrent random walks on groups
• Convergence rates of random walk on irreducible representations of finite groups
• Drift and entropy growth for random walks on groups
• The predicable dance of random walk: local limit theorems on finitely-generated abelian groups