Random sampling of labeled tournaments (Q1967114)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random sampling of labeled tournaments |
scientific article |
Statements
Random sampling of labeled tournaments (English)
0 references
12 March 2000
0 references
A tournament \(T\) is an oriented complete graph modeling a real-life round robin tournament with no ties. The paper extents a recent result of \textit{R. Kannan, P. Tetali}, and \textit{S. Vempale} [Random Struct. Algorithms 14, No.~4, 293-308 (1999; Zbl 0933.05145)]. It is shown that to any tournament \(T\) there is a Markov chain \(M\) having states associated with the tournaments equivalent in some sense with \(T\) (they have the same number of nodes and the same score function) having the property that after a bounded number of steps (the upper bound of the number of steps is given) the probability that \(M\) is in a state \(S\) is the same for all the states of \(M\).
0 references
tournaments
0 references
random sampling
0 references
Markov chains
0 references