Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
  • Inregistrare
Pune o întrebare

Newsletter


3,202 intrebari

6,362 raspunsuri

14,882 comentarii

2,011 utilizatori

Probabilități cu 500 de fire de lână

2 plusuri 0 minusuri
168 vizualizari
Încă o problemă drăguță cu probabilități.

Avem la dispoziție, într-o cutie, 500 de fire de lână (un fir este un segment de lână cu două capete, nu o buclă). La fiecare pas luăm câte două capete de fir la întâmplare dintre cele disponibile în cutie și le legăm unul de altul, apoi le punem la loc în cutie. Repetăm până când nu mai sunt capete disponibile. Câte bucle ar trebui să ne așteptăm să existe în cutie la finalul procedurii?
a intrebat goguv Senior (5,909 puncte) Apr 9 in categoria Matematica

1 Raspuns

2 plusuri 0 minusuri
 
Cel mai bun raspuns

Avem 500 de probleme simple, în una singură care pare complicată (cel puțin, așa mi-a părut mie până mi-a picat fisa).

Problema 1. Avem 1000 capete de fire. Luăm un capăt la întâmplare și avem la dispoziție 999 de capete libere ca să-l legăm de unu din ele, tot la întâmplare (nu-l putem lega de el însuși). Probabilitatea să facem o buclă, evident, e 1/999.

După ce am făcut nodul, ne rămân 499 de fire și 998 de capete. Asta, indiferent dacă am făcut o buclă, astfel că un fir și două capete au devenit indisponibile, sau nu, și atunci două fire au devenit un fir mai lung iar două capete au dispărut prin înnodare. 

Problema 2. Avem 998 capete de fire. Luăm un capăt la întâmplare și avem la dispoziție 997 de capete libere ca să-l legăm de unul din ele, tot la întâmplare. Probabilitatea să facem o buclă, evident, e 1/997.

La fel ca la Problema1., am mai pierdut un fir și două capete, adică două fire au devenit fie un fir mai lung și două capete au dispărul prin înnodare dacă nu s-a întâmplat să se formeze o buclă, ori, un fir și două capete au devenit indisponibile dacă am picat pe cazul favorabil adică s-a făcut buclă.

Problema 3. Avem 996 capete de fire. Luăm un capăt la întâmplare și avem la dispoziție 995 de capete libere ca să-l legăm de unul din ele, tot la întâmplare. Probabilitatea să facem o buclă, evident, e 1/995.

Seamănă problemele, nu? Ca și în cazurile anterioare, am mai pierdut un fir și două capete.

N-o mai lungesc. Tot pierzând câte două capete și un fir la fiecare nod, ajungem la problema 500:

Problema 500. Avem două capete de fire. Luăm un capăt la întâmplare și avem la dispoziție un capăt liber de care să-l legăm, tot la întâmplare.

Povestea Niels Bohr că un copil s-a dus cu o firfirea la băcan și a cerut bomboane amestecate, de mai multe feluri. Băcanul îi răspunde: De banii ăștia primești două bomboane. De amestecat le amesteci singur.

Lăsând bancurile, la Problema 500 probabilitatea, evident, e 1.

Punând la loc cele 500 de probleme într-una singură, deoarece ele sunt complet distincte și independente, pentru a calcula Așteptarea cerută A, nu avem decât să adunăm probabilitățile rezultate. Astfel,

A = 1/999 + 1/997 + 1/995 +...+ 1/5 + 1/3 + 1.

Cu ajutorul lui WolframAlpha aflăm că asta face 4,089.

Dar dacă nu aveam Wolfram Alpha?

Păi atunci aproximam sum(de la i=1 la i=500)din 1/(2i-1), cu integrală(de la 1 la 500) din 1/(2x-1) dx, că e ușoară. Știm că avem voie, de la unul din testele de divergență a seriei armonice. Substituim 2x-1 = u,  dx devine du/2, iar primitiva oricărei funcții de forma 1/u e  ln(u).

Calculând, ne iese că A = 0.5ln999 = 3,453. Cam mică față de Wolfram!

Dar îmbunătățim aproximația, prin adăugarea constantei Euler-Mascheroni, egală cu 0,577 cu aproximație. Obținem un încurajator 4,03.

Oricum, nu contează. Cum nu putem avea fracțiuni, mă aștept la 4 bucle.

a raspuns Puiu Senior (6,002 puncte) Apr 9
selectat de goguv Apr 12
Adunarea probabilitatilor nu se face decat pe probabilitatea unei reuniuni de evenimente independente.In acest caz nu e corect.Dupa parerea mea problema are ca cerinta sa aflam care numar de bucle are probabilitatea ceea mai mare ,adica media.Adica putem avea 0,1,2....500 de bucle posibile.Fiecare eveniment are o probabilitate si toate cele 500 de valori reprezinta asa numitul camp de evenimente iar ele intradevar adunate trebuie sa dea probabilitatea de 1.Cred ca in loc de 500 de fire mai elegant ar fi un numar sa zicem de 10 fire pentru a remarca valorile si modul de distributie.Cred ca o reinterpretare a problemei ajuta mai mult ,de exemplu putem considera capetele firelor ca niste bile numerotate cu acelasi numar aflate intr-o urna din care extragem cate 2 bile ,daca extragem doua bile identice avem o bucla.Dar totusi apare o intrebare fireasca datorita faptului ca sunt fire si ar fi de asteptat ca ele sa fie asezate ca un manuchi avand capetele in directii diferite ,doar ca aici lasa sa se inteleaga ca avem toate capetele intr-o singura parte caz pe care l-am considerat ca fiind.

Evenimentele sunt independente.Situația e aceeași cu a avea 500 de cutii, una cu 500 de fire, alta cu 499 de fir, alta cu 498,..., ultima cu un fir. Asta e perfect analog cu a avea o singură cutie cu 500 de fire și a face câte un nod până nu ne mai rămân capete libere. Faptul că firele se întâmplă să aibă lungimi diferite e nerelevant pentru problemă. De-aia am îngroșat literele la fiecare subproblemă, ca să se vadă că după fiecare nod pierdem un fir și două capete.

Problema cere să determinăm numărul de bucle la care ne putem aștepta în final, care înseamnă suma probabilităților fiecărui experiment.

Imaginați-vă că aveți un zar cu 999 de fețe și vreți să măsurați expectanța unicului eveniment favorabil. Ea e egală, firesc, cu 1/999.

Primiți încă un zar, cu 997 de fețe, între care una reprezintă evenimentul favorabil. Șansa evenimentului favorabil crește cu 1/997, adică valoarea așteptării de a avea evenimentul favorabil devine 1/999 +1/997, probabilitățile se adună pur și simplu. Și așa mai departe, până ajungem la ultimul zar cu o singură față,conținând cazul favorabil, care restituie probabilitatea 1.

Cu singura diferență că avem zaruri identice, vă propun următoarea analogie:

Avem un zar normal și să zicem că pe o față scrie buclă, care e cazul favorabil. Aruncarea zarului e echivalentă cu facerea unui nod. După aruncarea lui, așteptarea de a avea rezultatul buclă este egală cu probabilitatea de 1/6.

Aruncăm un alt zar. Șansa de a vedea fața buclă pe unul din ele crește, dându-ne o valoare așteptată de 1/6+1/6. Adăugând câte un zar, această așteptare crește de fiecare dată cu 1/6. Dacă am aruncat 6 zaruri, așteptarea devine 1, ceea ce e echivalent cu a spune că mă aștept să văd  o buclă pe unul din zaruri  Și tot așa, dacă arunc 12 zaruri, așteptarea evenimentului favorabil este fix 2, iar dacă arunc 13 zaruri așteptarea devine 2 și 1/6, ceea ce indică o șansă ușor mărită de a avea mai mult de două evenimente favorabile, pentru că am mai adăugat un zar.

Analogia cu perechile de bile nu pare bună. Dacă extrag o bilă, cealaltă rămâne desperecheată, pe când dacă fac un nod, capătul rămas liber se împerechează cu alt capăt. 

Poziția firelor în cutie nu văd ce importanță poate avea.

Mi se pare o soluție corectă și explicată exemplar și chiar mai mult decît era nevoie.
Aduni probabilitati si obtii numarul de bucle?
Da, adun probabilitâți de a forma o buclă și obțin numărul de bucle care mă aștept să se formeze.

Dacă aruncam 6 monede și mi se cerea să socotesc la câte steme mă aștept, adunam 6 probabilități de 1/2 și obțineam 3 steme, adică mă aștept ca 3 din 6 monede să cadă cu stema-n sus.

Așa se calculează expectația în acest tip de problemă. Aduni probabilități și obții estimarea numărului de cazuri favorabile care aștepți să se realizeze.

Ok in mare ideea e corecta .In primul rand eu am crezut gresit evident ca fiind bucla doar un fir legat la ambele capete,dar chiar si asa ideea corecta de rezolvare ramane pe medie ,asta justifica mai exact de ce ar fi 4 bucle raspunsul.Pentru ca vrea sa evaluam numarul de bucle din punctul meu de vedere rationamentul ar fi in felul urmator.Intai cate bucle ar putea sa fie si remarcam ca am putea avea de la 1 pana la 500, fiecare situatie cu sansa ei.Care situatie are sansa mai mare atunci aceea e considerata situatia la care ne putem astepta.Cum calculam probabilitatile fiecarui eveniment in parte si aici consider eveniment una din situatiile de a iesi un numar specificat de bucle.

Cazurile posibile se numara astfel initial alegem o combinatie de 2 din 1000 de fire dupa care urmatoarea alegere va fi o combinatie de 2 din 998 de fire etc ,deci ca idee asemanator cu modul de calcul din raspuns .Valoarea respectiva este egala 

 \binom{1000}{2} \binom{998}{2}.....\binom{2}{2} unde \binom{n}{k} reprezinta combinari de n luate cate k.

Pentru cazurile favorabile a unui numar sa zicem de k bucle aici trebuie numarat un pic mai altfel .Ca sa avem k bucle atunci trebuie partitionate cele 1000 fire in k parti adica ca si cum as distribui firele in k cutii dupa care le innodam in numarul de combinatii posibile astfel incat sa iasa bucla.Asta e problema mai grea sa numaram aceste moduri de a innoda sa iasa k bucle.

Încerc să fiu cât mai clar și metodic, pentru a vă convinge că ideea nu e corectă în mare, e corectă de la cap la coadă. Nu-i un efort mic, mi-ar fi fost mai simplu să explic unui novice decât unuia ca dvs,. tobă de matematică:)

E corectă ideea folosirii combinărilor pentru a găsi numărul de cazuri posibile, dar nu strict necesară. Când în cutie avem 1000 de capete libere (nu fire), numărul de cazuri posibile e C(1000, 2) - combinări de 1000 luate câte 2, doar așa pot să scriu . Un caz favorabil este evenimentul înnodării unui capăt cu celălalt capăt al aceluiași fir. 500 de fire, 500 de cazuri favorabile. C(1000, 2) = 999*500. Probabilitatea de a realiza o buclă e dată de nr. cazuri favorabile/nr. cazuri posibile, adică 

500/(999*500) = 1/999. Dar la această probabilitate se poate ajunge simplu, fără combinări. Orice capăt poate fi înnodat cu oricare din celelalte 999, dintre care doar 1 e capătul lui pereche, deci probabilitatea  buclei e 1/999, care poate fi scrisă și 1/(2*500 - 1)

În general, pentru n fire avem 2n capete, cazurile posibile de a înnoda 2 capete sunt n(2n - 1) (rezultă din evaluarea C(2n, 2)), iar probabilitatea de a face o buclă este n/n(2n-1) = 1/(2n - 1). Sper că sunteți de acord cu ce am spus pînă acum. Dacă da, ca să rezum, atunci când facem primul nod, avem o probabilitate de 1/999 de a face o buclă. Buuun.

Întrebare: 

De câte cutii identice (cu 500 de fire) am avea nevoie pentru ca, făcând câte un nod la întâmplare în fiecare cutie, să ne putem aștepta ca într-o cutie să găsim o buclă?

Răspuns:

 Am avea nevoie de 999 de cutii. De ce? Pentru că însumând probabilitățile de a face o buclă de 999 de ori, obținem probabilitatea 1.

Întrebare echivalentă: 

Dacă avem 999 de cutii, fiecare cu câte 500 de fire în ea, și în fiecare cutie înnodăm 2 capete de fir la întâmplare, în câte cutii ne putem aștepta să fi făcut o buclă?

Răspuns:

 Într-o cutie, pentru că suma probabilităților fiecărui eveniment în parte este 1. Dacă era 2, mă așteptam în 2 cutii, dacă era 3,85 mă așteptam, cu puțină șansă să găsesc câte o buclă în 4 cutii și, cu ceva ghinion, în 3 cutii.

Acum mai rămâne să fiți de acord, revenind la problemă, cu următorul fapt: la fiecare nod făcut pierdem un fir și, evident, 2 capete libere. Orice s-ar întâmpla, dacă s-a nimerit buclă am pierdut un fir și 2 capete înnodate între ele, dacă nu s-a nimerit buclă am pierdut un fir - din 2 mai scurte am făcut unul mai lung - și două capete, cele pe care le-am înnodat, adică, după ce am făcut un nod într-o cutie cu 500 de fire, primesc o altă cutie, cu 499 de fire, unde să fac un nod și în care evenimentul favorabil este să formez o buclă. 

Diferența e că, de data asta, probabilitatea de a face o buclă s-a mărit puțin, este de 1/(2*499 - 1) = 1/997. Așteptarea de a găsi o buclă într-una din aceste 2 cutii e de 1/999 + 1/997, altfel spus, ce ne putem aștepta e să găsim o fracțiune de buclă ceea ce e absurd, deci ne așteptăm să găsim zero bucle, deși probabilitatea e nenulă.

Mai departe lucrurile continuă prin recurență, așteptarea crește prin scăderea numărului de fire, cu 1 la fiecare nod, și deci probabilitatea crește. Procedăm exact ca în exemplul cu 999 de cutii a 500 de fire fiecare, adunând probabilitățile, cu singura diferență că probabilitățile de a face o buclă sunt diferite de la cutie la cutie.

Mi se pare foarte interesant și oarecum contraintuitiv că diferența de bucle așteptat a se forma din, să zicem, 100 de fire (3,2843), 500 de fire (cazul nostru - 4,0890) sau 1000 de fire (4,4356) e foarte mică. Practic între 500 și 1000 de fire nu e nicio diferență.

Bineînțeles că odată găsită formula de calcul pe care ați arătat-o lucrurile nu mai sunt deloc surprinzătoare...
Domnul Puiu aveti dreptate e un rationament 100% corect ,doar ca ce am comentat eu justifica corectitudinea adunarii sanselor.Domnul goguv sincer cred ca era mai ok cu 10 fire decat cu 500, plus faptul ca bucla apare in  paranteza ca referinta fata de fire si cea din final ca o bucla oarecare ,care pe mine personal ma derutat,caci imaginatia unei  bucle reale si ce bucle poate sa iasa cu asa multe fire te cam deruteaza.
Sincer să fiu eu nu v-am înțeles prea bine comentariile.

Eu am pus 500 cam la intâmplare. Acum, că am la dispoziție și o rezolvare și formula d-lui Puiu, văzând deci că e vorba de o serie divergentă, și văzând și cât de greu crește numărul de bucle, e și mai contraintuitiv pentru un neinițiat ca mine să gândesc că o asemenea serie tinde la infinit, deci că, cu un număr suficient de mare de fire la dispoziție, numărul de bucle poate crește și el oricât de mult.

...