Limit Probabilities for Random Sparse Bit Strings

  • Katherine St. John


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,{c\over n}}$. We show that for every first-order sentence $\phi$: $$ f_{\phi}(c) = \lim_{n\rightarrow\infty}{\Pr}[U_{n,{c\over n}} { 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$.

Article Number