ترغب بنشر مسار تعليمي؟ اضغط هنا

Expected Depth of Random Walks on Groups

65   0   0.0 ( 0 )
 نشر من قبل Ioan Manolescu
 تاريخ النشر 2016
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

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 be gin{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 re sult 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 an d 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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا