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: 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
  1. q(h,h-dx)= 1 if h(x)=1, where dx(y)=1 if x=y and 0 otherwise;
  2. 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;
  3. 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,
µ(hU)=
1
Z
 
Õ
C
QC(hC),
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.