infoarena

http://infoarena.ro/blog/interviu-wall-street

Salut,

O sa incerc sa-mi dau si eu cu parerea (disclaimer: nu prea le am cu matematica dar mi s-a aprut interesanta problema, asa ca daca aberez grav va rog nu dati cu pietre prea tare). OK, prima mea idee a fost ca evenimentele (de a face stanga sau dreapta) sunt independente la momente Tx diferite. Adica daca faptul ca furnica a facut stanga sau dreapta la momentul T nu influenteaza probabilitatea ca furnica sa faca ori stanga ori dreapta la momentul T+1. Deci daca am dreptate atunci putem scrie ca probabilitatea ca furnica sa _nu_ moara la icneput este 1 - probabilitatea_de_a_merge_spre_stanga = 1 - 1/3. La momentul 1 presupunand ca furnica a facut dreapta probabilitatea de a nu muri va fi (1-1/3) * (1 - 1/3 * 1/3) sau (1-1/3) * (1-1/9). Am scos acel 1/9 gandindu-ma ca la momentul 1 probabilitatea sa moara este probabilitatea de a face doi pasi spre stanga. De aici probabilitatea sa _nu_ moara vine cam 1-1/(3^2). Inmultind si cu probabilitatea sa nu fi murit la momentul anterior da  (1-1/3) * (1 - 1/(3^2)). Presupunand ca nu s-a rupt filmul corectitudinii mele pana acuma m-am gandit sa generalizez asta si am scos ceva gen:

produs de la n=1 -> +oo din (1 - 1/3^n)

Presupunand din nou ca nu am aberat crunt pana aici, pana acuma a fost matematica destul de elementara (deci rusine sa-mi fie daca am facut praf). De aici incolo sa calculeze limita din produs infinit m-a depasit. Dar am stat ceva si am cautat pe net cum se calculeaza un produs infinit din ceva gen

1 - 1/x^n (sau 1 - 1/p^n in cazul nostru)

si am gasit asta http://mathworld.wolfram.com/TreeSearching.html?affilliate=1  (http://mathworld.wolfram.com/TreeSearching.html?affilliate=1) unde pe la Flajolet and Richmond 1992 mentioneaza ceva ce seamana izbitor cu ce am gasit eu. Dupa cateva iteratii imi da ca probabilitatea la infinit ca furnica sa nu moara e ceva gen 0.5612803...

Nu sunt foarte convins ca n-am aberat crunt asa ca va rog sa ma corectati daca gresesc.

Cheers,
Claudiu

Hmm nu prea am generalizat foarte bine pentru ca in enunt era p nu 1/p probabilitatea. Dar putems a notam k = 1/p => p = 1/k si ajungem tot in generalizarea de mai sus.

Claudiu

Eu gandesc asa:
P(cadere)=P(cad pas 1)+P(cad pas 2) +...+p(cad pas ∞)
=1/3+ 2/3*(1/3)^2+.......+(2/3)^(∞+1)*(1/3)^(∞)
=1/3*(1+2/9 + (2/9)^2+...+(2/9)^∞)
=1/3* (( (2/9)^(∞+1)-1)/(2/9-1)
=1/3*((0-1)/(2/9-1))
=(1/3)*(9/7)
=9/21~=0.42
=> p(┐cadere)=1-.42~=0.58

Gresiti amandoi la calculul probabilitatii ca furnica ajunge in prapastie la pasul i.

Intr-adevar, nu poate ajunge decat in pasul 2k+1 in prapastie...

Se poate ajunge doar in 2k+1 pasi in prapastie si ultimul pas trebuie sa fie la stanga.
In primii 2k pasi nu trebuie sa ajunga in prapastie, deci "expresia" trebuie parantezata corect.
Conform Catalan, acesta se poate face in (k,2k)/(k+1) moduri, unde (k, 2k) reprezinta combinari 2k luate cate k.
Avem k pasi la dreapta, k+1 la stanga.
Deci probabilitatea sa ajunga in 2k+1 pasi in prapasite este:
(k,2k)/(k+1)*(2/3)^k*(1/3)^(k+1) si trebuie luata suma acestora de la k=0 la oo.
Rezultat: 1/2.

http://www.wolframalpha.com/input/?i=sum+binomial%282k%2Ck%29*%282%2F3%29%5Ek*%281%2F3%29%5E%28k%2B1%29*1%2F%28k%2B1%29 (http://www.wolframalpha.com/input/?i=sum+binomial%282k%2Ck%29*%282%2F3%29%5Ek*%281%2F3%29%5E%28k%2B1%29*1%2F%28k%2B1%29)
Sper ca e bine.

Definim Xn = +1 cu probabilitatea p sau -1 cu probabilitatea (1-p)      -> al n-lea pas al furnicii
Sn = suma 1_n  Xn                                                                    -> pozitia de la momentul n a furnicii
N = min {n | Sn = 0}                                                                 -> momentul de oprire

Pr = P(furnica moare) = suma 1_inf P(furnica moare la pasul i) = suma 1_inf P(N=i) = suma 1_inf p*P(N=i | X1=1) + (1-p)*P(N=i | X1=-1)

unde, in ultima egalitate am conditionat dupa primul pas, ie:
P(N=i) = P(N=i, X1=1) + P(N=i, X1=-1) =  P(N=i | X1=1)*P(X1=1) + P(N=i | X1=-1)*P(X1=-1) = p*P(N=i | X1=1) + (1-p)*P(N=i | X1=-1)
prima egalitate conform legii probabilitatii totale, iar cea de-a doua egalitate conform definitiei probabilitatilor conditionale.

Primul termen (i=1) din suma de mai sus este:
p*P(N=1 | X1=1) + (1-p)*P(N=1 | X1=-1) = p*0 + (1-p)*1 = 1-p

Deci,
Pr = 1-p + suma 2_inf p*P(N=i | X1=1) + (1-p)*P(N=i | X1=-1)
dar
P(N=i | X1=-1) = 0 pentru i>1 fiindca furnica a cazut deja in gaura la pasul 1.

Pr = 1-p + suma 2_inf p*P(N=i | X1=1)

Acum,
P(N=i | X1=1) = P (furnica incepe de la 1 si ajunge prima data la 0 in i pasi, stiind ca primul pas este +1)
= P (furnica incepe de la 2 si ajunge prima data la 0 in i-1 pasi)
= P (furnica incepe de la 2 si ajunge prima data la 1 in i-1 pasi, iar apoi urmeaza un pas -1)
= (1-p) * P (furnica incepe de la 2 si ajunge prima data la 1 in i-1 pasi)
= (1-p) * P(N=i-1)
fiindca doar am shiftat problema cu +1.

Pr = 1-p + suma 2_inf p*(1-p) * P(N=i-1)
= 1-p + p*(1-p) * suma 2_inf P(N=i-1)
= 1-p + p*(1-p) * suma 1_inf P(N=i)
= 1-p + p*(1-p) * Pr

Deci,
Pr = (1-p) / [1-p*(1-p)]

Pentru p=2/3, avem Pr = 3/7 = aprox 0.43

Nota:
* simple random walk (ie pasii posibili sunt +/-1)
* sper sa nu fi facut greseli in rationament
* am scris cele de mai sus in graba, ar fi fost frumos sa fie in LaTeX.

Fie X probabilitatea ca furnica sa ajunga pe 0 din pozitia initiala. (la infinit)
X e si probabilitatea ca furnica sa ajunga pe pozitia 1 daca ea se afla pe pozitia 2 (la infinit)

X = 1/3 + (2/3) * X^2

de unde X = 1 si 1/2, dar cum 1 e aberant, ramane X = 1/2

Hmm, tare faza cu random walk. Problema asta e legata cumva si de Gambler's ruin problem?

Matematic, pentru n pasi problema s-ar putea reduce la a calcula elementul al doilea de pe prima linie a unei matrici nxn la puterea n.
Matricea respectiva ar avea 1/3 deasupra diagonalei principale, 2/3 dedesubt cu exceptia A[1][0]=0 si in plus A[0][0]=1.
Experimental, pentru n-uri ceva mai mari numarul respectiv este 0.5.

Nu sunt totusi de acord cu explicatia lui cristi: cele doua cantitati nu sunt egale (la infinit, probabilitatea sa fie pe pozitia 1 cred ca tinde la 0). In 0 se acumuleaza, in 1 nu (pe aceasi logica, probabilitatea sa fie in 2 ar fi >2/3*X)
Recitita si inteleasa solutia lui Cristi imi pare buna :)... Si totusi, in 1 nu se acumuleaza, ceva nu imi pare ok in a egala cantitatile.

Pai nu trebuie sa se acumuleze, nu e probabilitatea sa fie la un anumit pas N pe pozitia 1. e mai degraba acelasi lucru: "sa fi ajuns cel putin odata pe pozitia 1, fiind la inceput pe pozitia 2".
Pt ca uite, daca suntem pe pozitia 2, ca sa ajungem in 0 trebuie neaparat sa trecem prin 1. si din 2 ajungem la un oricare pas in pozitia 1 cu probabilitatea X, si de acolo in 0 o sa fie tot X, chiar daca o sa creasca iar intre timp.

E buna solutia lui cristi8 :)

Am si generalizat, si daca P = "probabilitatea sa mearga o unitate la stanga", avem cele 2 solutii: X1 = P/(1-P), X2 = 1.

Tot nu mi-e clar ce e cu acel X2 = 1, pt ca daca P > 0.5, atunci X1 > 1 si ramane X2 = 1 ca probabilitatea sa ajunga pe pozitia 0 (are sens)..
Dar daca P < 0.5 (cum e in cazul asta 0.3333), atunci de ce sa ne uitam la valoarea finala 0.5 si nu la acel X2 = 1?

cristi8,

daca X e "probabilitatea sa fi ajuns cel putin odata pe pozitia 1, fiind la inceput pe pozitia 2", asta include drumuri care ajung la 1 apoi pleaca iar inspre 2 si se intorc la 1

dar tu cand faci X * X "numeri" drumurile astea de doua ori; adica daca X deja include posibilitatile in care ai fost in 1 si ai plecat inapoi in 2 si ai venit iar in 1, deci de ce mai inmultesti cu X, in loc de doar 1/3 (ar fi X = 1/3 + 2/3*X*1/3 = 3/7).

alta chestie e, "probabilitatea sa fi ajuns cel putin odata pe pozitia 1, fiind la inceput pe pozitia 2" include drumuri care ajung si in pozitia 0? Daca da, si drumrule astea sunt numarate de mai multe ori..

Exprimarea a fost intr-adevar defectuoasa.

X = probabilitatea sa ajunga in 0 daca porneste de pe pozitia 1.

Presupun ca sunt pe pozitia 2 si vreau sa calculez probabilitatea de a ajunge in 0. Fie ea = Y.

Pentru un anumit drum ce pleaca din 2, fie proprietatea A: Exista un nr minim K a.i. dupa K pasi sunt pe pozitia 1.
Este evident ca P(A | plec din 2) = X (este aceiasi problema, offsetata cu 1)

Acum, pentru drumurile care verifica proprietatea A, fie proprietatea B: drumul ajunge in 0.
Daca ignoram primii K pasi (care ne duc pe pozitia 1), avem evident P(B | A) = X. (pentru ca avem un drum infinit ce pleaca din 1)

Si drumurile care verifica ambele proprietati sunt cele care ne intereseaza.
Y = X*X.

Deci avem probabilitatea 1/3 la stanga , si 2/3 la dreapta, asta inseamna ca daca furnicuta noastra face 3 pasi facuti consecutiv  cu siguranta   1 va fi la stanga , iar 2 vor fi la dreapta , singura problema este ordinea . Pt primul pas , avem 33.33% la stanga deci o probabilitate de a nu cadea in prastie este  de 66.66% . A facut primul pas , daca , presupunem ca a facut la dreapta , sansa de a a mai ajunge la prastie este 0 , deoarece daca face un pas la stanga , automat urmatorii 2 vor fi la dreapta , deci , dupa al doilea pas teoretic , 
furnicuta nu mai  nici o sansa de a mai ajunge la prastie , deci singura posibilitatea de a ajunge in prastie este de 33% deci sansa de a nu ajunge este 66 % ,  tinand cont ca furnicutza face infinit pasi , si daca  infinit > 2, sansa ca ea sa mai ajunga vreodata la prastie este 0 , deci sansa ca furnicutza sa nu mai ajunga vreo data la prastie dupa infinit pasi este  de 100% .  .... nu-s chiar 100%sigur dar cred ca asa este solutia .

cristi8, cred ca ai dreptate.

Matei Tene, tu aici gresesti:
= P (furnica incepe de la 2 si ajunge prima data la 0 in i-1 pasi)
= P (furnica incepe de la 2 si ajunge prima data la 1 in i-1 pasi, iar apoi urmeaza un pas -1)

In primul rand ai vrut sa zici i-2 pasi in linia 2 (nu conteaza asta, ar da la fel), dar nu este corect: poate furnica ajunge prima data la 1 mai repede (in j < i-2) pasi, apoi dupa inca i-2-j pasi ajunge iar la 1, apoi urmeaza un pas -1.

@alexandru94

Probabilitate de 2/3 nu inseamna ca din 3 pasi 2 sunt 100% sigur facuti la dreapta... Daca ai o moneda ai 1/2 sanse sa cada cap, dar poti sa o arunci si de 5 ori si sa nu cada niciodata cap, nu inseamna nicidecum ca daca o arunci de 2 ori va cadea sigur o data cap si o data pajura...

Cat despre problema, nu a facut nimeni un program sa o simuleze, sa vada cu aproximatie cam cat da? :D

Solutia lui cristi8 e buna

Am bagat si ceva cod care ruleaza niste drumuri random de 100000 de pasi si numara cate nu se termina in 0.


0 : 0.0
1000 : 0.502497502498
2000 : 0.504247876062
3000 : 0.505164945018
4000 : 0.499625093727
5000 : 0.50149970006
6000 : 0.502082986169
7000 : 0.499785744894
8000 : 0.498937632796
9000 : 0.501388734585

Deci asa cum a zis cristi pe undeva pe la 1/2.

Totusi, ce-i cu solutia X = 1? de ce alegem 1/2 si nu 1? asta inca nu mi-e foarte clar..
Cateodata x1 iese din [0,1], cateodata nu. Si x2 e mereu 1.

@cristi5 Solutia cu 1 pentru p = 1/3 nu merge daca crezi ca probabilitatea sa supravietuiasca in functie de p e o functie continua pt ca f(0) = 1. Intuitiv ar trebui sa fie continua, dar nu stiu o demonstratie usoara.

Furnica pleaca de la punctul 1 si face un pas la stanga cu o probabilitate de 1/3 si la dreapta cu 2/3.

P(x) - probabilitatea de a ajunge la punctul 0 (prapastia), daca ne aflam in punctul x

P(x) = (1/3)^x + (2/3) * P(x+1), unde x -> INF

Explicatie : Probabilitatea de a te intoarce la 0 din punctul x este probabilitatea de face x pasi la stanga (cu o probabilitate de (1/3)^x) + probabilitatea de a te intoarce la 0 daca ai ajuns in punctul x+1 ((2/3) * P(x+1));

Inca nu mi-am dat seama cum sa aflu limita, dar implementand aceasta functie se pare ca probabilitatea tinde la 0.42857...

Sper ca am gandit bine si am sa incerc sa aflu cum se calculeaza limita. (Proful meu de mate nu a reusit sa o calculeze  :-k )

@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).

Intrebarea mea e: cand furnica face un pas la stanga de la 1 la 0, cade in prapastie, sau ramane pe marginea prapastiei ? Mai pe scurt, ca sa ajunga in prapastie, trebuie sa ajunga in 0 sau in -1 ?

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?

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 (http://infoarena.ro/utilizator/robybrasov?action=download&file=rezolvare.pdf&safe_only=false) 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.

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

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}.

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:

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

Principiul enuntat acolo nu se aplica la problema asta.

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.

Bine, hai sa si explic :).

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

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.

Am dreptate. Citeste cu mai multa atentie.
De asemenea, vezi ca ai mai multe erori matematice in argumentele expuse de tine.

Fii mai specific.

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.

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.

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?

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 :). 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.

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? :). 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.

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

Hmm, pare ca "mintile luminate" aveau dreptate pana la urma :shock:.

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.  :).

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:

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:

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.

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 (http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf)

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!

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

Si daca tot nu sunteti convinsi, uite o demonstratie mai scurta, bazata pe computabilitate. Presupunem p>0.

Fie W = {0,1}*. E clar ca W ~ Rron (multimea numerelor reale).
Fie w = a i-lea element al lui w (de la stanga la dreapta).
Pentru w finit, negol:
Fie u(w) = w din care elimin cea mai din dreapta cifra.
Fie w_0(w) = w din care elimin cel mai din dreapta 0, daca exista.
Fie w_1(w) = w din care elimin cel mai din dreapta 1, daca exista.
Fie w_*(w) = w_0(w_*(u(w))) daca ultima cifra a lui w este 1, w_1(w_*(u(w))) altfel.
Fie n0[w] = numarul de 0 din w.
Fie n1[w] = numarul de 1 din w.

Fie r raspunsul problemei. Presupunem prin absurd r>0.

Fie M(w) functia aferenta unei masini Turing care simuleaza furnica pentru un input w din W si se opreste atunci cand furnica cade in prapastie sau cand s-a ajuns la capatul lui w si produce la output M(w). M(w) = 1 daca furnica a cazut si 0 altfel.

Observam ca M(w) = 1 => Furnica pica in prapastie CERT pe orice extensie a lui w (chiar si infinita) (1)

r>0 => Exista v din W, a.i. M(pref(v)) = 0 pentru orice prefix finit pref(v) al lui v. Altfel =>(1) nu exista v (o serie de rezultate ale samplingului randomului) pentru care furnica sa traiasca la infinit => r = 0 contradictie.
Fie v cu proprietatea de mai sus si fie V multimea elementelor cu proprietatea lui v.

Fie seturile Si,Li,Ti de siruri din {0,1}^i, pentru orice i natural. Initial S0=L0=T0 = {0,1}^0 (Empty). Si+1 = U A(s)={s 0| M(s 0) = 0} U B(s)= {s 1)} pentru orice s din Si. Li+1 = {w_*(s)|s din Si+1} Fie Ti+1 = {s din Li+1 |  |s| = i+1}

=> Multimea Si este multimea tuturor prefixelor "plauzibile" de lungime i pentru v.
=> Pentru v => pentru orice prefix vk al lui v =>  (Exista) un i a.i. vk apartine Si => Exista i a.i. w_*(vk) apartine lui Li.
=> Li este multime de prefixe "plauzibile" (pentru orice v, a carui plauzibilitate se limiteaza la prefixul i)

Prin inductie Li inclus in {Empty, 1, 11, 111, ... }. //Observam ca w_*(A(s)) apartine unui Li-k si w_*(B(s)) la fel, mai putin daca s=1111....
Dar prin inductie din nou {1}^i inclus in Li => Li = {Empty, 1, 11, 111, ... }.

Fie x din Si, i>2. v = x ..., cu |x|=i . Fie alpha maximal a.i. x = 1 y alpha, cu w_*(alpha)=l2 din Li.
Daca |alpha| = 0 => x = 1 y => w_*(1 y) este in Li => w_*(y) este in Li => alpha nu e maximal. => |alpha|>0
|alpha| > 0  => Daca |y|>0 => x = 1 y alpha, cu |alpha|>=1 => x = 1 y' 0 alpha' 1 alpha'', cu w_*(alpha'j) din Li => Alpha nu e maximal => |y|=0. => x = 1 alpha, alpha maximal a.i. w_*(alpha)=l2 din Li => x apartine {f} din w_*^-1(w(x)) cu |f|=|x|.

Fie L = U Lj dupa j.

Fie Ri = {f | f apartine w_*^-1(L) si |f|=i}.
Ri = multimea prefixelor lungime i, plauzibile in orice moment.

Fie F(i,x) = {f | f apartine w_*^-1({1}^i) si |f|=x}
Fie Gi(x) = U F(k,x) pentru k<=i.

Observam ca F(i,x) = F(i-1,x-1) 1 U F(i,x-1) 0 => F(i,x) \ (F(i-1,x-1) 1) = F(i,x-1) 0 => F(i,x-1)0 U (F(i,x-1)\F(i-1,x-1))1 = F(i,x-1) 0 => F(i,x-1)=F(i-1,x-1).
=> Gi(x)= F(i,x). //Prin inductie: G(0) = F(0,0); G(i+1,x-1) = F(i+1,x-1) U G(i,x-1) =ind F(i+1,x-1) U F(i,x-1) = U F(i+1,x-1).
i>x => Gi(x) = F(i,x) = 0.

Ri = U Gj(i) dupa j natural = U Gj(i) dupa j<=i = U F(j,i), dupa j<=i = Gi(i) = F(i,i) => Ri = {1}^i.

Cum Prefi(v) apartine Ri pentru orice i => Orice prefix finit al lui v este alcatuit doar din 1.
v real (din W ~ Rron) => = v = lim i->inf din Sum(2^Prefi(v)[j]) => v = lim ( 2^(i+1) - 1). Dar lim(2^(i+1) - 1) nu apartine R (este +infinit) => v nu exista contradictie => Ipoteza r>0 falsa!!!

Daca vreti sa vedeti demonstratiile intr-un format usor mai lizibil, ele sunt disponibile si pe blogul meu :), http://mirceadigulescu.blogspot.com/ (http://mirceadigulescu.blogspot.com/) la sectiunea Informatica si Stiinta Computationala.

Raspunsul este tot ZERO pentru p>0.

Ca sa va stimulez sa cititi demonstratiile, uite si un bonus!

Aplicand Demonstratia 2 (ad literam practic) se demonstreza si ca:

Oricare ar fi o succesiune infinita de evenimente E = E0, E1, E2, ... Ek,  cu P(Ei | ~E0 ^ ~E1 ^ ... ^ ~E(i-1))>0 pentru orice i => probabilitatea ca nici un eveniment sa nu se intample (nici unul din infinitatea aceasta) daca le probez pe toate in ordine este fix ZERO.

Eh? Merita? :)

Cred ca se generalizeaza usor la daca E ~ N, cu P(e)>0 pentru o infinitate de elementele => Pentru orice succesiune infinita de evenimente, daca le-as proba => Probabilitatea sa iasa toate fals este ZERO.

M-as baza pe faptul ca probabil (sic! :) ) infinitatea aceea este numarabila => exista un izomorfism de la ea la E => exista un izomorfism intre functia succesor al secventei alese si succesorul din E => P(secventei alese) = P(oricarei secvente ~ succesorul din E).  Practic ignor toate experientele k in care P(Ek | ^Ei care s-au petrecut ^ (^~Ei-urilor) care nu s-au petrecut pentru i < k) = 0.

Ok, deci m-am inselat afirmand ca r = 0 oricand.
Adevarul este:
r = (1-2p)/(1-p), daca p<1/2
r=0, daca p>=1/2.

O demonstratie completa si corecta este si in sectiunea 1.2 aici: http://math.arizona.edu/~faris/stoch.pdf (http://math.arizona.edu/~faris/stoch.pdf) folosind http://en.wikipedia.org/wiki/Strong_law_of_large_numbers#Strong_law (http://en.wikipedia.org/wiki/Strong_law_of_large_numbers#Strong_law).

Remember furnicuta? [Probabilitatea unui random walk infinit]. I was vindicated: Pentru orice 0<p<1, probabilitatea ca furnicuta sa nu cada niciodata in prapastie la pozitia 0, este FIX 0, indiferent de p, daca facem niste asertii foarte firesti (intuitive) despre spatiul probabilistic in care formalizam problema!
That meens, I WAS RIGHT, and EVERYBODY ELSE (incluzand Radu Berinde, Andrei Grigorean, precum si unii studenti post-doctorali si profesori chiar) WERE WRONG!

Va rog si va provoc sa ma ajutati sa descopar greseala in demonstratia de mai jos. Ofer 1500 de ron primului care ma convinge ca e gresita (tineti minte ca pe un alt pariu cu Radu Berinde am achitat suma cand m-a convins de o o greseala in alta demonstratie) sau depisteaza o eroare fundamentala in ea.

http://informatica-computer-science.blogspot.com/2012/03/variatie-pe-tema-gamblers-ruin.html

Vesti bune pentru toti iubitorii de matematica! Rezultatul corect ramane P = (1-2p)/(1-p).

In demonstratia ta:


Randul 4 ar trebui sa fie P[1] = 0 + p / d * P[1], facand substitutia din randul 1. Deci ajungi ca P[1] = p / d * P[1], simplificand prin P[1] ai 1 = p / d, deci p = d. Nicio contradictie aici.

Deci, show me the money. Credits to Stefania Ionescu care a avut rabdare sa parcurga toata demonstratia ca sa gaseasca greseala.

No, they don't!!

Multumesc pentru evidentierea greselii din demonstratia trecuta. Voi credita cei 1500 de ron dupa cum am promis.

Insa am corectat demonstratia, si cea actuala este corecta si completa. Am pus la bataie inca 1400 de ron pentru cine imi evidentiaza primul o greseala majora in ea.

http://informatica-computer-science.blogspot.com/2012/03/variatie-pe-tema-gamblers-ruin.html