Convergence laws for random words.
James Francis Lynch · 1993
A random word is a finite sequence of symbols chosen independently at random from some finite alphabet. The probability distribution of the symbols may be constant, or it may depend on the length of the word, analogo'Us to the way that edge probabilities of a random graph depend on the number of vertices of the graph. Two formal languages which express properties of words are considered: a first-order predicate calculus, and a monadic second-order calc'ulus. It is shown that every sentence in the first-order language has probability that converges to a limiting value as the length of the word increases. This extends the known convergence r'es'ult for first-order sentences about random words with constant probabilities. A weaker form of convergence law is proven for the monadic second-order language. The proofs rely on a combinatorial game (the Ehrenfeucht game), and results on the asymptotic behavior of finite Markov chains with variable transition probabilities. 1