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.