Het matching probleem

Neem 4 kaarten met erop het nummer 1,2,3 en 4. Schud ze en leg ze op tafel terwijl je 1,2 3 en 4 zegt. Hoe groot is de kans dat  het nummer op de kaart overeen komt met het getal dat je zegt? 

Er zijn 4!= 24 mogelijke rangschikkingen; Noteer met P(i,4) de kans dat er i matches zijn bij 4 geschudde kaarten. Dan is 

  •  P(0,4)=\frac{9}{24}=0,375
  •  P(1,4)=\frac{8}{24}=0,333...
  •  P(2,4)=\frac{6}{24}=0,25
  •  P(4,4)=\frac{1}{24}=0,41666...

Het is duidelijk dat P(3,4) = 0 want als er 3 juist zijn moetje vierde automatisch ook juist zijn. Er bestaat een algemeen formule om de kans te berekenen op m matches in een rij van n geschudde kaarten:

    \[P(m,n)=\frac{1}{m!}\Big( \frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}...+\frac{(-1)^{n-m}}{(n-m)!}\Big)\]

De kans op 0 matches komt overeen met de formule voor derangements. De kans op minstens 1 overeenkomst is  62,5%

Dit probleem werd voor het eerst bestudeerd door de Franse wiskundige Pierre Rémond de Montfort in zijn ‘Essay d’Analyse sur les Jeux du Hazard’ uit 1708.

Montfort voerde het experiment uit met 13 kaarten en noemde het spel Treize.

Kansen en matrices

Een cavia bevindt zich in kamer 2. Ze kan deze kamer verlaten naar kamer 3,1 of 5 en dit met even grote waarschijnlijkheid. Hoe groot is de kans dat de cavia zich na 4 verplaatsingen in kamer 5 bevindt?

Noteer met a,b,c,d,e de kans dat de cavia zich op een zeker moment   in kamer 1,2,3,4,5 bevindt. Met a_i,b_i,c_i,d_i,e_i noteren we de kans dat het beestje zich, na i verplaatsingen, in kamer 1,2,3,4,5 bevindt. 

Dan is bijvoorbeeld a_1=0*a+\frac{1}{3}*b+\frac{1}{3}*c+\frac{1}{3}*d+\frac{1}{3}*e. We kunnen voor b_1,c_1,d_1,e_1 gelijkaardige formules vinden. Het is makkelijker die gegevens in een matrix M te steken die de overgang regelt van a,b,c,d,e naar a_1,b_1,c_1,d_1,e_1. De overgang wordt geregeld door A_1=M*A, hierbij is A=(a,b,c,d,e)^t ,A_1=(a_1,b_1,c_1,d_1,e_1)^t en 

    \[M= \begin{pmatrix}0&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\frac{1}{4}&0&\frac{1}{3}&0&\frac{1}{3}\\\frac{1}{4}&\frac{1}{3}&0&\frac{1}{3}&0\\\frac{1}{4}&0&\frac{1}{3}&0&\frac{1}{3}\\\frac{1}{4}&\frac{1}{3}&0&\frac{1}{3}&0\end{pmatrix}\]

Het is duidelijk dat bij de vierde verplaatsing A_4=M^4*A.

Berekening met een rekentoestel geeft:

    \[A_4=\begin{pmatrix}0,20987654\\0,21219136\\0,11342593\\0,21219136\\0,05555556\end{pmatrix}\]

Er is dus ongeveer 5,56% kans dat de cavia zich na 4 verplaatsingen in kamer 5 zit.

Technieken bij kansrekening

We onderzoeken 3 types oefeningen van kansrekening, gebaseerd op de manier waarop we ze benaderen.

  • Door te tellen. Neem bijvoorbeeld een zak met 16 knikkers , 4 blauwe en 12 groene. Je neemt er twee tegelijkertijd. Wat is de kans dat ze allebei blauw zijn? We gebruiken de formule van Laplace en we zoeken eerst het aantal mogelijkheden om 2 knikkers te nemen: C(16,2), het aantal combinaties van 2 elementen uit 16. Dan tellen we het aantal gunstige mogelijkheden: C(4,2). Besluit, na vereenvoudiging :

        \[P(\text{ 2 keer blauw} )= \dfrac{1}{20}\]

  • Meetkundige benadering. Neem een getal tussen 1 en 4 en een tweede getal tussen 2 en 6. Bereken de kans dat de som van die twee getallen groter is dan 5.Alle mogelijkheden om die 2 getallen te nemen komen overeen met de punten in de rechthoek ABCD.  De rechte Ef heeft vergelijking x+y=5. De gunstige mogelijkheden zijn de punten in de veelhoek EBDCF. De kansen kunnen nu berekend worden door de oppervlakten te delen. Nu is E(1,4) en F(3,2), dus we vinden

        \[P(x+y>5)=\dfrac{5}{6}\]

  • Kansen bereken via algebra. Jan en Piet spelen een spel met twee dobbelstenen. Ze gooien om de beurt en wie het eerst dubbel 1 gooit, die wint. Jan mag beginnen. Hoe groot is de kans dat Jan wint?Noteer de winstkansen van Jan en Piet respectievelijk door x en y. Dan weten we al zeker dat x+y=1. De kans dat Jan wint bij de eerste worp is \dfrac{1}{36}. De kans dat Piet bij zijn eerste worp wint is \dfrac{35}{36}*\dfrac{1}{36},  want eerst moet Jan verliezen en dan moet hij winnen. De kans dat Jan wint bij zijn tweede worp is \dfrac{1}{36}*\Big(\dfrac{35}{35}\Big)^2 . De kans dat Piet  wint bij zijn tweede worp is \dfrac{1}{36}*\Big(\dfrac{35}{35}\Big)^3. Je kan zo verder gaan en via de som van de termen van een meetkundige reeks het gewenste resultaat vinden, maar je kan ook opmerken dat de kans dat Piet wint altijd de kans is dat Jan wint vermenigvuldigd met \dfrac{35}{36}, dus y=\dfrac{35}{36}*x. Je krijgt een stelsel met 2 vergelijkingen en 2 onbekenden, dat als resultaat geeft dat x=\dfrac{36}{71}

Hoger Lager

Men neemt de 10 speelkaarten van de aas tot en met de tien van een bepaalde kleur. De speler zet een bepaald bedrag in. Daarna worden de kaarten geschud en de speler legt ze één na één met de beeldzijde op tafel. Telkens als de neergelegde kaart een hogere waarde heeft dan alle voorgaande kaarten, wint de speler een vast bedrag. Bereken de kans op winst bij de k-de kaart en wat is de gemiddelde winst per spel?

Veronderstel dat het spel gespeeld wordt met zelfgemaakte kaartjes die genummerd zijn van 1 to en met n. De kans op succes met het k-de kaartje noteren we met p_k.

Om deze kans te berekenen, zoeken we eerst het aantal manieren waarop de eerste k kaarten kunnen worden neergelegd. Dit is gelijk aanzet aantal k-variaties van n , genoteerd met V(n,k). We weten dat

    \[V(n,k)=\dfrac{n!}{(n-k)!}\]

Daarna berekenen we het aantal mogelijkheden waarbij de k-de kaart succes geeft. Dit hangt af van de waarde w_k van de k-de kaart. Immers:

  • Als w_k<k, dan is het onmogelijk dat de k-de kaart hoger is dan alle vorige kaarten.
  • Als w_k=k, dan win je als de vorige k-1 kaarten de nummers 1 tot en met k-1 zijn. Zo zijn er (k-1)! mogelijkheden.
  • Als w_k=k+1, dan heb je succes als de vorige k-1 kaarten een nummer hebben van 1 tot en met k. Hiervan zijn er V(k,k-1) mogelijkheden.
  • We kunnen zo verder werken en vinden dat als w_k=n er V(n-1,k-1) winstmogelijkheden zijn.

Het totaal aantal gunstige mogelijkheden is dan V(k-1,k-1)+V(k,k-1)+...+V(n-1,k-1). Via inductie kan men aantonen dat deze som gelijk is aan

    \[\dfrac{n!}{k(n-k)!}\]

Het is tenslotte niet moeilijk om de kans op succes met de k-de kaart uit te rekenen. Gebruik makend van de formule van Laplace vinden we

    \[p_k=\dfrac{1}{k}\]

We merken onmiddellijk op dat dit resultaat totaal niet afhangt van het aantal kaarten waarmee het spel gespeeld wordt. Stel nu even dat je bij winst bij de k-de kaart telkens een bedrag b krijgt.  Als X de winst is per spelletje  met n kaarten, dan is de gemiddelde winst gegeven door

    \[E(X)=\sum_{k=1}^{k=n}b.\dfrac{1}{k}\]

Bij een uitkering van 5 Euro per gewonnen kaart, vind je :

n=5   E(X)=11,4
n=10   E(X)=11,6
n=15   E(X)=16,6
n=20   E(X)=18

 

 

Kansen op het schaakbord.

Kies 2 vakjes op een schaakbord. Wat is de kans dat die twee vakjes 1 punt gemeen hebben?

  • Het aantal mogelijkheden om 2 vakjes te kiezen op een nxn bord is n^2 \choose 2 =\frac{n^2(n^2-1)}{2}.
  • Elk vakje in de hoek heeft 1 geschikte buur ( groen). Dus zo heb je al 4 mogelijkheden.
  • De vakjes op de rand, die niet in de hoeken liggen, hebben 2 geschikte buren(blauw). Er zijn 4(n – 2) dergelijke vakjes op de rand, dus heb je 2.4(n-2) gunstige mogelijkheden.
  • De inwendige vakjes hebben 4 geschikte buren ( geel). Er zijn (n-2)^2 dergelijke vakjes, dus 4(n-2)^2 gunstige mogelijkheden.
  • In het totaal zijn er 4+8(n-2)+4(n-2)^2=4n^2-8n+4 gunstige mogelijkheden. Maar die zijn dubbel geteld!
  • De kans dat er twee vakjes juist 1 punt gemeen hebben is

        \[\frac{4(n^2-2n+1)}{n^4-n^2}\]

  • Voor een  8×8 bord geeft dit ongeveer 4,8%.