1995

1995
Volume 1
Issue 1


V.A. Malyshev, A.D. Manita, E.N. Petrova and E. Scacciatelli
Hydrodynamics of the Weakly Perturbed Voter Model
pp. 3-56
    We study  the Euler and diffusion  limits for  a weakly perturbed voter
model. We present a new method for deriving the  hydrodynamics and we obtain
the  hydrodynamic equations for a large class of perturbations.
    Keywords: Processes with local interaction, voter model,
hydrodynamical behaviour, resummation of diagrams.

M.V. Menshikov and S.Yu. Popov
Exact Power Estimates for Countable Markov Chains
pp. 57-78
    We develop new methods for studying non-exponential asymptotics
of the stationary probabilities and the convergence  rates for
countable Markov chains.  For some well-known cases like zero drift
random walks on the quadrant we get coinciding lower and upper bounds.
    Keywords: Markov chains classification, stationary probabilities,
Lyapunov functions, martingales, convergence rate.

A.I. Ovseevich
The Laplace Operator in an Orthant (Algebraic Geometry Approach)
pp. 79-90
    Explicit integral formulas for the resolvent of the discrete Laplace
operator in an orthant are obtained, thus providing an analytic continuation
of the resolvent. A homological approach to the problem of the inversion of
Toeplitz operators is developed.
    Keywords: Toeplitz operators, Cech cohomology, Bergman-Weil integral
representation, random walks in an orthant.

A.S. Gajrat
Random Walk of an Active Particle in a Non-Homogeneous Environment
pp. 91-112
    We consider the following problem. A particle performs a random walk in a
non-homogeneous environment. The main feature of this random walk is that
the particle can alter the environment. We will show that the  behaviour of the
particle in the non-critical case ``does not depend'' on the initial state of
the environment. In the critical case however, the role of the initial
environment is more essential. As an example, we  can model a random computation
on a Turing machine by a head moving right and left along an infinite tape.
    Keywords: random walk, random environment, Lyapunov functions, random Turing machine

D.D. Botvich and A.A. Zamyatin
On Fluid Approximations for Conservative Networks
pp. 113-140
    In this paper  we study the fluid dynamics of stable work-conserving networks.
On the fluid level these networks behave in a similar manner to Jackson networks with Poisson arrivals
and exponential service times. We  develop the analysis of the fluid dynamics
in [H. Chen and A. Mandelbaum, Discrete flow networks: bottleneck analysis and
fluid approximations, Math. Oper. Res., 1991, v. 16, 408-446] in more detail.
This paper describes the fluid dynamics in terms of the oblique reflection
mapping. We use another approach and describe the dynamics in terms of the so-called
second vector field in an orthant $R^N_+$, where $N$ is the number of nodes in
the network [V.A. Malyshev, Networks and dynamical systems, Adv. Appl. Prob.,
1993, v. 25, 140-175; V.A. Malyshev and M.V. Menshikov, Ergodicity, continuity
and analyticity of countable Markov chains, Trans. Moscow Math. Soc., 1981,
v. 1, 1-48]. Our goal here is to construct the fluid dynamics in  explicit form
and to provide an efficient algorithm for its calculation. In particular, we calculate
the exact time it takes for all non-bottlenecks to  empty or, for an ergodic
network, the time for the system to empty. Other properties of the dynamics
are also studied. We prove that the fluid dynamics of each stable work-conserving
network is strictly acyclic in the sense of [V.A. Malyshev, Networks and dynamical
systems, Adv. Appl. Prob., 1993, v. 25, 140-175].
    Keywords: stable work-conserving networks, Jackson networks,
fluid approximation, Euler queue length-time scaling limit,
oblique reflection mapping, bottlneck and non-bottlneck nodes,
random walks, second vector field, induced chains, ergodic and non-ergodic
faces, induced vectors.

F.I. Karpelevich, V.A. Malyshev and A.N. Rybko
Stochastic Evolution of Neural Networks
pp. 141-161
    We study the dynamics of neural networks introduced by M. Cottrell for the
case of symmetric connections ($a_{ij}=a_{ji}$). We study the structure of
images that can be remembered by these networks and prove convergence to
these images starting from approximate images.
    Keywords: neural networks, random walks in the orthant, exit boundaries,
Euler limit, processes with local interaction.

1995
Volume 1
Issue 2


N. Cancrini and A. Galves
Approach to Equilibrium in the Symmetric Simple Exclusion Process
pp. 175-184
    We obtain an upper bound for the rate of convergence to equilibrium of the
$d$-dimensional simple symmetric exclusion process starting either with a periodic
configuration or with a stationary mixing probability distribution. More precisely,
denoting this process by $\eta^*_t$, we will show that for all $t$ large enough
$$
\left\vert {\sf P}\left\{\eta^*_t\in Y_N\right\} - \rho^{N} \right\vert
\le c_{d} ~N^2\Bigl({\log t \over \sqrt {t}}\Bigr)^d,
$$
where $Y_N$ is the cylindrical set with all  $N$ sites of the corresponding
box being occupied.
   Keywords: symmetric simple exclusion process, convergence rate.

F. den Hollander, M.V. Menshikov and S.E. Volkov
Two Problems about Random Walks in a Random Field of Traps
pp. 185-202
    This paper is about simple random walks on $Z^d$, $d \ge 3$, in a random
field of traps, the density of which tends to zero at infinity. We distinguish
between the quenched problem (when the traps are fixed) and the annealed problem
(when the traps are updated each unit of time). Our goal is not only to find
a criterion for zero vs. positive probability of survival, but also to show three
different methods that can be applied in this area. These methods are based on
Lyapunov functions, capacity and mean hitting time respectively.
    Keywords: simple random walk, random field of traps, Lyapunov function,
capacity, Wiener's test, annealed problem, quenched problem.

V.A. Malyshev and F.M. Spieksma
Intrinsic Convergence Rate of Countable Markov Chains
pp. 203-266
    The  exponential convergence rate to stationarity is very sensitive to perturbations
of the transition probabilities. This motivates introducing a parameter that
is invariant  under perturbations within a finite domain, called ``intrinsic
rate''. The intuitive interpretation of this invariant is the exponential rate
at which the Markov chain converges back to a finite domain ``from infinity''.
    For  random walks in $Z_+$ and $Z^2_+$ we will study this invariant using
probabilistic methods, in particular Large Deviations techniques, and analytic
methods. Thus we connect convergence rates, action functionals, singularities
of generating functions and spectral properties of transition matrices.
    Keywords: countable Markov chains, exponential convergence,
Large Deviations, essential spectrum.

S. Zachary
On Two-Dimensional Markov Chains in the Positive Quadrant with Partial Spatial Homogeneity
pp. 267-280
    We consider the problem of classifying Markov chains on the quarter
plane $Z_+^2$ which possess a property of partial spatial homogeneity.
Such chains arise frequently in the study of queueing and loss networks
and have been previously studied, notably by Malyshev and Menshikov and
by Fayolle. However existing results are either given under restrictive
conditions, or lack complete proofs. We take a new approach to the construction
of Lyapunov functions for such chains to give proofs which require weaker conditions,
are complete in all cases and additionally are considerably simpler.
We also describe the application of these results to the study of the
dynamic and equilibrium behaviour of large loss networks.
    Keywords: Markov chains, random walks, ergodicity, transience, Lyapunov
functions, loss networks, queueing networks.

A.S. Gajrat, V.A. Malyshev and A.A. Zamyatin
Two-Sided Evolution of a Random Chain
pp. 281-316
    A finite chain (string) is just a sequence of symbols from some finite
alphabet. We consider Markov chains with the state space equal to the set of all
finite strings. In the simplest situation left-sided evolution of the string
is defined by the following one-step transition probabilities:
$q_l(x,\emptyset )$ is the probability that the  leftmost symbol of the
string is erased, if this equals $x$; $q_l(x,y)$ is the probability that the
leftmost symbol $x$ is substituted by $y$; $q_l(x,yz)$ is the probability
that the leftmost symbol $x$ is substituted by $yz$.
    Right-sided evolution is defined similarly. We consider the case when left
and right evolution occur simultaneously and independently. In the generic
situation we obtain a complete classification of such Markov chains.
    Keywords: Markov chain, string, invariant measure, stabilisation law.

1995
Volume 1
Issue 3


J.T. Lewis, C.-E. Pfister and W.G. Sullivan
Entropy, Concentration of Probability and Conditional Limit Theorems
pp. 319-386
We provide a framework in which a class of conditional limit theorems can be
proved in a unified way. We introduce three concepts: a concentration set for
a  sequence of probability measures, generalizing the Weak Law of Large Numbers;
conditioning with respect to a sequence of sets which satisfies a regularity
condition; the asymptotic behaviour of the information gain of one sequence of
probability measures with respect to another. These concepts are required for
the statement of our main abstract result, Theorem 5.1, which describes
the asymptotic behaviour of the information gain of a sequence of conditioned
measures with respect to a sequence of tilted measures. Provided certain natural
convexity assumptions are satisfied, it follows that conditional limit theorems
are valid in great generality; this is the content of Theorem 6.1. We give several
applications of the formalism, both for independent and weakly dependent random
variables, extending in all cases previously known results. For the empirical
measure, we provide a conditional limit theorem and give an alternative proof
of the Large Deviation Principle. We discuss also the problem of equivalence of
ensembles for lattice models in Statistical Mechanics.
    Keywords: entropy, Large Deviation Principle, concentration, conditional
limit theorem, LD-regularity, equivalence of ensembles.

R.M. Burton, C.-E. Pfister and J.E. Steif
The Variational Principle for Gibbs States Fails on Trees
pp. 387-406
    We show how the variational principle for Gibbs States (which says that for
the $d$-dimensional cubic lattice, the set of translation invariant Gibbs States
is the same as the set of translation invariant measures which maximize entropy
minus energy and moreover that this quantity corresponds to the pressure) fails
for nearest neighbour finite state statistical mechanical systems on the
homogeneous 3-ary tree. Given an interaction there is a unique measure $\mu$
maximizing entropy minus energy, and we give necessary and sufficient conditions
so that it is a Gibbs State for that interaction, and that the maximum is equal
to the pressure. In the case of a 2-state system, these conditions define
a 2-dimensional manifold of the natural 3-dimensional parameter space of interactions,
so that generically in the interactions the entropy minus energy for $\mu$ is
strictly less than the pressure and $\mu$ is not a Gibbs State (for those parameter
values).
    Keywords: trees, Gibbs States, variational principle.

I.V. Evstigneev
The Shortest Path Around an Island Outside the Shallows
pp. 407-418
    Let $\xi = (\xi_x(\omega))_{x\in R^2}$ be a random field on
the plane $R^2$. Let $t_0$ be a domain in $R^2$ and $c$ a real number. We
analyse the variational problem of finding the shortest path $\lambda(\omega)$
around the domain $t_0$ outside the random set $\{x\in R^2:\ \xi_x(\omega) <
c\}$. We consider the random domain $\tau(\omega)$ bounded by the curve
$\lambda(\omega)$. We prove that $\tau(\omega)$ is a splitting random domain
for the field $\xi$. This yields the following result. If the field $\xi$ is
Markovian, then $\xi$ possesses the strong Markov property with respect to
$\tau$.
    Keywords: variational problem, random fields, Markov property,
Hausdorff measures.

A. Maruani, E. Pechersky and M. Sigelle
On Gibbs Fields in Image Processing
pp. 419-442
    This work contains two parts only connected  by a common theme, namely
applications of Gibbs fields in image processing.
    In the  first part we give a general description of Bayes approach to image
analysis, where Gibbs fields arise. We stress that the maximal posterior
distribution approach restricts the class of Gibbs fields that could find
applications in image processing. The more general Bayes approach permits
to use all Gibbs distributions without any restrictions.
    In the second part of our work we obtain rigorous results on a model with
Ising interaction and a chess-board external field. The results exhibit some
possibilities of Ising interaction in image processing.
    Keywords: image processing, Bayes strategy, Gibbs random fields,
Ising model, Peierls conditions.

1995
Volume 1
Issue 4


G. Gielis and C. Maes
Local Analyticity and Bounds on the Truncated Correlation Functions in Disordered Systems
pp. 459-472
    We consider Gibbs fields with local and unbounded random interactions
in the regime of Griffiths' singularities. We prove that the singularities
are not worse than that of the randomly diluted ferromagnet and obtain upper
bounds $(\sim C^k(k!)^2)$ for the semi-invariants of order $k$, for high
enough temperature. To obtain this result, we  extend the notion of complete
analyticity to that of local analyticity for non-translation invariant systems.
    Keywords: Griffiths' singularities, spin glasses, semi-invariants, local analyticity.

A. Greenberg, V.A. Malyshev and S.Yu. Popov
Stochastic Model of Massively Parallel Computation
pp. 473-490
    A problem of massive parallelism is considered, where  $N$ processor units are
used for large-scale  simulation or computation. Processor unit $i$ has its
accumulated local time variable $z_{i}(t)$. At Poisson time moments $t_{k}^{i}$,
it gets a job and chooses randomly $I$  other units. If its local time does not
exceed the local times of the chosen $I$ units, then  $z_{i}(t_{k}^{i})$
is augmented by an independent random variable $\eta_{ik}$. In the large $N$
limit we obtain a deterministic nonlinear PDE for the density of local times.
Subsequent corollaries are a travelling wave solution, the linear time growth of the mean local
time etc.
    Keywords: parallel computation, asymptotic independence.

A.L. Stolyar
On the Stability of Multiclass Queueing Networks: A Relaxed Sufficient Condition via Limiting Fluid Processes
pp. 491-512
     We consider a multiclass queueing network, whose underlying stochastic
process is a countable, continuous time Markov chain. Stability of the network
is understood as ergodicity of this Markov chain. The message class determines
a message route through the network and the mean message service time in each
node on its route. Each node may have its own queueing discipline within a wide
class, including FCFS, LCFS, Priority and Processor Sharing.
     We will show that the sequence of scaled (in space and time) underlying
stochastic processes converges to a fluid process with sample paths
defined as fixed points of a special operator. This convergence together
with continuity and similarity properties of the family of sample paths
of the fluid process allows us to prove the following result.
    If each sample path of the fluid process with non-zero initial state is such
that the ``amount of fluid'' in the network falls below its initial value
at least once, then the network is stable.
    Keywords: Multiclass queueing network, stability, fluid limit.

M. Bebbington, P. Pollett and X. Zheng
Dual Constructions for Pure-Jump Markov Processes
pp. 513-558
    In this paper we shall present a systematic treatment of the
construction of the dual of a pure-jump Markov process on a general
state space, specifically an inner-regular, measurable topological space
with a countable basis. Firstly, we prove the existence of a dual
$q$-pair with respect to an invariant or subinvariant measure and then
study its structure, highlighting those properties which are peculiar to
the uncountable-state setting. Next, we deal with the construction of
dual transition functions, giving particular attention to the minimal
process. This enables us to prove several results on invariant measures
for pure-jump processes which are analogous to those for Markov chains.
Finally, we shall explain how our results can be used in understanding
the relationship between invariant and subinvariant measures for a
transition function and those of the associated q-pair. Various
examples will be used to illustrate our results, and an application
given for a stochastic version of a slip-predictable model for
earthquake occurrences.
    Keywords: Markov processes, q-processes, invariant measures.