Browsing by Subject "satunnaiskävely"

Pólyan lauseen mukaan verkon Z^d symmetrinen satunnaiskävely on palautuva, jos d < 3 ja poistuva, jos d ≥ 3. Alunperin Georg Pólyan todistamalle lauseelle on ajan kuluessa muodostunut erilaisia todistusmenetelmiä. Tässä tutkielmassa syvennytään näistä kahteen toisiaan täydentävään menetelmään ja todistetaan Pólyan lause niiden avulla. Luvussa 5.1 Pólyan lauseelle esitetään laskennallinen todistus, joka tarjoaa yksinkertaisen ja konkreettisen tavan tutkia säännöllisen verkon satunnaiskävelyn käyttäytymistä. Luvussa 5.2 esitettävän virtauksen teorian avulla voidaan Pólyan lauseen lisäksi tutkia satunnaiskävelyn käyttäytymistä laajemmin eri verkoissa. Tarvittavat taustatiedot verkosta, Markovin ketjusta ja satunnaiskävelystä esitetään luvuissa 2 ja 3. Pólyan lauseen todistus on jaettu kahteen eri lukuun. Lauseen todistus alkaa luvusta 5.1, jossa verkon syklien ja polkujen lukumääriä tutkimalla Pólyan lause osoitetaan verkolle Z^d, missä d ≤ 3. Kombinatorinen todistus on idealtaan yksinkertainen, mutta siinä tehtävä arvio vaatii syvällisempää perustelua. Tutkielmassa tämä arvio toteutetaan Robbinsin kaavalla, joka on tarkempi arvio kirjallisuudessa useammin käytetylle Stirlingin kaavalle. Robbinsin kaava osoitetaan luvussa 4. Luvussa 5.2 esitetään verkon virtauksen teoria, jonka avulla Pólyan lause todistetaan verkolle Z^d, missä d > 3. Verkon virtauksen ja satunnaiskävelyn yhteys löytyy virtaukseen liittyvästä energian käsitteestä. Osoittautuu, että verkon virtauksista energialtaan pienimmän virtauksen energia riippuu verkon satunnaiskävelyn käyttäytymisestä. Tulos osoitetaan ensin äärelliselle verkolle, josta se johdetaan koskemaan ääretöntä verkkoa verkkoon liittyvän kontraktion käsitteen avulla. Luvussa 6 Pólyan lauseen merkitys korostuu, kun virtauslauseen avulla osoitetaan, että satunnaiskävelyn poistuvuus säilyy verkkojen kvasi-isometriassa. Tätä varten esitetään virtauslauseen seurauksia ja tarvittavat taustatiedot kvasi-isometriasta