infoarena

Comentarii la postul http://infoarena.ro/blog/abtibild

Nu inteleg cum ai scos formula la P(k), hai sa ii zicem E(k) :)

P(n,k) = probabilitatea ca un abtibild nou sa fie diferit fata de cele k unice din n pe care le deti deja
P(n,k) = (n-k) / n deorece toate au sansa egala si sunt n-k pe care nu le deti inca

ca sa ajungem de la k abtibilduri unice la k+1 trebuie sa facem in medie 1/P(n,k) extrageri

raspunsul va fi suma S = 1/P(n, 0) + 1/P(n, 1) + ... + 1/P(n, n-1)
S = n/n + n/(n-1) + n/(n-2) + ... + n/1
S = n (1 + 1/2 + 1/3 + ... + 1/n)

deci S e aproximativ n log n

super marfa problema :) !

E(k) sa-i zicem.

E(k) = suma cu z de la 1 la infinit din z*P(z)
unde P(z) = probabilitatea ca abia dupa z extrageri sa obtinem un pokemon diferit.
P(z) = R(k)^(z-1) * (1-R(k))
unde R(k) este probabilitatea sa nu extragi un pokemon diferit daca ai deja k pokemoni diferiti
R(k) = k/n
=> P(z) = (k/n)^(z-1) * (n-k / n)
=> E(k) = (n-k)/n * suma cu i de la 1 la infinit din (k/n)^(i-1)*i
=> (via Wolfram) E(k) = n/n-k

Fara sa ma amestec in problema efectiv vreau sa explic cum se poate calcula seria  ( fara Wolfram  :evil: )

Se considera suma partiala pentru seria geometrica 1 + x + x^2 + ... + x ^ i  = ( x^ (i+1) -1) / ( x - 1)
Se deriveaza 1 + 2 * x + 3 * x ^ 1 + .... + i * x ^ ( i - 1) + = ( i * x^(i+1) - (i+1) * x ^ i + 1 ) / ( x - 1 ) ^ 2
La limita i - > infinit termenii cu x ^ i si x ^ ( i+1 )  tind la 0  asa ca seria are suma 1 / ( x - 1 ) ^ 2 pentru orice x cu modul < 1 deci si pentru x = k / n.

In aceste conditii avem E(k) = ( n - k ) / n * 1 / ( k/n - 1 ) ^ 2 = n / ( n - k )  

Relativ la problema eu cred ca solutia e ( n ^ n ) / n ! evident daca inteleg eu corect ce se cere.

@Adrian, Eugen O demonstratie mai simpla ca pentru un eveniment ce se intampla cu probabilitatea p numarul mediu de pasi e 1/p e urmatoarea:
Fie m numarul mediu de pasi. m = 1 * p + (1 + m) * (1 - p) => m = 1/p

@Andrei Stii o demonstratie pentru O(n(1 + 1/2 + 1/3 + ... + 1/n)) = O(n log n)?

Spunea ca e aproximativ O(n log n) pentru ca lim(1 + 1/2 + 1/3 + ... + 1/n - ln n) = gamma(http://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant (http://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant)) care e destul de mica.

L= lim ( 1 + 1/2 + ... + 1/n) / ln n . Aplic Cesaro - Stolz

L= lim ( 1/(n+1) ) / (ln (n+1) - ln n) . Amplific cu n si restrang diferenta de logaritmi de la numitor ca logaritmul raportului

L= lim ( n / (n +1 ) ) / ( n * ln ((n+1)/n)) . Cand introduc n din fata logaritmului la exponentul argumentului se obtine ln e_n . Cum numaratorul -> 1 si e_n -> e obtinem

L= 1/ ln e = 1.

In legatura cu valoarea data ca raspuns la postul anterior mi-am dat seama ca am intels gresit ce se cerea  :fool:

@Adriani Alta solutie care e utila pentru marginirea mai multor serii:

1/x <= 1/[ x ] <= 1/(x - 1)
integram de la 2 la n + 1  => ln (n + 1) - ln 2 < suma i=2,n 1/i < ln n

@Cosmin

din cate stiu 1 + 1/2 + ... + 1/n se poate aproxima la ∫1/n care e ln n

aici este o explicatie mai stiintifica pentru aproximarea sumelor folosing integrale pt cei interesati - http://en.wikipedia.org/wiki/Summation#Approximation_by_definite_integrals

Andrei, asta ziceam si eu in postul anterior.

Problema este clasica si apare sub denumirea "cupon colector's problem" http://en.wikipedia.org/wiki/Coupon_collector's_problem

Solutia intreaga pe scurt:

(1) E(colectia cu n elemente) = E(1 element) + E(al 2-lea element) + .. + E(al n-lea element)

(2) P(al x+1-lea element, avand deja x elemente) = (n - x) / n

E(eveniment cu probabilitatea p) = 1 * p + (1 - p) (1 + E(eveniment cu probabilitatea p)) rezolvand ecuatia obtinem E(eveniment cu probabilitatea p) = 1 / p (3)

(1), (2), (3) => E(colectia cu n elemente) = n(1 + 1/2 + .. + 1/n) (4)

1/x <= 1/[ x ] <= 1/(x - 1)
integram de la 2 la n + 1  => ln (n + 1) - ln 2 < suma i=2,n 1/i < ln n => O(1 + 1/2 + .. + 1/n) = O(log n) (5)

(4), (5) => O(E(colectia cu n elemente)) = O(n log n)

facem 1 pas si terminam cu probabilitatea p
facem 1 + m pasi cu probabilitatea (1 - p)