Newsgroup: it.hobby.enigmi
Titolo: Le figurine

Salve a tutti.
    ho iniziato una raccolta di figurine, 100 in tutto. Purtroppo
non conosco nessun altro che faccia la stessa raccolta, quindi non
posso fare scambi. Le compro per posta 1 alla volta.
Se il produttore mi invia ogni volta una figurina scelta a caso,
quante ne comprero' in media per completare l'album?
Buona raccolta
Precisazioni
Figurine numerate, non intercambiabili, il produttore ne fabbrica lo
stesso
numero di ognuna e le spedice a caso, con la stessa probabilità per
ciascuna.
Mi e' venuto in mente per caso, e' "originale", salvo che e' troppo
ovvio
per non essere gia' comparso. Mi aspetto che si possa trovare sui testi
di statistica.
Ho trovato una soluzione, che scrivero' solo se si rivelera' corretta...
Ho in mente una variante leggermente piu' complessa, ma aspetto la
soluzione
di questa prima parte.
Dario, se ci inondi di bibliografia, mi fai un favore.
Ciao
Mauro Fiorentini

di statistica.
Infatti. Si trova in molti libri di probabilita'.
Se ci sono n oggetti da collezionare, e tu ne hai k,
la probabilita' che il prossimo oggetto sara' nuovo e'
(n-k)/n. Quindi il numero di acquisti che devi fare, mediamente, per
prendere un nuovo oggetto quando ne hai k e' n/(n-k).
Allora facciamo la somma di n/(n-k) per k da 0 a n-1.
E troviamo n(1 + 1/2 + 1/3 + ... + 1/n)
= n H_n
dove H_n e' l'ennesimo numero armonico.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
I am never forget the day I first meet great Lobachevsky. In one
word he told me secret of success in mathematics: Plagiarise.

 Mauro Fiorentini
Anche se non sono il piu' quotato nel ng. ci provo io per primo.
I problemi di statistica mi sono sempre piaciuti...  ;-)
Le figurine possibili sono C = 100
La probabilita' ad ogni acquisto e' p = 1/C
La probabilita' contraria e' (1-p)
La probabilita' contraria dopo n volte e' (1-p)^n
Approssimo per ottenere il 99.99% di confidenza dopo n acquisti...
(1-p)^n < 0.01
n log (1-p) < log 0.01
n > log 0.01 / log (1-p) =  458,21
Da cui si ricava che dopo 458 acquisti forse ce la puoi fare.
Ciao,
Massimo

     ho iniziato una raccolta di figurine, 100 in tutto...
Il prob. e' stato gia' trattato anche qui, postato da Matteo Frigerio
col titolo 20merendine20, in una forma leggermente differente. Ebbe
diverse risposte. Mi ricordo quella di Adam con l'utilizzo delle catene
di Marcov.
Riferimenti bibliografici?, puoi troverlo in:
Mosteller "Fifty Challenging Problems in Probability" Dover 1965
(prob.14)
Dunn " Mathematical Baffler" Dover 1980 pag.145
(Vado a memoria, e mi ricordo solo questi 2)
Se non ho sbagliato i conti, metto la sol. piu' sotto.
:)dario
?
?
?
?
Te ne dovrai comperare 519.

La probabilita' ad ogni acquisto e' p = 1/C
probabilita' di cosa?
sbalgliato in partenza, purtroppo.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
EXAKCIP

Mauro Fiorentini
ciao
paolo

 >quante ne comprero' in media per completare l'album?
Mi sembra che Mauro non chieda le probabilita', ma il tempo di attesa
necessario per finire la raccolta. 
Il prob. e' stato gia' trattato anche qui, postato da Matteo Frigerio
col titolo 20merendine20, in una forma leggermente differente. 
Pero' e' un problema noto, ed e' apparso piu' volte. A memoria mi
vengono in mente 2 riferimenti:
Mosteller "Fifty Challenging Problems in Probability" Dover 1965
(prob.14)
Dunn " Mathematical Baffler" Dover 1980 pag.145
Allora ecco la risposta.
Innanzi tutto danno la dimostrazione del fatto intuibile che per un
evento con probabilita' p, il tempo di attesa e' 1/p. Ad es. quante
volte dovro' lanciare un dado per ottenere un 6 ? p=1/6 tempo di attesa
= 1/(1/6) =6. Quante persone dovro' incontrare prima di trovarne una
nata un venerdi' sol. 7.
Possiamo vedere ora quali sono le prob. di ottenere una nuova figurina
ad ogni acquisto e calcolare il tempo di attesa per ogni figurina:
Acquisto   prob.       attesa
primo      100/100     1/(100/100)
secondo    99/100      1/(99/100)
terzo      98/100      1/(98/100)
.......
centesimo   1/100      1/(1/100)
La somma di tutti questi tempi e' semplificata in:
n(1 + 1/2 + 1/3 + 1/4 +.....+ 1/n)
nel nostro caso:
100(1+1/2+1/3+...+1/99+1/100)
che se non ho sbagliato il conto da' 518.xxxxx ma dovendo essere un
numero intero puoi aspettarti di finire la raccolta dopo aver comperato
519 figurine. 
:) dario


Mi chiedo qual e' la probabilita' di completare la collezione 
dopo esattamente N figurine comprate, con N>=100.
Vi sono 100^N possibili sequenze di figurine possibili,
devo calcolare quante di queste sequenze mi fanno completare la 
collezione esattamente alla N-ma figurina.
Se non ho fatto errori il numero di queste sequenze e'
100 * 99 * (N-2) * (N-3) * .... * (N-99)
La probabilita' di completare la serie alla N-ma figurina e' quindi
P(N) = 100^(1-N) * 99 * (N-2) * (N-3) * .... * (N-99)
Il numero medio di figurine comprate e' somma di N*P(N) 
con N da 100 a infinito
Ciao

519 figurine. 
In realta' la probabilita' di finire la collezione comprando non piu'
di 519 figurine e' solamente 0.575736165403761, ed i valori fino a 519
contribuiscono solamente 250.501449247219 alla media.
ecco un programmino in Perl, che fa i calcoli per una delle mie
amatissime catene di Markov.
"$n" e' il numero di figurine da collezionare.
compriamo una figurina al giorno
ogni "giorno" il programma ti dice la probabilita' di finire entro
quel giorno, e la media tenendo presente solo i contributi fino a quel
giorno.
$n=100;
$p[0][$old]=1;
$day=0;
$old=0;
while(1) {
        $new=1-$old;
        print "Giorno $day, Prob. $p[$n][$old] ";
        $m+=$day*($p[$n][$old]-$p[$n][$new]);
        print ", Media: $m\n";
        $day++;
        for $i (1..$n) {
                $p[$i][$new]=$p[$i-1][$old]*($n-$i+1)/$n+$p[$i][$old]*$i/$n;
                }
        $p[0][$new]=0;
        $old=1-$old;
        }
Vediamo che la mediana del numero di figurine e' 497
(prob. di finire entro 496 = 0.497437432225334,
prob. di finire entro 497 = 0.500984718329375)
La moda della distribuzione e' 460  (prob 0.00378656077038414 )
per essere sicuro ad almeno il 90% di finire la collezione, devi comprare
683 figurine.
per essere sicuro al 99%, devi comprarne 916
per essere sicuro al 99.9%, devi comprarne 1146
per essere sicuro al 99.99%, devi comprarne 1375
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
Eschew obfuscation!

dopo esattamente N figurine comprate, con N>=100.
programmino in Perl:
$n=100;
$p[0][$old]=1;
$p[$n][$old]=0;
$day=0;
$old=0;
while(1) {
    $new=1-$old;
    if ($day>99) {
        print "$day ";
        $p2=$p[$n][$old]-$p[$n][$new];
        print "$p2\n";
        }
    $day++;
    for $i (1..$n) {
        $p[$i][$new]=$p[$i-1][$old]*($n-$i+1)/$n+$p[$i][$old]*$i/$n;
        }
    $p[0][$new]=0;
    $old=1-$old;
    }
alcuni dei primi valori:
100 9.33262154439428e-43
101 4.61964766447515e-41
102 1.15868462837811e-39
103 1.9631539223762e-38
104 2.52739183060214e-37
105 2.63689957978152e-36
106 2.32216000305277e-35
107 1.77520972383109e-34
108 1.20245540755214e-33
109 7.33058128162695e-33
110 4.07195377738578e-32
111 2.08150663823866e-31
112 9.87231565142105e-31
113 4.37426869124652e-30
114 1.82124254712178e-29
115 7.16113050833177e-29
116 2.67076851578991e-28
117 9.48390523675546e-28
118 3.21733452977072e-27
119 1.04583436765344e-26
120 3.26625295672527e-26
e quelli piu' comuni:
454 0.0037801531209713
455 0.00378226318056557
456 0.00378395089546874
457 0.00378522032054041
458 0.00378607560332411
459 0.00378652097983284
460 0.00378656077038414
461 0.00378619937548752
462 0.00378544127178593
463 0.00378429100805266
464 0.00378275320124655
465 0.00378083253262596
466 0.00377853374392373
Ma anche valori molto piu' alti non sono improbabilissimi:
1000 4.34376019232685e-05
Per vedere i contributi alla media di 519.7qualcosa facciamo:
$n=100;
$p[0][$old]=1;
$p[$n][$old]=0;
$day=0;
$old=0;
while(1) {
    $new=1-$old;
    $m=$day*($p[$n][$old]-$p[$n][$new]);
    $mean+=$m;
    if ($day>99) {
        print "$day $m $mean\n";
        }
    $day++;
    for $i (1..$n) {
        $p[$i][$new]=$p[$i-1][$old]*($n-$i+1)/$n+$p[$i][$old]*$i/$n;
        }
    $p[0][$new]=0;
    $old=1-$old;
    }
e vediamo che ci sono contributi significativi alla media anche dai
valori piuttosto alti:
valore contributo     media fatta dai contributi fino a qui
790 0.275104874560037 487.510195680553
infatti, per arrivare a 518 bisogna andare fino a...
1203 0.0068163820156133 518.006644834072
andando molto piu' in la':
1789 2.80761603995705e-05 518.734816853336
sappiamo che la media e' 100 H_100 = 518.73775176396
quindi.. anche valori superiori a 1789 contribuiscono un bel po' al
totale.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
If I were a bumble bee
Z would be a U.F.D.

Salve,
    visto che la prima versione era vecchia e facile, ecco la seconda:
voglio completare DUE raccolte.
Non mi sembra molto piu' difficile, ma la soluzione mi sembra leggermente
controintuitiva.
piu' in generale, qual e' il numero medio di acquisti per completare n
raccolte.
Probabilmente e' anche questo un classico della letteratura.
Se anche questo e' gia' comparso in questo ng, mi autoescludo dal ng per
almeno 10 secondi!
Ciao
Mauro Fiorentini


Temevo, infatti.
Se non altro la soluzione che avevo trovato era corretta.
Non ero riuscito a calcolare quante comprarne per avere probabilita'
99% ecc.
Grazie
Mauro Fiorentini
P.S. Ci sono cascato anche io? Nel senso che era vecchio e gia' apparso;
non l'ho visto nelle FAQ. Scusate. Riprovero'

non l'ho visto nelle FAQ.
Nelle FAQ di it.fan.dewdney forse no.
Nelle FAQ di rec.puzzles c'e':
==> probability/coupon.p <==
There is a free gift in my breakfast cereal. The manufacturers say that
the gift comes in four different colors, and encourage one to collect
all four (& so eat lots of their cereal). Assuming there is an equal
chance of getting any one of the colors,  what is the expected number
of boxes I must consume to get all four?  Can you generalise to n
colors and/or unequal probabilities?
==> probability/coupon.s <==
The problem is well known under the name of "COUPON COLLECTOR PROBLEM".
The answer for n equally likely coupons is
(1)             C(n)=n*H(n)    with H(n)=1+1/2+1/3+...+1/n.
In the unequal probabilities case, with p_i the probability of coupon i,
it becomes
(2)             C(n)=int_0^infty [1-prod_{i=1}^n (1-exp(-p_i*t))] dt
which reduces to (1) when p_i=1/n (An easy exercise).
In the equal probabilities case  C(n)~n log(n). For a Zipf law,
from (2), we have C(n)~n log^2(n).
A related problem is the "BIRTHDAY PARADOX" familiar to people
interested in hashing algorithms: With a party of 23 persons,
you are likely (i.e. with probability >50%) to find two with
the same birthday. The non equiprobable case was solved by:
        M. Klamkin and D. Newman, Extensions of the birthday
        surprise, J. Comb. Th. 3 (1967), 279-282.


almeno 10 secondi!
La prima cosa che mi viene in mente e', prevedibilmente, una catena di
Markov.
Diciamo che ci sono n figurine, e vuoi k raccolte complete.
Gli "stati" hanno la forma {a_0, a_1, ..., a_k}
Dove a_i e' il numero di figurine di cui hai i copie, tranne a_k
che e' il numero di figurine di cui hai _almeno_ k copie.
la somma degli a_i e' n, ovviamente.
Lo stato iniziale e' {n,0,...,0} e lo stato finale e' {0,...,n}
Visto che la somma degli a_i e' sempre n possiamo abbreviare lo stato
tralasciando a_k. In un programma, probabilmente farei cosi'.
Le probabilita' di transizione sono abbastanza evidenti, ma non vorrei
farlo al computer per k maggiore di 2 o 3.
A qualcuno vengono in mente metodi migliori?
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
VOLCANO MISSING FEARED DEAD

voglio completare DUE raccolte.
primo tentativo (in perl):
$n=100;
$old=0;
$p[$n-1][1][$old]=1;
$p[$n][0][$old]=0;
$p[$n][0][1-$old]=0;
$p[0][0][$old]=0;
$day=1;
while(1) {
        $new=1-$old;
        print "Giorno $day, Prob. $p[0][0][$old]\n";
        $day++;
        for $i (0..$n-1) {
        for $j (0..$n-$i) {
                $p[$i][$j][$new]=$p[$i][$j][$old]*($n-$i-$j)/$n;
        $p[$i][$j][$new]+=$p[$i][$j+1][$old]*($j+1)/$n;
        if ($j>0) {
        $p[$i][$j][$new]+=$p[$i+1][$j-1][$old]*($i+1)/$n;
                }
        }
        }
        $old=1-$old;
        }
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
What's purple and commutes? An abelian grape.

mediana 706 per 2 raccolte?
il mio "intuito" diceva che per finire la seconda raccolta non ci
vuole molto tempo - quando finisci la prima raccolta avrai gia' un bel
po' di doppioni.
secondo te questo e' sorprendente? o la "sorpresa" e' un'altra cosa?
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
It is a sobering thought, for example, that when Mozart was my age, he had
been dead for two years. (T. Lehrer)


La sorpresa e' il gran numero di figurine da comprare la seconda volta.
Se la seconda raccolta completata lascia la stessa distribuzione media,
(non credo) il calcolo vale anche per le raccolte successive, tutte molto
costose.
Ciao
Mauro Fiorentini

Media 728.805230495801 per due raccolta.
non tutte quelle cifre saranno significative, ovviamente.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
"That's the biggest shark I've ever seen" he said, superficially.

Mauro Fiorentini
Ciao, Silv:o)


Che si stabilizzi sembra ragionevole. Dovrebbe essere possibile calcolare
ladistribuzione finale, sapendo che e' un punto fisso per l'operatore
"completo un'altra raccolta". Chi ci prova?
Ciao
Mauro

stanotte le ho completate tutte con circa 95 doppioni di media.
Ho seguito l'esempio di Adam, ed ho usato una Marcov: mi conferma i 95
doppioni
delle simulazioni.
Gli stati sono della catena sono del tipo [f,d] dove f e' il numero di
figurine uscite almeno una volta e d il numero dei doppioni, ovvero delle
figurine uscite almeno due volte.
Le probabilita' di transizione sono abbestanza semplici:
[f,d]-->[f+1,d] = (100-f)/100
[f,d]-->[f,d+1] = (f-d)/100
[f,d]-->[f,d] = d/100
Chiamiamo D(f,d) il numero di doppioni che mi aspetto quando sono nello
stato [f,d]
Si puo' scrivere il sistema:
D(100,d)=d
D(f,d)=(100-f)/100*D(f+1,d)+(f-d)/100*D(f,d+1)+d/100*D(f,d)
che risolto partendo da D(100,100)=0 e procedendo a ritroso con le
sostituzioni mi da'
D(0,0)=94.8126224823603
Ciao, Silv:o)

delle simulazioni.
ho fatto la stessa cosa per vedere quanti "triploni" dovrei avere
avendo completato 2 raccolte:
$n=100;
sub v {
    my ($x,$y,$z) = @_;
 
    if (defined $v[$x][$y][$z]) {
        return $v[$x][$y][$z];
        }
    #print "$x $y $z\n";
    #if ($y+$z==$n) {
    #print "bing!\n";
    #$v[$x][$y][$z]=$z;
    #return $z;
    #}
    $v[$x][$y][$z]=0;
    if ($x+$y+$z<$n) {
    $v[$x][$y][$z]+=v($x+1,$y,$z)*($n-$x-$y-$z)/$n
    }
    if ($x>0) {
    $v[$x][$y][$z]+=v($x-1,$y+1,$z)*$x/$n;
    }
    if ($y>0) {
    $v[$x][$y][$z]+=v($x,$y-1,$z+1)*$y/$n;
    }
    if ($z>0) {
    $v[$x][$y][$z]/=(1-$z/$n);
    }
    return $v[$x][$y][$z];
    }
for (0..100) {
    $v[0][100-$_][$_]=$_;
    }
printf v(0,0,0)."\n";
risposta:
96.355973847509
