On Effective Birkhoff’s Ergodic Theorem for Computable Actions of Amenable Groups

Nikita Moriakov*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)
36 Downloads (Pure)

Abstract

We introduce computable actions of computable groups and prove the following versions of effective Birkhoff’s ergodic theorem. Let Γ be a computable amenable group, then there always exists a canonically computable tempered two-sided Følner sequence (Fn)n≥ 1 in Γ. For a computable, measure-preserving, ergodic action of Γ on a Cantor space { 0 , 1 } endowed with a computable probability measure μ, it is shown that for every bounded lower semicomputable function f on { 0 , 1 } and for every Martin-Löf random ω∈ { 0 , 1 } the equalitylimn→∞1|Fn|∑g∈Fnf(g⋅ω)=∫fdμholds, where the averages are taken with respect to a canonically computable tempered two-sided Følner sequence (Fn)n≥ 1. We also prove the same identity for all lower semicomputable f’s in the special case when Γ is a computable group of polynomial growth and Fn := B(n) is the Følner sequence of balls around the neutral Γ.

Original languageEnglish
Pages (from-to)1269-1287
Number of pages19
JournalTheory of Computing Systems
Volume62
Issue number5
DOIs
Publication statusPublished - 2018

Keywords

  • Computable actions of groups
  • Effective ergodic theorems

Fingerprint

Dive into the research topics of 'On Effective Birkhoff’s Ergodic Theorem for Computable Actions of Amenable Groups'. Together they form a unique fingerprint.

Cite this