Seuraa 
Viestejä3
Liittynyt3.4.2018

Tervehdys palstan matikkaneroille! Osaisikohan joku hieman neuvoa todennäköisyysongelman kanssa?

Kyseessä on ymmärtääkseni nk. kuponginkerääjän ongelma (https://en.wikipedia.org/wiki/Coupon_collector's_problem) ja sen muunnokset. Lyhyesti, jos pussissa on n erilaista kuponkia (tai eriväristä palloa, miten vaan), kuinka monta nostoa tarvitaan, jotta jokaista erilaista kuponkia tulee nostettua vähintään yksi kappale. Oletetaan jokaista kuponkia olevan äärettömän monta ja suhteellisesti saman verran.

Olen käyttänyt wikipedian artikkelin notes-osiossa mainittua approksimaatiota n x ln(n) + gn + 1/2, jossa g on artikkelissa mainittu Euler-Mascheroni vakio. Itse artikkelin laskut ovat minulle täyttä hepreaa, en edes ymmärrä suurinta osaa symboleista. Ensimmäinen kysymykseni onkin, kuinka luotettava tuo edellämainittu approksimaatio on suuremmilla luvuilla (esim. n = 1E6)?

Toinen kysymys on, voiko jotenkin laskea todennäköisyyttä, jolla y% kupongeista tulee nostettua?

Ja viimeisenä, voiko todennäköisyyksiä laskea tai arvioida lainkaan, jos eri kuponkien osuus ei ole suhteessa toisiinsa sama, eli jos esim. osaa kupongeista on 100-kertainen määrä toisiin nähden? Tässä tapauksessa varmaan tarvitsisi tietää, minkälaista jakaumaa kupongit noudattavat. Jakauma muistuttaa (ymmärtääkseni) J-käyrän mallista potenssijakaumaa. Minkälaisia alkuoletuksia tarvitaan, jotta todennäköisyyksiä voi lainkaan laskea, vai voiko niitä?

En ole tämän tasoista matematiikkaa koskaan opiskellut, siksi pelkkä kysymysten muotoilu on minulle hankalaa. Voin yrittää selvittää ongelmaa tarkemmin tarvittaessa, jos joku on halukas auttamaan. Kaikki asialliset neuvot ja kommentit ovat tervetulleita!

Kommentit (6)

Retromake
Seuraa 
Viestejä48
Liittynyt1.12.2017

Käyttäjä6894 kirjoitti:
Tervehdys palstan matikkaneroille! Osaisikohan joku hieman neuvoa todennäköisyysongelman kanssa?

Kyseessä on ymmärtääkseni nk. kuponginkerääjän ongelma (https://en.wikipedia.org/wiki/Coupon_collector's_problem) ja sen muunnokset. Lyhyesti, jos pussissa on n erilaista kuponkia (tai eriväristä palloa, miten vaan), kuinka monta nostoa tarvitaan, jotta jokaista erilaista kuponkia tulee nostettua vähintään yksi kappale. Oletetaan jokaista kuponkia olevan äärettömän monta ja suhteellisesti saman verran.

Olen käyttänyt wikipedian artikkelin notes-osiossa mainittua approksimaatiota n x ln(n) + gn + 1/2, jossa g on artikkelissa mainittu Euler-Mascheroni vakio. Itse artikkelin laskut ovat minulle täyttä hepreaa, en edes ymmärrä suurinta osaa symboleista. Ensimmäinen kysymykseni onkin, kuinka luotettava tuo edellämainittu approksimaatio on suuremmilla luvuilla (esim. n = 1E6)?

Toinen kysymys on, voiko jotenkin laskea todennäköisyyttä, jolla y% kupongeista tulee nostettua?

Ja viimeisenä, voiko todennäköisyyksiä laskea tai arvioida lainkaan, jos eri kuponkien osuus ei ole suhteessa toisiinsa sama, eli jos esim. osaa kupongeista on 100-kertainen määrä toisiin nähden? Tässä tapauksessa varmaan tarvitsisi tietää, minkälaista jakaumaa kupongit noudattavat. Jakauma muistuttaa (ymmärtääkseni) J-käyrän mallista potenssijakaumaa. Minkälaisia alkuoletuksia tarvitaan, jotta todennäköisyyksiä voi lainkaan laskea, vai voiko niitä?

En ole tämän tasoista matematiikkaa koskaan opiskellut, siksi pelkkä kysymysten muotoilu on minulle hankalaa. Voin yrittää selvittää ongelmaa tarkemmin tarvittaessa, jos joku on halukas auttamaan. Kaikki asialliset neuvot ja kommentit ovat tervetulleita!

Kysyit muun muassa, kuinka luotettava  on kuponginkerääjän ongelman ratkaisussa käytetty  approksimaatio

n*(ln(n) + g) + 0.5 suurilla n-arvoilla.  Wikipedian artikkelissa "Coupon collector's problem" on viite (Blom-Holst-Sandell), jossa tuolla kaavalla approksimoidaan n*(1/n + 1/(n-1) + 1/(n-2) + ... + 1). Suurilla n- arvoilla approksimaatio näyttää antavan yhä tarkempia tuloksia. Tuota on helppo testata pienellä ohjelmalla. Kokeilin arvolla n=10^8, jolloin virhe oli alle 1/10000.

PPo
Seuraa 
Viestejä13410
Liittynyt10.12.2008

Käyttäjä6894 kirjoitti:
Tervehdys palstan matikkaneroille! Osaisikohan joku hieman neuvoa todennäköisyysongelman kanssa?

Kyseessä on ymmärtääkseni nk. kuponginkerääjän ongelma (https://en.wikipedia.org/wiki/Coupon_collector's_problem) ja sen muunnokset. Lyhyesti, jos pussissa on n erilaista kuponkia (tai eriväristä palloa, miten vaan), kuinka monta nostoa tarvitaan, jotta jokaista erilaista kuponkia tulee nostettua vähintään yksi kappale. Oletetaan jokaista kuponkia olevan äärettömän monta ja suhteellisesti saman verran.

Olen käyttänyt wikipedian artikkelin notes-osiossa mainittua approksimaatiota n x ln(n) + gn + 1/2, jossa g on artikkelissa mainittu Euler-Mascheroni vakio. Itse artikkelin laskut ovat minulle täyttä hepreaa, en edes ymmärrä suurinta osaa symboleista. Ensimmäinen kysymykseni onkin, kuinka luotettava tuo edellämainittu approksimaatio on suuremmilla luvuilla (esim. n = 1E6)?

Toinen kysymys on, voiko jotenkin laskea todennäköisyyttä, jolla y% kupongeista tulee nostettua?

Ja viimeisenä, voiko todennäköisyyksiä laskea tai arvioida lainkaan, jos eri kuponkien osuus ei ole suhteessa toisiinsa sama, eli jos esim. osaa kupongeista on 100-kertainen määrä toisiin nähden? Tässä tapauksessa varmaan tarvitsisi tietää, minkälaista jakaumaa kupongit noudattavat. Jakauma muistuttaa (ymmärtääkseni) J-käyrän mallista potenssijakaumaa. Minkälaisia alkuoletuksia tarvitaan, jotta todennäköisyyksiä voi lainkaan laskea, vai voiko niitä?

En ole tämän tasoista matematiikkaa koskaan opiskellut, siksi pelkkä kysymysten muotoilu on minulle hankalaa. Voin yrittää selvittää ongelmaa tarkemmin tarvittaessa, jos joku on halukas auttamaan. Kaikki asialliset neuvot ja kommentit ovat tervetulleita!

Linkissä esitetty ongelma

In probability theory, the coupon collector's problem describes the "collect all coupons and win" contests. It asks the following question: Suppose that there is an urn of n different coupons, from which coupons are being collected, equally likely, with replacement. What is the probability that more than t sample trials are needed to collect all n coupons.

Boldattu palloilla ja lokeroilla. 

Sijoitetaan n:ään lokeroon umpimähkään t (≥n) palloa. Millä todennäköisyydellä ainakin yksi lokeroista on tyhjä.

c(n,k) binomikerroin n yli k:n.

Komplementin ( jokaisessa lokerossa on ainakin yksi pallo) todennäköisyydeksi saadaan pikku pohdiskelun jälkeen

p=c(t-1,n-1)/(c(n+t-1,t)

joten  kysytty todennäköisyys on 1-p.

Spanish Inquisitor Jr
Seuraa 
Viestejä2273
Liittynyt24.1.2014

Käyttäjä6894 kirjoitti:
Tervehdys palstan matikkaneroille! Osaisikohan joku hieman neuvoa todennäköisyysongelman kanssa?

Kyseessä on ymmärtääkseni nk. kuponginkerääjän ongelma (https://en.wikipedia.org/wiki/Coupon_collector's_problem) ja sen muunnokset. Lyhyesti, jos pussissa on n erilaista kuponkia (tai eriväristä palloa, miten vaan), kuinka monta nostoa tarvitaan, jotta jokaista erilaista kuponkia tulee nostettua vähintään yksi kappale. Oletetaan jokaista kuponkia olevan äärettömän monta ja suhteellisesti saman verran.

Olen käyttänyt wikipedian artikkelin notes-osiossa mainittua approksimaatiota n x ln(n) + gn + 1/2, jossa g on artikkelissa mainittu Euler-Mascheroni vakio. Itse artikkelin laskut ovat minulle täyttä hepreaa, en edes ymmärrä suurinta osaa symboleista. Ensimmäinen kysymykseni onkin, kuinka luotettava tuo edellämainittu approksimaatio on suuremmilla luvuilla (esim. n = 1E6)?

Tervehdys, hyviä kysymyksiä sinulla. Tuohon approksimaation tarkkuuteen sanoisin, että se on tarkempi, mitä suurempi on kuponkien lukumäärä n. Laskin pienen taulukon, jossa nostojen lukumäärän odotusarvo E₁(T) on tarkka ja E₂(T) on sillä wikin likikaavalla laskettu:

n          E₁(T)                         E₂(T)
n=1    1,000                       1,07721
n=5    11,4166                  11,4332
n=10    29,2896           29,2980
n=50    224,9602       224,9619
n=100    518,7377       518,7385

Ylläolevassa on jätetty pyöristämättä eli numerot on katkaistu sellaisenaa tarkemmasta likiarvosta. Kyllähän tuo likiarvo on heti ihan hyvä jo pieniläkin n:n arvoilla. Mitä tarkkuutta sitten tarvitaan, riippuu toki tehtävästä tai sovelluksesta.

Käyttäjä6894 kirjoitti:
 

Toinen kysymys on, voiko jotenkin laskea todennäköisyyttä, jolla y% kupongeista tulee nostettua?

Voi laskea ja tavallaan sen saa ihan niistä wikin kaavoista. Palaan tähän  myöhemmin. 

Käyttäjä6894 kirjoitti:

Ja viimeisenä, voiko todennäköisyyksiä laskea tai arvioida lainkaan, jos eri kuponkien osuus ei ole suhteessa toisiinsa sama, eli jos esim. osaa kupongeista on 100-kertainen määrä toisiin nähden? Tässä tapauksessa varmaan tarvitsisi tietää, minkälaista jakaumaa kupongit noudattavat. Jakauma muistuttaa (ymmärtääkseni) J-käyrän mallista potenssijakaumaa. Minkälaisia alkuoletuksia tarvitaan, jotta todennäköisyyksiä voi lainkaan laskea, vai voiko niitä?

Voi näitäkin laskea, jossa tosiaan noita kuponkeja on "myynnissä" eri määriä ja siten se vaikuttaa noihin todennäköisyyksiin. Tämän kysymyksen käsittely on hieman hankalaa ja siinä on melkoinen kirjoitushomma jos tähän rupeaa sitä juurtajaksain selvittämään. Mihin oikeastaan tarvitset näitä kaavoja? Ymmärsin niin, että et kuitenkaan ole alan opiskelija, vaan tarvitset näitä tietoja johonkin, mutta mihin? Voin sitten yrittää vastailla viikonloppuna tarkemmin noihin, kun on aikaa paremmin, sillä Ihan aloittelijan kyssäreitä nuo sun kysymykset eivät ollenkaan ole.

Vanha nimimerkki Spanish Inquisitor uudelleensyntyneenä.

Käyttäjä6894
Seuraa 
Viestejä3
Liittynyt3.4.2018

Kiitos kaikille vastauksista!

Yritän soveltaa näitä laskuja genetiikassa. Lyhyesti; proteiinien toimintaa voidaan tutkia muuttamalla niiden rakennetta, eli aminohapposekvenssiä. Käytännössä muutokset tehdään DNA:han, eli proteiinia koodaavaan geeniin. DNA:ta on verrattaen helppo muunnella ja tuottaa valtava määrä geenivariantteja. Niiden tutkimisessa on kuitenkin pullonkaula, koska laajempaa tuotantoa varten muunnellut geenit on siirrettävä bakteereihin, joissa ne lisääntyvät. Bakteereiden kyky ottaa DNA:ta sisäänsä on kuitenkin rajoittunut normaalioloissa. Yleisesti käytetyssä reaktiossa joukko bakteereita pystyy ottamaan sisäänsä noin suuruusluokkaa 1E8 DNA molekyyliä. Tämän määrän skaalaaminen ylöspäin merkittävästi on ongelmallista. Jos siis halutaan tutkia muunneltua geenipopulaatiota, jossa on esim. 1E11 varianttia, käytännössä tutkittavien varianttien määrää rajoittaa yhtenä tekijänä tuo mainittu bakteerien kyky ottaa DNA:ta sisäänsä. 

Alkuperäisen kysymykseni voi siis muotoilla esimerkiksi tähän tyyliin. Jos on geenipopulaatio, jossa on yhteensä  1E12 DNA molekyyliä, jotka edustavat 1E8 erilaista geenivarianttia, kuinka monta bakteerikloonia on tutkittava, jotta jokainen variantti tulee mukaan vähintään yhtenä kopiona. Oletuksina voi olla homogeeninen (jokaista varianttia on yhtä monta kopiota) tai ei-homogeeninen geenipopulaatio.

Näin siis yksinkertaistettuna. Tarkempi kysymyksenasettelu ja siihen liittyvät tekniset seikat on melko spesifiä molekyyligenetiikkaa. 

Retromake, mitä tarkkaan ottaen tarkoitat tuolla saamallasi virhearvolla "alle 1/10000"? 

Spanish Inquisitor Jr, kiitos paljon kommenteistasi ja tarjouksesta palata kysymyksiin paremmalla ajalla! Nämä eivät tosiaan taida olla ihan peruskysymyksiä, ja voivat vaatia kohtuutonta vaivannäköä sinulta. Ymmärrän siis kyllä hyvin, jos aikasi ei riitäkään niihin paneutumiseen. Mikä tahansa apu kuitenkin kelpaa, ja vähintäänkin auttaa minua muotoilemaan kysymykseni paremmin jatkossa :)

Retromake
Seuraa 
Viestejä48
Liittynyt1.12.2017

Tarkoitin tuolla virhearvolla tarkan arvon ja approksimaatiolla saadun arvon erotusta. Laskin arvion liian epätarkalla 32-bittisellä tietotyypillä. Tein nyt laskelmat uudelleen 64-bitin tarkkuudella, jolloin saadaan vertailuarvoihin vähintään 15 numeron tarkkuus.  Jatkan taulukkoa, jonka Spanish Inquisitor Jr laski sinulle jo aiemmin pienemmille

 n-arvoille.

                                             E1(T)                                  E2(T)                                    | Ero |
n=  1000                      7485.4708605       7485.4709439         8.33333e-5             
n= 10000                97876.0603604    97876.0603688      8.33328e-6
n=100000                                                                                                                8.34930e-7
n=1000000                                                                                                            3.16649e-8

Tästä eteenpäin 128 bitin tietotyyppi olisi luotettavampi, mutta  approksimaation osuvuus näkyy jo näilläkin luvuilla.

Käyttäjä6894
Seuraa 
Viestejä3
Liittynyt3.4.2018

Retromake kirjoitti:
Tarkoitin tuolla virhearvolla tarkan arvon ja approksimaatiolla saadun arvon erotusta. Laskin arvion liian epätarkalla 32-bittisellä tietotyypillä. Tein nyt laskelmat uudelleen 64-bitin tarkkuudella, jolloin saadaan vertailuarvoihin vähintään 15 numeron tarkkuus.  Jatkan taulukkoa, jonka Spanish Inquisitor Jr laski sinulle jo aiemmin pienemmille

 n-arvoille.

                                             E1(T)                                  E2(T)                                    | Ero |
n=  1000                      7485.4708605       7485.4709439         8.33333e-5             
n= 10000                97876.0603604    97876.0603688      8.33328e-6
n=100000                                                                                                                8.34930e-7
n=1000000                                                                                                            3.16649e-8

Tästä eteenpäin 128 bitin tietotyyppi olisi luotettavampi, mutta  approksimaation osuvuus näkyy jo näilläkin luvuilla.

OK, kiitos tarkennuksesta! Käytännössä noin pienillä eroilla ei ole minulle mitään merkitystä, hyvä tietää, että approksimaatio on tässä suhteessa luotettava. Minulle riittää summittainen arvio "jos n = 10000, tarvitaan noin 100000 nostoa".

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat