Effective SMB theorem for measures

Let A\mathbb A^\infty be the space of one-sided infinite sequences over the alphabet AA, with shift operator TT. Let μ\mu be a computable ergodic TT-invariant measure, and define

hnμ(Z)=1nlogμ[Zn].h^\mu_n(Z)=-\frac{1}{n}\log\mu[Z\upharpoonright_n].

Write H(μ)=limnHn(μ)H(\mu)=\lim_n H_n(\mu) for the entropy of μ\mu, where

Hn(μ)=1nw=nμ[w]logμ[w].H_n(\mu)=-\frac{1}{n}\sum_{|w|=n}\mu[w]\log\mu[w].

Suppose that a measure ρ\rho is μ\mu-Martin-Löf absolutely continuous if ρ(Gm)0\rho(G_m)\to0 for every μ\mu-Martin-Löf test (Gm)mN(G_m)_{m\in\mathbb N}. Effective SMB theorem for measures. If ρ\rho is μ\mu-Martin-Löf absolutely continuous, then

limnEρhnμ=H(μ).\lim_n E_\rho h^\mu_n=H(\mu).

This extends the effective almost-sure Shannon–McMillan–Breiman conclusion from μ\mu-Martin-Löf random sequences to expectations with respect to measures absolutely continuous in the Martin-Löf sense. The supplied context identifies it as a special case of a conjecture from the 2017 Logic Blog; its resolution is not specified here.

Sources & referencesView supporting material

Primary source

Andre Nies, “Logic Blog 2018”, arXiv:1902.08725 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.