
We consider the long term behaviour of a Markov chain \xi(t) on \Z^N based on
the N station supermarket model. Different routing policies for the supermarket
model give different Markov chains. We show that for a general class of local
routing policies, "join the least weighted queue" (JLW), the N onedimensional
components \xi_i(t) can be partitioned into disjoint clusters C_k. Within each
cluster C_k the "speed" of each component \xi_j converges to a constant V_k and
under certain conditions \xi is recurrent in shape on each cluster. To
establish these results we have assembled methods from two distinct areas of
mathematics, semimartingale techniques used for showing stability of Markov
chains together with the theory of optimal flows in networks. As corollaries to
our main result we obtain the stability classification of the supermarket model
under any JLW policy and can explicitly compute the C_k and V_k for any
instance of the model and specific JLW policy.

We study the random walk in random environment on {0,1,2,...}, where the
environment is subject to a vanishing (random) perturbation. The two particular
cases we consider are: (i) random walk in random environment perturbed from
Sinai's regime; (ii) simple random walk with random perturbation. We give
almost sure results on how far the random walker will be from the origin after
a long time t, for almost every environment. We give both upper and lower
almost sure bounds. These bounds are of order $(\log t)^\beta$, for $\beta \in
(1,\infty)$, depending on the perturbation. In addition, in the ergodic cases,
we give results on the rate of decay of the stationary distribution.

We consider an exhaustive polling system with three nodes in its transient
regime under a switching rule of generalized greedy type. We show that, for the
system with Poisson arrivals and service times with finite second moment, the
sequence of nodes visited by the server is eventually periodic almost surely.
To do this, we construct a dynamical system, the triangle process, which we
show has eventually periodic trajectories for almost all sets of parameters and
in this case we show that the stochastic trajectories follow the deterministic
ones a.s. We also show there are infinitely many sets of parameters where the
triangle process has aperiodic trajectories and in such cases trajectories of
the stochastic model are aperiodic with positive probability.

We show that certain Markov jump processes associated to crystal growth
models are positive recurrent when the parameters satisfy a rather natural
condition.

We give criteria for ergodicity, transience and null recurrence for the
random walk in random environment on {0,1,2,...}, with reflection at the
origin, where the random environment is subject to a vanishing perturbation.
Our results complement existing criteria for random walks in random
environments and for Markov chains with asymptotically zero drift, and are
significantly different to these previously studied cases. Our method is based
on a martingale technique  the method of Lyapunov functions.