Knikkers uit vaas trekken: alleen rode terugleggen

[Verwijderd]

Tijdens het hobbyen aan een computer programmaatje, ben ik op een probleem gestuit dat als volgt kan worden beschreven.

In een vaas zitten een zeker aantal rode en witte knikkers. Telkens trekken we één knikker uit de vaas; is de knikker rood dan doen we hem terug in de vaas en is de knikker wit dan leggen we hem apart. Hoeveel trekkingen zijn minstens nodig om een redelijke kans te krijgen, het experiment met een gewenst aantal witte knikkers af te sluiten?

Dit probleem heb ik opgedeeld in 3 delen:

Deel 1
X is de kans dat we een witte knikker trekken na k (mislukte) trekkingen (met elk een kans p op een witte knikker). De stochast X is geometrisch verdeeld; daarom geldt:

P(X = k) = (1 - p)[sup](k - 1)[/sup] p (voor k = 1, 2, . . .)

Deel 2
Het minimaal aantal trekkingen n om een kans van Y te krijgen om 1 witte knikker te trekken is

 n
 Σ  P(X = k) ≥ Y 
k=1

Okee, dit is niet precies de formule om n uit te rekenen, praktisch genomen, komt dit neer op doorgaan met kansen P bij elkaar optellen totdat Y de gewenste kans heeft Bijvoorbeeld: 4 witte knikkers en 4 rode knikkers: p = 0.5 en we willen minstens 95% kans hebben om een witte knikker te pakken. We moeten dus 5 maal een knikker trekken, want pas bij n = 5 geldt Y = 0.96875. Bij 4 poging is Y slechts 0.9375. Voor mijn programma is deze methode voorlopig efficiënt genoeg.

Deel 3
Nadat een witte knikker is getrokken willen we doorgaan totdat we nóg een witte knikker hebben. Daartoe moeten we de p aanpassen omdat er nu minder witte knikkers in de vaas zitten, en dus de kans kleiner is geworden om nog een witte knikker te pakken. In het voorbeeld is p nu dus ongeveer 3/7=0.429. We willen weer minstens 95% kans hebben om de volgende witte knikker pakken, en nu moeten we dus minstens n = 6 maal proberen, want pas bij n = 6 geldt dat Y = 0.96518 (Bij 5 pogingen is de kans slechts 93.907%.)

---

En dan nu mijn vraag: Mogen we nu zeggen dat als we 0.96875 * 0.96518 = 93.5% kans op het trekken van twee witte knikkers willen hebben, dat we minstens 11 trekkingen moeten doen?

---

Zo nee, dan wil ik graag ook een uitleg waarom ik dat zo niet mag stellen. (Als het even kan )

[ Voor 1% gewijzigd door Verwijderd op 19-02-2009 00:49 . Reden: inconsistenties weggeëdit ]

[NMe]

Ik denk dat je topic meer kans maakt in Wetenschap & Levensbeschouwing.

SE&A >> W&L

[Rannasha]

Verwijderd schreef op donderdag 19 februari 2009 @ 00:35:

---

En dan nu mijn vraag: Mogen we nu zeggen dat als we 0.96875 * 0.96518 = 93.5% kans op het trekken van twee witte knikkers willen hebben, dat we minstens 11 trekkingen moeten doen?

---

Ja en nee. Je rekent nu de kans uit dat knikker 1, 2, 3, 4 of 5 wit is en dat daarna binnen 6 trekkingen weer een witte knikker valt. Een situatie waarbij knikker 10 de eerste witte is en knikker 11 de tweede is hierin niet meegenomen bijvoorbeeld. De werkelijke kans op het trekken van 2 witte knikkers na 11 trekkingen zal groter zijn dan 93.5%. En daarom is jouw uitspraak dus eigenlijk gewoon waar: Om 93.5% kans te behalen, zijn 11 of meer trekkingen zeker voldoende.

[Verwijderd]

Da's een snel antwoord! Bedankt!

edit: inderdaad, het lijkt erop dat je gelijk hebt. Ik heb een test programmaatje in elkaar geflanst dat het beschreven experiment simuleert. Als je maximaal 11 trekkingen uitvoert, is de kans dat je 2 witte knikkers trekt ruim 98%—en niet 93.5%.

Back to the drawing board dan maar.

[ Voor 142% gewijzigd door Verwijderd op 19-02-2009 20:43 . Reden: eindelijk een fatsoenlijk antwoord geformuleerd :) ]

[Dido]

Ooh, knikkers en vazen! En dan zie ik hem pas na 2 dagen

Om te beginnen: ik mis een paar randvoorwaarden in je startpost. Zo staat er niets over de hoeveelheid rode en witte knikkers. Als er maar 1 witte knikker is, is de kans dat je een tweede trekt 0. Als je 100 witte knikkers hebt, maar een miljoen rode, wordt de kans op witte knikkers ook een stuk kleiner.

In je rekenvoorbeeld geef je een eenvoudige situatie, maar dit soort randvoorwaarden zijn altijd handig om eventuele formules te controleren

Dan je vraagstelling. Als ik het goed begrijp wil je weten hoeveel trekkingen er nodig zijn om minimaal een kans P te hebben op N witte ballen, gegeven dat er N_rood en N_wit ballen aanwezig zijn.

In je voorbeeld ga je uit van N=2, maar het is natuurlijk veel leuker om te kijken naar een generieke oplossing

To be continued...

[Mx. Alba]

Interessant vraagstuk inderdaad.

Stel, N_wit is het aantal witte knikkers aan het begin, en N_rood is het aantal rode. N_wit-uit is het aantal witte knikkers dat je er al uit gepakt hebt, en N_wit-eind is het aantal witte knikkers waar je mee wilt eindigen.

P_wit is de kans om een witte te pakken, en P_rood de kans om een rode te pakken, en wat je wilt berekenen is P_klaar, de kans dat je na een X aantal keer graaien klaar bent.

Generiek kan je zeggen dat P_wit = ( N_wit - N_wit-uit ) / ( N_rood + N_wit - N_wit-uit )

P_rood is natuurlijk 1 - P_wit

Het probleem is nu, hoe hoog is N_wit-uit bij een bepaald aantal keer graaien? Daar moet je ook weer een kansberekening op loslaten.

Al met al kom je uit op een recursieve functie in de vorm van:

N_wit-uit(X) = P_wit(X) + N_wit-uit(X-1)

Hiermee bereken je het te verwachten gemiddeld aantal gevonden witte knikkers na X keer graaien.

Daarop moet je dan nog een standaarddeviatie ofzo op loslaten om de kans uit te rekenen dat je na die X keer graaien N witte knikkers hebt gegraaid...

Grrrr, mijn kansberekening is nogal roestig

[ Voor 14% gewijzigd door Mx. Alba op 23-02-2009 11:06 ]

[Verwijderd]

Na een beetje verder te hebben geploeterd, ben ik erachter gekomen dat het probleem iets anders in elkaar zit dan ik in eerste instantie dacht. In plaats van dat we met een vaas met witte én rode knikkers beginnen, moeten we eigenlijk beginnen met een vaas met alleen maar witte knikkers.

Telkens trekken we één knikker uit de vaas; is die knikker wit leggen we hem apart en doen we een rode knikker in de vaas. (Het totaal aantal knikkers in de vaas blijft dus gelijk.) Wanneer we een rode knikker trekken, doen we hem terug in de vaas. We gaan door totdat alle witte knikkers in de vaas zijn vervangen door een rode.

edit:
Of totdat we n witte knikkers hebben, om het meer generiek te houden

Het principe dat als een witte knikker is getrokken de kans op een witte kleiner wordt, is dus nog steeds van kracht. Alleen de manier waarop de kans wijzigt bij het trekken van een witte knikker is veranderd ten opzichte van mijn originele experiment.

In het probleem voor mijn computer programma komen bijna alleen maar vazen voor met 20, 30 of 40 witte knikkers in het begin. Op dit moment ben ik een simulatie met 40 knikkers aan het uitvoeren en ik zal straks mijn bevindingen posten.

[ Voor 3% gewijzigd door Verwijderd op 24-02-2009 00:19 ]

[Dido]

Ah, leuk Dat verandert e.e.a. inderdaad. In feite is de vraag dus hoe lang het duurt voordat je iedere bal minstens 1 keer getrokken hebt (het vervangen door een rode bal is hetzelfde als de bal zelf teruggooien en alleen de eerste keer dat je hem trekt tellen. Moet je wel alle ballen nummeren).

Oftewel: hoe vaak moet ik met een N-kantige dobbelsteen gooien om een kans van P te hebben dat ik alle uitkomsten een keer gehad heb?

[Verwijderd]

Ja, Dido, ik denk dat je met jou dobbelsteen-beschrijving hetzelfde bedoelt als ik met mijn vazen en knikkers. Ik zal eens kijken wat ik in de schoolboeken van vroeger daarover kan vinden. (In het geval van mijn originele experiment was dat 0,0—misschien dat mijn hernieuwde kijk op het probleem wel wat oplevert.)

Hieronder een grafiek van de uitvoer van het programma dat het experiment simuleert. We beginnen met een vaas met 40 witte knikkers. Telkens trekken we één knikker uit de vaas; is die knikker wit leggen we hem apart en doen we een rode knikker in de vaas. Wanneer we een rode knikker trekken, doen we hem terug in de vaas. We gaan door totdat alle witte knikkers in de vaas zijn vervangen door een rode. We houden bij hoeveel trekkingen er nodig zijn om alle witte knikkers uit de vaas te krijgen. Het experiment is 100000 maal herhaald.

Ik kan geen svg hotlinken.

Dan maar png:


Het progje is ook te bekijken.

[ Voor 56% gewijzigd door Verwijderd op 23-02-2009 19:27 . Reden: simulatie + grafiek toegevoegd ]

[aap]

Dido schreef op maandag 23 februari 2009 @ 16:47:
Oftewel: hoe vaak moet ik met een N-kantige dobbelsteen gooien om een kans van P te hebben dat ik alle uitkomsten een keer gehad heb?

Is de oplossing dan niet redelijk eenvoudig?

Stel we willen weten hoe vaak je gemiddeld met een normale dobbelsteen moet gooien voordat je alle cijfers 1-6 minstens 1 maal geworpen hebt. De eerste worp is altijd raak. Voor de tweede hebben we een kans van 1 op 6 dat we het cijfer werpen dat we al hadden, en 5 op 6 dat het goed gaat. Gemiddeld 6/5 worpen nodig om het tweede cijfer te gooien (je kunt dit ook afleiden door de kansboom te tekenen en m.b.v. een reeks uit te rekenen). Voor de derde 6/4 etc.
De eindoplossing is dan 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 is 14,7 worpen.

edit:
Voor het voorbeeld van 40 knikkers is de uitkomst 40/40 + 40/39 + ... 40/1 = 171,1. Wat op het oog goed lijkt overeen te komen met de grafiek hierboven.

[ Voor 8% gewijzigd door aap op 25-02-2009 00:32 ]

[Mx. Alba]

aap schreef op woensdag 25 februari 2009 @ 00:24:
De eindoplossing is dan 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 is 14,7 worpen.

edit:
Voor het voorbeeld van 40 knikkers is de uitkomst 40/40 + 40/39 + ... 40/1 = 171,1. Wat op het oog goed lijkt overeen te komen met de grafiek hierboven.

Klopt, maar dan heb je slechts het gemiddelde berekend.

Hoe bereken je nu de kans dat je met 6 keer gooien al alle 6 de kanten van de dobbelsteen hebt gehad? Dat is nog simpel want dat is (¹/₆)⁶. Maar wat is de formule waar de kans P dat je na N keer trekken X verschillende knikkers uit de vaas met Y knikkers trekt uit komt rollen?

[aap]

Mx. Alba schreef op woensdag 25 februari 2009 @ 09:05:
[...]


Klopt, maar dan heb je slechts het gemiddelde berekend.

Hoe bereken je nu de kans dat je met 6 keer gooien al alle 6 de kanten van de dobbelsteen hebt gehad? Dat is nog simpel want dat is (¹/₆)⁶. Maar wat is de formule waar de kans P dat je na N keer trekken X verschillende knikkers uit de vaas met Y knikkers trekt uit komt rollen?

Dat is minder eenvoudig. (Ik werk het even uit voor de dobbelsteen, zodat de getallen hanteerbaarder blijven.) De kans dat je in N keren alle cijfers geworpen hebt is:

(6/6) * (1/6)ⁱ*(5/6) * (2/6)^j*4/6 * (3/6)^k*3/6 * (4/6)^l*2/6 * (5/6)^m*1/6

en dan gesommeerd over alle combinaties van i, j, k, l en m waarvoor geldt dat i + j + k + l + m = N - 6 (en i, j, k, l, m >= 0)

Hier kan vast een analytische oplossing voor gevonden worden, maar ik heb die wiskunde niet meer zo paraat. Een computerprogramma dat bovenstaande formule implementeert geeft het volgende resultaat:




Merk overigens op dat de "simpele" oplossing voor N = 6 die jij noemt niet klopt, want dat moet (6/6)*(5/6)*(4/6)*(3/6)*(2/6)*(1/6) zijn, tenzij je eist dat je de cijfers in een specifieke volgorde werpt.

[ Voor 7% gewijzigd door aap op 25-02-2009 11:16 ]

[Mx. Alba]

aap schreef op woensdag 25 februari 2009 @ 10:57:
Merk overigens op dat de "simpele" oplossing voor N = 6 die jij noemt niet klopt, want dat moet (6/6)*(5/6)*(4/6)*(3/6)*(2/6)*(1/6) zijn, tenzij je eist dat je de cijfers in een specifieke volgorde werpt.

.... * Mx. Alba slaat zichzelf voor zijn kop. Bewijs dat ook mijn wiskunde verre van paraat is

[Verwijderd]

Okee, ik ben inmiddels weer een stapje verder gekomen. In een beschonken toestand creatieve bui heb ik maar voor de grap de dobbelsteen-versie (Dido, bedankt!) van het probleem letterlijk in google gestopt, en voilá hit 4: een middelbare-school-scholier met een vraag over een probleem dat erg veel op het mijne lijkt (6x met een dobbelsteen werpen, wat is de kans dat je slechts 4 kanten van de dobbelsteen boven ziet komen). De uitleg die bij die vraagstelling stond, geeft een flinke duw in de goede richting om het raadsel op te lossen: Markov-ketens. Mijn hoofd duizelt nog een beetje met wat je volgens de Engelse versie van het artikel allemaal met Markov-ketens kunt doen.

Het lijkt er trouwens op dat aap gelijk had met zijn formule. Als ik die Markov zijn materie wat beter begrijp zal ik een uitgewerkt voorbeeld van mijn probleem posten.