The tenacity of zero-one laws

The Ehrenfeucht-Fraisse game is a two-person game of perfect information which is connected to the Zero-One Laws of first order logic. We give bounds for roughly how quickly the Zero-One Laws converge for random bit strings and random circular bit sequences. We measure the tenaciousness of the second player ("Duplicator") in playing the Ehrenfeucht-Fraisse game, by bounding the numbers of moves Duplicator can play and win with probability 1-∈. We show that for random bit strings and random circular sequences of length n generated with a low probability (p ≪ n ^-1), the number of moves, T _∈(n), is Θ(log ₂ n). For random bit strings and circular sequences with isolated ones (n ^-1 ≪ p ≪ n ^-1/2), T _∈(n) = O(min(log ₂ np,-log ₂ np ²)). For n ^-1/2 ≪ p and (1 - p) ≪ n ^-1/2, we show that T _∈(n) = O(log* n) for random circular sequences, where log* n has the usual definition-the least number of times you iteratively apply the logarithm to get a value less than one.