Limit Probabilities for Random Sparse Bit Strings
Limit Probabilities for Random Sparse Bit Strings
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\ …