Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExpected Depth of Random Walks on Groups
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For $G$ a finitely generated group and $g in G$, we say $g$ is detected by a normal subgroup $N lhd G$ if $g otin N$. The depth $D_G(g)$ of $g$ is the lowest index of a normal, finite index subgroup $N$ that detects $g$. In this paper we study the expected depth, $mathbb E[D_G(X_n)]$, where $X_n$ is a random walk on $G$. We give several criteria that imply that $$mathbb E[D_G(X_n)] xrightarrow[nto infty]{} 2 + sum_{k geq 2}frac{1}{[G:Lambda_k]}, ,$$ where $Lambda_k$ is the intersection of all normal subgroups of index at most $k$. In particular, the equality holds in the class of all nilpotent groups and in the class of all linear groups satisfying Kazhdan Property $(T)$. We explain how the right-hand side above appears as a natural limit and also give an example where the convergence does not hold.
rate research
Read More
In this short note we give various near optimal characterizations of random walks over finite Abelian groups with large maximum discrepancy from the uniform measure. We also provide several interesting connections to existing results in the literature.
We describe a novel algorithm for random sampling of freely reduced words equal to the identity in a finitely presented group. The algorithm is based on Metropolis Monte Carlo sampling. The algorithm samples from a stretched Boltzmann distribution begin{align*}pi(w) &= (|w|+1)^{alpha} beta^{|w|} cdot Z^{-1} end{align*} where $|w|$ is the length of a word $w$, $alpha$ and $beta$ are parameters of the algorithm, and $Z$ is a normalising constant. It follows that words of the same length are sampled with the same probability. The distribution can be expressed in terms of the cogrowth series of the group, which then allows us to relate statistical properties of words sampled by the algorithm to the cogrowth of the group, and hence its amenability. We have implemented the algorithm and applied it to several group presentations including the Baumslag-Solitar groups, some free products studied by Kouksov, a finitely presented amenable group that is not subexponentially amenable (based on the basilica group), and Richard Thompsons group $F$.
A $k$-free like group is a $k$-generated group $G$ with a sequence of $k$-element generating sets $Z_n$ such that the girth of $G$ relative to $Z_n$ is unbounded and the Cheeger constant of $G$ relative to $Z_n$ is bounded away from 0. By a recent result of Benjamini-Nachmias-Peres, this implies that the critical bond percolation probability of the Cayley graph of $G$ relative to $Z_n$ tends to $1/(2k-1)$ as $nto infty$. Answering a question of Benjamini, we construct many non-free groups that are $k$-free like for all sufficiently large $k$.
The cutoff phenomenon was recently confirmed for random walks on Ramanujan graphs by the first author and Peres. In this work, we obtain analogs in higher dimensions, for random walk operators on any Ramanujan complex associated with a simple group $G$ over a local field $F$. We show that if $T$ is any $k$-regular $G$-equivariant operator on the Bruhat-Tits building with a simple combinatorial property (collision-free), the associated random walk on the $n$-vertex Ramanujan complex has cutoff at time $log_k n$. The high dimensional case, unlike that of graphs, requires tools from non-commutative harmonic analysis and the infinite-dimensional representation theory of $G$. Via these, we show that operators $T$ as above on Ramanujan complexes give rise to Ramanujan digraphs with a special property ($r$-normal), implying cutoff. Applications include geodesic flow operators, geometric implications, and a confirmation of the Riemann Hypothesis for the associated zeta functions over every group $G$, previously known for groups of type $widetilde A_n$ and $widetilde C_2$.
We consider one-dimensional discrete-time random walks (RWs) with arbitrary symmetric and continuous jump distributions $f(eta)$, including the case of Levy flights. We study the expected maximum ${mathbb E}[M_n]$ of bridge RWs, i.e., RWs starting and ending at the origin after $n$ steps. We obtain an exact analytical expression for ${mathbb E}[M_n]$ valid for any $n$ and jump distribution $f(eta)$, which we then analyze in the large $n$ limit up to second leading order term. For jump distributions whose Fourier transform behaves, for small $k$, as $hat f(k) sim 1 - |a, k|^mu$ with a Levy index $0<mu leq 2$ and an arbitrary length scale $a>0$, we find that, at leading order for large $n$, ${mathbb E}[M_n]sim a, h_1(mu), n^{1/mu}$. We obtain an explicit expression for the amplitude $h_1(mu)$ and find that it carries the signature of the bridge condition, being different from its counterpart for the free random walk. For $mu=2$, we find that the second leading order term is a constant, which, quite remarkably, is the same as its counterpart for the free RW. For generic $0< mu < 2$, this second leading order term is a growing function of $n$, which depends non-trivially on further details of $hat f (k)$, beyond the Levy index $mu$. Finally, we apply our results to compute the mean perimeter of the convex hull of the $2d$ Rouse polymer chain and of the $2d$ run-and-tumble particle, as well as to the computation of the survival probability in a bridge version of the well-known lamb-lion capture problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
