Stijn Vermeeren

Bij het schrijven van mijn doctoraatsthesis moet ik ook heel wat door historische bronnen pluizen om de correcte referenties te kunnen geven. Daarbij hoort ook de doctoraatsthesis van Jean André Ville uit 1939, getiteld "Étude critique de la notion de collectif". Hieruit komt de volgende passage:

Het is zonder meer de meest opmerkelijke paragraaf die ik in mijn bronnenonderzoek ben tegengekomen. Ik leg uit waarom.

Het centrale probleem in mijn onderzoek gaat als volgt. Veronderstel dat je een muntstuk herhaaldelijk opwerpt. Je schrijft het cijfer 0 elke keer als de uitkomst 'kop' is, en het cijfer 1 telkens als de uitkomst 'munt' is. Als er zo een rij als 0100101110... verschijnt, dan valt daar weinig op aan te merken. Als je echter de rij 0000000000... te zien krijgt, dan zal je snel achterdochtig worden. Onze intuïtie maakt een duidelijk onderscheid tussen toevalsrijen (random sequences) en regelmatige rijen. Toch zijn beide voorbeelden statistisch even waarschijnlijk. Het onderzoeksgebied van algorithmic randomness maakt gebruik van berekenbaarheidstheorie om definities van toevalsrijen te formuleren die een uitweg uit deze paradox bieden. Daarmee is algorithmic randomness een onderwerp op de grens tussen wiskundige logica en theoretische informatica.

De zoektocht naar een wiskundige definitie van toevalsrijen is echter ouder dan de berekenbaarheidstheorie zelf. In het begin van de twintigste eeuw, voordat Kolmogorov zijn axioma's formuleerde, was de kansrekening nog een erg onnauwkeurige discipline. Wiskundigen hoopten dat een wiskundige definitie van een toevalsrij een fundament zou zijn, waarop de rest van de kansrekening rigoureus zou kunnen gebouwd worden.

Richard Von Mises probeerde in 1919 toevalsrijen (die hij Kollektivs noemde) te definiëren door gebruik te maken van de wet van de grote getallen, die zegt dat in een toevalsrij de limietfrequenties van nullen en enen allebei gelijk moeten zijn aan 1/2. Dat is echter niet voldoende. De rij 010101010101... bijvoorbeeld, voldoet aan de wet van de grote getallen, maar is duidelijk geen toevalsrij. Uit deze rij kan je echter gemakkelijk een deelrij selecteren die niet meer voldoet aan de wet van de grote getallen. Bijvoorbeeld door alle even posities te selecteren, krijg je een rij met enkel nullen. (Ja, ik ben een logicus dus ik begin te tellen met positie nul.) Aldus definieerde Von Mises een toevalsrij als een rij waarvoor elke selecteerbare deelrij voldoet aan de wet van de grote getallen.

Helaas was Von Mises niet in staat om exact te formuleren wat nu juist een selecteerbare deelrij is. Pas rond 1936 kon Abraham Wald voor het eerst de dubbelzinnigheid uit Von Mises' definitie weghalen. Wald stelde voor het eerst expliciet dat men zich moet beperken tot een aftelbare verzameling van selectieregels en hij suggereerde ook dat die regels "in endlich vielen Schritten berechnet" moeten kunnen worden. In 1940 tenslotte eindigt de geschiedenis met Alonzo Church, die in de jaren '30 mee aan de wieg stond van de berekenbaarheidstheorie. Met een wiskundige definitie van berekenbare functie stelde Church voor om enkel berekenbare selectieregels te beschouwen. Het resulterende begrip, dat tegenwoordig Church stochasticity wordt genoemd, is eindelijk een exacte vorm van Von Mises's Kollectiv-idee.

Inmiddels was het kwaad echter al geschied voor Von Mises' project. Door de dubbelzinnigheid had Von Mises' benadering door de jaren heen meer tegenstanders dan aanhangers gevonden. Verschillende wiskundigen stelden dat het simpelweg een onmogelijke opgave is om een toevalsrij wiskundig te definiëren. Als je iets in een definitie kunt vatten, kan er van echte wanorde geen sprake meer zijn, toch? Toen Kolmogorov in 1933 zijn axioma's van de kansrekening formuleerde, werden die als snel algemeen aanvaard als basis voor de hele discipline. Tot overmaat van ramp ontdekte Jean Ville, al werkend aan zijn doctoraat, een fundamenteel probleem met Von Mises' benadering. In een toevalsrij verwachten we dat de frequentie van nullen rond de uiteindelijke limiet van 1/2 oscilleert. Bij het herhaaldelijk opwerpen van een muntstuk, heb je soms een groter aantal keer 'kop' dan 'munt', maar op andere ogenblikken zal het andersom zijn. Ville toonde echter aan dat dit oscillerende gedrag niet gevat kan worden door de wet van de grote getallen voor deelrijen te beschouwen, welke verzameling van selectieregels men ook gebruikt. Daarmee is ook de nauwkeurige definitie van Church stochasticity geen bevredigende definitie voor toevalsrijen. Pas in 1966 zou Per Martin-Löf eindelijk een algemeen aanvaarde definitie van toevalsrij geven, nu gekend onder de naam Martin-Löf randomness.

Nu komt echter de echte bombshell. We gaan terug naar de jaren '30. Ville onderzoekt in zijn thesis een mogelijke oplossing voor het probleem dat hij ontdekt heeft met Von Mises' benadering. Enkel de wet van de grote getallen beschouwen volstaat niet. Er is nood aan een meer algemene methode voor het ontdekken van regelmatigheden in een binaire rij. Ville denkt aan kansspelen in een casino. Stel je voor dat je geld kunt inzetten op de uitkomst van de worp van een muntstuk. Zet je geld in op de juiste uitkomst ('kop' of 'munt'), dan krijg je je inzet verdubbeld terug, maar als je verkeerd inzet dan verlies je je inzet. Als de uitkomsten een toevalsrij volgen, dan zal je geen noemenswaardige winsten kunnen verwachten. Als er echter een regelmaat zit in de rij, dan zal je een gokstrategie hebben die die regelmaat uitbuit en je onbegrensde winsten geeft.

Ville geeft een wiskundige definitie voor een dergelijke gokstrategie en geeft er de naam martingale aan. De naam martingalestrategie werd eerder al gebruikt voor de gokstrategie die bij verlies steeds de inzet zodanig verhoogt, dat bij een uiteindelijke goede uitkomst alle verliezen ongedaan worden gemaakt. Het probleem daarbij is natuurlijk dat de exponentieel groeiende inzet de gokker al snel blut zal maken, voordat hij de kans heeft om zijn verliezen terug in winst om te zetten, een voorbeeld van de zogenaamde gambler's ruin. Deze bepaalde strategie is een speciaal geval van Ville's martingales. Overigens, in zijn thesis geeft Ville ook een elegant bewijs van de gambler's ruin door slim gebruik te maken van zijn definitie van martingales.

Nu denk je reeds dat Ville met zijn martingales de oplossing heeft gevonden. Een toevalsrij is een rij waarvoor geen enkele gokstrategie succesvol is. Maar lees nu terug het citaat bovenaan dit bericht. De "question de l'irrégularité" is de zoektocht naar een wiskundige definitie van toevalsrij. En Ville legt zich neer bij de mening van een aantal gezaghebbende wiskundigen dat dit een "onoplosbaar probleem" is! De uitleg? Een definitie van toevalsrij met martingales vereist een "voorafgaande keuze" over welke verzameling van gokstrategieën we beschouwen, en aldus van welke rijen uiteindelijk als regelmatig worden beschouwd.

Maar he... zo'n probleem hadden we toch eerder ook met selectieregels in plaats van gokstrategieën? Dat loste Church op door de verzameling van berekenbare selectieregels te beschouwen. Dus waarom beschouwen we nu niet simpelweg de verzameling van berekenbare gokstrategieën? Had Ville deze link gelegd, dan was hij de grondlegger van algorithmic randomness geweest, bijna 30 jaar voor Martin-Löf! Maar Ville wist schijnbaar niets af van de recente ontwikkelingen in de berekenbaarheidstheorie. Uiteindelijk legde Claus-Peter Schnorr pas in 1970 de missing link en definieerde zo computable randomness, een alternatief voor Martin-Löf randomness.

Tragisch toch. Ville staat vlakbij een revolutionair resultaat. Het baanbrekende recept staat reeds op punt, alleen het allerlaatste ingrediënt moet nog toegevoegd worden. En hij geeft op en bestempelt het hele project als onoplosbaar...

Waarom gaf hij op? Zijn promotoren, Émile Borel en Maurice Fréchet, allebei grote namen in de wiskundegeschiedenis, waren eerder geïnteresseerd in analyse en aldus aanhangers van Kolmogorov's axioma's. De gangbare opinie was dat Von Mises' Kollektivs niet tot evenwaardige resultaten konden leiden. Ville was ongetwijfeld beïnvloed door die visie, wat ook duidelijk wordt uit de titel van zijn thesis, "Étude critique de la notion de collectif", en door de expliciete vermelding van Borel, Fréchet en een derde wiskundige, Lévy, in het bovenstaande citaat. Kansrekening en logica werden in de jaren '30 nog niet zo gerespecteerd als volwaardige disciplines. Ville had de meeste resultaten over toevalsrijen al klaar rond 1936. Het duurde echter nog tot 1939 voordat hij zijn thesis afwerkte, onder meer omdat hij onder druk stond om meer werk in analyse te doen om zijn thesis meer respectabel te maken. In 1936 echter waren de eerste wiskundige definities van berekenbaarheid nog maar pas geformuleerd door onder andere Turing en Church. Zonder contact met logici zal Ville zich niet bewust zijn geweest van deze ontwikkelingen. Toen de bekendheid van berekenbaarheidstheorie groeide, was Ville's aandacht reeds verschoven. Het is niet duidelijk of de definitie van Church stochasticity uit 1940 tot Ville is doorgedrongen. Dat is echter niet erg waarschijnlijk, vanwege de uitbraak van de Tweede Wereldoorlog in Frankrijk. Andersom is er in het artikel van Church geen enkel spoor van Ville.

Na de oorlog verdween het probleem van de toevalsrijen uit het gezichtsveld van de meeste wiskundigen. Ville's idee van de martingale kreeg, in een gewijzigde vorm, een belangrijke rol in de kansrekening, vooral dankzij het werk van Joseph Leo Doob. Pas in de jaren '60, met het werk van Kolmogorov en Solomonoff over algoritmische complexiteit en de daarop volgende definitie van Martin-Löf randomness, kwamen toevalsrijen terug in de aandacht. Zo was het uiteindelijk Schnorr die de ontbrekende stap in Ville's werk voltooide, 30 jaar na datum.

Wie meer wil lezen kan terecht bij het Journal Electronique d'Histoire des Probabilités et de la Statistique, waar een aantal gratis toegankelijke artikels over de geschiedenis van martingales te vinden is.