Faster random generation of linear extensions

AbstractThis paper examines the problem of sampling (almost) uniformly from the set of linear extensions of a partial order, a classic problem in the theory of approximate sampling. Previous techniques have relied on deep geometric arguments, or have not worked in full generality. Recently, focus has centred on the Karzanov and Khachiyan Markov chain. In this paper, we define a slightly different Markov chain, and present a very simple proof of its rapid mixing, using the method of path coupling. We show that this chain has mixing time O(n3logn), which significantly improves the previous best bound for this problem, which was a bound of O(n5logn), for the Karzanov and Khachiyan chain.We also show how a classical metric, Spearman's footrule, may be reformulated in terms of transpositions