On effective Birkhoff's ergodic theorem for computable actions of amenable groups

DOI10.1007/S00224-017-9822-5zbMATH Open1436.03234DBLPjournals/mst/Moriakov18arXiv1701.06365OpenAlexW2580431628WikidataQ59481939 ScholiaQ59481939MaRDI QIDQ722220FDOQ722220

Authors: Nikita Moriakov 

Publication date: 23 July 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We introduce computable actions of computable groups and prove the following versions of effective Birkhoff's ergodic theorem. Let $Gamma$ be a computable amenable group, then there always exists a canonically computable tempered two-sided F{o}lner sequence $(F_n{)}_{ngeq1}$ in $Gamma$. For a computable, measure-preserving, ergodic action of $Gamma$ on a Cantor space ${0,1}^{mathbbN}$ endowed with a computable probability measure $mu$, it is shown that for every bounded lower semicomputable function $f$ on ${0,1}^{mathbbN}$ and for every Martin-L"of random $omegain{0,1}^{mathbbN}$ the equality [ limlimits_{n o infty} frac{1}{|F_n|} sumlimits_{g in F_n} f(g cdot omega) = intlimits f d mu ] holds, where the averages are taken with respect to a canonically computable tempered two-sided F{o}lner sequence $(F_n{)}_{ngeq1}$. We also prove the same identity for all lower semicomputable $f$'s in the special case when $Gamma$ is a computable group of polynomial growth and $F_n:=mathrmB(n)$ is the F{o}lner sequence of balls around the neutral element of $Gamma$.

Full work available at URL: https://arxiv.org/abs/1701.06365

Recommendations

• Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• Subsequence ergodic theorems for amenable groups
• A comment on ergodic theorem for amenable groups
• Amenable equivalence relations and the construction of ergodic averages for group actions

zbMATH Keywords

computable actions of groupseffective ergodic theorems

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Ergodic theorems, spectral theory, Markov operators (37A30) Theory of numerations, effectively presented structures (03D45)

Cites Work

• Entropy and isomorphism theorems for actions of amenable groups
• Title not available (Why is that?)
• Croissance des boules et des géodésiques fermées dans les nilvariétés
• Operator theoretic aspects of ergodic theory
• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей
• Computable Algebra, General Theory and Theory of Computable Fields
• The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
• Cellular automata and groups
• Title not available (Why is that?)
• Pointwise theorems for amenable groups.
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points

Cited In (6)

• On decidability of amenability in computable groups
• Fluctuation bounds for ergodic averages of amenable groups
• Computable paradoxical decompositions
• Uncomputably noisy ergodic limits
• A notion of effectiveness for subshifts on finitely generated groups
• Computability theory. Abstracts from the workshop held January 7--13, 2018

This page was built for publication: On effective Birkhoff's ergodic theorem for computable actions of amenable groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722220)