Quick search | Browse volumes | |

XII: 32, 446-456, LNM 649 (1978)

**TAYLOR, John C.**

Some remarks on Malliavin's comparison lemma and related topics (Diffusion theory)

The comparison lemma considered here gives estimates for the hitting probabilities of a several dimensional diffusion in terms of the hitting probabilities of a half line for suitably constructed one-dimensional diffusions. A self-contained proof is given

Keywords: Hitting probabilities

Nature: Original

Retrieve article from Numdam

XIV: 39, 347-356, LNM 784 (1980)

**CHUNG, Kai Lai**

On stopped Feynman-Kac functionals (Markov processes, Diffusion theory)

Let $(X_t)$ be a strong Markov process with continuous paths on the line, and let $\tau_b$ be the hitting time of the point $b$. It is assumed that $\tau_b$ is $P_a$-a.s. finite for all $a,b$. The purpose of the paper is to study the quantities $u(a,b)=E_a[\,\exp(\int_0^{\tau_b} q(X_s)\,ds)\,]$ where $q$ is bounded. Then (among other results) if $u(a,b)<\infty$ for all $a<b$, we have $u(a,b)\,u(b,a)\le 1$ for all $a,b$

Keywords: Hitting probabilities

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

Some remarks on Malliavin's comparison lemma and related topics (Diffusion theory)

The comparison lemma considered here gives estimates for the hitting probabilities of a several dimensional diffusion in terms of the hitting probabilities of a half line for suitably constructed one-dimensional diffusions. A self-contained proof is given

Keywords: Hitting probabilities

Nature: Original

Retrieve article from Numdam

XIV: 39, 347-356, LNM 784 (1980)

On stopped Feynman-Kac functionals (Markov processes, Diffusion theory)

Let $(X_t)$ be a strong Markov process with continuous paths on the line, and let $\tau_b$ be the hitting time of the point $b$. It is assumed that $\tau_b$ is $P_a$-a.s. finite for all $a,b$. The purpose of the paper is to study the quantities $u(a,b)=E_a[\,\exp(\int_0^{\tau_b} q(X_s)\,ds)\,]$ where $q$ is bounded. Then (among other results) if $u(a,b)<\infty$ for all $a<b$, we have $u(a,b)\,u(b,a)\le 1$ for all $a,b$

Keywords: Hitting probabilities

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