pith. sign in

arxiv: 1809.02290 · v2 · pith:BFC2IWR3new · submitted 2018-09-07 · 🧮 math.LO · math.CO· math.PR

The entropy function of an invariant measure

classification 🧮 math.LO math.COmath.PR
keywords entropyfunctioninvariantmeasurefunctionsmeasuresarbitrarilyarity
0
0 comments X
read the original abstract

Given a countable relational language $L$, we consider probability measures on the space of $L$-structures with underlying set $\mathbb{N}$ that are invariant under the logic action. We study the growth rate of the entropy function of such a measure, defined to be the function sending $n \in \mathbb{N}$ to the entropy of the measure induced by restrictions to $L$-structures on $\{0, \ldots, n-1\}$. When $L$ has finitely many relation symbols, all of arity $k\ge 1$, and the measure has a property called non-redundance, we show that the entropy function is of the form $Cn^k+o(n^k)$, generalizing a result of Aldous and Janson. When $k\ge 2$, we show that there are invariant measures whose entropy functions grow arbitrarily fast in $o(n^k)$, extending a result of Hatami-Norine. For possibly infinite languages $L$, we give an explicit upper bound on the entropy functions of non-redundant invariant measures in terms of the number of relation symbols in $L$ of each arity; this implies that finite-valued entropy functions can grow arbitrarily fast.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.