Intrebare de interviu pe Wall Street

[•Cosmin]

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

[•claudiumihail]

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

[•claudiumihail]

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

[•unsilviu]

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

[•Cosmin]

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

[•unsilviu]

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

[•borsoszalan]

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
Sper ca e bine.

[•quicksand]

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.

[•cristi8]

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

[•claudiumihail]

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

[•seviyor]

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.

[•cristi8]

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.

[•wefgef]

E buna solutia lui cristi8

[•cristi8]

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?

[•raduberinde]

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

[•cristi8]

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.

[•alexandru94]

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 .

[•raduberinde]

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.

[•Cristy94]

@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?

[•Cosmin]

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.

Cod:

import random

def walk(steps, position):
  while position != 0 and steps > 0:
    if random.random() <= 1.0 / 3:
      position -= 1
    else:
      position += 1
    steps -= 1
  return position != 0

iterations = 10000
steps = 100000
start = 1
count = 0
for i in range(0, iterations):
   if i % 1000 == 0:
     print '%s : %s' % (str(i), str(float(count) / (i + 1)))
   if walk(steps, start):
     count += 1

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.

[•cristi8]

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.

[•Cosmin]

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

[•balakraz94]

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  )

[•raduberinde]

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

[•Illy]

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 ?