XV: 23, 311-319, LNM 850 (1981)
ALDOUS, David J.;
BARLOW, Martin T.
On countable dense random sets (
General theory of processes,
Point processes)
This paper is devoted to random sets $B$ which are countable, optional (i.e., can be represented as the union of countably many graphs of stopping times $T_n$) and dense. The main result is that whenever the increasing processes $I_{t\ge T_n}$ have absolutely continuous compensators (in which case the same property holds for any stopping time $T$ whose graph is contained in $B$), then the random set $B$ can be represented as the union of all the points of countably many independent standard Poisson processes (intuitively, a Poisson measure whose rate is $+\infty$ times Lebesgue measure). This may require, however, an innocuous enlargement of filtration. Another characterization of such random sets is roughly that they do not intersect previsible sets of zero Lebesgue measure. Note also an interesting example of a set optional w.r.t. two filtrations, but not w.r.t. their intersection
Keywords: Poisson point processesNature: Original
Retrieve article from Numdam
XVII: 28, 243-297, LNM 986 (1983)
ALDOUS, David J.
Random walks on finite groups and rapidly mixing Markov chains (
Markov processes)
The ``mixing time'' for a Markov chain---how many steps are needed to approximately reach the stationary distribution---is defined here by taking the variation distance between measures and the worst possible starting point, and bounded above by coupling arguments. For the simple random walk on the discrete cube $\{0,1\}^d$ with large $d$, there is a ``cut-off phenomenon'', an abrupt change in variation distance from 1 to 0 around time $1/4\ d\,\log d$. For a natural model of riffle shuffle of an $n$-card deck, there is an analogous cut-off at time $3/2\ \log n$. The relationship between ``rapid mixing'' and approximate exponential distribution for first hitting times on small subsets, is also discussed
Comment: In the 1960s and 1970s, Markov chains were considered by probabilists as rather trite objects. This work was one of several papers that prompted a reassessment and focused attention on the question of mixing time. In 1981, Diaconis-Sashahani (
Z. Wahrsch. Verw. Gebiete 57) had established the cut-off phenomenon for a different shuffling scheme. For a random walk on a graph, Alon (
Combinatorica 6, 1986) related an eigenvalue-based mixing time to expansion properties of the graph, and parallel work of Lawler-Sokal (
Trans. Amer. Math. Soc. 309, 1988) in the broader setting of reversible chains made a connection with models from statistical physics. Jerrum-Sinclair (
Inform. and Comput. 82, 1989) gave the first deep use of Markov chain methods in the theory of algorithms, while Geman-Geman (
IEEE Trans. Pattern Anal. Machine Intell. 6, 1984) promoted the use of Markov chains in image reconstruction. Such papers brought the attention of probabilists to the Metropolis algorithm in statistical physics, and foreshadowed the development of Markov chain Monte Carlo methods in Bayesian statistics, e.g. Smith (
Philos. Trans. Roy. Soc. London 337, 1991)
Keywords: Markov chains,
Hitting probabilitiesNature: Original Retrieve article from Numdam
