Distance reducing Markov bases for sampling from a discrete sample space
by
Satoshi Aoki
Graduate School of Information Science and Technology, The University of Tokyo
Coauthors: Akimichi Takemura

We study Markov bases for sampling from a discrete sample space equipped with a convenient metric. Starting from any two states in the sample space, we ask whether we can always move closer by an element of a Markov basis. We call a Markov basis distance reducing if this is the case. The particular metric we consider in this talk is the 1-norm on the sample space. Some characterizations of 1-norm reducing Markov bases are derived.

Date received: November 26, 2004