Mesiu tą juodą darbą, įsitaisysiu kaminkrėčiu…
Per tuos dėstytojavimo metus sufanatiškėji, pasidarai maniakas – negali palikti neišspręsto uždavinio.
Štai paprašiau studentų atnešti po tris neišspręstus uždavinius. Šaunuoliai – šeši studentai atnešė! „Užsikabinau“ už vieno uždavinio, štai jis:
***
If we have an empty room, and every week there is a 0.6 probability for a person to join, 0.2 probability for a person to leave, and 0.2 probability for no change (only one action can be performed per week), what is the probability that there are at least 40 people in the room after 104 weeks?
***
Susiradau jį internete:
Ten lyg ir yra sprendimas „Java“ kalba… Viena to sprendimo vieta man kelia įtarimų… Pritaikau sumažinimo principą:
*
Yra tuščias kambarys. Kiekvieną savaitę gali įvykti tik vienas įvykis: žmogus gali ateiti į kambarį (šio įvykio tikimybė yra 0,7), gali išeiti iš kambario (tikimybė 0,2), o gali ir nieko neįvykti (tikimybė 0,1). Kokia tikimybė, kad po keturių savaičių kambaryje bus du žmonės?
*
Dabar stebėkite, kaip aš sprendžiu ir kur klystu!
Tam, kad po keturių savaičių kambaryje būtų du žmonės, turi įvykti vienas iš dviejų nesutaikomų įvykių: dvi savaites po vieną žmogų į kambarį turi įeiti, o dvi savaites – nieko neįvykti; tris savaites po žmogų į kambarį turi įeiti, o vieną savaitę vienas žmogus turi išeiti.
Kiekvieno iš tų įvykių tikimybę skaičiuojame pagal apibendrintąją Bernulio formulę (yra B.B. knygoje…) ir tas dvi gautąsias tikimybes sudedame. Gavau 0,0294 ir 0,01372.
*
Lyg ir gerai? Bet aš patikrinu – negerai… Kaip patikrinu? Apskaičiuoju visų galimų baigčių po 4 savaičių tikimybes, štai tokių įvykių (įėjo, išėjo, niekas nepasikeitė):
220
112
004
103
211
202
310
301
400
Tų įvykių tikimybių suma turi būti vienetas, kas tuo abejoja? O aš negaunu vieneto… Padėkite!
Atsakymai
Burgis, 2012-03-07 12:43:14
Įvertinkite uždavinio grožį…
petras, 2012-03-07 13:27:25
Na aš su tikimybėm visai nedraugauju. bet man pasirodė keista, kad išėjimo tikimybė yra 0,2. tai čia tik tuo atveju jei patalpoj jau yra žmogus. jeigu jo nėra, tai išėjimo tikimybė 0.
todėl ir ten prie visų galimų baigčių gal reiktų irgi įrašyt išėjimus tuo atveju kai net nėra kam išeit.
arba tam tikru atveju (kai nieko nėra kambary) imt išėjimo tikimybę nulinę o įėjimo arba nesikeitimo tikimybę didesnę nei 0,6 ir 0,1
gal tai reiktų įvertint ? arba gal uždavinio sąlygos nepilnai pateiktos 🙂
sqrt, 2012-03-07 13:28:27
Aš antrą tikimybę gaunu kitokią, greičiausiai kažką blogai įstatėtė.
Beje, labai patogu tokius daiktus kaip pirmas uždavinys skaičiuoti su alpha, nereikia programuoti jokiom javom: http://www.wolframalpha.com/input/?i=Sum%5BSum%5BBinomial%5B104,i%5D*(3/5)^i*Binomial[104-i,o]*(1/5)^(104-i),{o,0,i-40}],{i,40,104}]
petras, 2012-03-07 13:29:09
oj, žiūriu, kad nusikalbėjau :DD ignoruokit mano ankstesnį postą.
sqrt, 2012-03-07 13:30:20
o dievaž, na ir baisiai gavosi nuoroda…
sqrt, 2012-03-07 13:33:53
o, kokia šauni Petro pastaba, net mintis nešovė, kad neigiamas skaičius žmonių kambaryje nepageidautinas!
Ah, bet kita vertus, kam įdomi ta realybė…
RascalLT, 2012-03-07 13:40:04
Suskaičiuoti nemoku, bet pritariu Petrui, kad kažkokiu būdu reikia įvesti ne vien įėjimų ir išėjimų skaičių, bet ir jų tvarką į lygtį. Neigiamas žmonių skaičius nepageidautinas ne vien po keturių savaičių, bet po kiekvieno žingsnio. P.Burgi, ar kiti matematikai – papasakokit prašau plačiau, kaip tokią užduotį aprašyti.
sqrt, 2012-03-07 15:21:50
Kadangi originaliai uždavinys suformuluotas be patikslinimo (ir tame forume nieko nėra), tai galim pakeisti kaip tik norim. Pavyzdžiui esant 0 žmonių, tą 0.2 tenkantį išėjimui perkelti prie 0.2 nepasikeitimui (atitinkamai 0.2 ir 0.1 Direktoriaus modifikacijoje).
Gaunasi gerokai įdomesnis uždavinys 🙂
Burgis, 2012-03-07 15:31:51
Sveikinu, vieną uždavinio netikslumą jūs jau pamatėte! Kaip gali būti tikimybė išeiti iš kambario visą laiką vienoda, jei nesant žmonių kambaryje ji akivaizdžiai lygi nuliui?
Bet man kažkodėl atrodo, kad esant didesniems skaičiams tai neturėtų duoti didelės paklaidos, o aš gaunu nemažą… Tiesa, mano skaičiai nėra dideli, gal dėl to?
sqrt, 2012-03-07 15:58:05
Nepataisę sąlygos (tiksliau pataisę tik pusiau) vieneto nepavyks gauti, o paklaida bus visada didesnė už 0.2, nesvarbu kokio didumo skaičiai. Jei negali būti neigiamų žmonių, turi tai atsispindėti skaičiuose.
sqrt, 2012-03-07 15:59:08
Nepataisę sakinio (tiksliau pataisę tik pusiau) sakyti spausti nevertėtų… Ech!
Burgis, 2012-03-07 16:15:33
sqrt: gal ko ir nesupratau, bet ką tik pabandžiau spręsti įvertindamas negalimybę išeiti nesančiam ir gaunu (logiška…) dar mažesnę sumą, man dar daugiau trūksta iki vieneto. Dar kažko nematau, neužčiuopiu…
Audrius, 2012-03-07 19:19:47
Norėčiau Jūsų teismui pateikti savo variantą.
Jei dviems žmonėms pasilikti kambaryje yra skirtos 4 savaitės, tai, galbūt, galimi tokie variantai:
I savaitė: įėjo pirmas žmogus 1*0,7;
II savaitė: įėjo antras žmogus 1*0,7;
III savaitė: kadangi kambaryje du žmonės, tai tikimybė vienam kuriam iš jo išeiti padvigubėja 2*0,2 (dvigubai daugiau šansų, kad bent vienas išeis);
IV savaitė: jei tolimesnė situacija nesikeis, tai ji vis tiek priklausys nuo kambaryje esančių žmonių skaičiaus, todėl 2*0,1.
Įvykus visiems įvykiams, o visus juos sudėjau (turiu abejonių, nors vertinau tai, kaip taško, šiuo atveju žmogaus, absoliutų padėties kitimą), po keturių savaičių turime gauti 2 žmones kambaryje. Taigi, jei kas savaitę nutinka po įvykį, o jam įvykti nurodytos tikimybės, tai kambaryje esančių žmonių skaičius: 1*0,7+1*0,7+2*0,2+2*0,1= 2 žmonės.
Padalinę šį reiškinį iš žmonių skaičiaus, t.y.2, gausime tikimybę lygią 1, kuri, tarsi, ir atspindėtų įvykių seką su minėtomis tikimybėmis (trumpiau): 0,7+0,2+0,1=1. Tai jei 0,2 yra tikimybė, kad kažkas iš kambario išeis, tai 0,8 – kad liks.
Burgis, 2012-03-07 20:10:08
Audriui: čia problemos su sąlygos skaitymu. Aš suprantu, kad tikimybė žmogui išeiti lieka 0,2, nepriklausomai nuo to, kiek žmonių kambaryje. Tai nelabai logiška, bet taip spręsta tame tinklalapyje…
Audrius, 2012-03-07 22:14:12
Gerb. Direktoriui: Sutinku, kad angliškasis variantas, beje nurodytoje svetainėje pateiktas ir atsakymas 0,61, yra sudėtingesnis, nes tokių gražių tikimybinių proporcijų, kaip Jūsų variante, tikrai negausime. Dėkui už intrigą. Gero vakaro!
Marius A., 2012-03-07 23:06:35
Pabandžiau išspręsti iš programuotojo pozicijų.
Turbo Pascal programos tekstas, jei kas domisi – paspaudus ant mano vardo 😉
Ignoruoju tą faktą, kad iš tuščio kambario negali išeiti žmogus. Pas mane – gali (galime laikyti, kad pradžioje yra 10 žmonių ir mes tikriname, ar po 4 savaičių yra 12 žmonių kambaryje).
Kol prausiausi – kompas prasuko 161 310 876 iteracijų, iš jų 49 005 045 atvejų po 4 savaičių buvo likę lygiai du žmonės, kas yra 0.303793 atvejų.
pilnas pasiskirstymas pagal likusius žmones:
-4 257982 0,001599285
-3 515338 0,003194688
-2 4000902 0,024802432
-1 5547645 0,034391017
0 21701231 0,134530489
1 19419544 0,120385832
2 49005045 0,303792566 <— mus dominantis rezultatas
3 22137547 0,137235303
4 38725642 0,240068388
Drįstu manyti, kad programa teisinga ir praktiniais skaičiais galima remtis su minimalia paklaida. Gal padės ieškant teisingo atsakymo 😉
ST, 2012-03-08 08:29:53
Skaičių 0,0294 gaunu, o skaičiaus 0,01372 negaunu (gaunu 0,2744):
p(2, 0, 2) = (4!/(2!*0!*2!))*0,7^2*0,2^0*0,1^2 = 6*0,49*0,01 = 0,0294
p(3, 1, 0) = (4!/(3!*1!*0!))*0,7^3*0,2*1*0,1^0 = 4*0,343*0,2 = 0,2744
Sumoje 0,3038 (artimas Mariaus kompiuteriu gautam).
Burgis, 2012-03-08 08:31:18
Atrodo, kad šiąnakt (pilnatis gi, pilnatis…) po pusiaunakčio radau ir klaidą, ir sprendimą… Skubu užrašyti, kad nepamirščiau.
*
Dar kartą pritaikykime sumažinimo principą. Kas bus po savaitės? Vienetą gautume tik sudėję tikimybes 0,7+0,2+0,1, bet juk aišku, kad niekas negalėjo išeiti iš kambario, nes ten nieko nebuvo…
*
Kas bus po dviejų savaičių?
a a 0,7*0,7=0,49;
a n 0,7*0,1=0,07;
a i 0,7*0,2=0,14;
n a 0,1*0,7=0,07;
n n 0,1*0,1=0,01.
Šių tikimybių suma – tik 0,78. Žinoma! Nes apibendrintoji Bernulio formulė norėtų skaičiuoti toliau:
i a
i n
n i
i i
Pridėję šias tikimybes tikrai gauname vienetą. Bet juk neįmanomų įvykių negalima įskaičiuoti…
*
Taigi siūlau perskaičiuoti ankstesnes tikimybes kaip sąlygines ir gauti (suapvalinu):
0,49/0,78=0,63;
0,09;
0,18;
0,09;
0,01.
Dabar šių penkių tikimybių suma yra vienetas. Visi turi būti patenkinti!
*
Visam uždaviniui išspręsti tikrai labai tiktų Paskalis…
Burgis-Q.E.D., 2012-03-08 10:27:18
ST: ačiū, tai buvo mano klaida, bet jos ištaisymas esmės nekeičia…
Vainius, 2012-03-10 00:23:44
Šitą uždavinį manau patogiausia spręsti per markov process framework’ą.
Galima užsirašyti one-step transition matrix, kurios “ij” elementas būtų tikimybė, kad būnant būsenoj “i” kitam žingsnyje atsidursim būsenoj “j”
Sumažintu atveju matrica atrodytų taip:
http://www.wolframalpha.com/input/?i=%7B%7B0.3%2C+0.7%2C+0%2C+0+%2C0%7D%2C%7B0.2%2C+0.1%2C+0.7%2C+0+%2C0%7D%2C%7B0%2C+0.2%2C+0.1%2C+0.7%2C+0+%7D%2C%7B0%2C+0%2C+0.2%2C+0.1%2C+0.7%7D%2C%7B0%2C+0%2C+0%2C+0%2C+0.2%7D%7D
O tada pasinaudoti Chapman–Kolmogorov lygybe, kad n-step transition matrix bus šita matrica pakelta n-tuoju.
Ir tuomet jeigu pradėjom pirmoj pozicijoj (t.y. kai kambary nulis žmonių), tai tikimybė, kad po 4 savaičių kambary bus būtent du žmonės yra laipsniu pakeltos matricos pirmos eilutės trečias elementas (t.y. 0.294, galit pasitikrint http://www.wolframalpha.com/input/?i=%7B%7B0.3%2C+0.7%2C+0%2C+0+%2C0%7D%2C%7B0.2%2C+0.1%2C+0.7%2C+0+%2C0%7D%2C%7B0%2C+0.2%2C+0.1%2C+0.7%2C+0+%7D%2C%7B0%2C+0%2C+0.2%2C+0.1%2C+0.7%7D%2C%7B0%2C+0%2C+0%2C+0%2C+0.2%7D%7D%5E4).
Jeigu norim rasti tikimybę, kad bus daugiau nei du žmonės, susumuojam tos eilutės elementus tolesnius nei trečias.
Pabandžiau tą patį pasidaryt su originalo sąlygą (105×105 didumo matrica, etc..) tai tikimybė gavos 0.6306065. Labai panašiai kaip tam, kur sprendė su Java, bet ne identiškai 🙂
Vainius, 2012-03-10 00:31:34
Tiesa, tikroji transiton matrix šitoj vietoj turėtų būti begalinė, bet kai aišku, ką norim žinoti (kiek žingsnių į priekį ir nuo kur pradėsim), tai galima apkarpyti 🙂
Burgis, 2012-03-10 19:32:32
Vainiui: kam Jūs gąsdinate svetainės lankytojus?… 🙂