O loterie const? din extragerea unui singur num?r cuprins între 1 ?i 49.

In câte extrageri putem spera ca TOATE numerele de la 1 la 49 s? fie extrase?

P?i, dac? suntem optimi?ti, în 49
Probabilitatea, ce-i drept, e cam

dar nu e zero.

Întrebarea mai precis? ar fi:

Care este media num?rului de extrageri necesare pentru a "nimeri" toate numerele de la 1 la 49?

[Citat] Întrebarea mai precis? ar fi: Care este media num?rului de extrageri necesare pentru a "nimeri" toate numerele de la 1 la 49?

Romania are ceva traditie in teoria probabilitatilor. Pentru a da sanse traditiei sa traiasca un secol mai departe, incerc sa rezolv problema asemanatoare cea mai simpla, incat sa fie clar despre ce este vorba pentru un public mai larg...

Desigur, generalizarea sta pe limba:
Intr-o urna se afla toate numerele de la 1 la N, N natural >1.
Un experiment simplu consta in a extrage un numar, a-l tine minte si pune la loc.
Un experiment "derivat", consta in a repeta experimentul simplu de atatea ori pana ce toate numerele au fost extrase (cel putin o data).

Intrebare: Care este media num?rului de extrageri necesare pentru a "nimeri" toate numerele de la 1 la N?


Rezolvam cazul N=2.

Notam cu

multimea rezultatelor posibile in experimentul simplu. Distributia de probabilitate este cea ce repartizeaza 1/2 pentru fiecare din cele doua rezultate posibile.

Notam cu

multimea rezultatelor posibile in experimentul "derivat". Elementele acestui "spatiu de probabilitate" sunt tupletele:
(1,2)
(2,1)
(1,1,2)
(2,2,1)
(1,1,1,2)
(2,2,2,1)
.........
dar pentru a scrie mai putin ("white noise", cum numesc unii probabilisti acele semne de punctuatie ce atrag atentia de la esenta, deci paranteze, virgule, etc), vom scrie in loc "cuvinte" din "alfabetul" cu "literele" 1 si 2, anume:
12
21
112
211
1112
2111
....

Notam cu

functia ("aleatoatre") care asociaza unui "cuvant"

numarul de litere din el, deci K, deci numarul de repetari ale experimentului simplu in "acest mers al lumii" pana ce am data de toate numerele din urna.


Media ceruta este numarul urmator:
2 x (probabilitatea ca sa ne oprim dupa doi pasi)
+ 3 x (probabilitatea ca sa ne oprim dupa trei pasi)
+ 4 x (probabilitatea ca sa ne oprim dupa patru pasi)
+ 5 x (probabilitatea ca sa ne oprim dupa cinci pasi)
+ 6 x (probabilitatea ca sa ne oprim dupa sase pasi)
+ 7 x (probabilitatea ca sa ne oprim dupa sapte pasi)
+ ...

Sa vedem cum stau lucrurile...

Desigur ca avem nevoie de cel putin doua extrageri.
Dupa doua extrageri, lucrurile stau cam asa:

11 - probabilitate 1/4 - mai extragem
12 - probabilitate 1/4 - stop
21 - probabilitate 1/4 - stop
22 - probabilitate 1/4 - mai extragem

tinem minte lucrurile cu stop, iar in celelalte...

111 - probabilitate 1/8 - mai extragem
112 - probabilitate 1/8 - stop
221 - probabilitate 1/8 - stop
222 - probabilitate 1/8 - mai extragem

tinem minte lucrurile cu stop, iar in celelalte...

1111 - probabilitate 1/16 - mai extragem
1112 - probabilitate 1/16 - stop
2221 - probabilitate 1/16 - stop
2222 - probabilitate 1/16 - mai extragem

si asa mai departe.
Avem deci de calculat:

(Adica cum, nici macar pentru N=2 nu dam de o problema banala?! Hmm...)
Idee de calcul: Plecand de la formula

derivand dupa x, luand x=1/2 si trecand la limita dupa K
(eventual vazand din timp ca acel x la "putere mare" nu va mai juca la sfarsit nici un rol, deci plecand poate direct cu x^2 / (1-x) ) obtinem:

Surprindere?

Sa incercam un "Monte Carlo": Lasam computerul sa traga de 10.000 ori la sorti si sa ne dea media
(cod python, insotit de rezultate pentru doua simulari):

Ei bine, ruland acelasi cod "Monte Carlo" pentru N=3 si N=4 obtinem:

Cum se pot explica valorile de mai sus pentru N=3 si N=4?

(Pentru N=49 trebuie facute muuuult mai multe incercari, pentru a avea cat de cat o apropiere statistica de "adevar".)

Poate ca n-are a face nimic de-a face cu problema, dar eu tiparesc. (De fapt, candva au vrut sa ma converteasca la algebra si se mai vad sechele...)

Consideram variabilele X,Y.
Consideram seriile de puteri:

Consideram produsul lor (pentru cei ce stiu sa inmulteasca polinoame este acelasi lucru, doar cu ceva "imprevizibil" in plus legat de acele puncte-puncte...). Nu-l mai scriu. Din produsul lor luam doar monoamele care il au fie pe X, fie pe Y la puterea intaia.. (Bun, cu monomul XY trebuie sa fim mai atenti, dar il luam -ca o conventie- astfel incat sa fie cel din...)

Desigur ca fiecare isi poate imagina cum arata ceea ce sta mai sus. (Se desfac parantezele si dam de o droaie de monoame, care cam seamana cu ce e mai sus scris sub forma 21, 221, 2221, ... , 12, 112, 1112, ... )

Consideram din capriciu functia w ce se obtine luand o noua variabila, sa zicem U, atat in locul lui X, cat si al lui Y, derivam dupa U, apoi luam U=1 in derivata. Dam de:

Ce are acest 3 de-a face cu ce este scris mai sus?

N.B. Partea cu convertirea este adevarata doar in parte, seriile generatoare sunt des intalnite in (combinatorica si) probabilitati (combinatorice).

Poate ca n-are mai departe nimic de-a face cu problema, dar eu tiparesc.
Incerc sa fac in mod secret rost de probabilitate in cazul N=3.

Consideram variabilele X,Y,Z.
Consideram seria de puteri in X,Y:

Aceasta serie aduna -in monoamele ce intervin- toate posibilitatile de a extrage "multe X-uri" si "multe Y-uri"
(din expandarea primei paranteze), insa insistand ca macar un X si macar un Y apar in fiecare monom.

Coeficientii ce apar in drum sunt exact probabilitatile cu care in experimentul derivat alegerea corespunzatoare apare (cumulat, daca facem abstractie de ordine).

Daca mai punem si un Z/3 in coada, dam de toate posibilitatile de a face "multe X-uri si Y-uri", in care atat X cat si Y apare, impreuna cu un prim (ultim) Z.

Acest lucru ne face sa asociem:

Cum numaram numarul de litere din fiecare monom ce apare?

Avem un truc algebric bine cunoscut, inlocuim X,Y,Z cu o variabila U, dam de o functie w(U), derivam dupa U si luam in sfarsit U=1.
Dam de:

Ce are acest 5.500000 de-a face cu acea simulare Monte Carlo de mai sus?


N.B.
Daca cineva nu crede ca am facut calculele...

Cazul general:

Ar trebui sa fie acum clar - desi ma indoiesc daca mie mi-ar fi clar intr-o luna- cum se transeaza cazul unui N general.

Consideram variabilele

.
Consideram seria de puteri in primele (n-1) variabile dintre ele, care printr-un principiu de includere excludere face rost de toate monoamele in toate aceste prime (n-1) variabile, cu ponderile de probabilitate corespunzatoare drept coeficienti, din pacate nu am gasit o formula mai simpla in graba:

Aceasta serie aduna -in monoamele ce intervin- toate posibilitatile de a extrage "multe X1-uri" si "multe X2-uri" si ...
si "multe X(N-1)-uri" (din expandarea primei paranteze), insa insistand ca fiecare simbol sa apara macar o data.

Coeficientii ce apar in drum sunt exact probabilitatile cu care in experimentul derivat alegerea corespunzatoare apare (cumulat, daca facem abstractie de ordine).

Daca mai punem si un

in coada, dam de un mod de a enumera toate elementele din acel spatiu de probabilitate Omega, ca monoame, iar coeficientii sunt exact probabilitatile cu care intervin aceste monoame.

Acest lucru ne face sa asociem:

(Aici, acel check peste Xi sugereaza suprimarea lui din enumerarea variabilelor.)

Cum numaram numarul de litere din fiecare monom ce apare?
Cu acelasi truc algebric, inlocuim

cu o variabila U, dam de o functie w(U), derivam dupa U si luam in sfarsit U=1.
Dam de:

(Putem face acum "back-engineering" din acel 1/( 1- LU/N ) si vom da de ceva cu suma primelor puteri
de un anumit ordin. Deoarece candva am invatzat ca intervin numere Bernoulli in astfel de formule, ma opresc aici cu reformatarea. (Cu numerele Bernoulli nu este de glumit. daca cineva vrea totusi sa glumeasca, sa se apuce de K-teorie...)


Derivata se poate calcula pentru valori speciale ale lui N (de exemplu N=49) si raspunsul este acel

Folosind computerul, am dat la repezeala de:

(Linia de definitie a lui w(U) a fost sparta de mine cu mana, altfel am probleme cu latex-ul. Ea trebuie pusa la loc, daca cineva chiar incearca acel sage...)

Sigur am gresit ceva pe undeva... sa vedem daca simulacrul ajunge tot pe acolo...

Da ajunge tot pe acolo, dupa ceva muzicutza de la ventilatorul laptop-ului meu si asa cu duhul dat...



P.S. Am gresit rau?! Sigur am gresit pe undeva...

Am incercat sa dau de media corespunzatoare pentru cateva N-uri...
Fie X(N) variabila aleatoare a carei medie (expectation) IE[ X(N) ] se cere in cazul in care avem N numere in urna.
Am obtinut cu formula de mai sus:

Faptul ca numitorul lui IE[ X(N) ] se divide cu (N-1)! nu este intamplator, desi din formula pe care o folosesc cu greu se vede o astfel de coincidenta. Probabil ca exista o alta solutie mai naturala, care sa explice aceasta coincidenta. De exemplu, numitorul lui E[ X(49) ] = 13881256687139135026631/63245806209101973600 este

care duhneste a factorial.

Cred ca raspunsul este 219.

Justificare:
Dupa prima extragere avem deja un numar

. De cate extrageri e nevoie (in medie) pentru a obtine un numar

diferit de primul?
Probabilitatea ca

sa apara la a 2-a extragere este

.
Probabilitatea ca

sa apara la a 3-a extragere este

.
Probabilitatea ca

sa apara la a 4-a extragere este

, samd.
Prin urmare, numarul de extrageri asteptat pentru a obtine un numar diferit de

este

Am folosit aici

pentru

Acum avem 2 numere extrase. De cate extrageri mai avem nevoie pentru un al treilea numar?

Rationand analog, numarul de extrageri estimat este

etc.

Deducem, in final, c? num?rul de extrageri c?utat este

care este aproximativ

Tot este bine... desi am fost pe langa rau, se obtine acelasi numar rational:

sage: 49 * sum( [ 1/k for k in range( 1, 50 ) ] )
13881256687139135026631/63245806209101973600

Hm, numere armonice...