BSc_thesis_Rik_Versendaal - TU Delft Institutional Repository

Technische Universiteit Delft
Faculteit Elektrotechniek, Wiskunde en Informatica
Delft Institute of Applied Mathematics
Arithmetische progressies in random kleuringen van
de natuurlijke getallen
(Engelse titel: Arithmetic progressions in random
colourings of the natural numbers)
Verslag ten behoeve van het
Delft Institute of Applied Mathematics
als onderdeel ter verkrijging
van de graad van
BACHELOR OF SCIENCE
in
TECHNISCHE WISKUNDE
door
RIK VERSENDAAL
Delft, Nederland
Juni 2014
c 2014 door Rik Versendaal. Alle rechten voorbehouden.
Copyright BSc verslag TECHNISCHE WISKUNDE
“Arithmetische progressies in random kleuringen
van de natuurlijke getallen”
(Engelse titel: “Arithmetic progression in random colourings
of the natural numbers”
RIK VERSENDAAL
Technische Universiteit Delft
Begeleider
Prof.Dr. F.H.J Redig
Overige commissieleden
Dr.ir. M.C. Veraar
Dr.ir F.H. van der Meulen
Dr.ir. M. Keijzer
Juni, 2014
Delft
iii
Samenvatting
In deze scriptie bestuderen we arithmetische progressies in random kleuringen van de natuurlijke
getallen. De aanleiding voor het onderwerp wordt gevormd door een aantal bekende resultaten,
zoals de stelling van Van der Waerden en die van Szemer´edi. Ook het recente resultaat van
Green en Tao, dat zegt dat de priemgetallen willekeurig lange arithmetische progressies bevatten,
heeft eraan bijgedragen. Mede door dit resultaat heeft Terence Tao in 2006 een Fields Medal
ontvangen. In een eerste hoofdstuk zullen we deze resultaten tot op een zekere hoogte bekijken.
Daarna is er de noodzaak om een aantal kanstheoretische begrippen te introduceren, met
name over de convergentie van rijen stochasten. Vooral omdat wij willen kijken naar het bestaan
van willekeurig lange arithmetische progressies, zal het nodig zijn om over te gaan op limieten.
We zullen twee manieren van convergentie bespreken die wij nodig zullen hebben. Daarnaast geven we nog enkele resultaten en voorbeelden om de betekenis van de begrippen te verduidelijken,
en ook om latere bewijzen wat eenvoudiger te maken.
Met deze theorie zijn we vervolgens in staat om een zwakke en een sterke versie van de wet
van de grote aantallen betreffende arithmetische progressies in onafhankelijke random kleuringen
te bewijzen. Deze resultaten zullen we vervolgens toepassen op het stochastische model van de
priemgetallen, zoals Cram`er dat heeft geformuleerd. Dit model staat beschreven in [5]. Het zal
blijken dat we dan een stochastisch analogon krijgen van de stelling van Green en Tao.
Vervolgens zullen we laten zien, dat het niet per se nodig is om te eisen dat de getallen
onafhankelijk van elkaar worden gekleurd. We kijken naar afhankelijkheden tussen progressies,
die afhangen van de minimale afstand tussen de progressies. We beginnen met een eenvoudige
vorm van afhankelijkheden om ons ervan te overtuigen dat kleine afhankelijkheden nog steeds
kunnen leiden tot een positief resultaat. Daarna kijken we naar een meer realistisch voorbeeld,
namelijk in de vorm van een Markovketen. Om hierover dingen te kunnen bewijzen, bespreken
we eerst een stukje theorie over koppeling van stochasten. Vervolgens leiden we een resultaat af
voor stationaire Markovketens, waarna we ook nog kijken naar inhomogene ketens.
Ten slotte kijken we nog kort naar Gaussische concentratie ongelijkheden. Dit zijn zeer
algemeen toepasbare ongelijkheden. Hierbij zullen we ook kijken naar dit soort ongelijkheden
voor afhankelijke rijen stochasten. We zullen laten zien dat in het geval van een Markovketen
met een geschikte koppeling we eenzelfde afschatting krijgen als voor onafhankelijke stochasten.
Het zal blijken dat deze ongelijkheden een alternatieve manier geven om de resulaten over bijna
zekere convergentie te bewijzen.
iv
Voorwoord
Het verslag dat voor u ligt betreft mijn bachelorproject ter afsluiting van de bachelor Technische
Wiskunde aan de TU Delft.
Tijdens mijn studie ben ik met veel verschillende vakgebieden van de wiskunde in aanraking
gekomen, en vooral de analyse, kansrekening en optimalisering hebben mijn aandacht getrokken.
Daarom was de keuze des te moeilijker voor een onderwerp voor mijn bachelorproject. Niet zo
zeer omdat ik geen keus had, maar juist omdat ik misschien te veel keus had.
Desalniettemin ben ik erg tevreden met de keuze van mijn onderwerp. Het laat mij niet
alleen op een exacte manier kanstheoretische begrippen toepassen, maar het is me ook duidelijk
geworden dat kansrekening en analyse goed met elkaar samengaan. Daarnaast heb ik ook nog
combinatorische resultaten kunnen bestuderen. Het heeft voor mij dus eigenlijk van alles wat!
Ik wil mijn begeleider Prof. Dr. F.H.J. Redig bedanken voor de begeleiding van het project,
voor alle hulp bij het uitwerken en verslagleggen van resultaten, en voor alle interessante en
leerzame gesprekken betreffende het onderwerp.
Inhoudsopgave
1 Inleiding
1.1 Random kleuringen en arithmetische progressies . . . . . . . . . . . . . . . . . .
1.2 Belangrijke resultaten op dit gebied . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Stochastische priemgetallen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
2
4
2 Convergentie van rijen stochasten
2.1 Convergentie in kans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Convergentie bijna zeker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
6
3 Onafhankelijke kleuringen
3.1 Zwakke wet van de grote aantallen . . .
3.2 Sterke wet van de grote aantallen . . . .
3.3 Toepassing . . . . . . . . . . . . . . . .
3.4 Voorbeeld in verband met Erd¨os-Turan
.
.
.
.
9
9
11
14
15
.
.
.
.
17
17
21
21
26
5 Concentratie afschattingen
5.1 Onafhankelijke rijen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Afhankelijke rijen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
29
30
4 Afhankelijke kleuringen
4.1 Eenvoudige afhankelijkheden
4.2 Koppeling . . . . . . . . . . .
4.2.1 Markovketens . . . . .
4.3 Inhomogene Markovketens . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
vi
INHOUDSOPGAVE
Hoofdstuk 1
Inleiding
In deze scriptie worden een aantal eigenschappen van zogehete random kleuringen van de natuurlijke getallen bestudeerd. Om deze kleuringen te maken, gebruiken we twee ’kleuren’, namelijk
wit en zwart. Hiermee delen we de natuurlijke getallen in feite op in twee klassen, in ons geval op
willekeurige wijze. Waar we vooral in ge¨ınteresseerd zijn, is de vraag of er in de klasse van zwart
gemaakte getallen oneindig veel arithmetische progressies voorkomen. Natuurlijk hangt dit af
van de verdeling waarmee we getallen zwart, dan wel wit maken, en een eerste resultaat zal ons
een voldoende voorwaarde geven opdat we bijna zeker oneindig veel arithmetische progressies
van iedere lengte zullen krijgen.
We vragen ons dus eigenlijk af hoe groot de verzameling zwarte getallen moet zijn, zodanig
dat we nog willekeurig lange arithmetische progressies kunnen vinden. Deze vraagstelling is
typisch voor Ramseytheorie. Ramseytheorie begint in het algemeen met een verzameling die
een zekere structuur kent. Vervolgens wordt deze verzameling in stukjes gehakt. De vraag is nu
hoe groot de oorspronkelijke verzameling moet zijn, zodanig dat ten minste een van de stukjes
een voorgeschreven interessante eigenschap heeft.
Een bekend voorbeeld uit de Ramseytheorie gaat over een groep personen. De vraag die
we ons hierover stellen, is hoe groot deze groep moet zijn, zodat we altijd een groepje van 3
personen aan kunnen wijzen die of elkaar allemaal onderling kennen, of juist allemaal onderling
vreemden voor elkaar zijn. Het blijkt dat we genoeg hebben aan zes personen om dit te bereiken.
De stelling uit de Ramseytheorie die voor ons van belang zal zijn, is de stelling van Van
der Waerden. Deze zegt dat als we N opdelen in een eindig aantal stukken, dat dan ten minste
een van die stukken willekeurig lange arithmetische progressies bevat. Hierop zullen we nog
terugkomen, alsmede op een resultaat van Szemer´edi betreffende een voldoende voorwaarde voor
het bestaan van willekeurig lange arithmetische progressies. Deze resultaten vormen namelijk
de aanleiding voor ons onderzoek naar arithmetische progressies in random kleuringen van de
natuurlijke getallen.
1.1
Random kleuringen en arithmetische progressies
We zullen nu eerst de belangrijkste begrippen defini¨eren. Aangezien we naar random kleuringen
van de natuurlijke getallen gaan kijken, zullen we eerst precies maken wat we daar mee bedoelen.
Definitie 1.1.1. Een random kleuring van de natuurlijke getallen met k kleuren is (de realisatie
van) een rij stochasten (Xn )n , waarbij Xn voor iedere n ∈ N (met kans 1) waarden aanneemt
in {0, 1, 2, . . . , k − 1}, de zogenaamde kleuren.
In feite deelt een random kleuring met k kleuren de natuurlijke getallen dus op willekeurige
wijze op in k stukken. Waar we nu in ge¨ınteresseerd zijn, is welke stukken willekeurig lange
1
2
HOOFDSTUK 1. INLEIDING
arithmetische progressies bevatten. Dit kunnen we op een eenvoudigere manier bekijken. Als
we bijvoorbeeld naar de verzameling getallen met kleur 1 willen kijken, kunnen we net zo goed
alle andere kleuren 0 maken. We verliezen dan namelijk geen informatie over de verzameling
getallen met kleur 1. Dit is precies de reden waarom wij random kleuringen zullen bekijken, die
slechts uit twee kleuren bestaan, namelijk 0 en 1. Hierbij noemen we een 0 wit en een 1 zwart.
We zullen nu gaan kijken naar zogehete arithmetische progressies in de zwarte getallen.
Definitie 1.1.2. Laat a, b ∈ N. Een arithmetische progressie van lengte k met startgetal a en
stapgrootte b is een eindige rij getallen {a + bi|i = 1, 2, . . . , k}. Een collectie A ⊂ N bevat een
arithmetische progressie van lengte k als er a, b ∈ N bestaan zodanig dat {a+bi|i = 1, 2, . . . , k} ⊂
A.
Wij zullen ons beperken tot arithmetische progressies beginnend in 0, oftewel met a = 0.
Dit maakt de notatie eenvoudiger.
1.2
Belangrijke resultaten op dit gebied
Zoals eerder al vermeld, is over het bestaan van willekeurig lange arithmetische progressies in
(deterministische) deelverzamelingen van de natuurlijke getallen al het nodige bekend. Hier
zullen we de resultaten van Van der Waerden en Szemer´edi toelichten. Het ligt voor de hand om
te beginnen met de stelling van Van der Waerden. Deze is al eerder genoemd, maar we zullen
hem voor de volledigheid nog even herhalen.
Stelling 1.2.1 (Van der Waerden). Stel dat we N kleuren met k verschillende kleuren. Dan
bevat ten minste ´e´en van de zo verkregen k deelverzamelingen willkeurig lange arithmetische
progressies.
Het bewijs van Van der Waerden zelf is combinatorisch. Voor dit bewijs verwijzen we naar
[1]. Interessant is het feit, dat er ook een dynamisch bewijs bestaat, hetgeen een verband legt
met ergodentheorie. Dit bewijs maakt gebruik van de volgende stelling.
Stelling 1.2.2 (Topological Multiple Recurrence, Furstenberg en Weiss). Laat T : X → X een
continu dynamisch systeem zijn op een compacte metrische ruimte X. Dan bestaat er voor alle
k ∈ N en > 0 een x ∈ X en n ∈ N zodanig dat d(T in (x), x) < voor alle i = 1, . . . , k. Er geldt
zelfs dat als Z ⊂ X dicht is in X, we x ∈ Z kunnen nemen.
Het bewijs van deze stelling is te vinden in [1]. We zullen nu, gebruikmakend van stelling
1.2.2, het topologische bewijs van de stelling van Van der Waerden geven.
Bewijs. [Van der Waerden] Laat A = {c1 , c2 , . . . , ck } de verzameling kleuren zijn, en laat verder
(xn )n ∈ AN een kleuring zijn van N. Hierbij staat xi uiteraard voor de kleur van getal i.
Beschouw nu de afbeelding T : AN → AN die alle kleuren eentje naar beneden schuift, oftewel
T (x1 , x2 , x3 , . . .) = (x2 , x3 , x4 , . . .)
Definieer nu de metriek d op AN gegeven door
d(x, y) =
1
met l = inf{n|xn 6= yn }
l
Merk nu op dat voor alle x, y ∈ AN geldt dat d(x, y) < 1 dan en slechts dan als x1 = y1 . Daaruit
volgt dat voor alle x, y ∈ AN en alle m, l ∈ N geldt dat d(T m (x), T l (y)) < 1 dan en slechts dan
als xm+1 = yl+1 .
1.2. BELANGRIJKE RESULTATEN OP DIT GEBIED
3
In het bijzonder geldt er voor een kleuring x ∈ AN , dat een arithmetische progressie m, m +
n, . . . , m + kn monochromatisch (i.e. allemaal dezelfde kleur) is dan en slechts dan als xm =
xm+n = · · · = xm+kn , oftewel, dan en slechts dan als
d(T m−1 (x), T m−1+in (x)) = d(T m−1 (x), T in (T m−1 (x))) < 1, i = 1, 2, . . . , k
Als we nu X = {T m (x)}∞
m=0 nemen, dan is X een compacte metrische ruimte, T een continu
dynamisch systeem op X en Z = {T m (x)}∞
m=0 is dicht in X. Uit stelling 1.2.2 volgt nu, met
= 1, dat er een m ∈ N is, zodanig dat d(T m (x), T in (T m (x))) < 1 voor i = 1, . . . , k. Maar dat
houdt in dat xm+1 = xm+1+n = · · · = xm+1+kn een monochromatische arithmetische progressie
is van lengte k. Aangezien bovenstaande geldt elke k volgt het gewenste resultaat.
Wat de stelling van Van der Waerden eigenlijk zegt, is dat ten minste ´e´en van de k deelverzamelingen ’groot genoeg’ is om willekeurig lange arithmetische progressies te bevatten. Het
nadeel is natuurlijk dat de stelling ons niet vertelt welk van deze deelverzamelingen groot genoeg
zijn. Om met een voldoende voorwaarde voor het bestaan van willekeurig lange arithmetische
progressies te komen, moeten we het begrip ’groot genoeg’ precies maken. Dat noemen we dan
de (boven)dichtheid van een deelverzameling.
Definitie 1.2.1. Laat A ⊂ N. De (boven)dichtheid van A (in N) is gedefinieerd als
d(A) = lim sup
n→∞
|A ∩ [1, n]|
n
De stelling van Szemer´edi geeft ons nu een voldoende voorwaarde voor het bestaan van
willekeurig lange arithmetische progressies.
Stelling 1.2.3 (Szemer´edi). Laat A ⊂ N zodanig dat d(A) > 0. Dan bevat A willekeurig lange
arithmetische progressies.
Er zijn echter nog veel meer klassen van deelverzamelingen van de natuurlijke getallen die willekeurig lange arithmetische progressies bevatten, in het bijzonder verzamelingen met dichtheid
0. De stelling van Green en Tao geeft ons het volgende.
Stelling 1.2.4 (Green-Tao). De verzameling P van priemgetallen bevat willekeurig lange arithmetische progressies.
Echter, we kunnen laten zien dat d(P) = 0. De priemgetalstelling van De La Vall´ee Poussin
geeft ons namelijk dat |P ∩ [1, n]| = logn n (1 + o(1)). Maar dan hebben we dus dat
d(P) = lim sup
n→∞
|P ∩ [1, n]|
1
= lim sup
(1 + o(1)) = 0
n
n→∞ log n
We zien dus dat de dichtheid van de priemgetallen 0 is. Hieruit kunnen we concluderen dat
we een ’nieuwe’ verzameling hebben gevonden die willekeurig lange arithmetische progressies
bevat. Het bewijs van de stelling van Green en Tao laat ons zelfs zien dat we hiermee weer een
geheel nieuwe klasse van dit soort verzamelingen hebben gevonden. De sleutel van het bewijs is
namelijk, dat er een deelverzameling A ⊂ N bestaat die P bevat, met de eigenschap dat als A
positieve dichtheid heeft in A, dat dan A willekeurig lange arithmetische progressies bevat. In
het bijzonder volgt dat ook iedere deelverzameling van N die positieve dichtheid in de priemgetallen heeft willekeurig lange arithmetische progessies bevat.
Bovenstaande illustreert dat er ook verzamelingen bestaan met dichtheid 0, maar die toch
willekeurig lange arithmetische progressies bevatten. De vraag is nu, of er ook een zwakkere
4
HOOFDSTUK 1. INLEIDING
voorwaarde bestaat die ook verzamelingen met dichtheid 0 toelaat. In 1737 heeft Euler laten
zien dat
X1
=∞
p
p∈P
De vraag is nu of dit de reden is dat de priemgetallen willekeurig lange arithmetische progressies
bevatten. Het volgende vermoeden wordt toegeschreven aan Erd¨os en Tur´an.
Vermoeden 1.2.1 (Erd¨
os-Tur´
an). Laat A ⊂ N. Neem aan dat
X1
=∞
n
n∈A
Dan bevat A willekeurig lange arithmetische progressies.
1.3
Stochastische priemgetallen
Nu gaan wij ons niet zozeer concentreren op deterministische deelverzamelingen van de natuurlijke getallen, maar meer op willekeurige. Om aan zo’n willekeurige deelverzameling te komen,
zullen we gebruik maken van een random kleuring van de natuurlijke getallen. Als eerste kijken
we naar een kleuring waarbij elk van de getallen onafhankelijk van elkaar zwart of wit gemaakt
wordt. Deze kleuring kunnen we schrijven als een rij stochasten (Xn )n met P (Xn = 1) = bn
voor iedere n, waarbij (Xn = 1) correspondeert met ’n is zwart’. Omdat het bestaan van willekeurig lange arithmetische progressies niet spannend is als we ’veel’ enen verwachten, zullen we
ook nog aannemen dat bn ↓ 0. In hoofdstuk 3 zullen we hiervoor bewijzen dat er een voldoende
voorwaarde is, zodanig dat er van elke willekeurige lengte oneindig veel arithmetische progressies
van zwarte getallen bestaan. Het zal blijken dat deze theorie bijvoorbeeld van toepassing is op
het stochastisch model voor de priemgetallen, zoals ge¨ıntroduceerd door Cram`er.
Om dit model goed te kunnen defini¨eren, moeten we een soort kans afleiden dat een natuurlijk
1
getal een priemgetal is. Hierboven hebben we al gezien dat |P∩[1,n]|
|[1,n]| ∼ log n . We zouden dit als
kans kunnen nemen dat een getal een priemgetal is.
Natuurlijk moeten we hier voorzichtig zijn met het gebruik van het woord kans. De verzameling priemgetallen is immers deterministisch, het toeval speelt geen rol. Desalniettemin kunnen
we met bovenstaande wel een stochastische benadering maken voor de priemgetallen. We maken
een random kleuring van de natuurlijke getallen met twee kleuren, waarbij voor iedere n > 2
geldt dat P (Xn = 1) = log1 n . Verder defini¨eren we P (X1 = 1) = 0 en P (X2 = 1) = 1. Op deze
manier zouden de zwart gekleurde getallen uit een realisatie een representatie van de priemgetallen moeten worden. Merk op dat inderdaad geldt dat log1 n → 0 als n → ∞. We zien dus
dat dit een experiment is waar resultaten van ons onderzoek hun toepassing in kunnen vinden.
We zullen in hoofdstuk 3 laten zien dat we voor dit stochastische model een kanstheoretisch
analogon krijgen voor de stelling van Green en Tao.
Hoofdstuk 2
Convergentie van rijen stochasten
In het vervolg willen ons richten op het laten zien dat er willekeurig lange arithmetische progressies bestaan in de verzameling zwart gemaakte getallen. Hiervoor is het uiteraard niet genoeg
om naar een eindige deelverzameling van N te kijken. Het zal er dus op neerkomen, dat we
naar zekere limieten van rijen stochasten moeten gaan kijken. In dit hoofdstuk zullen we twee
soorten van convergentie van een rij stochasten bespreken die wij nodig hebben. In het vervolg
nemen we aan dat we een vaste kansruimte (Ω, F, P ) hebben, tenzij anders vermeld. Stochasten
zijn dan meetbare functies van Ω naar R.
2.1
Convergentie in kans
Een manier om naar de convergentie van een rij stochasten (Xn )n te kijken, is door te beschouwen
wat de kans is op een gegeven afwijking van een zekere stochast X. Als dan de kans op een
afwijking naar 0 gaat naarmate n naar oneindig gaat, dan kunnen we X de limiet van (Xn )n
noemen. Dit is wat convergentie in kans inhoudt. We geven de precieze definitie.
Definitie 2.1.1 (Convergentie in kans). Laat (Xn )n een rij stochasten zijn, en laat verder X
p
ook een stochast zijn. We zeggen dat Xn in kans naar X convergeert, genoteerd als Xn → X,
als voor iedere > 0 geldt dat P (|Xn − X| ≥ ) → 0 als n → ∞.
We zullen dit begrip illustreren met behulp van een voorbeeld.
Voorbeeld 2.1.1. Definieer een rij onafhankelijke stochasten (Xn )n door P (Xn = 1) = n1 en
P (Xn = 0) = 1 − n1 . We zullen bewijzen dat (Xn )n in kans naar 0 convergeert. Neem daartoe
> 0 willekeurig. Dan geldt er dat P (|Xn | ≥ ) ≤ n1 → 0 als n → ∞. Hieruit kunnen we
p
concluderen dat lim P (|Xn | ≥ ) = 0, waaruit volgt dat Xn → 0.
n→∞
Wij hebben nog het volgende resultaat nodig betreffende convergentie in kans.
Lemma 2.1.1. Laat (Xn )n een rij stochasten
zijn met limn→∞ E(Xn ) = ∞. Neem verder aan
V (Xn ) 1
Xn in
dat er een c < ∞ bestaat zodanig dat E(Xn ) ≤ c voor iedere n. Dan geldt er dat E(X
n)
kans convergeert naar 1 = E(Xn /E(Xn )).
Bewijs. Uit de ongelijkheid van Chebyshev vinden we dat
V (Xn ) 1
V
c
X
1
E(Xn ) n
E(Xn ) 2
P Xn − 1 ≥ ≤
=
≤
→0
E(Xn )
2
|E(Xn )|2
|E(Xn )|
1
1
We vinden dus dat limn→∞ P E(Xn ) Xn − 1 ≥ = 0, oftewel, dat E(X
Xn in kans naar 1
n)
convergeert.
5
6
HOOFDSTUK 2. CONVERGENTIE VAN RIJEN STOCHASTEN
2.2
Convergentie bijna zeker
Aangezien een stochast eigenlijk niets anders is dan een functie, kunnen we ook naar de puntsgewijze limiet van (Xn )n kijken. Het is echter niet nodig dat deze puntsgewijze limiet voor elk
element uit Ω bestaat. Het is voldoende dat de puntsgewijze limiet bijna zeker (a.s.) bestaat,
dat wil zeggen, dat de kans 1 is dat limiet bestaat. We krijgen de volgende definitie.
Definitie 2.2.1 (Convergentie bijna zeker). We zeggen dat een rij stochasten (Xn )n bijna zeker
naar een stochast X convergeert, als geldt dat
P ({ω ∈ Ω| lim Xn (ω) = X(ω)}) = 1
n→∞
Bovenstaande definitie is echter vaak lastig om mee te werken. Gelukkig zijn er voldoende
voorwaarden die gemakkelijker te controleren zijn. We zullen hier een voldoende voorwaarde
afleiden die voor ons bruikbaar is. Hiervoor hebben we de begrippen ’infinitely often’ (i.o.) en
’almost always’ (a.a.) nodig. Als (An )n een rij gebeurtenissen is, dan is {An i.o.} de gebeurtenis
dat oneindig veel van de gebeurtenissen An optreden. De gebeurtenis {An a.a} is dan de
gebeurtenis dat alle gebeurtenissen optreden, op een eindig aantal na. Met deze termen op zak
hebben we het volgende lemma.
Lemma 2.2.1. Laat (Xn )n een rij stochasten zijn. Zij X ook een stochast. Neem aan dat voor
iedere > 0 geldt dat P (|Xn − X| ≥ i.o.) = 0. Dan geldt er dat Xn → X bijna zeker.
Bewijs. Merk op dat
P (Xn → X) = P [(∀ > 0)(|Xn − X| < a.a.)] = 1 − P [(∃ > 0)(|Xn − X| ≥ i.o)]
Merk op dat de kansmaat subadditief is. Daaruit volgt dat
X
P (∃ ∈ Q>0 , |Xn − X| ≥ i.o) ≤
P (|Xn − X| ≥ i.o.) = 0
∈Q>0
Merk nu op dat voor iedere > 0 er een 0 ∈ Q>0 bestaat zodanig dat 0 < . Maar dan geldt
er dat P (|Xn − X| ≥ ) ≤ P (|Xn − X| ≥ 0 ). Hieruit volgt dat
P ((∃ > 0)(|Xn − X| ≥ i.o)) ≤ P ((∃0 ∈ Q>0 )(|Xn − X| ≥ 0 i.o)) = 0
Hieruit volgt nu dat P (Xn → X) = 1, oftewel, dat Xn → X bijna zeker.
Hieruit kunnen we nu het volgende afleiden.
Gevolg 2.2.1. Laat (Xn )n eenPrij stochasten zijn. Laat verder X ook een stochast. Neem aan
dat voor iedere > 0 geldt dat ∞
n=1 P (|Xn − X| ≥ ) < ∞. Dan geldt er dat Xn → X a.s.
Bewijs. Zij > 0 willekeurig. Merk op dat voor iedere m ∈ N geldt dat


[
X
P (|Xn − X| ≥ i.o.) ≤ P 
|Xk − X| ≥  ≤
P (|Xk − X| ≥ )
k≥m
k≥m
P
P
Omdat ∞
n=1 P (|Xn − X| ≥ ) < ∞, geldt er dat limm→∞
k≥m P (|Xk − X| ≥ ) = 0. Omdat
bovenstaande voor iedere m geldt, kunnen we concluderen dat P (|Xn − X| ≥ i.o.) = 0. Uit
lemma 2.2.1 volgt nu dat Xn → X bijna zeker.
2.2. CONVERGENTIE BIJNA ZEKER
7
Dit gevolg geeft de voldoende voorwaarde voor bijna zekere convergentie waar wij gebruik
van zullen maken.
Als laatste zullen we de relatie tussen deze twee typen convergentie bespreken. We zullen
laten zien dat bijna zekere convergentie sterker is dan convergentie in kans. Daartoe bewijzen
we eerst dat convergentie in kans volgt uit bijna zekere convergentie.
Propositie 2.2.1. Als (Xn )n een rij stochasten is die bijna zeker naar een stochast X converp
geert, dan Xn → X.
Bewijs. Zij > 0 willekeurig. Definieer voor iedere n ∈ N de verzameling
An = {ω|∃m ≥ n zodanig dat |Xm (ω) − X(ω)| ≥ }
T
T
Dan hebben we dat An ↓ n An . Verder geldt er voor ω ∈ n A
Tn dat Xn (ω) 6→ X(ω) als
n → ∞. Maar dan volgt uit de monotonie van de kansmaat dat
P
(
n An ) ≤ P (Xn 6→ X) = 0.
T
De continu¨ıteit van de kansmaat geeft ons nu dat P (An ) → P ( n An ) = 0. Merk nu nog op dat
P (|Xn − X| ≥ ) ≤ P (An ) → 0, waaruit volgt dat lim P (|Xn − X| ≥ ) = 0. Hieruit volgt dat
n→∞
Xn in kans naar X convergeert.
We zullen nu nog illustreren dat het omgekeerde hiervan niet altijd waar is. Hiervoor bekijken
we weer de rij stochasten uit voorbeeld 2.1.1.
Voorbeeld 2.2.1. We zullen laten zien datP
de rij stochasten uit voorbeeld
P∞ 1 2.1.1 niet bijna zeker
∞
P
(X
=
1)
=
naar 0 convergeert. Merk daartoe op dat
n
n=1 n = ∞. Aangezien de
n=1
stochasten onhankelijk zijn, volgt nu uit het Borel-Cantelli Lemma dat P (Xn = 1 i.o.) = 1.
Maar dan kan Xn natuurlijk niet met kans 1 naar 0 convergeren. Hieruit volgt dat deze rij niet
bijna zeker convergeert.
Voor de volledigheid zullen we nog een voorbeeld geven van een rij stochasten die wel bijna
zeker convergeert. Ook hier kunnen we weer onze inspiratie uit voorbeeld 2.1.1 halen.
Voorbeeld 2.2.2. Bekijk weer de rij stochasten (Xn )n uit voorbeeld 2.1.1. We zullen laten zien
dat
P∞de rij (Xn /n)n bijna zeker naar 0 convergeert. Neem daartoe > 0 willekeurig. Bekijk
n=1 P (|Xn /n| ≥ ). Merk op dat deze som maar eindig veel termen ongelijk 0 bevat. Er geldt
namelijk dat PP
(|Xn /n| ≥ ) > 0 precies als n1 ≥ , oftewel, precies als n ≤ 1 . Maar dan zien we
dus dat zeker ∞
n=1 P (|Xn /n| ≥ ) < ∞. Uit gevolg 2.2.1 volgt nu dat Xn /n → 0 bijna zeker.
Toch kunnen we nog wel iets zeggen over bijna zekere convergentie als we convergentie in
kans hebben. We hebben het volgende.
Propositie 2.2.2. Laat (Xn )n een rij stochasten zijn. Laat verder X ook een stochast. Neem
aan dat Xn in kans naar X convergeert. Dan is er een deelrij (Xnk )k van (Xn )n zodanig dat
Xnk bijna zeker naar X convergeert.
Bewijs. We zullen recursief een deelrij (nk )k construeren, zodanig dat Xnk → X bijna zeker.
Definieer n1 = 1. Neem vervolgens aan dat n1 , . . . , nk al zijn geconstrueerd. Definieer
1
−k
nk+1 = inf n > nk |P |Xn − X| ≥
≤2
k
Aangezien Xn → X in kans, geldt er dat nk+1 < ∞. We zullen nu bewijzen dat de deelrij die
we op deze manier verkrijgen inderdaad voldoet.
8
HOOFDSTUK 2. CONVERGENTIE VAN RIJEN STOCHASTEN
Neem daartoe > 0 willekeurig. Merk op dat er een Nk ∈ N bestaat zodanig dat
alle k > Nk . Merk nu op dat
∞
X
P (|Xnk − X| ≥ ) =
k=1
≤
≤
Nk
X
P (|Xnk − X| ≥ ) +
∞
X
k=1
k=Nk +1
Nk
X
∞
X
P (|Xnk − X| ≥ ) +
k=1
k=Nk +1
Nk
X
∞
X
k=1
P (|Xnk − X| ≥ ) +
1
k
< voor
P (|Xnk − X| ≥ )
1
P |Xnk − X| ≥
k
2−k
k=Nk +1
< ∞
Uit gevolg 2.2.1 volgt nu dat Xnk bijna zeker naar X convergeert.
Propostie 2.2.2 kunnen we nu gebruiken om te laten zien dat convergentie bijna zeker niet
van een metriek kan komen. Als convergentie van een metriek komt, dan hebben we namelijk
het volgende voor een rij (xn )n : Als voor iedere deelrij (nj )j geldt dat daar een deelrij (n0j )j van
bestaat zodanig dat xn0j → x dan geldt er dat xn → x.
Stel nu eens dat bijna zekere convergentie van een metriek komt. Bekijk de rij stochasten
uit voorbeeld 2.1.1. We hebben gezien dat deze rij in kans convergeert naar 0. Neem nu een
willekeurige deelrij (nj )j . Dan geldt er dat Xnj → 0 in kans. Uit propositie 2.2.2 volgt dan
dat er een deelrij (n0j )j van (nj )j bestaat zodanig dat Xn0j bijna zeker naar 0 convergeert. Als
nu bijna zekere convergentie van een metriek komt, dan volgt uit bovenstaande dat Xn bijna
zeker naar 0 convergeert. Echter, in voorbeeld 2.2.1 hebben we gezien dat dit niet zo is. Hieruit
kunnen we concluderen dat bijna zekere convergentie niet van een metriek kan komen.
Hoofdstuk 3
Onafhankelijke kleuringen
In dit hoofdstuk zullen we kijken naar arithmetische progressies van de zwarte getallen in een
onafhankelijke random kleuring van de natuurlijke getallen. Voordat we onze eerste resultaten
kunnen noemen, moeten we eerst de situatie schetsen, en een manier vinden om arithmetische
progressies in een random kleuring op te sporen.
3.1
Zwakke wet van de grote aantallen
Zoals eerder al vermeld, gaan we kijken naar een rij onafhankelijke stochasten (Xn )n met P (Xn =
1) = bn en P (Xn = 0) = 1 − bn voor alle n. We eisen verder dat bn ↓ 0. Wat we eigenlijk willen
weten, is hoeveel arithmetische progressies van zwarte getallen van een gegeven lengte k er
zullen zijn in een kleuring. Merk nu op dat de getallen i, 2i, . . . , ki allemaal zwart zijn, precies
als Xi = X2i = · · · = Xki = 1. Maar dat is precies hetzelfde als zeggen dat Xi X2i · · · Xki = 1.
In het geval dat ten minste ´e´en van deze getallen wit is,Pzal er een 0 verschijnen in het product,
eren, dan is Sk
waaruit volgt dat Xi X2i · · · Xki = 0. Als we dus Sk = ∞
i=1 Xi X2i · · · Xki defini¨
een stochast die staat voor het
aantal
arithmetische
progressies
van
lengte
k
met
a = 0.
Pn
Nu defini¨eren we Sn,k = i=1 Xi X2i · · · Xki en Bk (n) = E(Sn,k ). Om nu tot resultaten te
komen, moeten we een eerste aanname doen.
Aanname 3.1.1 (Zwakke aanname). Voor iedere k ∈ N geldt er dat
∞
X
bi b2i · · · bki = ∞
i=1
We noemen dit de zwakke aanname, omdat zal blijken dat dit veelal voldoende is voor
resultaten met betrekking tot convergentie in kans. We krijgen de volgende stelling.
Stelling 3.1.1. Onder aanname 3.1.1 geldt er voor iedere k ∈ N dat
1
p
Sn,k → 1
Bk (n)
Bewijs. Laat k ∈ N willekeurig. We zullen gebruik maken van lemma 2.1.1. Daartoe
moeten
we
V (Sn,k ) dus laten zien dat limn→∞ Bk (n) = ∞ en dat er een c < ∞ bestaat zodanig dat Bk (n) < c
voor alle n.
Merk daartoe allereerst op dat
Bk (n) = E(Sn,k ) =
n
X
i=1
E(Xi X2i · · · Xki ) =
n
X
i=1
9
E(Xi )E(X2i ) · · · E(Xki ) =
n
X
i=1
bi b2i · · · bki
10
HOOFDSTUK 3. ONAFHANKELIJKE KLEURINGEN
Uit de aanname volgt nu dat
lim E(Sn,k ) =
∞
X
n→∞
bi b2i · · · bki = ∞
i=1
Nu rest ons alleen nog de variantie af te schatten. Neem daartoe n ∈ N willekeurig. We
weten dat
!
n
X
V (Sn,k ) = V
Xi X2i · · · Xki
i=1
=
n
X
V (Xi X2i · · · Xki ) + 2
i=1
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj )
i<j
Merk op dat voor iedere i geldt dat V (Xi X2i · · · Xki ) = bi b2i · · · bki − (bi b2i · · · bki )2 . Nu
moeten we alleen nog naar de covarianties kijken. Er geldt dat
Cov(Xi · · · Xki , Xj · · · Xkj ) = E(Xi · · · Xki Xj · · · Xkj ) − E(Xi · · · Xki )E(Xj · · · Xkj )
≤ E(Xi · · · Xki Xj · · · Xkj )
Omdat Xj ∈ {0, 1} voor iedere j vinden we dat
E(Xi · · · Xki Xj · · · Xkj ) ≤ E(Xi · · · Xki )
Als we nu nog de onafhankelijkheid gebruiken, dan vinden we dat
Cov(Xi · · · Xki , Xj · · · Xkj ) ≤ E(Xi ) · · · E(Xki ) = bi b2i · · · bki
P
Nu zijn we in staat om i<j Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) op een geschikte manier af
te schatten. Merk op dat we kunnen schrijven dat
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) =
i<j
n X
n
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj )
i=1 j=i+1
Pn
Als we nu i even vast nemen, dan kan
j=i+1 Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) maximaal
1
2 k(k−1) termen ongelijk 0 hebben. In het ergste geval hebben we namelijk dat j = 2i, 3i, . . . , ki,
2j = 3i, 4i, . . . , ki, etc. allemaal voorkomen als overlap tussen de progressies. Merk nu verder
op dat we hierboven al hebben bewezen dat we elke niet-nul term af kunnen schatten met
bi b2i · · · bki . Maar dan kunnen we nu de volgende afschatting maken
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) ≤
i<j
n
X
1
i=1
=
2
k(k − 1)bi b2i · · · bki
1
k(k − 1)Bk (n)
2
3.2. STERKE WET VAN DE GROTE AANTALLEN
11
Al het bovenstaande stelt ons nu in staat om de variantie af te schatten. We vinden namelijk
dat
V (Sn,k ) =
=
n
X
i=1
n
X
i=1
V (Xi X2i · · · Xki ) + 2
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj )
i<j
bi b2i · · · bki −
n
X
X
(bi b2i · · · bki )2 + 2
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj )
i=1
i<j
≤ Bk (n) + k(k − 1)Bk (n)
= (k(k − 1) + 1)Bk (n)
V (Sn,k ) Maar dan zien we dus dat Bk (n)
≤
We hebben dus dat limn→∞ Bk (n) =
ons nu dat
1
Bk (n) Sn,k
(k(k−1)+1)Bk (n)
= k(k − 1) + 1 < ∞.
Bk (n)
V (Sn,k ) ∞ en Bk (n)
< k(k − 1) + 1 < ∞. Lemma
2.1.1 geeft
in kans naar 1 convergeert.
In de volgende paragraaf zullen we een sterke versie van bovenstaand resultaat afleiden.
3.2
Sterke wet van de grote aantallen
Om een sterke versie van de stelling uit de vorige paragraaf te kunnen bewijzen, hebben we iets
meer informatie nodig over hoe Bk (n) naar oneindig gaat. We hebben namelijk nodig dat voor
een zekere C > 0 geldt dat Bk (n) > Cn1−δ voor alle δ ∈ (0, 1). Het is echter waarschijnlijk niet
zo dat dit in al zijn algemeenheid, i.e. onder aanname 3.1.1 op pagina 9, zal gelden. Daarom
moeten we een extra eis formuleren, zodanig dat we bovenstaande onderschatting krijgen. Het
blijkt genoeg om te eisen dat limn→∞ nδ bn bestaat voor iedere δ ∈ (0, 1). We krijgen dus de
volgende sterke aanname.
Aanname 3.2.1 (Sterke aanname). Voor iedere k ∈ N geldt er dat
∞
X
bi b2i · · · bki = ∞
i=1
`en er geldt dat limn→∞ nδ bn bestaat voor iedere δ ∈ (0, 1).
Opmerking. De vraag is of de extra eis die we opleggen echt nodig
Om te beginnen
Pis.
∞
kunnen we hiervoor
kijken naar de vraag of de eis dat voor iedere k
i=1 bi b2i · · · bki = ∞
P
impliceert dat ni=1 bi ≥ Cn1−δ voor iedere δ ∈ (0, 1). Op deze vraag hebben we echter (nog)
geen sluitend antwoord.
dat aangeeft dat de zwakkere eis dat voor
P∞ Welk hebben we een voorbeeld P
iedere k geldt dat i=1 (bi ) = ∞ niet impliceert dat ni=1 bi ≥ Cn1−δ . Hiervoor defini¨eren we
b2i = log1 i voor alle i > 2 en verder bk = 0. Merk nu op dat
∞
X
i=1
bki =
∞
X
i=3
1
(log i)k
Uit de ongelijkheden uit paragraaf 3.3 en het Majorantenkenmerk vinden we dat
P
k
∞. Maar dan volgt uit bovenstaande dat ook ∞
i=1 bi = ∞.
P∞
1
i=3 (log i)k
=
12
HOOFDSTUK 3. ONAFHANKELIJKE KLEURINGEN
Echter geldt er voor iedere n dat
n
X
blog2 nc
bi =
i=1
X
i=3
log2 n
log n
1
≤
=
log i
log(3)
(log 2)(log 3)
P
hooguit logaritmisch groeit in n. Hieruit volgt dat er geen C > 0
We zien dus dat ni=1 bi P
∈ (0, 1). Echter, bovenstaand voorbeeld
kan bestaan zodanig dat ni=1 bi ≥ Cn1−δ voor alle δ P
k
illustreert ook dat P
de eis dat voor iedere k geldt dat ∞
i=1 (bi ) = ∞ zwakker is dan dat voor
∞
iedere k geldt dat i=1 bi b2i · · · bki = ∞. Desalniettemin geeft dit voorbeeld wel aanleiding om
te vermoeden dat we de extra eis die we opleggen nodig hebben, al is het mogelijk dat deze nog
afgezwakt kan worden.
Nu zullen we laten zien dat we met de extra eis dat limn→∞ nδ bn bestaat, we in ieder geval
wel het gewenste resultaat krijgen. Merk allereerst op dat moet gelden dat limn→∞ nδ bn = ∞.
Stel maar eens dat dit niet zo is. Dan is er een constante c ≥ 0, zodanig dat limn→∞ nδ bn = c.
Daaruit volgt dat er een N ∈ N bestaat zodanig dat voor iedere P
n ≥ N geldt dat nδ bn < c + 1,
c+1
oftewel, bn < nδ . Neem nu k ∈ N zodanig dat kδ > 1 en bekijk ∞
n=1 bn b2n · · · bkn . We krijgen
dat
∞
∞
∞
X
X
1 1
1
(c + 1)k X 1
k
bn b2n · · · bkn < (c + 1)
···
=
<∞
nδ (2n)δ
(kn)δ
(k!)δ
nkδ
n=1
n=1
n=1
waarbij het laatste geldt omdat P
k zo gekozen is dat kδ > 1. Echter hebben we aangenomen dat
voor iedere k moet gelden dat ∞
n=1 bn b2n · · · bkn = ∞. We hebben dus een tegenspraak. Er
volgt dat limn→∞ nδ bn = ∞.
Neem nu δ ∈ (0, 1) en k > 1 willekeurig. We zullen laten zien dat voor n groot genoeg
geldt dat Bk (n) > Cn1−δ met C > 0 een constante. Merk op dat uit bovenstaande volgt dat
limn→∞ nδ/k bn = ∞. Maar dan bestaat er dus een n0 ∈ N zodanig dat voor alle n > n0 geldt
dat nδ/k bn > 1, oftewel, bn > n−δ/k . Voor n > n0 vinden we dan dat
Bk (n) =
n
X
bi b2i · · · bki
i=1
=
n0
X
n
X
bi b2i · · · bki +
i=1
bi b2i · · · bki
i=n0 +1
≥ K+
≥ K+
1
(k!)δ
1
(k!)δ
n
X
i−δ
i=n0 +1
Z n
−δ
x
dx
n0
≥ Cn1−δ
Hierbij is C > 0 een constante. Hieruit kunnen we concluderen dat voor n groot genoeg geldt
dat Bk (n) > Cn1−δ . Dit zullen we nu gebruiken om de volgende stelling te bewijzen.
Stelling 3.2.1. Onder de sterke aanname 3.2.1 op bladzijde 11 geldt er voor iedere k ∈ N dat
lim
n→∞
1
Sn,k = 1 a.s.
Bk (n)
3.2. STERKE WET VAN DE GROTE AANTALLEN
13
Bewijs. Om dit te kunnen bewijzen, zullen we het vierde moment van Sn,k − Bk (n) afschatten.
We willen dus een afschatting maken van E[(Sn,k − E(Sn,k ))4 ]. Merk op dat we dit kunnen
schrijven als

!!4 
n
n
X
X

E[(Sn,k − E(Sn,k ))4 ] = E 
Xi X2i · · · Xki − E
Xi X2i · · · Xki
i=1

= E
n
X
i=1
!4 
(Xi X2i · · · Xki − E(Xi X2i · · · Xki ))

i=1
Als we nu Yik = Xi X2i · · · Xki defini¨eren, dan kunnen het laatste nog uitschrijven als
n X
n X
n X
n
X
E[(Yik1 − E(Yik1 ))(Yik2 − E(Yik2 ))(Yik3 − E(Yik3 ))(Yik4 − E(Yik4 ))]
i1 =1 i2 =1 i3 =1 i4 =1
Merk nu op dat van deze viervoudige sommatie heel wat termen 0 zijn. Immers, als progressies elkaar niet overlappen, dan zijn de bijbehorende stochasten onafhankelijk, en kunnen we de
verwachting van het product schrijven als product van de verwachtingen. Zodra een van de vier
progressies onafhankelijk is van de andere drie, dan wordt die term 0.We krijgen dus hooguit
bijdragen als we de vier factoren op kunnen splitsen in twee paren waarvan de progressies elkaar
overlappen. We zullen nu beredeneren dat de viervoudige sommatie van de orde n2 zal zijn.
Merk allereerst op dat we de vier indices in 6 verschillen paren op kunnen delen. We bekijken
nu het aantal mogelijke overlappen voor een zekere verdeling. We beweren dat we dit aantal
af kunnen schatten in k. Merk op dat we het aantal manieren waarop Yik1 en Yik2 overlappen af
kunnen schatten met k 2 . Immers, voor elke a ∈ {1, 2, . . . , k} zijn er k mogelijke waarden voor b
zodanig dat ai1 = bi2 . Op deze manier tellen we eventueel dubbel, maar we kunnen dus zeker
nooit meer dan k 2 afhankelijkheden krijgen. Hetzelfde geldt natuurlijk voor Yik3 en Yik4 . Hieruit
kunnen we concluderen dat we maximaal k 4 afhankelijkheden hebben. Aangezien er 6 mogelijke
verdelingen zijn van indices in paren, kunnen we concluderen dat er maximaal 6k 4 overlappingen
zijn. Aangezien elke overlapping op n2 manieren voor kan komen (elke index kan immers n
waarden aannemen), zien we dus dat bovenstaande sommatie maximaal 6k 4 n2 termen ongelijk
0 kan hebben. Laat C = sup E[(Yik1 − E(Yik1 ))(Yik2 − E(Yik2 ))(Yik3 − E(Yik3 ))(Yik4 − E(Yik4 )) < ∞.
i1 ,i2 ,i3 ,i4
Dan kunnen we de verwachting dus afschatten met
E[(Sn,k − E(Sn,k ))4 ] ≤ 6Ck 4 n2 = O(n2 )
Nu zijn we in staat om te bewijzen dat de convergentie bijna zeker is. Merk op dat uit
gevolg
P∞ 2.2.11 volgt dat het voldoende is om te laten zien dat voor iedere > 0 geldt dat
n=1 P (| Bk (n) Sn,k − 1| ≥ ) < ∞. Neem dus > 0 willekeurig. Als we nu de ongelijkheid
van Markov gebruiken, dan vinden we dat
1
= P (|Sn,k − Bk (n)| ≥ |Bk (n)|)
P Sn,k − 1 ≥ Bk (n)
= P ((Sn,k − Bk (n))4 ≥ Bk (n)4 4 )
≤
≤
E((Sn,k − Bk (n))4 )
4 Bk (n)4
Kn2
Bk (n)4
14
HOOFDSTUK 3. ONAFHANKELIJKE KLEURINGEN
Hierbij is K > 0 een zekere constante. Nu rest ons alleen nog aan te tonen dat dit laatste sommeerbaar is. Hiervoor kunnen we gebruik maken van de overschatting die we hebben
afgeleid aan het begin van de paragraaf. Neem δ = 15 . Dan bestaat er een C > 0 en een
N ∈ N zodanig dat voor alle n > N geldt dat Bk (n) > Cn4/5 en dus dat Bk (n)4 > C 4 n16/5 .
2
K/C 4
6
Maar dan geldt er dus dat BKn
4 < n6/5 voor n > N . Aangezien 5 > 1 is deze bovengrens
k (n)
P∞
2
sommeerbaar, en uit het majorantekenmerk volgt nu dat n=1 B n(n)4 < ∞. Maar dan geldt er
k
P
1
dus dat ∞
n=1 P (| Bk (n) Sn,k − 1| ≥ ) < ∞. Aangezien > 0 willekeurig was, kunnen we hieruit
concluderen dat Bk1(n) Sn,k bijna zeker naar 1 convergeert.
3.3
Toepassing
We zullen nu bovenstaande toepassen op het stochastisch model van de priemgetallen, zoals
ge¨ıntroduceerd in paragraaf 1.3. We hebben dus een rij onafhankelijke stochasten (Xn )n met
P (Xn = 1) = log1 n voor n > 2 en verder P (X1 = 1) = 0 en P (X2 = 1) = 1. We zullen hiervoor
P
1
1
1
eerst laten zien dat voor iedere k ∈ N geldt dat ∞
n=3 log n log(2n) · · · log(kn) = ∞. Neem daartoe
k willekeurig. Merk op dat
1
1
1
1
···
≥
log n log(2n)
log(kn)
(log(kn))k
We zullen nu nog laten zien dat log(kn) ≤ k(kn)1/k . Merk hiervoor op dat
ek(kn)
1/k
=
∞
X
(k(kn)1/k )j
j!
j=1
≥
k k (kn)
≥ kn
k!
1
Maar dan geldt er dus dat log(kn) ≤ k(kn)1/k . Maar dan vinden we dus dat (log(kn))
k ≥
We vinden dus dat
1
1
1
1
···
≥ k+1
log n log(2n)
log(kn)
k n
P∞
1
en aangezien n=2 kk+1 n = ∞, kunnen we uit het Majorantenkenmerk concluderen dat
∞
X
n=3
1
.
kk+1 n
1
1
1
···
=∞
log n log(2n)
log(kn)
Nu moeten we alleen nog laten zien dat voor iedere δ ∈ (0, 1) geldt dat limn→∞ nδ log1 n =
∞. Hiervoor kunnen we bovenstaande afschatting weer gebruiken. Neem immers maar k >
1
1/k . Maar dan geldt er dus dat nδ 1
δ . Dan geldt er dat log(n) ≤ log(kn) ≤ k(kn)
log n ≥
1
1
1
1
δ
δ−1/k
n k(kn)1/k = k1+1/k n
. Aangezien k > δ , geldt er dat δ − k > 0. Maar dan hebben we dus
1
dat limn→∞ k1+1/k
nδ−1/k = ∞. Uit alles kunnen we nu concluderen dat limn→∞ nδ log1 n = ∞.
We zien dus dat deze random kleuring voldoet aan alle voorwaarden van stelling 3.2.1. Maar
dan weten we dus dat voor iedere k geldt dat
n
1 X
lim
Xi X2i · · · Xki = 1 a.s.
n→∞ Bk (n)
i=1
Aangezien limn→∞ Bk (n) = ∞, houdt dit resultaat in, dat we met kans 1 van elke willekeurige
lengte oneindig veel arithmetische progressies van zwarte getallen krijgen. Deze zwarte getallen stellen een realisatie van stochastische priemgetallen voor. Met het resultaat dat we hier
hebben gevonden, hebben we dus met kans 1 willekeurig lange arithmetische progressies in de
stochastische priemgetallen. Hiermee hebben we dus het stochastische analogon van de stelling
van Green en Tao verkregen.
¨
3.4. VOORBEELD IN VERBAND MET ERDOS-TURAN
3.4
15
Voorbeeld in verband met Erdo
¨s-Turan
We zullen nu een voorbeeld bekijken in het licht van het vermoeden
os en Turan op
P van Erd¨
1
bladzijde 4. We zullen laten zien dat het niet noodzakelijk is dat n∈{n|Xn =1} n = ∞ a.s. voor
het feit dat de verzameling zwarte getallen willekeurig lange arithmetische progressies bevat.
Om dit te laten zien bekijken we de random kleuring (Xn )n met P (Xn = 1) = (log1n)2 voor alle
n > 2 en P (X1 = 1) = P (X2 = 1) = 0.
Merk op dat in dit geval geldt dat


!
∞
∞
X
X
X
1
1
1


E
Xn =
=E
n
n
n(log n)2
n=3
n=1
n∈{n|Xn =1}
Merk nu op dat
∞
X
n=3
1
n(log n)2
Z
∞
1
dx
x(log x)2
≤
2
Z
∞
=
log 2
1
dt
t2
< ∞
We zien dus dat de verwachting van
P
dat n∈{n|Xn =1} n1 < ∞ met kans 1.
1
n∈{n|Xn =1} n
P
eindig is. Daaruit kunnen we concluderen
Desalniettemin bevat {n|Xn = 1} met kans 1 willekeurig lange arithmetische progressies.
Op een gelijke manier als in paragraaf 3.3, kunnen we laten zien dat voor iedere k geldt dat
∞
X
n=2
1
1
1
···
=∞
2
2
(log n) (log 2n)
(log kn)2
Ook kunnen we weer laten zien dat limn→∞ nδ (log1n)2 = ∞ voor alle δ ∈ (0, 1). Uit stelling
3.2.1 volgt dan dat de verzameling zwarte getallen met kans 1 willekeurig lange arithmetische
progressies bevat.
Opmerking. Onder aanname 3.2.1 op bladzijde 11 kunnen we ook voor eindige n een
afschatting geven van P (Sn,k > 0), i.e de kans op ten minste ´e´en arithmetische progressie van
lengte k in [1, . . . , kn]. Met behulp van de Cauchy-Schwarz ongelijkheid vinden we namelijk dat
E[Sn,k ] = E[Sn,k I(Sn,k > 0)] ≤ E[(Sn,k )2 ]1/2 (P (Sn,k > 0))1/2
Hieruit volgt dat
(E[Sn,k ])2
E[(Sn,k )2 ]
Dit is een zogehete second moment bound. Deze ondergrens kunnen we nog verder omschrijven
P (Sn,k > 0) ≥
(E[Sn,k ])2
E[(Sn,k )2 ]
=
=
=
(E[Sn,k ])2
(E[Sn,k ])2 + V (Sn,k )
(Bk (n))2
(Bk (n))2 + V (Sn,k )
1
1+
V (Sn,k )
(Bk (n))2
16
HOOFDSTUK 3. ONAFHANKELIJKE KLEURINGEN
In het bewijs van stelling
3.1.1 hebben we echter al gezien dat er een constante K > 0
V (Sn,k ) bestaat, zodanig dat Bk (n) < K. Verder weten we ook dat er een C > 0 bestaat zodanig dat
Bk (n) ≥ Cn1−δ voor iedere δ ∈ (0, 1). Maar dan vinden we dus dat
(E[Sn,k ])2
E[(Sn,k )2 ]
≥
≥
1
1+
K
Bk (n)
1
1+
K
Cn1−δ
Hiermee hebben we dus een ondergrens gevonden voor de kans dat er ten minste ´e´en arithmetische progressie van lengte k te vinden is in het interval [1, kn].
Merk verder nog op dat deze ondergrens naar 1 gaat als n → ∞, oftewel, dat de kans op
ten minste ´e´en arithmetische progressie van lengte k naar 1 gaat naarmate we een steeds groter
interval bekijken.
Hoofdstuk 4
Afhankelijke kleuringen
In het vorige hoofdstuk hebben we alleen gekeken naar onafhankelijke kleuringen van de natuurlijke getallen. Het is echter niet noodzakelijk dat de kleuring geheel onafhankelijk is. We zullen
in dit hoofdstuk met een resultaat waar we via eenvoudige aannames de covarianties kunnen
controleren laten zien dat lichte afhankelijkheden de resultaten niet verstoren. Daarna zullen
we ook naar een meer relevante afhankelijke kleuring kijken, namelijk een kleuring volgens een
Markovketen. Ook hiervoor zullen we analoge resultaten afleiden.
Opmerking. We zullen in het vervolg aannemen dat we te maken hebben met mixing, dat
wil zeggen dat voor alle begrensde functies f, g geldt dat
Cov(f (X≤i ), g(X≥j )) → 0 als |i − j| → ∞
4.1
Eenvoudige afhankelijkheden
Alhoewel het volgende resultaat misschien niet het meest praktische is, geeft het in ieder geval
wel op een eenvoudige wijze aan, dat we de eis van onafhankelijkheid niet als noodzakelijk hoeven
te beschouwen. In dit voorbeeld nemen we aan dat afhankelijkheden tussen progressies afnemen,
naarmate ze verder uit elkaar liggen. We krijgen het volgende resultaat.
Propositie 4.1.1. Laat (Xn )n een random kleuring zijn met kleuren Ω = {0, 1}. Neem aan dat
wordt voldaan aan aanname 3.1.1 op bladzijde 9. Neem verder aan dat voor alle i, j ∈ N, i 6= j,
geldt dat
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) ≤ E(Xi X2i · · · Xki )E(Xj X2j · · · Xkj )e−d(i,j)
waarbij d(i, j) = min{|ai − bj| : a, b ∈ {1, 2, . . . , k}}. Dan convergeert
1
Bk (n) Sn,k
in kans naar 1.
Bewijs. We gaan dit bewijzen met behulp van lemma 2.1.1. We beginnen met de verwachting.
Merk op dat
!
n
n
X
X
E(Sn,k ) = E
Xi X2i · · · Xki =
E(Xi X2i · · · Xki )
i=1
i=1
17
18
HOOFDSTUK 4. AFHANKELIJKE KLEURINGEN
Omdat we aan hebben genomen dat we te maken hebben met mixing, geldt er dat
lim E(Sn,k ) =
n→∞
=
=
lim
n→∞
lim
n→∞
∞
X
n
X
i=1
n
X
E(Xi X2i · · · Xki )
E(Xi )E(X2i ) · · · E(Xki )
i=1
bi b2i · · · bki
i=1
= ∞
Nu gaan we nog kijken naar de variantie. We zullen nu bewijzen dat er een C > 0 bestaat
zodanig dat V (Sn,k ) ≤ CE(Sn,k ). Merk op dat we weer hebben dat
!
n
X
V (Sn,k ) = V
Xi X2i · · · Xki
i=1
=
n
X
V (Xi X2i · · · Xki ) + 2
i=1
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj )
i<j
Merk op dat
n
X
V (Xi X2i · · · Xki ) =
i=1
≤
=
n
X
i=1
n
X
i=1
n
X
E((Xi X2i · · · Xki )2 ) − E(Xi X2i · · · Xki )2
E((Xi X2i · · · Xki )2 )
E(Xi X2i · · · Xki )
i=1
Hierbij hebben we in de laatste gelijkheid gebruik gemaakt van het feit dat (Xi X2i · · · Xki )2 =
1 precies als Xi X2i · · · Xki = 1.
Nu moeten we alleen nog het tweede stuk afschatten. Merk op dat we sommeren over i < j.
Merk op dat als i < j, dat dan voor iedere 0 < a < b geldt dat |bi − aj| ≤ |ai − bj|. Verder geldt er dat |i − j| ≤ a|i − j| voor alle a ≥ 1. Hieruit volgt dat voor i < j geldt dat
d(i, j) = min{|i − j|, min{|bi − aj| : 1 ≤ a < b ≤ k}}.
Merk op dat
X
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) ≤
E(Xi X2i · · · Xki )E(Xj X2j · · · Xkj )e−d(i,j)
i<j
i<j
≤
=
X
i<j
n
X
E(Xi X2i · · · Xki )e−d(i,j)
n
X
E(Xi X2i · · · Xki )e−d(i,j)
i=1 j=i+1
=
n
X
i=1
E(Xi X2i · · · Xki )
n
X
j=i+1
e−d(i,j)
4.1. EENVOUDIGE AFHANKELIJKHEDEN
19
Hierbij hebben we gebruik
van het feit dat E(Xj X2j · · · Xkj ) ≤ 1. We zullen nu een
Pn gemaakt
−d(i,j)
, onafhankelijk van i en n. Merk daarvoor allereerst op
afschatting maken van j=i+1 e
dat voor i < j geldt dat
e−d(i,j) = e− min{|i−j|,min{|bi−aj|:1≤a<b≤k}} ≤ e−|i−j| +
X
e−|bi−aj|
1≤a<b≤k
Maar dan vinden we dus dat
n
X
n
X
e−d(i,j) ≤
j=i+1
j=i+1
n
X
X
e−|i−j| +
e−|bi−aj|
1≤a<b≤k j=i+1
Nu moeten we alleen nog al deze termen afschatten. We zullen beginnen met
Er geldt dat
n
X
e
−|i−j|
=
j=i+1
n−i
X
Pn
j=i+1 e
−|i−j| .
e−|i−j|
j=1
≤
n
X
e−|i−j|
j=1
=
i
X
j=1
=
i
X
n
X
e−|i−j| +
j=i+1
n
X
e−(i−j) +
j=1
=
≤
i−1
X
j=0
∞
X
e−|i−j|
e−(j−i)
j=i+1
e−j +
e−j +
j=0
n−i
X
j=1
∞
X
e−j
e−j
j=0
< ∞
Neem nu 1 ≤ a < b ≤ k. We zullen laten zien dat we
kunnen schatten.
n
X
−|bi−aj|
e
≤
j=i+1
bn
X
Pn
−|bi−aj|
j=i+1 e
e−|bi−aj|
j=1
=
b
i
bX
a c
e
−|bi−aj|
j=1
=
b
i
bX
a c
j=1
bn
X
+
e−|bi−aj|
j=d ab ie
b
e−a( a i−j) +
bn
X
j=d ab ie
b
e−a(j− a i)
op identieke wijze af
20
HOOFDSTUK 4. AFHANKELIJKE KLEURINGEN
Nu gaan we deze twee sommen apart bekijken.
b
i
bX
a c
e
−a( ab i−j)
≤
j=1
b
i
bX
a c
e−a(b a ic−j)
b
j=1
=
≤
ic−1
b abX
e−aj
j=0
∞
X
e−aj
j=0
< ∞
Ook hebben we dat
bn
X
b
e−a(j− a i) ≤
j=d ab ie
bn
X
e−a(j−d a ie)
b
j=d ab ie
bn−d ab ie
=
≤
X
e−aj
j=0
∞
X
−aj
e
j=0
< ∞
Omdat er slechts eindig veel verschillende sommen (uitsluitend afhankelijk van k) zijn, en
aangezien we elke met een P
constante af kunnen schatten, vinden we dus dat er een constante
C > 0 bestaat zodanig dat nj=i+1 e−d(i,j) < C. Maar dan vinden we dus dat
X
Cov(Xi X2i · · · Xki , Xj X2j · · · Xkj ) ≤ C
i<j
n
X
E(Xi X2i · · · Xki )
i=1
Als we nu alles samennemen dan zien we dat
V (Sn,k ) ≤
n
X
E(Xi X2i · · · Xki ) + 2C
i=1
n
X
i=1
E(Xi X2i · · · Xki ) = (1 + 2C)
n
X
E(Xi X2i · · · Xki )
i=1
V (Sn,k ) In het bijzonder geldt er dus dat E(Sn,k
) ≤ 1 + 2C < ∞. Maar dan geeft lemma 2.1.1 ons dat
1
E(Sn,k ) Sn,k
in kans naar 1 convergeert.
We willen nogmaals benadrukken dat bovenstaande voorwaarde niet erg natuurlijk is. Als
de twee arithmetische progressies niet door elkaar heen lopen, is zo’n type afschatting nog wel
te rechtvaardigen. Echter, als de twee progressies wel door elkaar heen gaan lopen, dan kunnen
we in het algemeen niet verwachten dat een bovengrens afhankelijk is van de verwachting van
de progressies apart.
Merk ook op dat in de exponent van de afschatting niet per se −d(i, j) hoeft te staan. We
maken namelijk vooral gebruik van het feit, dat we hierdoor afschatting kunnen maken met
4.2. KOPPELING
21
behulp van convergente reeksen. Er mag dus ook best een functie van d(i, j) in de exponent
staan, zolang we maar gebruik kunnen blijven maken van de convergente reeksen.
Alhoewel het resultaat misschien niet heel praktisch is, geeft propositie 4.1.1 wel aan, dat
we nog steeds positieve resultaten kunnen krijgen als er lichte afhankelijkheden zijn, die vooral
afhangen van de afstand tussen de progressies. Markovketens hebben in het algemeen de eigenschap dat de afhankelijkheden afnemen, naarmate de tijdstippen verder uit elkaar gaan liggen.
Aangezien Markovketens zeer toepasbaar zijn, zullen we daarom dieper ingaan op kleuringen
volgens een Markovketen.
4.2
Koppeling
Om onze resultaten voor Markovketens te kunnen bewijzen, kunnen we geen gebruik vaken van
de eenvoudige afhankelijkheidsstructuur uit de vorige paragraaf. We kunnen echter wel gebruik
maken van koppeling van stochasten, om alsnog tot een bewijs te komen. Daarom zullen we
bespreken wat we precies bedoelen met het koppelen van stochasten, en in het bijzonder van
rijen van stochasten.
Definitie 4.2.1. Laat X en Y twee stochasten zijn, gedefinieerd op een kansruimte (Ω, F, P ).
ˆ Yˆ ) gedefinieerd op (Ω × Ω, F ⊗ F, Pˆ ),
Een koppeling van X en Y is een paar stochasten Z = (X,
zodanig dat de marginalen van Z dezelfde verdeling hebben als X en Y .
Merk op dat elk paar stochasten dat aan bovenstaande voldoet een koppeling is. We kunnen
dus in het algemeen niet praten over de koppeling van twee stochasten.
Een koppeling van twee rijen van stochasten is een speciaal geval van bovenstaande definitie.
Laat (Xn )n en (Yn )n twee rijen stochasten zijn, zodanig dat Xn en Yn voor iedere n gedefinieerd
zijn op de kansruimte (Ω, F, P ). Definieer nu X = (Xn )n en Y = (Yn )n . Dan zijn X en Y
twee stochasten gedefinieerd op de kansruimte (ΩN , F N , P 0 ). Hierop kunnen we vervolgens de
definitie van koppeling van stochasten toepassen.
Bij het koppelen van rijen van stochasten is het natuurlijk om je af te vragen hoelang het
duurt totdat de componenten van een koppeling bij elkaar komen en samen verder gaan. Dit
noemen we de koppelingstijd.
Definitie 4.2.2. Laat (Xn )n en (Yn )n twee rijen stochasten zijn gedefinieerd op dezelfde kansruimte. Laat ((Xˆn )n , (Yˆn )n ) een koppeling zijn. De koppelingstijd τ is nu gedefinieerd als
ˆ m = Yˆm voor alle m ≥ n}
τ = inf{n ∈ N|X
Hierbij is het mogelijk dat τ = ∞.
We noemen een koppeling succesvol, als τ bijna zeker eindig is, dat wil zeggen dat P (τ <
∞) = 1. We hebben er immers weinig aan als we met positieve kans oneindig lang moeten
wachten totdat er koppeling optreedt.
4.2.1
Markovketens
De toepassing die we willen bespreken betreft Markovketens. Voordat we hiermee gaan werken,
zullen we de belangrijkste definities geven, en ook een succesvolle koppeling introduceren voor
Markovketens.
22
HOOFDSTUK 4. AFHANKELIJKE KLEURINGEN
Definitie 4.2.3. Een rij stochasten (Xn )n op een aftelbare toestandsruimte Ω heet een Markovketen als aan de zogeheten Markov-eigenschap
P (Xn+1 = xn+1 |Xn = xn , Xn−1 = xn−1 , . . . , X0 = x0 ) = P (Xn+1 = xn+1 |Xn = xn )
voldaan wordt.
De Markov-eigenschap houdt in feite in dat de toekomst gegeven het heden onafhankelijk is
van het verleden. Het is voor het vervolg dus alleen belangrijk waar we zijn beland, en niet hoe
we er zijn gekomen.
In sommige gevallen is het ook wenselijk om naar rijen te kijken met een zogeheten meerstapsgeheugen. Dat wil zeggen, dat niet alleen het heden belangrijk is voor het vervolg, maar
ook een aantal stappen uit het verleden. Zo’n rij met een k-stapsgeheugen moet dan voldoen
aan
P (Xn+1 = xn+1 |Xn = xn , Xn−1 = xn−1 , . . . , X0 = x0 ) =
= P (Xn+1 = xn+1 |Xn = xn , Xn−1 = xn−1 , . . . , Xn−k+1 = xn−k+1 )
Dit hoeven we echter niet apart te bekijken, omdat we hier een Markovketen van kunnen maken. Als we namelijk Yn = (Xn , Xn+1 , . . . , Xn+k−1 ) defini¨eren, dan is (Yn )n een Markovketen,
en kunnen we daar de theorie op toepassen.
Het blijkt dat overganskansen heel belangrijk zijn voor een Markovketen. We defini¨eren dus
pi (a, b) = P (Xi+1 = b|Xi = a) de overgangskans van toestand a naar b op tijdstip i. Als deze
kans niet afhangt van i dan noemen we de Markovketen homogeen (stationair). Anders noemen
we de keten inhomogeen.
In het vervolg zullen wij Markovketens bekijken waarbij Ω = {0, 1 . . . , k − 1}. In dat geval
kunnen we de Markovketen namelijk zien als een random kleuring van de natuurlijke getallen,
welke we aan het bestuderen zijn. De koppeling die wij nodig zullen hebben, is die tussen twee
dezelfde Markovketens, alleen beginnend in andere toestanden. Daarbovenop eisen we ook nog
dat de koppeling weer een Markovketen is. We zullen uitschrijven wat een koppeling voor dit
speciale geval is.
Definitie 4.2.4. Laat (Xn )n een Markovketen zijn op een (eindige) toestandsruimte Ω. Laat
(Xn1 )n een Markovketen zijn startende vanuit x ∈ Ω met L((Xn1 )n ) = L((Xn )n ). Laat verder
(Xn2 )n een Markovketen zijn startende vanuit y ∈ Ω met L((Xn2 )n ) = L((Xn )n ). Een Markovkopˆ n1 , X
ˆ n2 )n met overgangkansen
peling van deze twee ketens is een Markovketen (X
1
2
ˆ i+1
ˆ i+1
ˆ i1 , X
ˆ i2 ) = (x, y)]
pˆi ((x, y), (a, b)) = P [(X
,X
) = (a, b)|(X
zodanig dat
X
pˆi ((x, y), (a, b)) = pi (x, a)
b∈Ω
X
pˆi ((x, y), (a, b)) = pi (y, b)
a∈Ω
voor alle i ∈ N
Voor onze doeleinden moeten we een succesvolle koppeling verzinnen die aan bovenstaande
voldoet. Gelukkig is die bekend.
4.2. KOPPELING
23
Voorbeeld 4.2.1. Laat (Xn )n een irreduciebele, aperiodische Markovketen zijn op een (eindige) toestandsruimte Ω. Laat (Xn1 )n de Markovketen zijn startende vanuit x ∈ Ω en (Xn2 )n de
Markovketen startende vanuit y ∈ Ω. De koppeling die we gaan maken laat deze twee ketens
eerst onafhankelijk lopen, totdat ze samen komen. Vanaf dat moment gaan ze samen verder.
Om dit te bereiken moeten we de overgangskansen als volgt defini¨eren.


pi (x1 , y1 )pi (x2 , y2 ) x1 6= x2
pˆi ((x1 , x2 ), (y1 , y2 )) = pi (x1 , y1 )
x1 = x2 , y1 = y2


0
x1 = x2 , y1 6= y2
We laten het aan de lezer over om na te gaan dat er inderdaad aan de eis uit definitie 4.2.4
wordt voldaan.
De koppeling in bovenstaande voorbeeld is op een technisch detail na succesvol. Als we
echter eisen dat de Markovketen homogeen is, dan is de koppeling zeker succesvol. Voordat we
dit kunnen bewijzen, moeten we nog defini¨eren wat we bedoelen met de m-staps overganskansen
(m)
pi (a, b). Intu¨tief is dit de kans om vanaf tijdstip i in m stappen van toestand a naar toestand
b te gaan. Deze kansen zijn als volgt inductief gedefinieerd.
Definitie 4.2.5. Laat i ∈ N willekeurig. Zij verder x, y ∈ Ω. Voor iedere m ∈ N is de m-staps
overgangskans van x naar y gedefinieerd als
X (m−1)
(m)
(1)
pi (x, y) =
pi
(x, z)pi+m−1 (z, y), met pi (x, y) = pi (x, y)
z∈Ω
Nu kunnen de volgende propositie bewijzen.
Propositie 4.2.1. Laat (Xn )n een stationaire, irreducibele en aperiodische Markovketen zijn
op een eindige toestandsruimte Ω. Dan is de koppeling zoals ge¨ıntroduceerd in voorbeeld 4.2.1
succesvol.
Bewijs. We zullen laten zien dat limn→∞ P (τ > n) = 0. Omdat de keten stationair is, hangen de
overgangskansen niet van de tijd af. Daarom zullen we het subscript weglaten. Merk allereerst
op dat, aangezien de keten irreducibel en aperiodisch is, dat er een m ∈ N bestaat, zodanig dat
p(m) (x, y) > 0 voor alle x, y ∈ Ω. Omdat Ω eindig is, kunnen we hieruit concluderen dat er een
> 0 bestaat zodanig dat voor alle x, y ∈ Ω geldt dat p(m) (x, y) > .
Hieruit volgt nu voor iedere i dat
X
1
2
1
2
= t|Xi2 = y)
Pˆ (Xi+m
= Xi+m
|Xi1 = x, Xi2 = y) =
P (Xi+m
= t|Xi1 = x)P (Xi+m
t∈Ω
> X
2
P (Xi+1
= t|Xi2 = y)
t∈Ω
= 1
2
We vinden dus voor iedere i dat Pˆ (Xi+m
6= Xi+m
) ≤ 1 − . Merk nu op dat, vanwege de
Markoveigenschap van de koppeling, we de gebeurtenis τ > n kunnen zien als het feit dat het
ten minste n keer mislukt is om de ketens bij elkaar te brengen. Omdat wij in tijdstappen van
grootte m willen kijken, krijgen we dat
P (τ > n) ≤ P τ > m
j n k
m
≤
n
bY
mc
i=1
n
1
2
Pˆ (Xi+m
6= Xi+m
) ≤ (1 − )b m c
24
HOOFDSTUK 4. AFHANKELIJKE KLEURINGEN
Maar dan hebben we voor alle n > 2m dat
P (τ > n) ≤ eb m c log(1−) ≤ e 2m log(1−) = e−an
n
n
n
met a = − 2m
log(1 − ) > 0. Omdat limn→∞ e−an = 0, kunnen we nu concluderen dat
limn→∞ P (τ > n) = 0. Hieruit volgt dat de koppeling succesvol is.
We zullen nu bespreken dat we de exponenti¨ele bovengrens voor P (τ > n) kunnen gebruiken
om te laten zien dat we in dit geval nog steeds een zwakke wet van de grote aantallen krijgen.
Daartoe zullen we eerst een aantal lemma’s bewijzen. In deze lemma’s nemen we telkens aan
dat (Xn )n een Markovketen is op toestandsruimte Ω.
Lemma 4.2.1. Laat k ∈ N willekeurig. Neem verder aan dat er een succesvolle koppeling bestaat
zodanig dat P (τ > n) ≤ e−an voor een zekere a > 0. Neem verder aan dat Ω eindig is. Laat
i1 < i2 < · · · < ik . Laat C = sup{|ω| : ω ∈ Ω}. Dan geldt er dat
|E(Xi2 · · · Xik |Xi1 ) − E(Xi2 · · · Xik )| ≤ 2C k−1 e−a(i2 −i1 )
Bewijs. Merk allereerst op dat, aangezien Ω eindig is, dat C < ∞. Merk verder op dat |Xn | ≤ C
voor iedere n. Er geldt nu dat
|E(Xi2 · · · Xik |Xi1 ) − E(Xi2 · · · Xik )|
P
= |E(Xi2 · · · Xik |Xi1 ) − x∈Ω E(Xi2 · · · Xik |Xi1 = x)P (Xi1 = x)|
≤ supx,y∈Ω |E(Xi2 · · · Xik |Xi1 = x) − E(Xi2 · · · Xik |Xi1 = y)|
≤ 2||Xi2 · · · Xik ||∞ P (τ > i2 − i1 )
≤ 2C k−1 e−a(i2 −i1 )
Lemma 4.2.1 kunnen we nu gebruiken om het volgende aan te tonen.
Lemma 4.2.2. Laat k ∈ N willekeurig. Laat i1 < i2 < · · · < ik . Zij verder a > 0 zoals in het
vorige lemma. Neem wederom aan dat Ω eindig is, en laat weer C = sup{|ω| : ω ∈ Ω}. Definieer
d(i1 , i2 , . . . ik ) als
d(i1 , i2 , . . . , ik ) = min{|ia − ib | : a, b = 1, . . . , k}
Dan geldt er dat
|E(Xi1 Xi2 · · · Xik ) − E(Xi1 )E(Xi2 ) · · · E(Xik )| ≤ 2C k−1 e−ad(i1 ,...,ik )
Bewijs. We zullen dit bewijzen met inductie naar k. Merk op dat de uitspraak duidelijk waar
is voor k = 1. Neem nu k ∈ N willekeurig, en neem aan dat voor iedere i1 < i2 < · · · < ik
de uitspraak waar is. We zullen laten zien dat het ook waar is voor k + 1. Laat daartoe
j1 < j2 < · · · jk < jk+1 . Merk nu op dat
|E(Xj1 Xj2 · · · Xjk+1 ) − E(Xj1 )E(Xj2 ) · · · E(Xjk+1 )|
= |E(Xj1 [E(Xj2 · · · Xjk+1 |Xj1 ) − E(Xj2 ) · · · E(Xjk+1 )])|
≤ E(|Xj1 ||E(Xj2 · · · Xjk+1 |Xj1 ) − E(Xj2 ) · · · E(Xjk+1 )|)
4.2. KOPPELING
25
Nu gaan we |E(Xj2 · · · Xjk+1 |Xj1 ) − E(Xj2 ) · · · E(Xjk+1 )| afschatten. Dit doen we in stappen.
Hierbij zullen we gebruik maken van lemma 4.2.1 en van de inductiehypothese. Merk allereerst
op dat
E(Xj2 · · · Xjk+1 |Xj1 ) − E(Xj2 ) · · · E(Xjk+1 )
≤ 2C k−1 e−a(j2 −j1 ) + E(Xj2 · · · Xjk+1 ) − E(Xj2 ) · · · E(Xjk+1 )
≤ 2C k−1 e−a(j2 −j1 ) + 2C k−1 e−ad(j2 ,...,jk+1 )
≤ 4C k−1 e−ad(j1 ,j2 ,...,jk+1 )
Op eenzelfde wijze hebben we dat
E(Xj2 · · · Xjk+1 |Xj1 ) − E(Xj2 ) · · · E(Xjk+1 )
≥ −2C k−1 e−a(j2 −j1 ) + E(Xj2 · · · Xjk+1 ) − E(Xj2 ) · · · E(Xjk+1 )
≥ −2C k−1 e−a(j2 −j1 ) − 2C k−1 e−ad(j2 ,...,jk+1 )
≥ −4C k−1 e−ad(j1 ,j2 ,...,jk+1 )
Uit bovenstaande volgt dat
|E(Xj2 · · · Xjk+1 |Xj1 ) − E(Xj2 ) · · · E(Xjk+1 )| ≤ 4C k−1 e−ad(j1 ,j2 ,...,jk+1 )
Dit kunnen we nu gebruiken. We krijgen dat
|E(Xj1 Xj2 · · · Xjk+1 ) − E(Xj1 )E(Xj2 ) · · · E(Xjk+1 )|
≤ E(|Xj1 |)4C k−1 e−ad(j1 ,j2 ,...,jk+1 )
≤ 4C k e−ad(j1 ,j2 ,...,jk+1 )
= 2C 0k e−ad(j1 ,j2 ,...,jk+1 )
We vinden dus dat de uitspraak waar is voor k + 1. Hiermee is het bewijs rond.
Nu gaan we kijken naar een stationaire, irreducibele en aperiodieke Markovketen die voldoet
aan de sterke aanname 3.2.1 op bladzijde 11. We zullen de toestandsruimte Ω = {0, 1} gebruiken,
zodat de Markovketen
toe hebben bekeken.
Pneen random kleuring voorstelt zoals wij die tot1 nuP
Laat weer Bk (n) = i=1 E(Xi X2i · · · Xki ) we zullen bewijzen dat Bk (n) ni=1 Xi X2i · · · Xki in
kans naar 1 convergeert.
Merk daartoe op dat, aangezien de Markovketen stationair, irreducibel en aperiodiek is, dat
er een a > 0 bestaat, zodanig dat P (τ > n) ≤ e−an . Omdat verder Ω = {0, 1}, kunnen we
lemma 4.2.2 toepassen met C = 1. Als we dat doen, dan vinden we dat
P
V ( ni=1 Xi X2i · · · Xki )
P
P
= E ( ni=1 Xi · · · Xki )2 − E ( ni=1 Xi · · · Xki )2
P
= ni,j=1 E(Xi · · · Xki Xj · · · Xkj ) − E(Xi · · · Xki )E(Xj · · · Xkj )
P
≤ ni,j=1 E(Xi · · · Xki Xj · · · Xkj ) − (E(Xi ) · · · E(Xki ) − 2e−ai )(E(Xj ) · · · E(Xkj ) − 2e−aj )
P
= ni,j=1 E(Xi · · · Xki Xj · · · Xkj ) − E(Xi ) · · · E(Xki )E(Xj ) · · · E(Xkj ) + O(e−ai + e−aj )
P
≤ ni,j=1 2e−ad(i,...,ki,j,...,kj) + O(e−ai + e−aj )
Op een gelijke manier als in het bewijs van propositie
P 4.1.1 kunnen we voor vaste i een constante
K > 0 vinden, afhankelijk van k zodanig dat nj=1 2e−ad(i,...,ki,j,...,kj) + O(e−ai + e−aj ) ≤ K.
26
HOOFDSTUK 4. AFHANKELIJKE KLEURINGEN
P
Maar dan vinden we dus dat V ( ni=1 Xi X2i · · · Xki ) ≤ Kn. Merk nu op dat we nog steeds
hebben dat er een C > 0 bestaat zodanig dat voor n groot genoeg geldt dat Bk (n) > Cn1−δ
voor alle δ ∈ (0, 1). Dit volgt namelijk eenvoudig uit lemma 4.2.2. Als we deze afschatting
gebruiken met δ = 41 dan vinden we voor n groot genoeg dat
1
V
Bk (n)2
n
X
!
Xi X2i · · · Xki
≤
i=1
1
K
Kn
= 2 n− 2 → 0
3/2
2
C
C n
Met de ongelijkheid van Chebyshev zien we dan voor willekeurige > 0 dat
P
!
n
1 X
Xi X2i · · · Xki − 1 ≥ Bk (n)
V
≤
4.3
1
Bk (n)
1
Bk (n)
Pn
i=1 Xi X2i · · · Xki
2
Pn
V ( i=1 Xi X2i · · · Xki )
=
Bk (n)2 2
→ 0
i=1
Uit bovenstaande volgt dat inderdaad
Pn
i=1 Xi X2i · · · Xki
in kans naar 1 convergeert.
Inhomogene Markovketens
Nu gaan we kijken naar een inhomogene, irreducibele en aperiodieke Markovketen (Xn )n met
eindige toestandsruimte Ω. In de vorige paragraaf hebben we al een aantal nuttige lemma’s
afgeleid, die ook goed toepasbaar zijn op inhomogene ketens. Het lastige is vooral de exponenti¨ele
bovengrens op P (τ > n) verkrijgen. Het probleem is namelijk dat de overgangskansen van de
tijd afhangen. We kunnen daarom niet meer zeggen dat er een m ∈ N bestaat, zodanig dat
p(m) (x, y) > voor alle x, y ∈ Ω. We krijgen nu zoiets als dat er een m bestaat zodanig dat voor
(m)
iedere i geldt dat pi (x, y) > i voor alle x, y ∈ Ω. In dat geval krijgen we dat
P (τ > n) ≤
n
bY
mc
(1 − i )
i=1
maar dat hoeft niet per se afgeschat te kunnen worden door een exponenti¨ele bovengrens.
Daarom zullen we ons nu beperken tot een geval dat in de lijn ligt van wat we tot nu toe
hebben gedaan. We zullen namelijk de toestandsruimte Ω = {0, 1} gebruiken. Definieer
pi (0, 1) = ai , pi (0, 0) = 1 − ai , pi (1, 1) = ci en pi (1, 0) = 1 − ci . Conform de idee¨en dat de
kans op een 1 steeds kleiner moet worden, zullen we aannemen dat ai , ci ↓ 0.
1
2 ) = a (1 − c ) + c (1 − a ) ≤ a + c . Maar dan vinden we dus
Merk nu op dat Pˆ (Xi+1
6= Xi+1
i
i
i
i
i
i
dat
n
n
Y
Y
1
2
P (τ > n) ≤
Pˆ (Xi+1
6= Xi+1
)≤
(ai + ci )
i=1
i=1
Deze bovengrens kunnen we als volgt schrijven
n
Y
i=1
(ai + ci ) = e
Pn
i=1
log(ai +ci )
≤ e−
Pn
i=1
1−ai −ci
4.3. INHOMOGENE MARKOVKETENS
27
Omdat ai , ci ↓ 0, bestaat er een i0 ∈ N zodanig dat voor alle i > i0 geldt dat 1 − ai − ci > 12 .
Maar dan vinden we voor n groot genoeg dus dat
n
Y
(ai + ci ) ≤ e−
Pn
1
i=1 2
1
= e− 2 n
i=1
We zien dus dat er een a > 0 bestaat, zodanig dat P (τ > n) < e−an . Op een gelijke
wijze P
als in de vorige paragraaf kunnen we dan laten zien, dat ook in dit geval geldt dat
n
1
i=1 Xi X2i · · · Xki in kans naar 1 convergeert. We hebben daarin namelijk nergens anders
Bk (n)
gebruik gemaakt van de homogeniteit.
28
HOOFDSTUK 4. AFHANKELIJKE KLEURINGEN
Hoofdstuk 5
Concentratie afschattingen
In dit hoofdstuk zullen we ingaan op een algemenere afschatting van P (|X − E(X)| ≥ ). We
gaan hiervoor kijken naar zogehete Gaussische concentratie ongelijkheden. Het zal blijken dat
deze methode van afschatten een alternatief
bewijs zal geven voor stelling 3.2.1, i.e. voor de
P
bijna zekere convergentie van Bk1(n) ni=1 Xi X2i · · · Xki naar 1. Verder zullen we ook zien dat we
een sterker resultaat af kunnen leiden voor Markovketens.
5.1
Onafhankelijke rijen
Voor een rij onafhankelijke, identiek verdeelde en begrensde stochasten (Xn )n en een functie
f : Rn → R is voor iedere > 0 de volgende Gaussische concentratie afschatting bekend
−c P
P (|f (X1 , X2 , · · · , Xn ) − E(f )| ≥ ) ≤ e
2
2
i (δi f )
waarbij δi f gedefinieerd is als
δi f = sup {|f (x) − f (y)| : xj = yj voor alle j 6= i}
x,y∈Ωn
Intu¨ıtief is δi f de maximale variatie in f die enkel wordt veroorzaakt door de i-de co¨ordinaat.
De constante c in de afschatting is gebaseerd op de verdeling van X1 , . . . , Xn .
Met bovenstaande ongelijkheid in ons hoofd, kunnen we terug kijken naar de situatie van
een onafhankelijke kleuring waarmee we zijn begonnen. We hebben dus een rij stochasten
(Xn )n , waarbij voor iedere n Xn Bernoulli verdeeld is met parameter bn . Verder eisen we dat
wordt voldaan aan de sterke aanname 3.2.1 op baldzijde 11. We zullen laten zien dat we met
behulp van de Gaussische concentratie afschatting een alternatief bewijsPkrijgen voor het feit
n
dat Bk1(n) Sn,k bijna zeker naar 1 convergeert. Hierbij is weer Sn,k =
i=1 Xi X2i · · · Xki en
Pn
Bk (n) = E(Sn,k ) = i=1 bi b2i · · · bki .
We zitten alleen met het probleem, dat in ons voorbeeld de stochasten niet identiek verdeeld zijn. Echter, voor Bernoulli verdeelde stochasten is het bekend, dat de constante c in de
Gaussische concentratie afschatting het slechtst is als de succeskans een half is. Immers, dan
is de variantie maximaal. We kunnen dus in dit geval deze constante nemen voor elk van de
afschattingen die volgen.
We defini¨eren nu fn : Rkn → R door
n
1 X
fn (X1 , X2 , . . . , Xkn ) =
Xi X2i · · · Xki
Bk (n)
i=1
29
30
HOOFDSTUK 5. CONCENTRATIE AFSCHATTINGEN
Nu rest ons nog te bepalen wat δi fn is voor iedere i = 1, 2, . . . , kn, of in ieder geval, wat een
geschikte bovengrens hiervoor is. We moeten dus
sup {|fn (x) − fn (y)|xj = yj , j 6= i}
δi fn =
x,y∈Ωkn
afschatten.
P
Merk daartoe op dat xi in maximaal k termen van de som nj=1 Xj X2j · · · Xkj voor kan
komen, namelijk als i = j, i = 2j, . . . , i = kj. In het geval dat i = aj, met 1 ≤ a ≤ k, dan
hebben we dat
|xj · · · x(a−1)j xi x(a+1)j · · · xkj − xj · · · x(a−1)j yi x(a+1)j · · · xkj |
= |(xj · · · x(a−1)j x(a+1)j · · · xkj )(xi − yi )|
≤ |xi − yi |
≤1
Uit alles kunnen we nu concluderen dat δi fn ≤
kn
X
(δi fn )2 ≤
i=1
kn X
i=1
k
Bk (n) .
k
Bk (n)
Daaruit volgt dat
2
=
k3 n
Bk (n)2
Maar dan vinden we dus dat
!
2
n
1 X
c2 Bk (n)2
−c Pkn (δi fn )2
i=1
P Xi X2i · · · Xki − 1 ≥ ≤ e
≤ e− k 3 n
Bk (n)
i=1
Merk nu op dat we eerder hebben bewezen dat voor iedere δ ∈ (0, 1) geldt dat Bk (n) > Cn1−δ
voor een zekere C > 0. Als we deze afschatting gebruiken met δ = 41 , dan vinden we dat
P
!
n
1 X
c2 (Cn3/4 )2
c2 C 2 √
= e− k3 n
Xi X2i · · · Xki − 1 ≥ ≤ e− k3 n
Bk (n)
i=1
Merk nu op dat
∞
X
e−
c2 C 2 √
n
k3
<∞
n=1
Samen met bovenstaande afschatting geeft dit ons dat
!
∞
n
1 X
X
P Xi X2i · · · Xki − 1 ≥ < ∞
Bk (n)
n=1
Gevolg 2.2.1 geeft ons nu dat
5.2
i=1
1
Bk (n) Sn,k
bijna zeker naar 1 convergeert.
Afhankelijke rijen
De afschatting uit de vorige paragraaf werkt echter alleen als de stochasten onafhankelijk verdeeld zijn. Als er afhankelijkheden zijn, is echter nog niet alles verloren. Om eenzelfde soort
5.2. AFHANKELIJKE RIJEN
31
afschatting te kunnen maken, moeten we de zogehete koppelingsmatrix D defini¨eren. Dit is een
n × n-matrix gegeven door
(
ˆ 1 6= X
ˆ 2 |X
ˆ 1 = x, X
ˆ 2 = y) i < j
supx,y Pˆ (X
j
j
i
i
Dij =
0
elders
Als we dan de vector δf defini¨eren als (δf )i = δi f , dan krijgen we de volgende afschatting
P (|f (X1 , X2 , · · · , Xn ) − E(f )| ≥ ) ≤ e
−c
2
||Dδf ||2
2
We zullen laten zien dat voor een Markovketen met een succesvolle koppeling waarvoor er
een a > 0 bestaat zodanig dat P (τ > n) < e−an deze afschatting op hetzelfde neerkomt als de
Gaussische concentratie ongelijkheid voor onafhankelijke stochasten.
Merk hiervoor op dat we een lineaire
P operator D : `2 (N) → `2 (N) kunnen defini¨eren als
(fi )i∈N 7→ ((Df )i )i∈N , waarbij (Df )i = j Dij fj . Merk verder op dat voor i < j geldt dat
ˆ j1 6= X
ˆ j2 |X
ˆ i1 = x, X
ˆ i2 = y) ≤ P (τ > j − i) ≤ e−a(j−i)
Dij = sup Pˆ (X
x,y
Verder geldt er voor i ≥ j dat Dij = 0. We vinden dus dat Dij ≤ e−a|i−j| voor alle i, j. Met
behulp van Young’s ongelijkheid vinden we dan dat
||Dδf ||22 =
n X
n
X
(Dij δj f )2 ≤ C
i=1 j=i+1
n
X
(δi f )2
i=1
Hieruit volgt nu dat
−c
P (|f (X1 , X2 , · · · , Xn ) − E(f )| ≥ ) ≤ e
2
||Dδf ||2
2
−c
≤e
C
2
Pn (δ f )2
i=1 i
−c0 Pn
=e
2
(δi f )2
i=1
We zien dus dat we in dit geval inderdaad eenzelfde soort bovengrens krijgen!
Met eenzelfde argument als in het onafhankelijke geval kunnen we nu dus ook concluderen
dat als (Xn )n een eindige, aperiodieke, irreducibele Markovketen is, dat dan ook nog Bk1(n) Sn,k
bijna zeker naar 1 convergeert.
We sluiten af met een opmerking betreffende Markovkleuringen. We hebben eigenlijk alleen
maar gekeken naar kleuringen met twee kleuren. Nu hebben we bij de introductie van een
random kleuring in hoofdstuk 1 uitgelegd, dat dit geen probleem is, omdat we een kleuring met
k kleuren altijd terug kunnen brengen naar een kleuring met 2 kleuren. Dit is in het geval
van een onafhankelijke kleuring zeker waar. Echter, als we kleuren volgens een Markovketen,
dan kunnen we niet zomaar kleuren veranderen. We kunnen er dan namelijk niet zomaar van
uitgaan, dat de nieuwe keten met enkel twee kleuren nog steeds een Markovketen is. We zullen
nu laten zien, dat het toch genoeg is om Markovketens met twee kleuren te bekijken.
Laat daartoe (Xn )n een Markovketen zijn op Ω = {1, 2, . . . , r}, dat is, een random kleuring
volgens een Markovketen met r kleuren. Definieer nu de rij stochasten (Yn )n door
(
1 Xn = 1
Yn =
0 Xn 6= 1
Dan is (Yn )n in het algemeen geen Markovketen. Toch hebben we het volgende afschatting.
32
HOOFDSTUK 5. CONCENTRATIE AFSCHATTINGEN
1 6= Y
ˆ 2 |Y0 = y0 , . . . , Yi = yi )
P (Yˆi+n
i+n
ˆ 1 6= X
ˆ 2 |X0 = x0 , . . . , Xi = xi )
≤ supx0 ,...,xi P (X
i+n
i+n
≤ P (τX > n)
≤ e−an
voor een zekere a > 0.
Deze afschatting is genoeg om onze resultaten toe te kunnen passen. Alhoewel we veelal
hebben ge¨eist dat P (τ > n) afgeschat kan worden met een exponenti¨ele bovengrens, hebben we
eigenlijk altijd de tweede ongelijkheid uit bovenstaande serie ongelijkheden toegepast om ervan
gebruik te kunnen maken.
Omdat we de eigenschappen van Markovketens alleen maar gebruikt hebben om aan deze
exponenti¨ele bovengrens te komen, zien we nu, dat we onze resultaten ook toe kunnen passen
op (Yn )n . Hiermee hebben we ge¨ıllustreerd dat we ook in het geval van een kleuring volgens een
Markovketen slechts naar het geval met twee kleuren hoeven te kijken.
Bibliografie
[1] A. Arbieto, C. Matheus, C.G. Moreira. The remarkable effectiveness of ergodic theory in
number theory, Ensaios Mathem´aticos, vol 17, 2009
[2] J.S. Rosenthal. A first look at rigorous probability theory, second edition, World Scientific,
2006
[3] F. den Hollander. Probability theory:
the coupling method, 2012,
http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf
online:
[4] J. Chazottes, F. Redig. Concentration inequalities for Markov processes via coupling, Electronic Journal of Probability, vol 14, 1162-1180, 2008
[5] A. Kourbatov. The distribution of maximal prime gaps in Cram`er’s probabilistic model of
primes, 2010, online: http://arxiv.org/pdf/1401.6959v1.pdf
[6] M. Ledoux. The concentration of measure phenomenon, American Mathematical Society,
2001
[7] H. Bauer. Measure and integration theory, De Gruyter Studies in Mathematics, 2001
[8] B. van Schriek. Rekenkundige progressies in Markovkleuringen van de natuurlijke getallen,
Bachelorscriptie Radboud Universiteit Nijmegen, 2011
33

Download Report