Quick search | Browse volumes | |

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 processes

Nature: 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 probabilities

Nature: Original

Retrieve article from Numdam

XXXIX: 14, 269-303, LNM 1874 (2006)

**ALDOUS, David**; **PITMAN, James W.**

Two recursive decompositions of Brownian bridge related to the asymptotics of random mappings

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 processes

Nature: Original

Retrieve article from Numdam

XVII: 28, 243-297, LNM 986 (1983)

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 (

Keywords: Markov chains, Hitting probabilities

Nature: Original

Retrieve article from Numdam

XXXIX: 14, 269-303, LNM 1874 (2006)

Two recursive decompositions of Brownian bridge related to the asymptotics of random mappings