Newsgroup: it.hobby.enigmi
Titolo: Estrazioni casuali

Supponiamo di poter estrarre dei valori a caso fra 0 e 1
uniformemente distribuiti.
Ne estraggo tanti finché la loro somma non supera 1.
Quanti ne serviranno mediamente?
(la soluzione è piuttosto interessante e poco intuitiva, secondo me)
Volendo provate a generalizzare con numeri scelti fra 0 e "a"
la cui somma deve raggiungere "b".
Ciao
Andrea

 (la soluzione è piuttosto interessante e poco intuitiva,
secondo me)
SPOILER
v
v
v
v
v
v
v
v
v
v
v
v
v
v
Nella metà dei casi dovrebbero bastare 2 estrazioni, in un quarto
occorrono 3 estrazioni, in un ottavo 4 estrazioni, e così via.
Si ha quindi  2/2 + 3/4 + 4/8 + 5/16 + ...... , che dovrebbe
tendere a 3
Ciao
Gianni

e così via.
Simulando un milione di prove, trovo
estr.    casi      estr. totali
2       499 896       999 792
3       333 181       999 543
4       125 106       500 424
5        33 567       167 835
6         6 844        41 064
7         1 195         8 365
8           188         1 504
9            23           207
10            0             0
totale              2 718 734
la media 2.718734 somiglia molto ad
e = 2.718282
l'ultima colonna della tabella presenta una particolarita' interessante:
i rapporti tra un valore ed il successivo sono all'incirca
1, 2, 3, .....
ciao
paolo

 >e cosě via.
La probabilita` che servano k estrazioni vale
p(k)=1/(k*(k-2)!)
k   p(k)
2   1/(2*0!)=1/2
3   1/(3*1!)=1/3
4   1/(4*2!)=1/8
5   1/(5*3!)=1/30
..
La media vale 2*p(2)+3*p(3)+..+n*p(n)+.. = 1/0!+1/1!+1/2!+..+1/n!+.. = e
Ciao, Silv:o)

la cui somma deve raggiungere "b".
Ciao Andrea, la media richiesta sara' la stessa che si ha nel caso che
gli addendi sono tra 0 e 1 e la somma deve raggiungere x=b/a. Cioe'
non e' restrittivo assumere "a"=1.
Per ora considero solo x intero>1. La probablilita' che per superare x
servano m estrazioni di variabili uniformi in [0,1] e'
p(m,x) = (m-x)f(m,x)/m!
dove f(m,x) e' la seguente funzione ricorsiva:
f(m,0)=f(m,m)=0
f(2,1)=1
f(m,x)=(m-x)f(m-1,x-1)+xf(m-1,x)
La media e' somma{m=x+1..inf} (m-x)f(m,x)/(m-1)! = ?
Ciao

Silvio Sergio wrote

OK! OK!
Sono piů di 15 anni che non mi occupo di statistica e le mie
circonvoluzioni cerebrali si sono un po' arruginite. :-(
Ciao
Gianni

La media e' somma{m=x+1..inf} (m-x)f(m,x)/(m-1)! = ?
In effetti, se x=2, f(m,x) ha la forma non ricorsiva 2^(m-1)-m. In
questo caso la media e'
somma{m=2..inf} (m-1)*(2^m-m-1)/m! = e^2 - e
Probabilmente ci sono espressioni chiuse anche per x>2. Ciao 

 restare sotto l'unità e, perciò, 1/4 di probabilità che questo accada.
Non poteva essere altrimenti, viste le premesse.
Pero' il calcolo di nuovo ti smentisce: la probabilita` di sballare al terzo
vale 1/3
In generale, p(k)=(k-1)/k!
E la media vale proprio e
Prova a fare qualche simulazione, ti convincerai
Ciao, Silv:o)

 a 1 e y che va da 1-x ad 1.
Ho fatto un po' di confusione: i vincoli che propongo vanno bene per i casi
che superano l'unita` (ovviamente y va da 0 a 1-x), inoltre ho dimenticato
un fattore 2 perche` x ed y sono distribuiti uniformemente in una regione di
area 1/2.
   1    1-x
   /    /
 E=| (  | (x+y) 2 dy ) dx = 2/3
   /    /
 x=0  y=0
Scusate, me ne accorgo sempre un attimo dopo aver postato.
Silv:o)

 Andrea
S
P
O
I
L
E
R
Ho visto le varie risposte e, francamente, non mi sembra che vi sia grande
sintonia.
Non posso, perciò, far mancare il mio contributo di confusione e propongo
una ulteriore impostazione del problema.
La probabilità di superamento dell'unità, all'n° lancio, è data dal prodotto
delle probabilità di NON superamento in tutti i lanci precedenti per la
probabilità di superamento nel lancio in esame.
Dobbiamo, inoltre, assumere che il valore di ciascuna estrazione sia quello
medio nell'ambito di quelli coerenti con l'ipotesi considerata.
Così al primo lancio non abbiamo nessuna possibilità di superamento in
quanto possiamo estrarre al massimo 1.
Assumendo che al primo lancio si sia estratto 0.5 (media tra 0 ed 1), al
secondo lancio abbiamo i valori tra 0 e 0.5 che ci lasciano al disotto di 1
ed e valore tra 0.5 e 1 che ci fanno superare: dunque una probabilità di
restare entro l'unità pari ad 1/2.
Qualora ciò si sia verificato, avremo estratto mediamente 0.25, totalizzando
complessivamente 0.75
Al lancio successivo (il terzo) abbiamo un margine residuo di 0.25 per
restare sotto l'unità e,perciò, 1/4 di rpobabilità che questo accada.
Ecc. ecc.
Dunque possiamo dire che
lancio     probab. di non super/to     probab. di super/to
1            1                                       0
2            1/2                                    1/2
3            1/2*1/4                             1/2*3/4
4            1/2*1/4*1/8                      1/2*1/4*7/8
5            1/2*1/4*1/8*1/16             1/2*1/4*1/8*15/16
6            1/2*1/4*1/8*1/16*1/32    1/2*1/4*1/8*1/16*31/32
............................................................................
................
La probabilità di superare l'unità all'n° lancio è dunque
P(n) = {1/2^[(n-1)*(n-2)/2]} * {[2^(n-1)-1]/2^(n-1)} =
       =  1/2^((n-1)*(n-2)/2) - 1/2^(n*(n-1)/2)
La media di lanci necessari per superare l'unità è pertanto:
Somma(n=1..inf)     n/2^((n-1)*(n-2)/2) - n/2^(n*(n-1)/2)
Francamente non saprei determinarne il valore ma, col solito foglio
elettronico, ottengo
n      Somma
1      0
2      1
3      2,125
4      2,5625
5      2,6357421875
6      2,64141845703125
7      2,64162874221801758
8      2,64163252711296082
9      2,64163256050960626
10    2,6416325606548412
11    2,64163256065515353
12    2,64163256065515387
13    2,64163256065515387
14    2,64163256065515387
15    2,64163256065515387
16    2,64163256065515387
17    2,64163256065515387
18    2,64163256065515387
19    2,64163256065515387
20    2,64163256065515387
rapidissimamente convergente (già per n=12 a meno di 10^-17) ad un valore
inferiore ad e di  0,0766492678038913694
Sbaglio?
et

 restare sotto l'unità e,perciò, 1/4 di rpobabilità che questo
accada.
No, caro Enrico, stai facendo lo stesso errore che, un po'
superficialmente, ho fatto anch'io.
E' vero che dopo la 2° estrazione avanza il 50%, ma questo 50%
non è distribuito uniformemente fra i valori da 0 a 0,9
(periodico), ma avrà una densità inferiore per i valori più
bassi.
Mentre i valori di ciascuna estrazione sono tutti equiprobabili,
i valori combinati di due estrazioni si distribuiscono secondo
una gaussiana (immagina una distribuzione a campana) con un
addensamento attorno al loro valore medio (pensa al lancio di un
solo dado ed a quello di due), quindi quando togliamo la metà dei
valori (quelli > 1), residueranno dei valori distribuiti a
triangolo rettangolo con l'ipotenusa a forma di esse, con la moda
a 0,9(periodico).
Ovviamente, la possibilità di superare l'1, saranno ben più
grandi di metà.
Ciao
:-))))
Gianni

...

Una forma chiusa c'è per 0<x<1.
Per x>1 effettivamente le cose si complicano, sto ancora cercando
se ne trovo di forme chiuse.
Ciao
Andrea

f(m,x)=(m-x)f(m-1,x-1)+xf(m-1,x)
Passando a x reale, si puo' dimostrare che la probabilita' che per
superare x servano m estrazioni di variabili uniformi in [0,1] e'
p(m,x) = (m-x)g(m,x)/m
dove g(m,x) e' la densita' della somma di n variabili uniformi in
[0,1], anche essa definita ricorsivamente su m in modo analogo a f:
g(1,x):= 1 se x e' in [0,1], 0 altrimenti
g(m,x):=( (m-x)g(m-1,x-1) + xg(m-1,x) )/(m-1)
g(m,x) e' facilmente esplicitabile per ogni m se x e' in [0,1]: si ha
g(m,x) = x^(m-1)/(m-1)! per cui la media di p(m,x) risulta
somma{m=1..infinito} (x-m) x^(m-1)/(m-1)! = e^x  per ogni x in [0,1]
Ciao

Silvio Sergio e Giovanni Ravesi mi correggono un errore di assoluta
superficialità, imperdonabile soprattutto perché solo pochi giorni fà ho
affrontato, allora correttamente, il quesito del tutto analogo proposto da
Silvio (UNO).
Grazie della lezione. Starò più attento.
et

se ne trovo di forme chiuse.
Ciao Andrea, per 1<x<2 c'e' e^x-(x-1)e^(x-1).

...

Bravo Filibustero! Anch'io avevo notato che le forme chiuse si esprimono
per n<x<n+1 con n intero.
Interessante il fatto che compaia (x-1)*e^(x-1)
forse sapendo che
0<x<1 => e^x
1<x<2 => e^x-(x-1)e^(x-1)
si può congetturare:
2<x<3 => e^x - (x-2)e^(x-2) + eventualmente qualcos'altro.
Ci penserò.
Ciao
Andrea

somma{m=1..infinito} (m-x) x^(m-1)/(m-1)! = e^x  per ogni x in [0,1]
non esiste una forma generale per la densita' g(m,x), ma esistono
diverse forme chiuse a seconda dell'intervallo a cui appartiene x. In
generale si ha, per ogni x in [k,k+1] con k intero non negativo e m>k,
g(m,x) = [somma{h=0..k} (-1)^h (m su h) (x-h)^(m-1)]/(m-1)!
e lo stesso vale per la media = somma{m=1..inf}(x-m)g(m,x). Ad
esempio, per ogni x in [2,3], la media sara'
somma{m=1..inf} (m-x)/(m-1)! 
        (x^(m-1) - m(x-1)^(m-1) + m(m-1)(x-2)^(m-1)/2) =
= e^x - (x-1)e^(x-1) + (x-2)^2/2 e^(x-2)
e, in generale, nell' intervallo [k,k+1],
media = somma{h=0..k} (x-h)^h/h! e^(x-h). Ciao