Abstract | ||
---|---|---|
We determine the mixing time (up to a constant factor) of the Markov chain whose state space consists of n "dots" on the unit interval, wherein a dot is selected uniformly at random and moved to a uniformly random point between its two neighbors. The method involves a two-step coupling for the upper bound, and an unusual probabilistic second- moment argument for the lower. |
Year | Venue | Keywords |
---|---|---|
2005 | ALENEX/ANALCO | state space,mixing time,markov chain,upper bound |
Field | DocType | Citations |
Statistical physics,Combinatorics,Markov chain mixing time,Additive Markov chain,Upper and lower bounds,Markov chain,Unit interval,Balance equation,State space,Mathematics,Absorbing Markov chain | Conference | 1 |
PageRank | References | Authors |
0.44 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dana Randall | 1 | 29 | 8.15 |
Peter Winkler | 2 | 126 | 18.77 |