Random expansions of trees with bounded height

Abstract

We consider a sequence $\mathbf{T}=({\mathcal{T}}_n:n\in {\mathbb{N}}^{+})$ of trees ${\mathcal{T}}_n$ where, for some $\hat{I}”\in {\mathbb{N}}^{+}$ every ${\mathcal{T}}_n$ has height at most $\hat{I}”$ and as $n\to \infty$ the minimal number of children of a nonleaf tends to infinity. We can view every tree as a (first-order) $\ddot{I}„$-structure where $\ddot{I}„$ is a signature with one binary relation symbol. For a fixed (arbitrary) finite and relational signature $\ddot{I}ƒ\supseteq \ddot{I}„$ we consider the set ${\mathbf{W}}_n$ of expansions of ${\mathcal{T}}_n$ to $\ddot{I}ƒ$ and a probability distribution ${\mathbb{P}}_n$ on ${\mathbf{W}}_n$ which is determined by a (parametrized/lifted) Probabilistic Graphical Model (PGM) $\mathbb{G}$ which can use the information given by ${\mathcal{T}}_n$. The kind of PGM that we consider uses formulas of a many-valued logic that we call $PL{A}^{\ast }$ with truth values in the unit interval $[0,1]$. We also use $PL{A}^{\ast }$ to express queries, or events, on ${\mathbf{W}}_n$. With this setup we prove that, under some assumptions on $\mathbf{T}$, $\mathbb{G}$, and a (possibly quite complex) formula $\ddot{I}†(x_1,\dots ,x_k)$ of $PL{A}^{\ast }$, as $n\to \infty$, if $a_1,\dots ,a_k$ are vertices of the tree ${\mathcal{T}}_n$ then the value of $\ddot{I}†(a_1,\dots ,a_k)$ will, with high probability, be almost the same as the value of $\ddot{I}ˆ(a_1,\dots ,a_k)$, where $\ddot{I}ˆ(x_1,\dots ,x_k)$ is a ``simple'' formula the value of which can always be computed quickly (without reference to $n$), and $\ddot{I}ˆ$ itself can be found by using only the information that defines $\mathbf{T}$, $\mathbb{G}$ and $\ddot{I}†$. A corollary of this, subject to the same conditions, is a probabilistic convergence law for $PL{A}^{\ast }$-formulas.

arXiv admin note: text overlap with arXiv:2401.04802 Author comment: This is a minor revision (but with some important corrections) of the first version