Monte-Karlo metodas  

Su azartiniais žaidimais jis susijęs nebent suprantant plačiausia prasme. Monte-Karlo metodai yra būdas spręsti sudėtingus uždavinius netikėčiausiu būdu. Jie buvo sukurti kai kurių atominės bombos kūrimo metu kilusių uždavinių sprendimui. O pirmąkart šis metodas aprašytas A. Holo 1872 m.
Vis tik išgirdus apie atsitiktinių skaičių naudojimą kompiuteriuose, pirma mintis būna apie kompiuterinius žaidimus. Juk visai nebūtų įdomu, jei kiekvieną kartą žaidimas kartotų ankstesnius.

Archetipiniu pavyzdžiu yra lošimų kauliuko programavimas. Dažniausiai naudojama speciali atsitiktinio skaičiaus tarp 0 ir 1 generavimo funkcija (dažnai vadinama rnd). Pavyzdžiams naudosime JavaScript kalbą. Tada atsitiktiniui sveikam skaičiui 1..6 generuoti komanda būtų:
Math.floor(Math.random()*6)+1

Šis pavyzdys 6 kartus “išmeta” kauliuką:

<SCRIPT Language='JavaScript'>
var kaulas;
for (var k=1; k<=6; k++) {
   kaulas = Math.floor(Math.random()*6)+1;
   document.write ('
Kauliukas:' + kaulas);  
}
</SCRIPT>

Dažna pradedančiųjų klaida yra praleidžiant „+1”. Kadangi funkcija niekada negražina reikšmės 1, tai be „+1” gauname skaičius 0..5

Atkreipiame dėmesį, kad atsitiktinius dydžius suskaidome į lygaus dydžio intervalus, taigi rezultatas yra yra su vienoda tikimybe. Tad mūsų „kauliuko“ mėtymas yra korektiškas.

Suprantama, kad jei įvykiai nevienodų tikimybių, tada reikia imti nevienodo pločio intervalus – proporcingai tikimybėms.

Viskas tarsi ir aišku, tačiau čia yra kiek sudėtingesnė problema generuojant atsitiktines reikšmes galimyų reikšmių kontinuume. random funkcija gražina „vienodai pasiskirsčiusias“ reikšmes intervale 0..1. Kartais reikalingi kitokie pasiskirstymai ir tam yra gausus technikų pasirinkimas. Pvz., jei norime normaliojo pasiskirstymo, tai visa, ko mums reikia, tai gauti kelias atsitiktines reikšmes ir paskaičiuoti jų vidurkį. Tada apytikslis pasiskirstymas bus apie 0.5 reikšmę.

Pvz., paskaičiuojami 6-i vidurkiai iš 5 atsitiktinių reikšmių:

var vidurkis;
for (var k=1; k<=6; k++) {
   vidurkis = (Math.random()+Math.random()+Math.random()+Math.random()+Math.random())/5;
   document.write ('
vidurkis:' + vidurkis);
}

Po šios įžangos pats laikas grįžti prie Monte-Karlo metodo. Nesunku sugalvoti uždavinį, simuliuojantį atsitiktinį procesą (pvz., degalinės darbo priklausomybę nuo kolonėlių skaičiaus). Suprantama, kad tokia simuliacija neduos tikslaus atsakymo – kiekvienas jos įvykdymas bus skirtingas. Tačiau mes galime įvesti tikėtinas įvykių tikimybes, kurioms esant rezultatas tam tikrame intervale bus su didele tikimybe. Pvz., 90% atvejų eilė bus iš 8-11 laukiančių mašinų.

Štai čia ir braunasi susirūpinimas. Ir nors yra 90% tikėtinumas, kad eilė bus tokio dydžio, tačiau lieka 10% tikėtinumas, kad taip nebus. Ir apie tai reikia rūpintis.

Naudojant kompiuterius tikimasi tiksliai išspręsti uždavinį. Pvz., skaičiuojant netaisyklingos figūros plotą, galime ją suskaidyti į daugelį stačiakampių ir gauti apytikslę ploto reikšmę. Ji nėra tiksli, tačiau galime stačiakampius mažinti ir rezultatą tikslinti.

Plotų skaičiavimas (matematiškai, funkcijų integravimas) labai svarbus fizikoje ir inžinerijoje. Jis iškilo ir atominės bombos projekte. To meto kompiuteriai nebuvo pakankamai spartūs. Džonas fon Neimanas mąstė, kaip tai padaryti paprasčiau panaudojant atsitiktinius skaičius.

Kad tai suprastume, įsivaizduokime šautuvą, atsitiktinai šaudantį į taikinį. Pataikymų kiekis yra proporcingas taikinio plotui. Tai ir yra Monte-Karlo metodo esmė.

Tarkime, reikia paskaičiuoti skritulio plotą. Mums tereikia generuoti atsitiktines taškų (x,y) koordinates ir paskaičiuoti, kiek taškų patenka į skritulį, ir kiek ne. Jei tai padarysime pakankamą kartų kiekį, rezultatas apsistos ties apskritimo ploto santykiu su srities plotu.

Atrodytų, kad toks uždavinio „apvertimas žmyn galva“ yra keistas, tačiau reikia atsižvelgti į tai, kad atsitiktinių skaičių porų generavimas, o taip pat „pataikymo“ patikrinimas yra greiti. Ir tai buvo priežastis, kodėl atominės bombos kūrime buvo naudojami atsitiktiniai skaičiai.

Vis tik, ploto paskaičiavimas nedaro jums didelio įspūdžio, tačiau pasižiūrėkime į p reikšmės suradimą. Juk jei paimsime skritulį, kurio spindulys yra 1, tai jo plotas bus tiksliai p! Ir tada p galima lengvai paskaičiuoti naudojant atsitiktinius skaičius...

Šią idėją 18 a. iškėlė prancūzų gamtininkas, Bufono kunigaikštis Georges-Louis Leclerc'as. Jis klausė – kokia tikimybė, kad ant grindų numesta adata pataikys į plyšį tarp lentų, kurių plotis yra pusė jos ilgio. Atsakymas į šį klausimą buvo 1/p. Tai buvo praktiškai išbandyta 1901 m. ir gauta reikšmė 355/113 nėra labai bloga p aproksimacija – atsižvelgiant į tai, tebuvo mėtoma adata paskaičiuojant, kiek kartų ji pataiko į tarpą tarp lentų.

Tačiau kas toliau? Ogi tai, kad galite įvertinti bet kokio paskaičiavimo rezultatus naudodami vien atsitiktinius skaičius. Vienintelė problema – paaiškinimas, kodėl tai suveikia, veda gilyn į matematiką.

Tarkim, Monte-Karlo metodas leidžia spręsti tiesinių lygčių sistemą Ax=b, kur b yra reikšmių vektorius, o A - matrica.

Paprastai ji sprendžiama skaičiavimo metodų metodais, tačiau atvirkštinės matricos suradimui reikia didelių skaičiavimo sąnaudų. Tam mums reikia paskaičiuoti sandaugą y=Ab. Tai atliekama sumuojant kiekvienos eilutės sandaugą su vektoriaus reikšme.

Pvz. - šios lygčių sistemos atsakymas yra (9, -1),

var j, b = new Array(4,2);
var A = new Array(), Y = new Array();
A[0] = new Array(1,5); A[1] = new Array(2,4);

for (var i=0; i<2; i++) {
   Y[i] = 0;       
   for (j=0; j<2;j++) {
      Y[i] += A[i][j] * b[j];
   }
   document.write ('
Y['+i+']=' + Y[i]);
}

Rezultatas:
Y[0]=14
Y[1]=16

Tarkim, kad visos matricos reikšmės teigiamos ir mažesnės už 1, o kiekvienos eilutės reikšmių suma lygi 1. tai leidžia mus eilutes laikyti kaip kažkokių įvykių tikimybes.
Tarkim, kad A = ( (0.5, 0.3, 0.2), (0.2, 0.1, 0.7) ), o b = (4.3, 6.2, 3.2).
Tada mes turim: a) sukurti atsitiktinių skaičių generatorių R(1), kuris 4.3 pateiktų su 0.5 tikimybe, 6.2 – su 0.3 tikimybe, 3.2 – su 0.2 tikimybe;
b) ir R(2) generatorių, kuris tas pačias reikšmes pateikia su antroje eilutėje nurodytomis tikimybėmis.

O tai galima nesunkiai pasiekti anksčiau aprašytais būdais! Generuojame atsitiktinius skaičius ir skaičiuojame jų vidurkius – jų sudarytas vektorius yra ieškomo atsakymo aproksimacija.

Lieka tik klausimas – kam gi reikalingi kvantiniai kompiuteriai, jei turime Monte-Karlo metodą, kurį galime panaudoti sudėtingų skaičiavimų aproksimacijai?

Matroidai
Loterijų matematika
Algebra akimirksniu
Kur viešpatauja chaosas?
Skaičiai – apžvalga/ pradmenys
Ar įrodytas abc teiginys?
Revoliucija mazgų teorijoje
Izingo modelis įmagnetinimui
Pagrindinės statistinės sąvokos
Mokslininkui nereikia matematikos!
Kita skaičiavimo metodų istorijos pusė
Ultimatyvi logika: Iki begalybės ir toliau
Žvaigždžių virš Babilono funkcija
Geriausios alternatyvos parinkimas
Šiuolaikiniai iškilūs matematikai
Žaidimų teorijos panaudojimas
Nepaprasti Visatos skaičiai
Iniciatyva: Matematikos keliu
Visata kaip kompiuteris
Didžioji Ferma teorema
Matematiniai anekdotai
Laplasas. Dėl tikimybių
Dygios eilutės
Perkoliacija
Parabolė
Vartiklis