We consider two problems: randomly generating labeled bipartite graphs with
a given degree sequence and randomly generating labeled tournaments with a
given score sequence. We analyze simple Markov chains for both problems. F
or the first problem, we cannot prove that our chain is rapidly mixing in g
eneral, but in the near-regular case, i.e., when all the degrees are almost
equal, we give a proof of rapid mixing. Our methods also apply to the corr
esponding problem for general (nonbipartite) regular graphs, which was stud
ied earlier by several researchers. One significant difference in our appro
ach is that our chain has one state for every graph (or bipartite graph) wi
th the given degree sequence; in particular, there are no auxiliary states
as in the chain used by Jerrum and Sinclair. For the problem of generating
tournaments, we are able to prove that our Markov chain on tournaments is r
apidly mixing, if the score sequence is near-regular. The proof techniques
we use for the two problems are similar. (C) 1999 John Wiley & Sons, Inc.