Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Let
be a unique sink orientation on the d-cube. Take a
direction i and consider any two vertices v,w of Cd such that
and
(that is, v lies in the ``top facet'' and
w in the ``bottom facet'' with respect to direction i). Suppose
that within the subcube they span, v and w have the same out-map
except possibly for direction i, i.e.,
Conversely, if we fix two (d-1)-dimensional unique sink orientations
and
on these facets, these orientations define an equivalence relation on
the edges in direction i. Moreover, if we orient the edges in
direction i, we obtain a unique sink orientation on the whole cube
iff we give the same orientation to edges in a common equivalence
class.
Based on these observations, Pavel Valtr and Jirí Matousek
have designed the following Markov chain whose stationary distribution is the
uniform distribution on the set
of all unique sink orientations on the
d-dimensional cube.
Let
be a given unique sink orientation on the d-cube.
Choose a direction
uniformly at random. Then the
edges in direction i are partitioned into a certain number
of equivalence
classes. With probability 1/2, we flip all the edges in one class, and
we do so independently for each equivalence class.
This defines a Markov chain on .
For
,
let
denote the probability that
starting from
,
we arrive at
in one step as described
above. Thus,
is the transition matrix of our
Markov chain.
Note that
,
unless
and
agree on
all edges except possibly on some in a fixed direction, that is, unless
and
for some (unique) i. In this case,
In particular, it follows that
for all
.
Translated into the terminology of random
processes, the first observation means that our Markov chain is
symmetric, while the second one implies that it is aperiodic.
Moreover, it is also irreducible, i.e. for any two
,
there is a positive probability of
getting from
to
in a finite number of transitions. This
is the case because one can get from any
to the uniform
orientation
(and back, by symmetry): We can make all edges in
a given direction i uniformly oriented by flipping certain equivalence
classes of edges in this direction. Proceeding by one direction at a
time, we obtain the uniform orientation.
These three observations imply that the Markov chain converges to a stationary distribution, i.e. a probability distribution
such that
,
and
that
is, in fact, the uniform distribution.
The question remains, of course, whether we can say anything about the mixing rate.