Effective SMB theorem for measures

About 7 years old · traced to

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⁡μ[Z↾n].h^\mu_n(Z)=-\frac{1}{n}\log\mu[Z\upharpoonright_n].

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

Hn(μ)=−1n∑∣w∣=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)m∈N(G_m)_{m\in\mathbb N}. Effective SMB theorem for measures. If ρ\rho is μ\mu-Martin-Löf absolutely continuous, then

lim⁡nEρ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.

References

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.