|
||||||||||||||||||||||||||
| Rijen van random getallen. | ||||||||||||||||||||||||||
| Hieronder zie je een aantal decimalen van e | ||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
| 't is natuurlijk maar
een klein deel, en als je er meer wilt weten staan die op
http://apod.nasa.gov/htmltest/gifcity/e.2mil., daar staan er 2
miljoen, berekend door Nemiroff en Bonnell. Bij zulke enorme
rijen getallen zonder vaste regelmaat stel ik mezelf altijd direct een
aantal vragen. Zoals natuurlijk "Staat mijn verjaardag
erin?" of "Zou er een serie van zes keer hetzelfde
cijfer zijn?" en nog veel meer. Deze les gaat het om de vraag: "Staat er een serie van 10 verschillende cijfers in?". Dus alle cijfers van 0 tm 9, eventueel in willekeurige volgorde. Het antwoord is "JA". Maar nou komt de eigenlijke hoofdvraag: "Op welke plaats in de rij zal zo'n serie gemiddeld (in een rij van random gekozen getallen) voor het eerst te vinden zijn?" Markov-Ketens. Om deze vraag te beantwoorden maken we gebruik van zgn. Markov-ketens. Je mag het ook overgangsmatrices noemen. Dat werkt zó: We kennen eerst aan elke serie cijfers een bepaalde "toestand" toe en kijken dan hoe die toestanden in elkaar overgaan als er nieuwe cijfers worden toegevoegd |
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
| Hier zie je een aantal toestanden van stukjes van e: | ||||||||||||||||||||||||||
| 2.71828
is T2 2.718281828459045235360 is T4 2.7182818284590452353602874713526 is T7 |
||||||||||||||||||||||||||
| Zodra T10 is bereikt
hebben we onze gezochte serie van 10 verschillende cijfers gevonden. Laten we eens kijken wat er gebeurt als er aan een serie in een bepaalde toestand een nieuw random cijfer wordt toegevoegd. Neem bijvoorbeeld de T4 serie van hierboven: 2.718281828459045235360 Als het nieuwe cijfer niet bij de laatste 4 staat (dus 124789) wordt de toestand T5, De kans daarop is 0,6 Als het nieuwe cijfer gelijk is aan 0 wordt het T1. De kans daarop is 0,1. Als het nieuwe cijfer gelijk is aan 6 wordt het T2. De kans daarop is 0,1. Als het nieuwe cijfer gelijk is aan 3 wordt het T3. De kans daarop is 0,1. Als het nieuwe cijfer gelijk is aan 5 blijft het T4. De kans daarop is 0,1. Als we van al deze overgangen tussen toestanden een overgangsmatrix opstellen dan geeft dat de volgende matrix (alle kansen moet nog gedeeld worden door 10): |
||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||
| Merk nog even op dat we toestand
T10 er niet in hebben staan. Dat is de reden dat die laatste
kolom met kansen niet opgeteld 1 oplevert, maar 0,9. Door nu een beginvector B te nemen met daarin de kansen op de begintoestand kunnen we door met deze matrix Mn te vermenigvuldigen de kansen op de verschillende toestanden na n stappen berekenen. De som van al die kansen opgeteld wordt steeds kleiner want wat er mist is de kans op toestand T10, en die wordt steeds groter. Voorbeeld. Als we met een willekeurig random begincijfer beginnen dan is de beginvector B een kolom met 1 op de eerste plaats en de rest nullen want het is immers een toestand T1. Laten we kijken hoe het na 15 overgangen is (dan hebben we 16 cijfers), dus laten we M15 • B berekenen. |
||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||
| Dus voor een serie van 16 random
cijfers is de kans bijvoorbeeld ongeveer 9% dat de laatste 6
verschillend zijn (T6). De kansen opgeteld leveren 0,9977 dus de kans op toestand 10 is 1 - 0,9977 = 0,0023 Als we beginnen met een random serie van 10 cijfers en vanaf daar cijfers gaan toevoegen, dan kunnen we de toestand startkansen in die eerste randomserie dus makkelijk uitrekenen met M9 • B. Dat geeft voor een willekeurige serie van 10 cijfers: |
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
| Die laatste is weer berekend met
1 - rest. Natuurlijk kunnen we als controle deze kansen ook wel met de hand uitrekenen. Hoe groot is bijvoorbeeld de kans dat een random serie van 10 getallen eindigt op 4 verschillenden? Begin gewoon van achteraf te checken: • het laatste cijfer is willekeurig: kans 1 • het cijfer daarvoor is ongelijk aan het laatste: kans 0,9 • het cijfer daarvoor is ongelijk aan de twee laatsten: kans 0,8 • het cijfer daarvoor is ongelijk aan de drie laatsten: kans 0,7 • het cijfer daarvoor is gelijk aan één van de vier laatsten: kans 0,4 • de rest is willekeurig: kans allemaal 1 Dat geeft totaalkans 1 • 0,9 • 0,8 • 0,7 • 0,4 • 1 • 1 • 1 • 1 • 1 = 0,2016. YES! precies die uit de tabel!! (Alhoewel? Waarom ben ik zo blij?? Dit is toch wiskunde, dus dat klopt vanzelfsprekend! Niks aparts aan de hand). De verwachtingswaarde voor 10 verschillenden. We beginnen nu met een serie van 10 random getallen met de kansen zoals in de tabel hierboven. Dat noemen we vector B0 Daarmee maken we door steeds met matrix M te vermenigvuldigen een serie vectoren B1, B2, B3, .... Hoe is het met de kans dat toestand T10 voor het eerst plaatsvindt bij een bepaalde B? Tel alle kansen van de kolom Bi op, en noem dat Pi. We hebben al gezien dat die kansen niet samen 1 zijn omdat er kansen op toestand T10 missen. 1 - Pi is dus precies alles wat er tot en met Bi "uit het systeem gelekt is", dus alles wat in T10 is gekomen. Maar dan is (1 - Pi) - (1 - Pi-1) dus de kans dat toestand T10 precies bij stap i wordt bereikt, namelijk hoeveel er in deze stap i extra in T10 terechtkomt. Dat geeft deze tabel: |
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
| Voor de verwachtingswaarde van
deze tabel (het gemiddeld aantal cijfers totdat T10 wordt
bereikt) geldt: E = 10 • {1 - P0} + 11 • {(1 - P1) - (1 - P0)} + 12 • {(1 - P2) - (1 - P1)} + 13 • {(1 - P3) - (1 - P2)} + .... = 10 - 10P0 + 11 - 11P1 - 11 + 11P0 + 12 - 12P2 - 12 + 12P1 + 13 - 13P3 - 13 + 13P2 + ... = 10 + P0 + P1 + P2 + P3 + ... = 10 + somB0 + somB1 + somB2 + somB3 + ... = 10 + som(B0) + som(MB0) + som(M2B0) + som (M3B0) + ... = 10 + som(B0 + MB0 + M2B0 + M3B0 + ...) = 10 + som( (I + M + M2 + M3 + ...) • B0 ) waarbij I de (9 × 9) eenheidsmatrix is. Daar in het rood staat gewoon een meetkundige rij voor de matrices M, M2 , M3 , .... De som daarvan is de matrix S = (I - M)-1 waarbij die ^-1 betekent: "de inverse matrix nemen". Dan is E = 10 + R • S • B0 waarbij R de rijvector (1 1 1 1 1 1 1 1 1 ) is, die ervoor zorgt dat de som wordt genomen. http://matrix.reshish.com/inverCalculation.php rest volgt.... |
||||||||||||||||||||||||||
|
© h.hofstede (h.hofstede@hogeland.nl) |
||||||||||||||||||||||||||
