Shakkilautatehtävä

Tuolla on ratkaisu kun ratsun odotetaan palaavan takaisin lähtökulmaan.

http://www.math.wisc.edu/~valko/courses/632/632_hw3_s.pdf


6. (From Durrett.) Compute the expected number of moves it takes a knight to return to its
initial position if it starts in a corner of the chessboard, assuming there are no other pieces
on the board, and each time it chooses a move at random from its legal moves. (Note: A
chessboard is {0, 1, ..., 7}2. A knights move is L-shaped; two steps in one direction followed
by one step in a perpendicular direction.)

Hint: this is just a simple symmetric random walk on a graph (which consists of the possible
moves of the knight on the board). Because of this the stationary measure is easy to compute.

The following table shows the number of possible moves the knight can make from a given
place.
._______________.
|2 3 4 4 4 4 3 2|
|3 4 6 6 6 6 4 3|
|4 6 8 8 8 8 6 4|
|4 6 8 8 8 8 6 4|
|4 6 8 8 8 8 6 4|
|4 6 8 8 8 8 6 4|
|3 4 6 6 6 6 4 3|
|2 3 4 4 4 4 3 2|
.---------------.

Since we have a simple symmetric random walk on the underlining graph, these numbers give
an invariant measure for the walk (we showed that in class). To get a stationary distribution
we need to normalize this, and for the corner position this gives
2/(2 4 3 8 4 20 6 16 8 16) = 1/168

It is easy to check that the chain is irreducible and since it is nite it must also be recurrent.
This means that the stationary distribution is unique and it is also equal to the reciprocal of
the expected return time. This gives 168 for the expected return time at the corner.


En ole lukenut tuota joten en tiedä ymmärränkö itsekään ratkaisua. Pitääpä katsoa...

http://fi.wikipedia.org/wiki/Satunnaiskulku
http://en.wikipedia.org/wiki/Random_walk

Tekaisin tämän tehtävän numeerista ratkaisua varten pienen FORTRAN-ohjelman. Numeroin ensin shakkilaudan ruudut 0-63 ja kirjoitin Markovin prosessia kuvaavan 64x64 siirtymämatriisin. Alkutilajakaumaa kuvaavaan vektoriin sijoitin ensimmäiseksi komponentiksi ykkösen ja muut asetin nolliksi. Käytin laskuissani FORTRANin REAL(8)-kaksoistarkkuuden liukulukuja. Annoin ohjelman pyöriä maksimissaan 10000 kierroksen verran. Jokaisen kierroksen jälkeen annoin ohjelman nollata sen vastakkaisen kulmaruudun (nielu) todennäköisyyden tilajakaumassa. Näin hoidin tuon ehdon, että tarkastellaan sitä askelmäärää, jolla ratsu ensimmäisen kerran päätyy vastakkaiseen kulmaruutuun.

Askelmäärän odotusarvoksi ohjelmani antoi 212,75118491938426.

Kokeilin sitten muuntaa sen loppuruudun paikkaa ohjelmassa.

Odotusarvoksi sille askelmäärälle, jolla ratsu palaa ensimmäisen kerran samaan kulmaan, josta se lähti liikkeelle, ohjelmani antoi 167,99999999999770.

Numeerisen tarkkuuden rajoissa tämä näytäisi olevan hyvin sopusoinnussa niiden teoreettisten tarkastelujen kanssa, joihin joku tuolla edellä viittasi.

Vielä kokeilin laskea odotusarvon sille askelmäärälle, jolla ratsu ensimmäisen kerran tulee (määrättyyn) viereiseen kulmaruutuun. Tälle askelmäärälle ohjelmani antoi odotusarvon 211,14287927441291.

Ovatko muut saaneet vastaavia tuloksia?

PS. Biljardinpelaajat varmaankin odottelevat jo tuskaisesti odotusarvoa sille askelmäärälle, jolla ratsu liikkeelle lähtönsä jälkeen ensimmäisen kerran päätyy johonkin kulmaruutuun. Tälle ohjelmani antoi arvoksi 41,999999999999893. Ilmeisesti tarkka arvo olisi 42, mutta tämän todistaminen jätettäköön pohdittavaksi.