Huang, Xiang 黄湘

An English translation of the paper Endliche Automaten und Zufallsfolgen

 

This site is new and I haven't decided what to put here yet. 

To begin with, I decided to put an English translation of a German paper (translated by me + Google Translator) here. The funny thing is, I don't know any German, nor my English writing is excellent.

 

Title: Finite Automata and Random Sequence (or Endliche automaten und zufallsfolgen )

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

Files: The original German paper; the English translation. 

Acknowledgment: Professor Schnorr gave 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 originally 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. Agafonov's original proof is way too short to be understandable.