An English translation of the paper titled Endliche Automaten und Zufallsfolgen

Here is an English translation of a paper that was published only in German.

Note added in 2026. I made this translation by hand around 2018, with Google Translate as a crutch and no German of my own. A language model today would produce a better one in minutes. What does not get easier is the permission: Professor Schnorr agreed to have an English version posted here, and that is why the page stays up.

Title: Finite Automata and Random Sequence (Endliche Automaten und Zufallsfolgen)

Authors: C. P. Schnorr and H. Stimm.

File: the English translation.

Acknowledgment: Professor Schnorr granted permissions to put the papers above on this page.

This paper contains the so-called Schnorr-Stimm dichotomy theorem, which concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet.

The theorem asserts that, for each such sequence S, the following two things are true.

1. If S is normal in the sense of Borel (meaning that any two strings of equal length appear with equal asymptotic frequency in S), then every finite-state gambler loses money at an exponential rate betting on S.
2. If S is not normal, then there is a finite-state gambler that wins money at an exponential rate betting on S.

Not a lot of people really read the original proof, since it is in German. I decided to read it nonetheless. So I used Google Translator to help me along the way. I took notes carefully because I didn’t want to retype everything I had typed and asked Google Translator again. I reframed Google Translator’s output together with my understanding and generate this document.

Their paper also contains a detailed reproof (and extension) of Agafonov’s theorem, whose original proof is far too terse to follow.