Note: Section 5.3.2 is superseded by the paper by Kalyanakrishnan,
Tewari, Auer, and Stone (2012). In particular Corollary 5.12 in this
dissertation is to be withdrawn in favour of Corollary 7 in the latter
paper. Also, we now have less confidence in the plausibility of
Conjecture 5.13.


Erratum: In the first paragraph of Section 3.1.1, the following
statement is incorrect.

``On taking N (E), the agent moves north (east) with probability p and
it moves east (north) with probability 1 - p.''

The statement should instead read as follows.

``On taking N (E), the agent moves north (east) with probability 1 - p
and it moves east (north) with probability p.''

The author thanks Ruohan Zhang for pointing out this error.