## 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 language | English (US) |
---|---|

Pages (from-to) | 1-14 |

Number of pages | 14 |

Journal | Electronic Journal of Combinatorics |

Volume | 8 |

Issue number | 2 R |

State | Published - 2001 |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics