Name
Abstract | ||
|---|---|---|
We determine, up to a log factor, the mixing time of a Markov chain whose state space consists of the successive distances between n labeled “dots” on a circle, in which one dot is selected uniformly at random and moved to a uniformly random point between its two neighbors. The method involves novel use of auxiliary discrete Markov chains to keep track of a vector of quadratic parameters. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11538462_36 | APPROX-RANDOM |
Keywords | Field | DocType |
successive distance,quadratic parameter,auxiliary discrete markov chain,state space,log factor,novel use,markov chain,random point,mixing time | Total variation,Discrete mathematics,Combinatorics,Markov chain,Quadratic equation,Combinatorial optimization,Stationary distribution,State space,Mathematics | Conference |
Volume | ISSN | ISBN |
3624 | 0302-9743 | 3-540-28239-4 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dana Randall | 1 | 29 | 8.15 |
| Peter Winkler | 2 | 583 | 85.60 |