The Philosophers' Process on Graphs
Bernard Ycart
INRIA-Rocquencourt
Algorithms Seminar
November 18, 1997
[summary by Philippe Robert]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
1 Introduction
The talk is concerned with a stochastic model based on the dining
philosophers' problem which is called the philosophers process. The philosophers are on the
N vertices of some graph G, they have two states 0 or 1. The state
of the process is given by the vector h=(h(x)) where
h(x)Î{0,1} is the state of node x. The dynamics of this
process forbid the states where two vertices with value 1 are
neighbours.
The stochastic process is described as follows:
-
If a node has the value 1, then at rate 1 it becomes 0;
- If a node and all its neighbours have the value 0, then at rate
l, its value becomes 1.
This can be translated in a Markov process context; If
htÎ{0,1}N is the state of the process at time t, then its
generator Q=(q(h,z)) is given by
-
q(h,h-dx)= 1 if h(x)=1, where
dx(y)=1 if x=y and 0 otherwise;
- q(h, h+dx) = l if h(y)=0 for all
yÎ N(x), where N(x) is the set of the neighbours of
x;
- q(h,z)=0 otherwise if h¹z.
Because of the constraint on the 1's, only a subset S of
{0,1}N contains the states which are admissible. It is well known
that this process is reversible, that is at equilibrium the process
from time 0 to time T looks the same in distribution as in the
reversed time scale from T to 0. Its equilibrium measure p is
also known,
p(h)=[låx h(x)]/ZG, with hÎ S.
ZG is a normalizing constant, so that p( S)=1, also known as
the partition function. The constant ZG is a polynomial in
l, its
degree I corresponds to the states with a maximal number of nodes
with value 1. The coefficient of lI in ZG is the number of
states with I nodes with value 1. Hence, in some sense, finding the
explicit value of Z can be presented as a combinatorial problem.
The main results of this talk concern the explicit representations
that can be obtained for the equilibrium measure and in particular for
the partition function.
2 Markov random fields
We begin with some general definitions concerning Markov random
fields. These objects are probability measures on the state space
which can be expressed in terms of local specifications instead of a
global description such as the one we have encountered for p. It
turns out that the measure p as we shall see can also be expressed
in that setting. This result gives a simple recursive sequence to
express the partition function ZG.
Definition 1
(i). A probability measure µ on {0,1}N is a Markov Random Field
if for all U, V Ì {1,...,N} such that VÈ
N(V)Ì U, and h,
µ(hU)=µ(hU-V)µ(hV/hN(V)),
where hU is the set of coordinates of h whose index is in
U and N(V) is the set of the neighbours of V.
(ii). A probability measure µ on {0,1}N is a
clique system
if for all U Ì {1,...,N}, hÎ
S,
where the product is on the subsets C of the set of indices such
that C is a complete subset of U or C is in the complementary of U.
Obviously (ii) is stronger than (i). Roughly speaking, the definition (i)
expresses that the state on V can be determined by the neighbours
of V, in this sense µ has local specifications.
Proposition 1
The measure p defined above is a clique system.
Using the definition of Markov Random Fields, the following
proposition holds. It gives a recursive procedure to calculate the
partition function.
Proposition 2
If CÌ {1,...,N} is a complete subgraph of G, then
ZG= ZG-x+l ZG-x_, ZG= ZG-C+l åxÎ
CZG-x_, µG(h(x)=0)= ZG-x/ZG,
µG(h(x)=1)= ZG-x_/ZG.
3 Applications to some graphs
If G1 and G2 are two graphs, the Cartesian product of these
graphs G1× G2 is the graph for which the set of vertices is
the usual Cartesian product of the set of vertices. Two nodes are
neighbours, if one their coordinates is the same and the two other ones
are neighbours in the corresponding initial graph.
The graph in line [resp. on the torus] with m nodes is denoted
as Lm [resp. Cm].
Proposition 3
If Kn is the clique with n vertices, then the partition function
of the graphs Kn× Cm, Kn× Lm can be expressed
explicitly.
Some recursive procedures can also be defined in the case of
hypercubes and trees.
4 A phase transition phenomenon
Up to now, the state space of our processes were finite. The Markov
processes we considered were irreducible, i.e. with positive
probability one can reach one state from any other state. As a
consequence, a unique equilibrium measure existed. If the graph has an
infinite number of nodes, this is not the case anymore. It is possible
to have more than one equilibrium measure, and even an infinite
number. In this case the model is said to have a phase
transition. Although it occurs with infinite graphs, it also has
consequences for finite graphs. Roughly speaking, if
there are at least two invariant measures for the infinite graph, this
implies that for a finite graph converging to this graph, the
equilibrium measure will be a combination of at least two attractors
for the state process.
Here, we are interested by the Cartesian product Kn×
T¥d, where T¥d is the infinite regular tree of
degree d.
Proposition 4
If d³ n³ 2 and
l >(d+1)d/[dd(d-n+1)],
then the associated Markov process has more than one equilibrium
measure.
References
- [1]
-
Louth (G. M.). --
Stochastic Networks: Complexity, Dependence and Routing. --
PhD thesis, Cambridge University, December 1990.
- [2]
-
Ycart (B.). --
The philosophers' process: an ergodic reversible nearest particle
system. Annals of Applied Probability, vol. 3, n°2,
1993, pp. 356--363.
This document was translated from LATEX by
HEVEA.