The entropy function of an invariant measure

DOI10.1142/9789813237551_0001MaRDI QIDQ6306366FDO

Authors Nathanael Ackerman, Cameron E. Freer, Rehana Patel

Publication date 6 September 2018

Abstract: Given a countable relational language $L$, we consider probability measures on the space of $L$-structures with underlying set $mathbbN$ 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 $ninmathbbN$ 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 $kge1$, and the measure has a property called non-redundance, we show that the entropy function is of the form $C{n}^k+o(n^k)$, generalizing a result of Aldous and Janson. When $kge2$, 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 page was built for publication: The entropy function of an invariant measure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6306366)