On the sampling entropy of permutons

Abstract

For a permuton $\mu$ let $H_n(\mu )$ denote the Shannon entropy of the sampling distribution of $\mu$ on $n$ points. We investigate the asymptotic growth of $H_n(\mu )$ for a wide class of permutons. We prove that if $\mu$ has a non-vanishing absolutely continuous part, then $H_n(\mu )$ has a growth rate $\Theta (n\log n)$. We show that if $\mu$ is the graph of a piecewise continuously differentiable, measure-preserving function $f$, then $H_n(\mu )/n$ tends to the Kolmogorov--Sinai entropy of $f$. Using genericity arguments, we also prove the existence of function permutons for which $H_n(\mu )$ does not converge either after normalizing by $n$ or by $n\log n$. We study the sampling entropy of a natural family of random fractal-like permutons determined by a sequence of i.i.d. choices. It turns out that for every $n$, $H_n(\mu )/n$ is heavily concentrated. We prove that the sequence $H_n(\mu )/n$ either converges or has deterministic log-periodic oscillations almost surely, and argue towards the conjecture that in nondegenerate case, oscillation holds. On the other hand, for a straightforward random perturbation of the model $\tilde{\mu }$ of $\mu$, we prove the almost sure convergence of $H_n(\tilde{\mu })/n$.

43 pages, first submission