The tenacity of zero-one laws

Joel H. Spencer, Katherine St. John

Research output: Contribution to journalArticlepeer-review

Abstract

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 2 n). For random bit strings and circular sequences with isolated ones (n -1 ≪ p ≪ n -1/2), T (n) = O(min(log 2 np,-log 2 np 2)). 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.

Original languageEnglish (US)
Pages (from-to)1-14
Number of pages14
JournalElectronic Journal of Combinatorics
Volume8
Issue number2 R
StatePublished - 2001

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'The tenacity of zero-one laws'. Together they form a unique fingerprint.

Cite this