Limit probabilities for random sparse bit strings
Summary: Let \(n\) be a positive integer, \(c\) a real positive constant, and \(p(n) = c/n\). Let \(U_{n,p}\) be the random unary predicate under the linear order, and \(S_c\) the almost sure theory of \(U_{n,\frac{c}{n}}\). We show that for every first-order sentence \(\phi\): \[ f_{\phi}(c) = \lim_{n\rightarrow\infty} \text{Pr}[U_{n,\frac{c}{n}} \text{ has property } \phi] \] is an infinitely differentiable function. Further, let \(S = \bigcap_c S_c\) be the set of all sentences that are true in every almost sure theory. Then, for every \(c>0\), \(S_c = S\).
random unary predicate under linear order
scientific article; zbMATH DE number 1118008