Random Sparse Bit Strings at the Threshold of Adjacency

摘要

We give a complete characterization for the limit probabilities of first order sentences over sparse random bit strings at the threshold of adjacency. For strings of length n, we let the probability that a bit is "on" be c/square root of (n), fro a real positive number c. For the every first order sentence fai, we show that the limit probability function: f sub fai(c)=lim sub n-infinity Pr[U sub n, c/square root of (n) has the property fai] is infinitely differnetiable. Our methodology for showing this is in itself interesting. We begin with finite models, go to the infinite (via the almost sure theories) and then characterize f sub fai(c) as an infinite sum of products ofpolynomials and exponentials. We further show that if a sentence fai has limiting probability 1 for some c, then fai has limiting probability idnetically 1 for every c. This gives the surprising result that the almost sure theories are idnetical for every c.