Kans op minstens 1x precies twee dezelfde knikkers

Continue & discrete verdelingen, toevalsveranderlijken, betrouwbaarheidsintervallen, correlaties.
Plaats reactie
wband
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 11 aug 2016, 08:01

Kans op minstens 1x precies twee dezelfde knikkers

Bericht door wband » 11 aug 2016, 08:53

Ik heb een puzzel waar ik niet uit kom, wie er uit komt ben ik erg dankbaar:

Stel je hebt een vaas met M knikkers. Daaruit trek ik er n met terugleggen. Hoe groot is nu de kans dat ik minstens 1 knikker precies 2 keer trek? Dus niet minder of meer dan dubbel. Dus stel ik trek er 5 (n=5), dan voldoen de volgende trekkingen:

3, 3, 1, 5, 6
3, 3, 1, 4, 4 (zowel 3 als 4 worden precies twee keer getrokken)

Maar de volgende niet, omdat geen enkele knikker precies 2 keer is getrokken:

3, 3, 3, 1, 2 (3 komt meer dan, dus niet precies 2x voor)
1, 2, 3, 4, 5
4, 4, 4, 4, 1

Ik heb al een antwoord op een deelprobleem: de kans dat een specifieke knikker precies 2 keer voor komt. Dat kan je op twee verschillende manieren benaderen; van de grond af met Laplace, of via de binomiale verdeling.

Binomiale verdeling: de kans p dat je de specifieke knikker pakt is 1/M, en aangezien we terugleggen blijft deze kans gelijk gedurende de trekking, dus kun je:



De geldigheid van deze toepassing kan bewezen worden met Laplace, ik laat het bewijs hier nu achterwege (mocht iemand geinteresseerd zijn, laat het weten).

Maar nu wil ik weten wat deze kans is voor een willekeurige knikker.

Je zou dit kunnen benaderen m.b.v. de somregel, want het gaat hier om een 'of' situatie: je trekt knikker m1 precies 2 keer, of je trekt knikker m2 precies 2 keer, etc. Dan zou je simpelweg kunnen vermenigvuldigen met M, maar dat mag niet: de somregel eist dat de gebeurtenissen elkaar uitsluiten, en dat is niet het geval: je kunt in een trekking immers meerdere knikkers precies 2 keer trekken. Die gebeurtenissen zou je dan dubbel tellen.

Iemand heeft al eerder gesuggereerd om het alsvolgt te benaderen:

De kans dat je een specifieke knikker niet precies 2 keer trekt is:



De kans dat je een willekeurige knikker niet precies 2 keer trekt is (hypothese):



En dan kun je dit als laatste stap weer aftrekken van 1 om het uiteindelijke antwoord te krijgen, maar ik ben niet zeker van de bovenstaande hypothese. Hier wordt de vermenigvuldigingsregel toegepast. Dat mag in geval van een 'en' situatie, maar alleen als de ene kans de ander niet beinvloedt, en dat laatste ben ik nog niet over uit.

Heeft iemand hier antwoord op?

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door arie » 12 aug 2016, 15:37

Noem G(m,n) het aantal gunstige (=goede) trekkingen uit een vaas met m kleuren en met n beschikbare posities. Een gunstige trekking is een trekking die voldoet aan je eisen, dus een trekking waarbij ten minste van 1 kleur precies 2 posities die kleur hebben.

Je kans P(m,n) = het aantal gunstige trekkingen G(m,n) gedeeld door het totaal aantal mogelijke trekkingen T(m,n) uit een vaas met m kleuren en met n beschikbare posities (met terugleggen):



Het totaal aantal mogelijke trekkingen is



Het aantal gunstige trekkingen G(m,n) gaan we recursief definieren.
We maken een tabel waarin we in de rijen m uitzetten en in de kolomen n.

De eerste rij, als m=1, kunnen we zo invullen:
m=1 houdt in dat er 1 kleur in de vaas zit, we trekken deze ene kleur n keer, alleen als n=2 hebben we 1 gunstige trekking (namelijk precies 2 posities met die ene kleur), in alle andere gevallen is G(1,n) = 0: we trekken of 1 keer of meer dan 2 keer die ene kleur.

De eerste kolom, als n=1, kunnen we ook invullen:
als we slechts 1 positie beschikbaar hebben, kunnen er nooit precies 2 posities dezelfde kleur hebben: G(m,1) = altijd nul

De tweede kolom, als n=2, kunnen we ook invullen:
als we 2 posities hebben en m kleuren, dan kunnen die posities op m manieren dezelfde kleur krijgen. Hebben ze verschillende kleuren, dan voldoen ze niet aan onze eisen.

De tabel kunnen we nu dus al zo invullen:

Code: Selecteer alles

G(m,n)    n=1     n=2     n=3     n=4     n=5     n=6     n=7     n=8
m=1       0       1       0       0       0       0       0       0
m=2       0       2
m=3       0       3
m=4       0       4
m=5       0       5
m=6       0       6
m=7       0       7
m=8       0       8
Nu moeten we de overgebleven waarden nog vinden, dit doen we regel voor regel, en per regel van links naar rechts (dus in de leesrichting, alsof we een boek schrijven).

Stel we hebben n posities beschikbaar, en we hebben de tabel opgelost voor alle voorgaande (m-1) regels = (m-1) rijen.
Nu voegen we een nieuwe kleur m toe.
Noem i het aantal posities van de n beschikbare posities waarop die nieuwe kleur voorkomt.

Als i=2, dan hebben we altijd een gunstige uitkomst, alle (n-2) andere posities mogen elk van de overige (m-1) kleuren hebben: dit levert dit aantal mogelijke gunstige uitkomsten:



(precies 2 keer die nieuwe kleur kunnen we op (n over 2) manieren plaatsen, daarna hebben we nog (n-2) plaatsen beschikbaar, die we elk met de oude (m-1) kleuren op (m-1) manieren kunnen kleuren)

Als i ongelijk aan 2 is, dan draagt kleur m niet bij aan een gunstige uitkomst, en houden we nog (n-i) posities over, die we met (m-1) kleuren gunstig moeten kleuren.
Dit kan op G(m-1, n-i) manieren.

En dit moeten we doen voor i=0 t/m i=(n-2):
- als i=n voor n>2 is dit nooit een gunstige trekking
- als i=(n-1) en i ongelijk 2, dan is dit ook nooit een gunstige trekking.

Onze formule wordt dus:



Om G(m,n) te berekenen hebben we dus alleen de G-waarden uit de vorige regel nodig (t/m n).

Als we de tabel zo invullen, krijgen we:

Code: Selecteer alles

G(m,n)    n=1     n=2     n=3     n=4     n=5     n=6     n=7     n=8
m=1       0       1       0       0       0       0       0       0
m=2       0       2       6       6       20      30      42      56
m=3       0       3       18      54      150     540     1386    4116
m=4       0       4       36      180     720     3060    12852   48888
m=5       0       5       60      420     2300    12000   63420   321440
m=6       0       6       90      810     5700    36450   229950  1428000
m=7       0       7       126     1386    11970   91980   680022  4955076
m=8       0       8       168     2184    22400   202440  1729896 14464016
In jouw voorbeeld had je 6 kleuren en 5 posities.





dus




Nu hangt het er van af wat je verder nog wilt.
Ik verwacht wel een mogelijk snellere recursie per rij of per kolom (vaste m of vaste n), maar een gesloten formule waaruit direct de kans rolt zal ingewikkeld worden (of wellicht onmogelijk).

De getallen worden namelijk al snel heel groot:
G(10,10) = 9124200450
G(20,20) = 103898258360894821080791000
G(50,50) = 8881694006707988609289039078188895731091265209921248216498394987783310891602413341250
G(100,100) = 99999999987995248467250493412379675070927950744933210439424485713327812653767081
796881722966105072249028052249805600920542216200607926465504066922026136656249089675059258227
371397558743422809929175000

De kansen zijn afgerond:
P(10,10) = 0.9124200450000000000000000000
P(20,20) = 0.9908510051812631710127925873
P(50,50) = 0.9999898454757216275355912019
P(100,100) = 0.9999999998799524846725049341

wband
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 11 aug 2016, 08:01

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door wband » 14 aug 2016, 11:36

He Arie,

Hartelijk dank voor je tijd! Ik had een recursieve benadering nog niet overwogen, ik vermoed onbewust door het feit dat, in het praktische probleem dat ik probeer te benaderen, m erg groot is (een paar duizend), en ik me beperkte tot het zoeken naar een alomvattende/niet recursieve formule. Variabele n, overigens, is ergens binnen 2..5. Ik heb nog wel even gecheckt of je de som over i mag nemen, maar kwam snel tot de conclusie dat je nooit zowel precies x als y <> x kleur m hebt getrokken, dus de verzamelingen zijn gescheiden.

Ik ga eens met de tabel spelen. Ik laat je weten waar ik op uit kom.

PS: de omvang van het getal kan evt. worden aangepakt tussentijds door te delen door m^n, ofwel de kans te berekenen in plaats van de hoeveelheid mogelijkheden. Dit komt mogelijk ten koste van nauwkeurigheid, afhankelijk van de verhouding tussen de hoeveelheid gewenste en mogelijke uitkomsten, of de kans zelf.

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door arie » 14 aug 2016, 14:41

Voor kleine n is dit goed te doen.
Voor n=1 en n=2 is de oplossing triviaal (zie mijn eerdere post).

Voor grotere n is de recursie voor kolom n:




Voor n=5 levert dit:



ofwel



Voorbeeld: de berekening van m=8=k uit de 5 voorgaande waarden (zie tabel):






De gesloten formule van dergelijke relaties heeft de vorm:



in ons voorbeeld (n=5):



Met de eerste n waarden kunnen we nu c_1 t/m c_n oplossen.
Voor n=5 geeft dit het stelsel:







De oplossing van dit stelsel is:







waardoor we deze gesloten formule overhouden:



Voorbeeld:




Evenzo kom ik uit op (NOOT: lukt het je met bovenstaande om deze formules zelf te krijgen?):





en




wband
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 11 aug 2016, 08:01

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door wband » 15 aug 2016, 11:06

arie schreef:NOOT: lukt het je met bovenstaande om deze formules zelf te krijgen?
Dat lukt wel:

Voor n=3:
















Maar het voelt een beetje als een aap die een kunstje nadoet; gauss eliminatie herinner ik me nog wel, maar je hebt hierboven de recursieve definitie van G(m,n) gereduceerd naar een die alleen van de kolom, en daarna zelfs naar een gesloten formule. Dat kan ik nog niet helemaal volgen:

Ik mis even hoe je bij de eerste formule komt in je vorige post (1):
arie schreef:Voor grotere n is de recursie voor kolom n:

Verder weet ik niet op basis waarvan je mag stellen (2):
arie schreef:De gesloten formule van dergelijke relaties heeft de vorm:

Maar misschien moet ik dan toch even mijn handen uit de mouwen steken en mijn wiskunde opfrissen, ik heb al veel van je tijd besteed, en heb mijn initiele probleem opgelost. Ik ben er helemaal uitgekomen met de eerdere recursieve definitie van G(m,n). De tabel bevestigt (zoals al geconcludeerd in de openingspost) dat de somregel niet kan worden toegepast, en toont verder aan dat ook de hypothese niet geldig is. Echter, voor grote m, en kleine n, is het verschil verwaarloosbaar. Verder is dit verschil in die situaties, hoe klein al, waarschijnlijk te wijten aan gebrek aan nauwkeurigheid bij grote getallen.

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door arie » 15 aug 2016, 13:51

De recursieve formule volgt uit het principe van inclusie en exclusie,
zie bv https://en.wikipedia.org/wiki/Inclusion ... _principle
In het kort:
Je telt het aantal gunstige rijtjes door in elk gunstig rijtje met (m-1) kleuren de kleur op 1 positie te vervangen door een nieuwe kleur.
Daarna corrigeer je voor kleuren die dubbel voorkomen (die rijtjes heb je zojuist dubbel geteld),
daarna corrigeer je voor kleuren die driedubbel voorkomen (die rijtjes heb je eerst 3 keer geteld, en daarna 3 keer gecorrigeerd wegens dubbeltelling),
etc.

Het oplossen van recurrente betrekkingen vind je hier:
https://en.wikipedia.org/wiki/Recurrenc ... polynomial
De karakteristieke polynoom heeft in ons geval de bijzondere vorm



dwz, wortel lambda = 1 met multipliciteit n
De oplossing van de recursie vind je dan op die wiki pagina onder
"As a result of this theorem a homogeneous linear recurrence relation with constant coefficients can be solved in the following manner:"
waarbij we maar 1 wortel lambda hebben.
Doordat bovendien lambda = 1, vallen alle factoren lambda^n weg, en houden we over:




Wat betreft de benadering:
Als m heel groot is ten opzichte van n, dan is:
- de kans op een dubbele kleur heel klein,
- de kans op twee of meer dubbele kleuren nog veel kleiner (= te verwaarlozen), en
- de kans op drie- of meervoudig voorkomende kleuren ook veel kleiner (= te verwaarlozen).
Neem nu een kleur k.
De kans dat k 2 keer in je rijtje voorkomt is dus ongeveer (nC2) * (1/m)^2 * 1^(n-2)
Omdat er m kleuren zijn is de kans op een dubbele kleur dan



Merk op dat ook in alle oplossingen in mijn vorige post de coefficient van de hoogste macht van m, dat is m^(n-1) steeds (nC2) is. Voor grote m nadert G(m,n) steeds (nC2)*m^(n-1),
waardoor P(m,n) = G(m,n) / (m^n) bovenstaande formule nadert.

wband
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 11 aug 2016, 08:01

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door wband » 23 aug 2016, 16:05

He Arie,

Ik kan je redenering niet helemaal volgen:
arie schreef:Je telt het aantal gunstige rijtjes door in elk gunstig rijtje met (m-1) kleuren de kleur op 1 positie te vervangen door een nieuwe kleur.
Stel ik ben op zoek naar G(4,3) = , m=4 en n=3. Dan is het volgende rijtje gunstig voor G(3,3) = , dus m=3 en n=3:

Code: Selecteer alles

1 1 3
Als ik dan de kleur op 1 positie vervang door een nieuwe kleur 4, krijg ik:

Code: Selecteer alles

4 1 3
Dat is geen gunstig rijtje. Ik moet iets triviaals niet goed begrepen hebben.. (je uitkomsten kloppen als een bus).

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door arie » 27 aug 2016, 13:29

We moeten inderdaad wel in de oplossingsruimte blijven, daarin zoeken we ook de recursie.
Als we de kleur van positie 1 veranderen, veranderen we ook diezelfde kleur op andere posities.

Voorbeeld: rijlengte=3, kleuren=4:

Code: Selecteer alles

1e positie=dubbelkleur: 112
                        113
                        114

                        121
                        131
                        141

1e positie=enkelkleur:  122
                        133
                        144
Hierboven alleen de rijtjes die beginnen met kleur 1, de complete tabel (met alle 4 de kleuren als beginkleur) is 4 keer zo lang.

Als we hierin achtereenvolgens de eerste, tweede en derde positie veranderen, krijgen we:

Code: Selecteer alles

1e positie=dubbelkleur: 112   kk2   kk2   11k
                        113   kk3   kk3   11k
                        114   kk4   kk4   11k

                        121   k2k   1k1   k2k
                        131   k3k   1k1   k3k
                        141   k4k   1k1   k4k

1e positie=enkelkleur:  122   k22   1kk   1kk
                        133   k33   1kk   1kk
                        144   k44   1kk   1kk
Kijk vervolgens hoeveel rijtjes je van elk type hebt, en wat je nodig hebt voor 5 kleuren, corrigeer voor het teveel of te weinig (weer binnen de bekende oplossingen).


Maar we hebben deze zware machinerie voor n=3 posities eigenlijk helemaal niet nodig:
Kijk weer naar de eerste tabel in deze post (maar nu in het algemeen met k kleuren):
Als de eerste kleur k1 is en dubbel voorkomt, hebben we deze 2 structuren:
[1] "k1 k1 k2", voor k1 hebben we k mogelijkheden, voor k2 hebben we (k-1) mogelijkheden, in totaal dus k*(k-1) mogelijkheden
[2] "k1 k2 k1", voor k1 hebben we k mogelijkheden, voor k2 hebben we (k-1) mogelijkheden, in totaal dus k*(k-1) mogelijkheden
Als k1 enkelvoudig voorkomt, hebben we alleen deze mogelijkheid:
[3] "k1 k2 k2", voor k1 hebben we k mogelijkheden, voor k2 hebben we (k-1) mogelijkheden, in totaal dus k*(k-1) mogelijkheden
Tellen we deze 3 bij elkaar op, dan vinden we
G(k,3) = 3*k*(k-1) = 3k^2 - 3k
zoals we hiervoor gevonden hadden.

Dit soort problemen, met nette en gestructureerde aantallen, heeft doorgaans ook een nette recursieve formule. In dit geval heb ik ze (quick and dirty, zonder formeel bewijs) afgeleid uit de tabel die we in eerste instantie bepaald en berekend hadden.

wband
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 11 aug 2016, 08:01

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door wband » 29 aug 2016, 15:21

He Arie,

Voor n=3 is de recursie inderdaad overkill omdat we ons daar moeten beperken tot 1 paar. Ik zou zelf overigens zo hebben geredeneerd: je kunt voor k kleuren, de dubbele kleur k1 op 3 over 2 plaatsen, en voor k-1 kleuren k2 plaatsen op de overgebleven plek, dus (3 over 2)*k*(k-1)=3*k^2-3*k.

Ik probeerde je toepassing van het inclusion-exclusion principe te begrijpen, en om het te kunnen visualiseren heb ik kleine waarde gekozen voor m, n. Dat is nog niet helemaal gelukt, zelfs niet met je toelichting, maar ik zal er nog een keer over nadenken voor ik je er weer mee lastig val.

Wat ik er wel met succes door heb bereikt is waar ik in mijn openingspost ben gestopt voor de somregel, verder te gaan m.b.v. het inclusie-exclusie principe:

Voor precies 2 keer een specifieke kleur zijn het aantal mogelijkheden:



Stel dat ik de mogelijkheden voor alle kleuren bij elkaar optel (bovenstaande vermenigvuldig met m), tel ik er een aantal dubbel. Voor m=5, en n=5, bijvoorbeeld, komt 1122x zowel voor in de verzameling voor kleur k1 als k2.

Het aantal dubbelen kan alsvolgt worden geteld (de laatste 2! ter correctie van de permutaties van de kleuren k1 en k2):



Ofwel, voor de eerste kleur hebben we de keuze uit m kleuren, die we op n over 2 manieren kunnen plaatsen. Op de overige n-2 plaatsen, kunnen voor de tweede kleur uit m-1 kleuren kiezen, die we op n-2 over 2 manieren kunnen plaatsen.

In het algemeen, voor enkelen (i=0), dubbelen (i=1), driedubbelen (i=2), etc.



En:



Dus:



Dan, per inclusie-exclusie, is het aantal rijtjes met minstens 1 kleur die precies op 2 posities voorkomt:


wband
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 11 aug 2016, 08:01

Re: Kans op minstens 1x precies twee dezelfde knikkers

Bericht door wband » 31 aug 2016, 11:42

Ik heb helaas een vergissing gemaakt in de vorige post, maar kan hem niet meer bewerken (er zal wel een timeout op staan, aangezien ik dit eerder wel kon), bij deze dan maar zo:

...
In het algemeen, voor enkelen (i=1), dubbelen (i=2), driedubbelen (i=3), etc.



En:



Dus:



Dan, per inclusie-exclusie, is het aantal rijtjes met minstens 1 kleur die precies op 2 posities voorkomt:


Plaats reactie