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

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

Abstract: We introduce computable actions of computable groups and prove the following versions of effective Birkhoff's ergodic theorem. Let

G a m m a

be a computable amenable group, then there always exists a canonically computable tempered two-sided F{o}lner sequence

(F_{n})_{n g e q 1}

in

G a m m a

. For a computable, measure-preserving, ergodic action of

G a m m a

on a Cantor space

{0, 1}^{m a t h b b N}

endowed with a computable probability measure

m u

, it is shown that for every bounded lower semicomputable function

f

on

{0, 1}^{m a t h b b N}

and for every Martin-L"of random

o m e g a i n {0, 1}^{m a t h b b N}

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})_{n g e q 1}

. We also prove the same identity for all lower semicomputable

f

's in the special case when

G a m m a

is a computable group of polynomial growth and

F_{n} := m a t h r m B (n)

is the F{o}lner sequence of balls around the neutral element of

G a m m a

.

Recommendations

Cites work

Cited in

(6)

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)