Pagini: 1 [2] 3   În jos
  Imprimă  
Ajutor Subiect: Intrebare de interviu pe Wall Street  (Citit de 34267 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
cristi8
Strain
*

Karma: 7
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #25 : Februarie 27, 2012, 20:00:26 »

@cristi8, da, deci in cazul cu 1/2 si 1 demonstratia nu e suficienta pentru a alege unul din aceste rezultate. stim doar ca e unul din ele. trebuie demonstrat altfel ca X < 1 (practic asta nu e demonstrat de recurenta ta).

Pai da, ar mai trebui demonstrat asta. Cosmin a zis o idee interesanta, dar ceva riguros e mai greu de gasit.

Ai vreo idee cum s-ar putea demonstra?
Memorat
Robybrasov
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #26 : Martie 01, 2012, 22:52:25 »

Eu cred ca am putea modela scenariul cu probabilitati de trecere. In cazul in care avem o singura conditie, ele sunt de fapt probabilitati conditionale, unde probabilitatea evenimentului al doilea depinde de cea a primului eveniment. Cu alte cuvinte, primul eveniment influenteaza decursul celui de-al doilea.

La probabilitatile de trecere insa, putem considera oricat de multe evenimente, si nu doar doua, ca la cele conditionale. Voi da un scurt exemplu cu bile sa clarific probabilitatile de trecere. Cei ce sunt familiarizati cu acest subiect pot sari peste exemplu.

Avem 4 bile: 1 rosie si 3 negre. Cand scoatem o bila ii notam culoarea si o punem inapoi cu inca o bila de aceeasi culoare. Ne intereseaza probabilitatea ca a doua bila scoasa sa fie rosie. Daca scoatem prima oara una rosie o sa avem inainte de a doua tragere 2 rosii si 3 negre, iar daca scoatem una neagra o sa avem 1 rosie si 4 negre. Prima oara tragem una rosie cu probabilitate 1/4 si cu prob. 3/4 una neagra. A doua oara tragem cu prob. 2/5 una rosie (daca prima a fost rosie), respectiv cu 1/5 una rosie (daca prima a fost neagra). Adica, daca am nimerit cu probabilitatea 1/4 una rosie si implicit in urna o sa fie la a doua tragere 2 rosii si 3 negre, vom avea 2/5 probabilitate sa nimerim una rosie, deci in total 1/4 * 2/5. La fel in cazul in care tragem prima neagra, unde vom avea o probabilitate de 3/4 * 1/5 ca a doua sa fie rosie. Cu alte cuvinte avem o probabilitate de 1/4 ca a doua probabilitate sa fie 2/5 (prima rosie) si o probabilitate de 3/4 ca a doua probabilitate sa fie de 1/5. Apoi le insumam si obtinem probabilitatea totala ca a doua bila trasa sa fie rosie de 1/4 * 2/5 + 3/4 * 1/5. Putem extinde acest experiment pe oricat de multe trageri. De exemplu putem spune ca, daca a doua bila trasa a fost rosie, mai adaugam doua negre si daca a doua a fost neagra, putem scoate una rosie, sau orice altceva. Probabilitatea se calculeaza analog prin insumarea produselor fiecaror probabilitati. Nu intru in detalii tehnice aici. Vom folosi exact aceasta idee, pentru a modela scenariul din problema.

Am pus aici un document, in care am scris calculele in LaTeX impreuna cu explicatia, ca altfel nu se intelegeau prea multe. Pe aceeasi idee intuitiva vad ca au mers si unsilviu si balakraz94, amandoi avand probabilitatea ca furnica sa cada la fel ca si mine de 3/7. quicksand are si el aceeasi probabilitate. El face cumva cu probabilitati conditionale, dar nu m-am uitat prea atent.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #27 : Martie 01, 2012, 23:28:22 »

Nu e 3/7, nu ai vazut ca am bagat simulare si da 1/2 Ai citit ce s-a discutat mai sus?
Memorat
Robybrasov
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #28 : Martie 02, 2012, 01:40:10 »

Da am citit. Imi dau acum seama, ca probabilitatea de a ajunge din 2 in 0 nu e 1/3 * 1/3, ci e mai mare, pentru ca poti merge din 2 in 1, apoi din 1 in 2 si tot asa. Pentru un a_i probabilitatea de a ajunge la 0 va fi de forma 1/3 * a_{i - 1} + 2/3 * a_{i + 1}.
Memorat
pricop_stfn
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #29 : Martie 02, 2012, 11:49:22 »

Am mai auzit de intrebari pt angajare pe Wall Street(MS, Apple s.a.m.d) si de obicei toate erau capcane... in cazul asta nu prea am vazut furnici care cad de pe pereti, indiferent daca sunt de prapastii sau nu Evil or Very Mad
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #30 : Martie 11, 2012, 17:31:21 »

Incredibil! Ma uimeste cum atatea minti luminate nu s-au prins pana acum!

Daca p>0 atunci rasupunsul este ZERO, pentru orice p.

Daca p=0 atunci raspunsul este 1.

http://en.wikipedia.org/wiki/Almost_surely
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #31 : Martie 11, 2012, 18:56:09 »

Principiul enuntat acolo nu se aplica la problema asta.
Memorat
Vman
Echipa infoarena
Vorbaret
*****

Karma: 45
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #32 : Martie 11, 2012, 19:12:33 »

Am mai auzit de intrebari pt angajare pe Wall Street(MS, Apple s.a.m.d) si de obicei toate erau capcane... in cazul asta nu prea am vazut furnici care cad de pe pereti, indiferent daca sunt de prapastii sau nu Evil or Very Mad

Nu stiu de unde ideea asta cu intrebarile capcana, am dat peste 10 interviuri si nu am primit nicio intrebare capcana. Eventual se mai dau intrebari "ciudate" ca sa vada cum gandesti si cum iti dezvolti ideile, dar capcane de genul asta in niciun caz.
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #33 : Martie 11, 2012, 19:17:39 »

Bine, hai sa si explic Smile.

I: "Presupunem prin absurd ca P = Pr { furnica supravietuieste la infinit } > 0"

Daca furnica traieste minim k pasi, dupa cei k pasi, pozitia furnicii poate fi descrisa de un sir de 0 (reprezentand mutare la stanga) si 1 (mutare la dreapta) reprezentand rezultatul a k evenimente aleatorii. Ceva gen:

1101011010101111101010101010101010101101011111.....

E clar ca nu toate sirurile de 1 si 0 de lungime k descriu o instanta valida de k pasi soldata cu supravietuirea furnicii (E necesar ca nr. de 0 sa fie >= nr. de 1).

Fie Z[k] = pozitia maxima a furnicii dupa k pasi. E usor de observat ca Z[k] = k.

Fie X[k] = Pr {furnica nu cade in prapastie primii k pasi} si Y[k] = Pr{furnica face k pasi consecutivi la stanga}.

I = > X[k] > 0 oricare ar fi k numar natural (1). [STRICT mai mare]
Y[k] = p^k > 0 => Y[k] > 0 pt. orice k numar natural (2)

Fie Ek = "E este 'adevarat' daca si numai daca furnica face k mutari si traieste iar apoi toate mutarile furnicii sunt la stanga."

Se observa ca Ek <=> "Furnica traieste maxim 2k pasi" <=> "furnica moare in cele din urma" (3).

Pr {Ek = 'adevarat'} >= Pr {k este astfel incat X[k]>0 si furnica face Z[k] mutari la stanga dupa pasul k} = Pr {Ek = 'adevarat'} >= Pr {k este astfel incat X[k]>0 si apoi furnica face k mutari la stanga dupa pasul k} = Pr {X[k]*Y[k]} > (din (1) si (2)) 0 =>

Pr {Ek = 'adevarat'} > 0 pentru orice k numar natural (4).

Fie E = "Sirul infinit de experiente E1, E2, ... dau toate rezultat negativ".

Pr {E} = lim k {(1-E1)*(1-E2)*....*(1-Ek)} = un produs infinit de valori SUBUNITARE (c.f. (4)). = 0.
[Intuititv, e ca si cum ai incerca de un infinit de ori sa arunci o moneda care are probabillitate > 0 de a pica stema de fiecare data cand o arunci, si totusi nu pica niciodata stema.]

Pr {E} = 0 => Pr {!E} = 1 => Daca incerc de un infinit de ori => Pr {Exista k, a.i. Ek se produce} = 1 => Exista un k a.i. Ek se produce => (3) "furnica moare in cele din urma" => Ipoteza I este falsa.

qed
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #34 : Martie 11, 2012, 19:49:45 »

In primul rand mi se pare ca daca Ek = probabilitatea ca furnica sa moara dupa maxim k pasi, atunci Ek cam include toti Ej cu j < k, ceea ce nu e foarte ok.
Sa zicem ca Pk e probabilitatea ca furnica sa moara dupa exact k pasi. Acum probabilitatile sunt disjuncte.
Probabilitatea sa nu mori niciodata e (1 - lim k-> inf Suma valorilor Pk).
Ori asta nu prea mai e 0.
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #35 : Martie 11, 2012, 20:01:39 »

Am dreptate. Citeste cu mai multa atentie.
De asemenea, vezi ca ai mai multe erori matematice in argumentele expuse de tine.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #36 : Martie 11, 2012, 20:04:24 »

Fii mai specific.
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #37 : Martie 11, 2012, 21:46:42 »

1. Pk-urile, asa cum le-ai definit tu nu sunt independente. Furnica moare fix la pasul k => furnica traieste k-1 pasi.
2. Randul 3 nu implica randul 4: Limita unui sir de sume, ai caror termeni descresc nu este neaparat marginita. Vezi 1 + 1/2 + 1/3 + 1/4 + 1/5 +... . 
Vezi si lim 1 + 1/2 + 1/4 + 1/8 + 1/16 = 2.
3. Chiar si daca Pk ar fi independente, probabilitatea sa se produca fie P1, fie P2, ... , fie Pk este P1 + (1-P1)*P2 + (1-P1)*(1-P2)*P3 + ... , pentru orice k NATURAL.

Si, oricum, vezi eu am definit Ek diferit de cum ai spus tu.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #38 : Martie 11, 2012, 22:26:03 »

Sunt constient ca limita sumei unui sir descrescator nu este neaparat marginita. Ideea e ca e suma si nu produs.
Eu am spus ca sunt disjuncte, nu independente. Daca moare la pasul k nu poate muri la alti pasi. Daca moare la pas < k, inseamna si ca poate muri la pas < i, pentru toti i < k..
Avand in vedere ca evenimentele posibile sunt moarte la pasul k pentru k natural sau sa nu moara, e clar ca P1 + P2 + ....Pk + P_sa_nu_mori = 1, deci P_sa_nu_mori = 1 - (P1 + P2 + .. Pk).
In orice caz.. rezultatul este limita unei sume si nu a unui produs, ceea ce iti submineaza argumentul principal, cel al produsului unui numar infinit de termeni subunitari.
« Ultima modificare: Martie 11, 2012, 22:32:16 de către Mihai Calancea » Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #39 : Martie 11, 2012, 23:38:15 »

Nu are rost sa mai continui. Iti propun urmatorul targ, Mihai Calancea:

Tu alegi un x constant si un p > 0. Eu iti platesc tie 10*x*"Raspunsul problemei pentru p" ron si tu mie x * (1-"Raspunsul problemei pentru p") ron. Ce zici, esti de acord?
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #40 : Martie 12, 2012, 00:02:44 »

Nu are rost sa continuam fiindca de fapt nu e o conversatie. Din punctul meu de vedere e o discutie despre o problema, in care sunt deschis la ideea ca e posibil sa fi gresit eu, dar imi apar parerea fiindca mi se pare valida si nu mi-ai demontat-o inca. Din punctul tau de vedere, probabil, sunt comentariile frustrate ale unui individ inferior care nu iti intelege solutia revolutionara. Pe mine personal ma deranjeaza tonul tau Smile. Daca te uiti un pic pe topicul asta ai sa vezi ca multa lume a oferit solutii chiar confirmate prin simulare. E super in regula sa ai o parere diferita de a majoritatii. Nu prea e ok sa o impui ca fiind solutia absoluta, desconsiderand orice argument pentru alternative, doar fiindca este solutia ta.

Ma retrag si eu ca nu are sens sa ne inraim dintr-o prostioara de genul asta:). Good luck and have fun.
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #41 : Martie 12, 2012, 01:50:58 »

Presupun ca am fost putin cam intransigent, convins fiind de corectitudinea demonstratiei mele. Ce rost are sa asculti argumente care pun la indoiala ceva ce ai demonstrat deja, nu? Smile. La fel si din punctul tau de vedere... Daca ceva e "confirmat prin simulare", cine ignora orice argumentatie contra, 'face pe desteptul', nu?

Revenind la problema, rezultatul meu este corect. Demonstratia in schimb are o scapare.

Am zis:
Fie E = "Sirul infinit de experiente E1, E2, ... dau toate rezultat negativ".
Pr {E} = lim k {(1-E1)*(1-E2)*....*(1-Ek)} = un produs infinit de valori SUBUNITARE (c.f. (4)). = 0.


Ultima egalitate nu este intotdeauna adevarata (exista produse infinite de expresii subunitare care converg la ceva diferit de 0).

Dar demonstratia ar trebui sa ramana valabila.
Memorat
gcosmin
Nu mai tace
*****

Karma: 205
Deconectat Deconectat

Mesaje: 307



Vezi Profilul
« Răspunde #42 : Martie 12, 2012, 04:47:59 »

Revenind la problema, rezultatul meu este corect. Demonstratia in schimb are o scapare.

Am zis:
Fie E = "Sirul infinit de experiente E1, E2, ... dau toate rezultat negativ".
Pr {E} = lim k {(1-E1)*(1-E2)*....*(1-Ek)} = un produs infinit de valori SUBUNITARE (c.f. (4)). = 0.


Ultima egalitate nu este intotdeauna adevarata (exista produse infinite de expresii subunitare care converg la ceva diferit de 0).

Dar demonstratia ar trebui sa ramana valabila.

Tocmai ca demonstratia nu este valabila. Uite-te la produsul unui sir de genu (1-(1/3)^k). Vezi: http://www.wolframalpha.com/input/?i=product_%28k%3D1%29%5Einf+%281+-+%281%2F3%29%5Ek%29

Deci daca Ek scade exponential atunci produsul ala nu e deloc 0. Si dupa cum ai definit tu Ek = prob ca furnica sa mearga k pasi si sa nu moara apoi sa faca toate mutarile la stanga = ceva numar intre 0 si 1 * p^k => Ek scade exponential
Asadar nu este deloc adevarat ca produsul tau de numere subunitare este 0.

Daca tot nu esti convins ca rapunsul e 1/2 citeste urmatoarele doua posturi:
http://mindyourdecisions.com/blog/2010/11/30/puzzle-a-drunkard-and-a-cliff/
http://everything2.com/title/Solution+to+the+Drunk+Guy+on+a+Cliff+Puzzle
« Ultima modificare: Martie 12, 2012, 04:59:56 de către Gheorghe Cosmin » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #43 : Martie 12, 2012, 10:20:46 »

Hmm, pare ca "mintile luminate" aveau dreptate pana la urma Shocked.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #44 : Martie 12, 2012, 10:30:00 »

Se pare ca m-am inselat afirmand ca rezultatul e 1 pentru orice p>0. In particular, pentru p = 1/3, probabilitatea e fix 1/2.  Smile.

Totusi,am reusit sa arat:
 - pentru p<1/2, raspunsul e fix p/(1-p).
 - pentru p>=1/2 raspunsul e 1.

Iata si demonstratia:

Cod:
Fie s o secventa de 0,1. 
Notam len[s] = lungimea secventei, n0[s] = nr. de 0 din s, n1[s] = nr. de 1 din s si Pr[s]=p^n0*(1-p)^n1.

Fie X[k] = Pr{furnica traieste k pasi} = Sum ( Pr[s] | len[s]=k si pentru orice prefix t al lui s, avem n0[t]<=n1[t])

x[k][1] = Pr{furnica traieste k pasi si se afla la pozitia 1 in final} = Sum ( Pr[s] | len[s]=k si pentru orice prefix t al lui s, avem n0[t]<=n1[t] SI n1[s]=n0[s]=k/2) = [p*(1-p)]^(k/2) * Count (s | len[s]=k si pentru orice prefix t al lui s, avem n0[t]<=n1[t] SI n1[s]=n0[s] SI n1[s]=n0[s]=k/2) = [p-p^2]^(k/2) * f(k/2).

Observam despre f:

f(0) =conventie 1.
f(j) = Sum i=1..j { g(i) * f(j-i) }, unde g(i) = Count { s | n0[s]=n1[s]=i si pt. oricare prefix t al lui s, avem n1[s]>n0[s]}

Se observa ca g(i) = f(i-1). //Pt. orice sir s numarat de f(i-1), exista 1s0 numarat de g; Pt. orice sir t numarat de g => t se termina in 0. Cum t incepe cu 1 => t e de forma 1x0, cu x balansat.

f(j) = Sum i=1..j {f(i-1)*f(j-i)}.

=> f(j+1) = Sum i=0..j {f(i)*f(j-i)}
=> f(j) = Catalan (j) [http://en.wikipedia.org/wiki/Catalan_number#First_proof]

Deci x[2*j][1] = (p-p^2)^j * f(j).

Fie R[k] = Pr {furnica moare dupa cel mult 2k+1 pasi}.

R[k] = R[k-1] + Pr {furnica traieste 2*k pasi si se afla la pozitia 1 in final} * Pr {furnica muta la stanga la pasul 2k+1}

=> R[k] = R[k-1] + X[k][1]*p = R[k-1] + (p-p^2)^k*Catalan[k]*p.
=> R[k] = Sum i=0..k ((p-p^2)^k * Catalan[k]*p).

Raspunsul cautat P = lim {R[k]} dupa k=0..infinit.

Dintr-un motiv sau altul pentru p<1/2 ea converge la p/(1-p) si daca p>=1/2 la 1.

Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #45 : Martie 12, 2012, 11:52:12 »

Se pare ca m-am inselat afirmand ca rezultatul e 1 pentru orice p>0. In particular, pentru p = 1/3, probabilitatea e fix 1/2.  Smile.

Totusi,am reusit sa arat:
 - pentru p<1/2, raspunsul e fix p/(1-p).
 - pentru p>=1/2 raspunsul e 1.

Iata si demonstratia:

Cod:
Fie s o secventa de 0,1. 
Notam len[s] = lungimea secventei, n0[s] = nr. de 0 din s, n1[s] = nr. de 1 din s si Pr[s]=p^n0*(1-p)^n1.

Fie X[k] = Pr{furnica traieste k pasi} = Sum ( Pr[s] | len[s]=k si pentru orice prefix t al lui s, avem n0[t]<=n1[t])

x[k][1] = Pr{furnica traieste k pasi si se afla la pozitia 1 in final} = Sum ( Pr[s] | len[s]=k si pentru orice prefix t al lui s, avem n0[t]<=n1[t] SI n1[s]=n0[s]=k/2) = [p*(1-p)]^(k/2) * Count (s | len[s]=k si pentru orice prefix t al lui s, avem n0[t]<=n1[t] SI n1[s]=n0[s] SI n1[s]=n0[s]=k/2) = [p-p^2]^(k/2) * f(k/2).

Observam despre f:

f(0) =conventie 1.
f(j) = Sum i=1..j { g(i) * f(j-i) }, unde g(i) = Count { s | n0[s]=n1[s]=i si pt. oricare prefix t al lui s, avem n1[s]>n0[s]}

Se observa ca g(i) = f(i-1). //Pt. orice sir s numarat de f(i-1), exista 1s0 numarat de g; Pt. orice sir t numarat de g => t se termina in 0. Cum t incepe cu 1 => t e de forma 1x0, cu x balansat.

f(j) = Sum i=1..j {f(i-1)*f(j-i)}.

=> f(j+1) = Sum i=0..j {f(i)*f(j-i)}
=> f(j) = Catalan (j) [http://en.wikipedia.org/wiki/Catalan_number#First_proof]

Deci x[2*j][1] = (p-p^2)^j * f(j).

Fie R[k] = Pr {furnica moare dupa cel mult 2k+1 pasi}.

R[k] = R[k-1] + Pr {furnica traieste 2*k pasi si se afla la pozitia 1 in final} * Pr {furnica muta la stanga la pasul 2k+1}

=> R[k] = R[k-1] + X[k][1]*p = R[k-1] + (p-p^2)^k*Catalan[k]*p.
=> R[k] = Sum i=0..k ((p-p^2)^k * Catalan[k]*p).

Raspunsul cautat P = lim {R[k]} dupa k=0..infinit.

Dintr-un motiv sau altul pentru p<1/2 ea converge la p/(1-p) si daca p>=1/2 la 1.


M-am prins cum sa demonstrez complet.
Ramasese de aratat ca P converge la p/(1-p) daca p<1/2 si la 1 altfel.
Folosind notatiile de mai sus, avem:

Cod:
Fie T[k] = R[k]-R[k-1] cu T[-1]=0.

Fie H[i] = T[i+1]/T[i].
T[i] = H[i]*T[i-1].
T[i+1] = H[i]*H[i-1]*...H[1]*H[0]*T[0].

P = T[0] ( 1 + H[0] + H[0]*H[1] + H[0]*H[1]*H[2]+...)
P = p * (1 + V[0] + V[1] + V[2] + ...), V[k] = H[0]*H[1]*..*H[k].

H[k] = T[k+1]/T[k] = (p-p^2)^k * (p-p^2) * Catalan[k+1]*p / [(p-p^2)^k * Catalan[k]*p] = (p-p^2) * Catalan[k+1] / Catalan[k], p>0.

Fie a = (p-p^2).

V[k] = a*Catalan(k+1)/Catalan(k)*V[k-1] = a*Catalan(k-1)/Catalan(k) * a * Catalan(k)/Catalan(k-1) * .... * a * Catalan(2)/Catalan(0) => V[k] = a^(k+1)*Catalan(k+1)

=> P = p * (1 + Sum k {a^(k+1)*Catalan(k+1)}). = p * (1+B-1) => P = p*B.

B = Sum k {a^k * Catalan(k)}, k = 0..+inf.

Daca p<1/2 => a<1/4
-----------

B = 2/(sqrt(1-4a) + 1) [http://www.wolframalpha.com/input/?i=Sum%28a%5Ek*CatalanNumber%28k%29%29%2C+k%3D0..infinity]

Cum 1-4a = 1-4*p+4*p^2 = (1-2*p)^2

=> B = 2/(1-2*p+1) = 2/(2-2*p) = 1/(1-p).
=> P = p/(1-p).

Daca p=1/2 => a=1/4
-----------

B = Sum k {1/4^k * Catalan(k)}
B = 2 [http://www.wolframalpha.com/input/?i=Sum%281%2F4%5Ek+*+CatalanNumber%28k%29%29%2C+k%3D0..infinity].
=> P = 1/2*2 = 1.

Daca p>1/2 => a<1/4
-----------

B = 1/(1-p) => P = p/(1-p). Dar cum p>1/2 => p>(1-p) => P>=1 => P = 1.

Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #46 : Martie 12, 2012, 14:01:47 »

In concluzie, sintetizand:

Probabilitatea ca furnica sa pice in prapastie este, in functie de p, astfel:
 - p/(1-p) , daca p<1/2
 - 1 daca p >= 1/2.

Ca atare, probabilitatea ca ea sa NU cada este, in functie de p, astfel:
 - (1-2p)/(1-p), daca p<1/2
 - 0, daca p>=1/2.
Memorat
cosminp
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #47 : Martie 14, 2012, 01:58:14 »

Intamplator am gasit solutia pt p=0.5 la pag.327 in documentul de mai jos. Nu am citit cu atentie toate comment-urile insa sunt convins ca va fi mai usor de inteles si de generalizat.

http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #48 : Martie 14, 2012, 02:09:29 »

AM DEMONSTRAT CA RASPUNSUL ESTE 0 PENTRU ORICE p>0!!!!

Practic limita calculata anterior nu corespundea Raspunsului pe un spatiu probabilistic!! Acum chiar am demonstrat!
N-am apucat sa ma uit pe documentul din comentariul anterior, dar sunt convins ca imi va da dreptate:).

Just wait and see! Revin si cu demonstratia momentan!
Memorat
MirceaD85
Strain
*

Karma: -32
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #49 : Martie 14, 2012, 03:34:50 »

Bun, revenind... Se pare ca "mintile luminate" n-au avut dreptate pana la urma! Raspunsul este 0 pentru orice p>0, ceea ce corespunde intuitiei.

Este esential modul in care este formalizata problema. Cum intrebarea este "Care este probabilitatea sa...", deducem ca problema trebuie formalizata intr-un spatiu probabilistic [http://en.wikipedia.org/wiki/Probability_space].

Conteaza foarte mult cum este definit spatiul probabilistic. El TREBUIE definit astfel incat tot enuntul problemei sa poate fi exprimat in cadrul sau.

Fie Nron multimea numerelor naturale si NULL multimea vida.

Enuntul problemei poate fi descris astfel:
 - Femron = C U A, unde:

  C = "furnica nu cade niciodata" - concluzia. De remarcat ca OBLIGATORIU C apartine lui Femron, altminteri C nu apartine nici Omega (C nu este eveniment in spatiul probabilistic), din inchiderea lui Femron la complement. Fie ~C complementul lui C. Din inchiderea lui Femton la Complement => ~C apartine Femton.

  A este multimea starilor furnicii dupa (orice) numar *finit* de momente. A = U M'i, dupa i moment. Unde M'i = {~c}i U N'i. Unde {~c}i = "Furnica paseste in groapa in momentul i" iar N'i este multimea starilor nongroapa la care furnica poate ajunge dupa fix i pasi. Fie N' = U N'i. Exista o injectie de la A la B = (M X (N' U {~c})), definit mai jos.

  B = M X (N' x {~c}) reprezinta starea furnicii la momentul m din M'. Furnica poate sa se gaseasca la momentul m din M pe pozitia n din N' sau ea sa paseasca in groapa (cazul {~c}) fix in acel moment. De remarcat ca (m,{~c}) inclus in ~C = Complement(C) pentru orice m, din ipoteza naturala (I1): C => "nu exista un moment la care furnica sa fi pasit in groapa".

  M este multimea momentelor. Daca presupunem ca momentele sunt discrete (I2), M este determinata de inchiderea lui {moment_0} (momentul initial) la operatia "moment ulterior" succ. Am aplicat ipoteza ca exista succesorul oricarui moment (necesara pentru a putea exista termenul "la infinit"). Daca deciziile stanga/dreapta la diferite momente sunt independente (I3) atunci Succ este obligatoriu injectiva => (M, succ) ~ (Nron, suc). Deci M este o multime izomorfa cu Nron. Cum Ni U {~c}i este o multime finita => A ~ Nron. Cum B ~ Nron => A~B => Putem considera A = B, fara a afecta vreun rezultat in spatiul probabilistic.

  N' este multimea pozitiilor pe care furnica poate ajunge. (N',+) este din enunt (R,+). Dar cum singurele elemente supuse operatiei + sunt numere naturale, putem limita N' ~ Z. Mai mult, cum enuntul nu precizeaza cum sunt determinate stari ulterioare celei in care furnica a cazut in prapastie, vom presupune ca (I4) nu exista o stare ulterioara picajului in groapa al furnicii. Ca atare, putem limita N' ~ Nron+. Cum {~c} ~ {0}, putem, fara a pierde generalitate, lua {c} = {0}. Ca atare, N' U {~c} ~ Nron. N.B.!!!: Daca (1-p)>0 (I5), atunci |N'|>=|M|=(sub I2 si I3)|Nron|. Deci nu putem limita mai mult. 

Notam cu Fm,i elementul (m,i) din M X (N' U {~c}). Notam cu Fm = U Fm,i dupa toti i din N' (fara {~c}).

Functia de probabilitate P trebuie sa satisfaca:
 a) P(Fm+1,0 | Fm1) = p, pentru orice m //Furnica moare cu probabilitate egala cu a pasi in stanga, daca se afla anterior pe pozitia 1.
 b) P(Fm+1,0 | Complement(Fm1)) = 0, //Furnica nu moare daca nu era anterior pe pozitia 1.
 c) P(Fm+1,i | Fm,i+1) = p, i>0 //Furnica muta stanga
 d) P(Fm+1,i | Fm,i-1) = 1-p, pentru i>1 //Furnica muta dreapta
 e) P(Fm,i | Complement(Fm,i+1) Inters Complement(Fm,i-1)) = 0, i>1 //Nu exista alt mod de a ajunge la momentul m pe pozitia i.
 f) P(Fm,1 | Complement(Fm,2)) = 0
 g) P(F0,1) = 1, F(0,0)=0, P(F0,i) = 0, pentru orice i != 1. // Initializare pozitie
 h) P(Fm,i Inters Fm,j) = 0, pentru orice i!=j //La un moment dat, furnica se afla intr-o singura pozitie, i.e. evenimentele Fm,i si Fm,j sunt independente.

Acestea sunt conditii NECESAR satisfacute de un spatiul probabilistic care descrie problema. Daca exista un astfel de spatiu, conditiile sunt si suficiente. Acum vom arata ca in aceste conditii P(C) = 0.
---

Presupunerea absurda 0 (P0)
---------------------------
Presupunem prin absurd P(C) > 0  => C != NULL.

Fie ~Cm = U Fk,0 dupa k<=m => ~Cm = "furnica moare in cel mult m pasi". Din inchiderea lui Femton la reuniune numarabila => ~Cm apartine Femton.

Lemma (A): Pentru orice m, P(Fm) = 1 - P(~Cm), pentru orice k<m natural.
----------
P(F0) = Sum(U P(F0,i)) = P(F0,1) = 1. Prin inductie dupa m,

P(Fm) = p1 + p2 + ... - P(~Cm)// cu pi = P(Fm,i).

P(Fm+1) =
 p1* p - p1*p // = 0
          + p2 * p  + ...  +  //din (c)
 p1*(1-p) + p2*(1-p) + ... // din (d)
 
= p1 + p2 + p3 + .... - p1*p =inductie P(Fm+1) - P(~Cm) - p1*p = P*(Fm+1) - P(~Cm+1).
---

Fie F'm = Fm U ~Cm. Din inchiderea lui Femton la reuniune => F'm apartine Femton.
P(F'm) = P(Fm) + P(~Cm) =(A) 1 - P(~Cm) + P(~Cm) = 1.

Fie ~F'm = Complement( F'm ). Din inchiderea lui Femton la complement => ~F'm apartine Femton.
P(~F'm U Fm) = P(~F'm) + P(F'm)  =>
P(Omega) = P(~F'm) + P(F'm) =>
1 = P(~F'm) + 1 =>
P(~F'm) = 0.

Lemma (B): Pentru orice m, si A din Femton, cu A \ F'm = NULL => P(A)=0.
----------
Fie A inclus in Femton, a.i. A \ F'm = NULL. => A Inters F'm = NULL => A inclus in ~F'm. => P(A) <= P(~F'm) = 0 => P(A) = 0.
---

Lemma (C): Daca F'm \ X = A => P(A) = 0, pentru orice m moment si A din Femton.
----------
Din ipoteza => A \ F'm = NULL. Din (B) => P(A) = 0.
---

Lemma (D): P(F'm\C) = 0.
----------
F'm\C = (F'm Inters ~C). Cum F'm este in Femton si ~C este in Femton => F'm\C este in Femton =>(C) P(F'm\C)=0.
---

Teorema (T1): P(C Inters F'm) = P(C), pentru ORICE m.
------------
Fie X = C Inters F'm
Fie Y = C\F'm.
=> X, Y disjuncte.
=> C = X U Y.

P(Y) = P(C\F'm) = P(C Inters ~F'm) = P(O\(O\~F'm U O\C)) = 1-P(F'm U ~C).
P(F'm U ~C) >= P(F'm) = 1 => P(Y) <= 1 - 1 = 0 => P(Y) = 0.

P(C) = P(X) + P(Y) = P(X) + 0 = P(C Inters F'm).
---

Teorema (T2) P(C) = 1
------------
Aplicam T1 pentru m = 0.
Cum ~C0 = 0 =>
P(C) > 1 => P([F0 U ~C0] Inters C) > 0 => P(F0 Inters C) + 0 > 0 => P(F0 Inters C)>0. Cum F0 este numarabila (e chiar finita) => (Exista) e0 apartine F0 Inters C, a.i. P(e0)>0 => e0 = F0,1 => F0,1 apartine C => P(C)=1.
F0,1 inclus in C (toate celelalte au probabilitate 0) => P(C)=1.

//Ca fapt divers, orice m as alege => Exista un Fm,i cu i>0 (Fm,0 apartine ~C) apartine C ==> F1,0 apartine C.

Teorema T P(C) = 0
---------

P(C) = 1 => P(~C) = 0 => P(orice x inclus in ~C)=0 => P(C1) = 0.
Dar P(C1) = P(F1,0) = p.
Din I5 p > 0 => P(~C)>0 => P(C)<1 contradictie cu T2 => Presupunerea absurda P0 este FALSA!!

qed.

Concluzie: Daca cele 4 ipoteze I1, I2, I3, I4,I5 de mai sus sunt adevarate (intuitiv este sa fie) atunci raspunsul este 0.

I1: "furnica nu cade niciodata" => "nu exista un moment la care furnica sa fi pasit in groapa".
I2: "momentele sunt discrete" (i.e. exista succesorul unui moment).
I3: "deciziile stanga/dreapta la diferite momente sunt independente"
I4: "nu exista o stare ulterioara picajului in groapa al furnicii"
I5: p>0
Memorat
Pagini: 1 [2] 3   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines