Hoeveel getallen trekken?

[M.B.]

Ik heb een uniforme kansverdeling van de getallen 1,2...,100 dus elk getal in deze reeks treedt op met kans 1/100.

Mijn vraag is nu:

hoeveel random getallen uit deze verdeling moet ik trekken zodat ik met 95% zeker ben dat ik alle 100 getallen uit de reeks heb getrokken?

Het kan zijn dat als je 100 getallen trekt er twee of drie of meerdere keren hetzelfde getal bijzit, terwijl andere getallen niet een keer getrokken zullen worden.

Dus, vandaar mijn vraag.

Ik heb gedacht aan Tchebychev ongelijkheid, combinatoriek, ... maar ik zie het licht niet.

Alvast bedankt.

[EvilBro]

Stel je hebt een bak met 100 ballen. Hiervan zijn er k rood en de rest is blauw. Je wilt een rode bal trekken. Je trekt een bal en kijkt of het een rode is. Als dit zo is dan stop je. Als dit niet zo is dan gooi je de bal terug in de bak, hussel je de ballen en trek je een nieuwe bal. Hoeveel trekkingen verwacht je te doen?

[M.B.]

Al mijn 100 ballen zijn toch zogezegd rood?

Elk getal dat ik trek is een 'correct' getal. Het mag dat ik meerdere keren hezelfde getal trek, maar ik wil gewoon een bepaalde zekerheid (95% ofzo) dat ik alle getallen een keer gehad heb.

[EvilBro]

Al mijn 100 ballen zijn toch zogezegd rood?

Stel je hebt tweehonderd ballen: honderd rode ballen genummerd van 1 t/m 100 en honderd blauwe ballen van 1 t/m 100. Je stopt alle rode ballen in een bak en begin je je trekkingsproces. Elke keer als je een rode bal trekt vervang je deze door de blauwe met hetzelfde nummer. Als je een blauwe bal trekt dan leg je deze gewoon terug in de bak. Er komen dus steeds minder rode ballen in de bak (en steeds meer blauwe). Zie je nu hoe mijn vraag samenhangt met de vraag die jij probeert te beantwoorden. Dit geeft je overigens nog niet een betrouwbaarheidsinterval maar wel de verwachtingswaarde van het aantal trekkingen dat je moet doen.

[M.B.]

Ik zie het niet.

Ok, de eerste keer dat ik een getal trek is het een rode bal. Dat getal heb ik al getrokken dus telt al niet meer mee.

Zo een paar keer tot ik een eerste keer een getal trek dat ik al getrokken heb, dat is een blauwe bal dan. Deze leg ik terug vermits ik verschillende keren hetzelfde getal kan trekken.

Maar dan nog zie ik niet hoeveel keer je moet trekken om alle rode ballen een keer gehad te hebben.

Kans op een rode bal is 1/200 (uniforme trekking)

Als het een rode bal is, leg hem opzij. volgende kans op rood is dan 1/199.

maar hoe zeg ik dan dat "als hij blauw is, ik hem terugleg" : trekking met teruglegging of zoiets, combinatoriek?

[Rogier]

EvilBro bedoelt dat in het begin die blauwe ballen nog niet in de bak zitten, die leg je ernaast. Er zitten dus alleen 100 rode ballen in de bak. Telkens als je een rode pakt, vervang je die door een blauwe (dus het is trekken met terugleggen uit een bak van voortdurend 100 ballen, alleen voor een rode leg je een blauwe met hetzelfde nummer terug).

Rood/blauw is dus een manier om te 'markeren' of je een bepaalde bal al gehad hebt.

Hoeveel beurten heb je naar verwachting nodig om de eerste rode bal te pakken? En hoeveel daarna voor de tweede? En hoeveel daarna, enz.

[M.B.]

De eerste trekking is altijd een rode bal, er zitten nog geen blauwe ballen in. Dus 1 x voor de eerste rode bal.

De tweede trekking heb ik, om zeker te zijn dat ik een rode bal heb, minstens 2 trekking nodig (eventueel trek ik eerst de blauwe en pas daarna een rode)

Maar, dit is wel als ik de blauwe zou trekken, hem tijdelijk niet terugleg zodat ik zeker ben dat mijn volgende bal rood is.

Dus 2 trekkingen.

Voor de derde rode bal, er liggen nu 2 blauwe ballen in de bak, trek ik dan 3 keer om zeker te zijn.

Dus ik zou denken dat je 1+2+3+4+...+100 keer moet trekken om alle rode ballen minstens 1 keer te hebben gehad.

[Rogier]

De eerste trekking is altijd een rode bal, er zitten nog geen blauwe ballen in. Dus 1 x voor de eerste rode bal.

De tweede trekking heb ik, om zeker te zijn dat ik een rode bal heb, minstens 2 trekking nodig (eventueel trek ik eerst de blauwe en pas daarna een rode)

Je zou (weliswaar onwaarschijnlijk) 2x achter elkaar die ene blauwe bal kunnen pakken. Dus zodra er eenmaal een blauwe bal in zit is er geen minimum aantal trekkingen meer om zeker een rode te krijgen, je kunt in theorie willekeurig vaak achter elkaar steeds die blauwe trekken.

[M.B.]

Kan je dan ooit zekerheid hebben dat je alle rode ballen getrokken zult hebben, zonder oneindig aantal keer te moeten trekken?

Ik zie niet goed hoe je dit leidt tot "de verwachtingswaarde van het aantal trekkingen" (verwachting van wat: minstens 1 rode bal, 100 verschillende rode ballen?)

[EvilBro]

Stel je hebt een bak met 100 ballen. Hiervan zijn er k rood en de rest is blauw. Je wilt een rode bal trekken. Je trekt een bal en kijkt of het een rode is. Als dit zo is dan stop je. Als dit niet zo is dan gooi je de bal terug in de bak, hussel je de ballen en trek je een nieuwe bal. Hoeveel trekkingen verwacht je te doen?

Het verwachte aantal trekkingen gegeven een bak met k rode ballen en in totaal 100 ballen:

\(E_k = \sum_{n=1}^\infty n \cdot \frac{k}{100} \left(\frac{100 - k}{100}\right)^{n-1}\)

Dus het verwachte aantal trekkingen om elk getal een keer gezien te hebben:

\(E = \sum_{k=1}^{100} E_k\)

[Rogier]

Kan je dan ooit zekerheid hebben dat je alle rode ballen getrokken zult hebben, zonder oneindig aantal keer te moeten trekken?

Nee.

Naarmate N groter wordt, wordt de kans dat je na N trekkingen nog niet alle rode ballen minstens één keer gehad hebt, wel willekeurig klein. Maar nooit 0.