De verstrooide professor Edward Omey HUB - Stormstraat 2 1000 Brussel
[email protected]
1
Inleiding
In hun nota bestuderen Guido Herweyers en Ronald Rouseau (G. Herweyers en R. Rousseau, Een onverwacht resultaat bij trekken zonder terugleggen. Wisk. & Ond. 38, 236-239, 2012.) het volgende probleem. We beschikken over een zak met witte en zwarte bollen en bepalen de kans dat de k- de trekking een witte bol oplevert. In hun nota tonen de auteurs aan dat deze kans niet afhangt van de manier waarop - met of zonder - terugleggen dit trekken gebeurt. In deze nota bekijken we het probleem van een verstrooide professor die om binnen te raken in zijn huis 1 of 2 passsende sleutels moet vinden! We bekijken telkens de twee manieren van trekken.
2
Eenvoudig
Na een lange dag van werken komt een vermoeide professor ’s avonds laat in het donker thuis. In zijn broekzak bevinden zich 7 sleutels waarvan er slechts 1 zijn beveiligde voordeur kan openen. Omdat het donker is, moet de professor de sleutels in willekeurige volgorde uit zijn broekzak nemen. Hij kiest de sleutels 1 na 1 tot de voordeur open is.
2.1
Strategie 1: met terugleggen
Nadat hij een sleutel heeft geprobeerd en de sleutel blijkt niet te passen, dan steekt hij de sleutel terug bij de andere sleutels en kiest hij opnieuw blindelings een sleutel. Bij deze strategie is de kans op succes bij elke poging uiteraard gelijk aan 1=7. Stel nu X1 = het aantal pogingen om het huis binnen te raken. We vinden P (X = n) = P (eerst n 1 mislukkingen en dan 1 succes) en dus 6 P (X = n) = ( )n 7
1
1 ;n 7
1.
Het verwacht aantal pogingen E(X) om binnen te raken is E(X) = 7. Opmerkingen De kansverdeling (kv) van X noemt met een geometrische verdeling met parameter p = 1=7. Het is immers zo dat de kv weergegeven wordt door een geometrisch rij: P (X = n) = p(1 p)n 1 ; n 1, met p = 1=7.
1
Het gemiddelde bij een algemene geometrische verdeling is gelijk aan E(X) =
1 X
nP (X = n) = p
n=1
1 X
n(1
p)n
1
.
n=1
Om dit aan te tonen gebruiken we de volgende bekende reeksontwikkeling: 1 1
z
=
1 X
zn; 0
z < 1.
n=0
Door het nemen van de afgeleide naar z vinden we 1 (1 Met de keuze z = 1
z)2
1 X
nz n
1
.
n=1
p vinden we dat
E(X) = p
2.2
=
(1
1 p 1 = 2 = . 2 (1 p)) p p
Strategie 2: zonder terugleggen
Bij deze strategie gaat de professor als volgt te werk: nadat hij een sleutel uit de rechterzak heeft geprobeerd en de sleutel blijkt niet te passen, dan steekt hij deze sleutel weg in zijn linkerzak en daarna kiest hij een andere sleutel uit de rechterzak. We bekijken opnieuw X = het aantal pogingen tot succes. We vinden * P (X = 1) = P ( eerste keer goede keer ) = 1=7; * P (X = 2) = P ( eerst fout en dan correct ) = (6=7) (1=6) = 1=7; * P (X = 3) = P ( fout - fout - correct ) = (6=7) (5=6) (1=5) = 1=7; enz. * P (X = 6) = (6=7) (5=6) ::: (1=2) = 1=7; * P (X = 7) = 1 (6=7) = 1=7. Het verwacht aantal pogingen hier is E(X) = (1 + 2 + ::: + 7)=7 = 4. Opmerkingen Een andere werkwijze om de kv van X te bepalen bestaat erin 7 genummerde hokjes te tekenen. In deze hokjes moeten we 6 mislukkingen plaatsen en 1 succes. Het is duidelijk dat dit op 7 manieren (ofwel succes in vakje 1 ofwel in vakje 2 enz.) kan gebeuren en elke manier heeft evenveel kans. We vinden hier dus dat P ( succes in vakje i) = 1=7. De kv van X is de uniforme verdeling over de getallen f1; 2; 3; 4; 5; 6; 7g. Elke uitkomst heeft immers dezelfde kans nl. 1=7. In het algemeen heeft X een uniforme verdeling over de verschillende getallen fx1 ; x2 ; :::; xn g als elke uitkomst dezelfde kans 1=n heeft: P (X = xi ) =
2
1 ;1 n
i
n.
Het gemiddelde bij een uniforme verdeling is gelijk aan n X
n X
1 E(X) = xi P (X = xi ) = xi = n i=1 i=1
Pn
i=1
xi
n
= x,
dit is het gewone rekenkundig gemiddelde van de verschillende getallen.
3
Iets moeilijker
Om de deur van zijn streng beveiligd huis te openen, moet de professor in het donker 2 sloten openen met 2 verschillende maar gelijkaardige sleutels die in het donker niet van elkaar te onderscheiden zijn. In zijn broekzak bevinden zich nog steeds in totaal 7 sleutels.
3.1
Strategie 1: slechte sleutel terugleggen
Nadat hij een sleutel heeft geprobeerd en de sleutel blijkt niet te passen, dan steekt hij de sleutel terug bij de andere sleutels en kiest hij blindelings opnieuw een sleutel. Een sleutel die past wordt uiteraard in het slot gelaten. Bij deze strategie vinden we de eerste sleutel in een aantal beurten gelijk aan X1 waarbij X1 geometrisch verdeeld is met parameter p1 = 2=7. Er zijn immers 2 goede sleutels bij een totaal van 7 sleutels. Na het vinden van de eerste sleutel is het bijkomend aantal beurten X2 om de tweede sleutel te vinden geometrisch verdeeld met parameter p2 = 1=6. Omwille van het terugleggen zijn X1 en X2 onafhankelijk. Noem N = X1 + X2 het totaal aantal pogingen N om binnen het huis te raken. Voor n 2 vinden we P (N = n) als volgt:
P (N = n) =
n X1
P (X1 = k; X2 = n
k) =
k=1
n X1
P (X1 = k)P (X2 = n
k).
k=1
Deze laatste stap is geldig omdat X1 en X2 onafhankelijk zijn. We vinden P (N
= n) =
n X1 k=1
=
=
2 7
5 ( )k 7
n 1 1X 6 k=1
2 5 n ( ) 35 6
1
5 7 n X1 k=1
12
7
5 ( )n 6
k 1
6 ( )k 7
3
5 6 1
.
k 11
n 1
6 5 6
k+1
5 6
1
Met de bekende rekenregels volgt hieruit dat P (N
= n) = = =
2 5 n ( ) 35 6
11
(6=7)n 1 6=7
1
6 2 5 n 1 ( ) (1 ( )n 1 ) 5 6 7 12 7 P (X1 = n). P (X2 = n) 5 5
Het verwacht aantal pogingen tot hij zijn huis kan betreden is nu E(N ) = E(X1 ) + E(X2 ) = 7=2 + 6 = 9:5. Opmerkingen Twee toevalsvariabelen X en Y zijn onafhankelijk indien voor alle relevante uitkomsten x; y geldt dat P (X = x; Y = y) = P (X = x)P (Y = y). De variabelen zijn afhankelijk indien deze gelijkheid minstens één keer niet geldt. Bij een negatief binomiaal experiment, voeren we hetzelfde binair experiment (met dezelfde succeskans p) uit tot er precies 2 successen zijn. Het ogenblik N waarop dit gebeurt heeft de volgende kv: P (N
= n) = P (n 1 trekkingen met juist 1 succes, en daarna 1 succes) n 1 = (1 p)n 2 p p 1 =
(n
1)p2 (1
p)n
2
.
In dit geval kan N geschreven worden als N = X1 + X2 waarbij X1 en X2 onafhankelijk zijn en dezèlfde geometrische verdeling hebben met parameter p. In ons voorbeeld is N = X1 + X2 waarbij X1 en X2 onafhankelijk zijn, maar een verschillende geometrische verdeling hebben.
3.2
Strategie 2: zonder terugleggen
Nadat hij een sleutel uit de rechterzak heeft geprobeerd en de sleutel blijkt niet te passen, dan steekt hij deze sleutel weg in zijn linkerzak en kiest hij vervolgens een nieuwe sleutel uit de rechterzak. We bekijken hier twee werkwijzen.
4
3.2.1
Eerste werkwijze
We stellen N = aantal pogingen om het huis binnen te kunnen gaan. Dit is dus het aantal pogingen tot de 2 successen werden getrokken. Via bijvoorbeeld een boomdiagram vinden we (S = succes; M = mislukking) dat 2 7
1 1 = 6 21
P (N
=
2) = P (S S) =
P (N
=
3) = P ( S M S of M S S ) =
2 7
5 6
1 5 + 5 7
2 6
1 2 = 5 21
en in het algemeen dat P (N = i) =
i
1 21
,2
i
7.
Voor de verwachte waarde vinden we
E(N ) = 2 3.2.2
1 +3 21
2 + ::: + 7 21
6 16 = 21 3
Tweede werkwijze
Een andere werkwijze bestaat er in te werken met 7 genummerde hokjes. In deze hokjes moeten we 5 mislukkingen plaatsen en 2 successen. Het is duidelijk dat dit op 72 = 21 manieren kan gebeuren en elke manier heeft evenveel kans, nl. 1=21. We stellen N = het vakje dat het tweede succes bevat. Het is duidelijk dat N 2 f2; 3; 4; 5; 6; 7g. Om P (N = n) te bepalen gaan we als volgt te werk. Indien N = n dan bevindt zich één succes in de vakjes (1; 2; :::; n 1). Dit ene succes kan daar op n 1 manieren geplaatst worden. Vervolgens komt in het n de vakje een succes en in de resterende vakjes komen de overige mislukkingen. We vinden dus opnieuw P (N = n) =
4
n
1 21
;2
n
7.
Veralgemening
Stel dat de verstrooide professor of B "goede" sleutels beschikt en over A "slechte" sleutels. Om de deur ’s avonds te kunnen openen zijn er k "goede" sleutels nodig, waarbij k B. Om de deur te openen kan de professor terug werken volgens twee werkwijzen
4.1
Strategie 1: slechte sleutels terugleggen
In dit geval is het aantal pogingen X1 tot de eerste sleutel geometrisch verdeeld met parameter B=(A + B). Het bijkomend aantal pogingen X2 tot de tweede 5
goede sleutel is geometrisch verdeeld met parameter (B aantal pogingen voor de i de goede sleutel is
1)=(A + B
1). Het
B i+1 ). A+B i+1 In totaal zijn N = X1 + X2 + ::: + Xk pogingen nodig. De verwachte waarde van N is gelijk aan Xi s GEO(
E(N ) =
k X A+B i=1
B
Wanneer k = B vinden we
E(N ) = B +
B X i=1
4.2
k X i+1 A =k+ . i+1 B i+1 i=1 B X 1 A =B+A . B i+1 j j=1
Strategie 2: zonder terugleggen
Om de kv van N = het aantal pogingen te bepalen, gaan we als volgt te werk. We beschikken over A + B genummerde vakjes en verdelen de "goede" en "slechte" sleutels over deze vakjes. Het aantal verschillende manieren om dit te doen is gelijk aan A+B . B Voor n k bekijken we nu het aantal mogelijkheden waarbij er bij poging n precies k "goede" sleutels genomen werden. Het aantal mogelijkheden is gelijk aan: eerst kiezen we k 1 vakjes uit de n 1 vakjes en plaatsen daar een "goede" sleutel. Het aantal manieren waarop dit kan is gelijk aan n k
1 . 1
vervolgens plaatsen we een "goede" sleutel in vakje n; vervolgens verdelen we de resterende B k "goede" sleutels in de resterende A + B n vakjes. Dit kan op A+B n B k manieren. We besluiten dat P (N = n) =
n k
1 1
A+B n A+B = ;k B k B
Men kan aantonen dat E(N ) = k(1 +
6
A ) B+1
n
A+B
5
Tot slot
Stel dat de verstrooide professor of B "goede" sleutels beschikt en over A "slechte" sleutels. Om de deur ’s avonds te kunnen openen zijn er k "goede" sleutels nodig. Bij het selecteren van sleutels zonder terugleggen kunnen we de volgende toevalsvariabelen bekijken. 1) Wanneer we n sleutels kiezen, dan kunnen we tellen hoeveel "goede" sleutels er getrokken werden: X = het aantal goede sleutels bij n trekkingen. De kv van X is bekend en noemt men de hypergeometrische verdeling: B r
P (X = r) =
A n
r
=
A+B ;0 n
r
n; k
2) De variabele N telt het aantal pogingen dat nodig is tot we k goede sleutels hebben. We vonden P (N = n) =
n k
1 1
A+B n A+B = ;k B k B
n
A + B.
De kv van N noemt men de negatief hypergeometrische verdeling.
7
