Doob's h-transform

In mathematics, more specifically in stochastics, Doob's $h$ -transform is a method to transform a Markov process into a new Markov process, which exhibits certain properties. Most prominently, for a homogeneous Markov process $X$ with (random) lifetime $T$ , the reverse process $(X_{T - t})_{t \geq 0}$ and the conditioned process $X ∣ X_{T} = x$ on terminating at a single point $x$ , can be expressed as an $h$ -transform of the original process via some deterministic function $h$ . The method was first introduced by J. L. Doob in 1957 to analyze quotients $f / h$ of superharmonic functions $f$ and (positive) harmonic functions $h$ from a probabilistic point of view.

The key advantage of Doob's $h$ -transform is that the transition probabilities of the transformed process are explicitly given as functions of $h$ . If $X$ is an Itô diffusion, for example a Brownian motion, then under relatively mild conditions, the $h$ -transformed process is again an Itô diffusion with an explicit drift term depending on $\nabla \log h$ .

Motivation

Consider a $d$ -dimensional Brownian motion $W$ started in $x_{0}$ and stopped at the time $T$ , when it first hits the unit ball $B$ , and one is interested in the process $W^{x}$ of $W$ conditioned on hitting some point $x \in \partial B$ at time $T$ . In law, $W^{x}$ is given by $ℙ^{x_{0}} (W^{x} \in A) := ℙ^{x_{0}} (W \in A ∣ W_{T} = x) = ℙ (W \in A ∣ W_{T} = x, W_{0} = x_{0}),$ for any Borel set $A \subset {f \in C ([0, \infty), ℝ^{d}) : f (0) = x_{0}}$ .

According to Bayes formula, for some fixed $t \geq 0$ , conditioning $W_{t}$ on $W_{T}$ can be expressed in terms of the distribution of $W_{T}$ given $W_{t}$ and the distribution of $W_{t}$ , namely for $M \in ℬ (ℝ^{d})$ $ℙ^{x_{0}} (W_{t} \in M ∣ W_{T} = x) = \frac{1}{q (x ∣ x_{0})} \int_{M} q (x ∣ y) ℙ^{x_{0}} (W_{t} \in d y),$ with $q (x ∣ y) := \frac{d ℙ (W_{T} \in \cdot ∣ W_{t} = y)}{d σ} (x) = \frac{d ℙ^{y} (W_{T} \in \cdot)}{d σ} (x),$ where $σ$ denotes the uniform distribution on the sphere. In this context, the function $q$ happens to be the well-known Poisson kernel, which has the explicit formula $q (x ∣ y) = \frac{1}{σ (\partial B)} \frac{1 - ‖ y ‖^{2}}{‖ x - y ‖^{d}}, x \in \partial B, y \in B .$ The distribution of $W_{t}$ under $ℙ^{x_{0}}$ is explicit as well, since the Brownian Motion is a Gaussian process and so the Bayes formula for $W_{t}^{x}$ gives an explicit way to compute the transition probabilities. The Bayes formula from above is precisely an $h$ -transform of $W$ with $h = q (x ∣ \cdot)$ .

For the simulation of $W^{x}$ , one is interested in a stochastic differential equation for the latter. With the Bayes formula from above, the infinitesimal generator $𝒜^{x}$ of $W^{x}$ can be related to the generator $𝒜 = \frac{1}{2} Δ$ (the Laplace operator) of Brownian motion: For $f \in C^{2} (ℝ^{d})$ , and by denoting the Feller semigroups of $W$ and $W^{x}$ by $(P_{t})_{t \geq 0}$ and $(P_{t}^{x})_{t \geq 0}$ respectively, it holds for $y \in ℝ^{d}$ $\begin{matrix} 𝒜^{x} f (y) & = lim_{t \to 0} \frac{P_{t}^{x} f (y) - f (y)}{t} \\ = \frac{1}{q (x ∣ y)} lim_{t \to 0} \frac{P_{t} (q (x ∣ \cdot) f) (y) - q (x ∣ y) f (y)}{t} \\ = \frac{1}{q (x ∣ y)} 𝒜 (q (x ∣ \cdot) f) (y) \\ = \frac{1}{q (x ∣ y)} \nabla_{y} q (x ∣ y) \cdot \nabla f (y) + \frac{1}{2} Δ f (y), \end{matrix}$ because $Δ q (x ∣ \cdot) = 0$ . Comparing $𝒜^{x}$ with the generator of a general Itô diffusion, one can conclude that $d W_{t}^{x} = \nabla \log q (x ∣ W_{t}) d t + d W_{t}, W_{0} = x_{0} .$

Definition

Homogeneous Markov processes

Let $X$ be a homogeneous Markov process with state space $E$ , which is often assumed to be a locally compact Polish space to guarantee the existence of regular conditional expectations, and denote its transition semigroup by $(P_{t})_{t \geq 0}$ . Let $h : E \to [0, \infty]$ be an excessive function, that is, $\begin{matrix} \forall t \geq 0 : & \int_{E} h (y) P_{t} (x, d y) \leq h (x), \\ lim_{t \to 0} & \int_{E} h (y) P_{t} (x, d y) = h (x) . \end{matrix}$ Then the $h$ -transform $X^{h}$ is defined as the Markov process with transition semigroup $(P_{t}^{h})_{t \geq 0}$ defined by $P_{t}^{h} (x, A) := {\begin{matrix} \frac{1}{h (x)} \int_{A} h (y) P_{t} (x, d y), & x \in E ∖ {h = 0 or h = \infty} \\ 0, & x \in {h = 0 or h = \infty} \end{matrix}$ for all $t \geq 0$ and $A \in ℬ (E)$ .

This definition implies that in general $P_{t}^{h} (x, E) \leq 1$ , which means that the process need not staying inside its state space for all times. For such processes, one usually defines an additional cemetery state $\partial \notin E$ that the process enters with probability $1 - P_{t} (x, E)$ for all $x \in E$ and which it never leaves again, i.e., $P_{t} (\partial, {\partial}) = 1$ . In other words, the process is allowed to be killed at some finite time. On the extended state space $E_{\partial} = E \cup {\partial}$ , the $P_{t}^{h} (x, \cdot)$ with the previous definitions are probability measures for all $x \in E_{\partial}$ by construction.

The points $x \in {h = 0 or h = \infty}$ are so-called branching points, for which it holds $P_{0} (x, {x}) = 0$ and $P_{0} (x, {\partial}) = 1$ . Thus, the $h$ -transformed process never enters the set ${h = 0 or h = \infty}$ , and it is killed at the random time $T^{h} = inf {t \geq 0 : X_{t}^{h} = \partial}$ .

Inhomogeneous Markov processes

Let $X$ be an inhomogeneous Markov process with values in $ℝ^{d}$ , inhomogeneous transition probabilities $(P_{t, s})_{t \geq s \geq 0}$ and let $h : [0, \infty) \times ℝ^{d} \to (0, \infty)$ be space-time regular, that is, for $s > 0$ , $t \geq 0$ and $x \in ℝ^{d}$ $h (t, x) = \int_{ℝ^{d}} h (t + s, y) P_{t + s, s} (x, d y) .$ Then the $h$ -transform $X^{h}$ is defined as the (inhomogeneous) Markov process with transition probabilities $(P_{t, s}^{h})_{t \geq s \geq 0}$ defined by $P_{t + s, s}^{h} (x, A) := \frac{1}{h (t, x)} \int_{A} h (t + s, y) P_{t + s, s} (x, d y), \forall x \in E, A \in ℬ (E) .$

Properties

In the theory of $h$ -transforms for homogeneous Markov processes $X$ on a filtered probability space $(Ω, ℱ, (ℱ_{t})_{t \geq 0}, ℙ)$ it is assumed that

$X_{0}$ is distributed according to some distribution $μ$ ,
$X$ has a lifetime $T$ , that is, a random variable (not necessarily a stopping time) such that $X_{t} (ω) \in E$ for $t > T (ω)$ and $X_{t} (ω) = \partial$ for $t \geq T (ω)$ ,
$X$ is a strong Markov process with càdlàg paths on $(0, T)$ .

For simplicity, the underlying probability space is usually chosen as the canonical space of càdlàg paths with values in $(E, ℬ (E))$ and $X$ as the identity.

Probabilities

The transition semigroup $(P_{t}^{h})_{t \geq 0}$ generates a family of probability measures $(ℙ_{h}^{x})_{x \in E}$ on the canonical space of càdlàg paths. For any stopping time $τ$ , it holds for $A \in ℱ_{τ}$ and $x \in E ∖ {h = 0 or h = \infty}$

$ℙ_{h}^{x} (A, T > τ) = \frac{1}{h (x)} 𝔼^{x} [1_{A} h (X_{τ})] .$

For a family $(u_{s})_{s \in S}$ of excessive functions on $E$ over an index set $S$ (and measurable w.r.t. the product $σ$ -algebra on $E \times S$ ), if $h$ is of the form

$h (x) = \int_{S} u_{s} (x) d β (s)$

with some finite measure $β$ on $S$ , then for $A \in ℱ$ the probability simplifies to

$ℙ_{h}^{x} (A) = \frac{1}{h (x)} \int_{S} u_{s} (x) ℙ_{u_{s}}^{x} (A) d β (s) .$

Infinitesimal generator

As an almost direct consequence of the above, if $X$ has infinite lifetime ( $T = \infty$ ) and has generator $A$ , then the generator of its $h$ -transformed process $X^{h}$ is

$\begin{matrix} A^{h} f (x) = lim_{t \to 0} \frac{𝔼^{x} [f (X_{t}^{h})] - f (x)}{t} & = \frac{1}{h (x)} lim_{t \to 0} \frac{𝔼^{x} [f (X_{t}) h (X_{t})] - f (x) h (x)}{t} \\ = \frac{1}{h (x)} A (f h) (x) \end{matrix}$

for all $x \in E$ and all functions $f$ such that $f h$ is in the domain of $A$ .

Killing

If $τ$ is a co-optional time, that is, if for any $t \geq 0$ it holds $τ \circ θ_{t} = (τ - t)^{+}$ , where $(θ_{s})_{s \geq 0}$ is the shift-semigroup, then one can define $\begin{matrix} h (x) := ℙ^{x} (τ > 0), x \in E \\ X_{t}^{τ} := {\begin{matrix} X_{t}, & t < τ \\ \partial, & t \geq τ \end{matrix} \end{matrix}$ for which it holds that $X^{τ}$ is an $h$ -transform of $X$ .

Time-reversal

The time-reversal $\overset{\leftarrow}{X}$ of $X$ is defined as

$\overset{\leftarrow}{X_{t}} (ω) = {\begin{matrix} X_{T (ω) - t}, & t \leq T (ω) \\ \partial, & t > T (ω) or T (ω) = \infty \end{matrix} .$

$\overset{\leftarrow}{X}$ is again a homogeneous Markov process, however now with left-continuous paths.

If $X^{h}$ has initial measure $ν \propto h \cdot d μ$ , then the reverses of $X$ and $X^{h}$ have the same transition probabilities. In particular, for a co-optional time $τ$ (for example a last hitting time), if $X$ starts in a fixed point almost surely, then the reverses of $X$ and $X^{τ}$ have the same transition probabilities.

Moreover, if $X$ possesses a dual process $\hat{X}$ (defined below), then its reverse can be expressed as an $h$ -transform of its dual. To formulate this statement, we define for $X$ and $\hat{X}$ respectively the transition semigroups $(P_{t})_{t \geq 0}$ and $({\hat{P}}_{t})_{t \geq 0}$ , and, for $p \geq 0$ , the resolvents

$\begin{matrix} U_{p} := \int_{0}^{\infty} e^{- p t} P_{t} d t, \\ {\hat{U}}_{p} := \int_{0}^{\infty} e^{- p t} {\hat{P}}_{t} d t . \end{matrix}$

While for $p > 0$ the resolvents are always finite, $U_{0}$ can become infinite.

As the dual of $X$ , $\hat{X}$ must fulfill for some measure $ν$

$\hat{X}$ is a strong Markov process with càdlàg paths,
For all $p \geq 0$ and $f, g \geq 0$ measurable: $\int_{E} \int_{E} f (y) U_{p} (x, d y) g (x) d ν (x) = \int_{E} f (x) \int_{E} g (y) {\hat{U}}_{p} (x, d y) d ν (x),$
For all $p \geq 0$ and $x \in E$ , both $U_{p} (x, \cdot)$ and ${\hat{U}}_{p} (x, \cdot)$ are absolutely continuous w.r.t. $ν$ .

By setting

$h (y) := \int_{E} \frac{d U_{0} (x, \cdot)}{d ν} (y) d μ (x) := \int_{E} u_{0} (x, y) d μ (x), y \in E,$

if $0 < h < \infty$ , then $\overset{\leftarrow}{X}$ and ${\hat{X}}^{h}$ have the same transition probabilities.

Conditioning

Doob's $h$ -transform can also be used to condition the process $X$ on hitting a distinct point or, more generally, to attain a pre-determined distribution at its lifetime. For simplicity, it is supposed that ${\hat{P}}_{0} (x, {x}) = 1$ for all $x \in E$ , that is, the dual process $\hat{X}$ has no branching points.

Let $y \in E$ and $U_{0}$ be the resolvent of $X$ for $p = 0$ as defined above. Then with

$h (x) = u_{0} (x, y),$

it holds that $X_{T -}^{h} = lim_{t ↑ T} X_{t}^{h} = y$ almost surely on ${T < \infty}$ .

If $μ = δ_{x_{0}}$ , that is, $X$ starts in $x_{0}$ almost surely, and $α$ is a distribution on $E$ such that

$β (A) = \int_{A} \frac{1}{u_{0} (x, y)} d α (y), A \in ℬ (E),$

is a $σ$ -finite measure, then one can achieve $X_{T -}^{h} \sim α$ by choosing

$h (x) := \int_{E} u_{0} (x, y) d β (y) = \int_{E} \frac{u_{0} (x, y)}{u_{0} (x_{0}, y)} d α (y) .$

Applications

Generative modelling

Doob's $h$ -transform has begun to find applications in generative modelling, for example for point clouds, climate data, graphs and image segmentation. The method has also been proposed for faster conditional training and sampling of diffusion models.

Notes

↑ Doob, Joseph L. (1957). "Conditional Brownian motion and the boundary limits of harmonic functions". Bulletin de la Société Mathématique de France. 45: 431–458. doi:10.24033/bsmf.1494. hdl:2027/mdp.39015095252097.
↑ Doob, Joseph L. (1958). "Probability and the first boundary value problem". Illinois Journal of Mathematics. 2: 19–36. doi:10.1215/ijm/1255380830.
↑ Chung & Walsh 2005, p. 334.
1 2 Särkkä & Solin 2019, pp. 113–115.
1 2 Rogers & Williams 2000, p. 83–86.
↑ Chung & Walsh 2005, p. 45.
↑ Chung & Walsh 2005, p. 320.
↑ Chung & Walsh 2005, p. 325.
↑ Chung & Walsh 2005, p. 326.
↑ Chung & Walsh 2005, p. 331.
↑ Chung & Walsh 2005, pp. 303–304.
↑ Chung & Walsh 2005, p. 333.
↑ Chung & Walsh 2005, p. 366.
1 2 Chung & Walsh 2005, p. 368.
↑ Ye, Mao; Wu, Lemeng; Liu, Qiang (2022). "First Hitting Diffusion Models for Generating Manifold, Graph and Categorical Data". Advances in Neural Information Processing Systems. 35: 27280–27292. arXiv:2209.01170. doi:10.52202/068431-1978. ISBN 978-1-7138-7108-8.{{cite journal}}: CS1 maint: periodical has ISBN (link)
↑ Denker, Alexander; Vargas, Francisco; Padhy, Shreyas; Didi, Kieran; Mathis, Simon; Dutordoir, Vincent; Barbano, Riccardo; Mathieu, Emile; Komorowska, Urszula Julia; Lio, Pietro (2024). "DEFT: Efficient Fine-Tuning of Diffusion Models byLearning the Generalised h-transform". Advances in Neural Information Processing Systems. 37: 19636–19682. doi:10.52202/079017-0620. ISBN 979-8-3313-1438-5.{{cite journal}}: CS1 maint: periodical has ISBN (link)

References

Chung, Kai Lai; Walsh, John B. (2005). Markov Processes, Brownian Motion, and Time Symmetry (2nd ed.). Springer. doi:10.1007/0-387-28696-9. ISBN 978-0387-22026-0.
Doob, Joseph L. (1984). Classical Potential Theory and Its Probabilistic Counterpart. Springer. ISBN 978-3642-56573-1.
Rogers, L.C.G; Williams, David (2000). Diffusions, Markov Processes, and Martingales. Vol. 2 (2nd ed.). Cambridge: Cambridge University Press. ISBN 0-521-77593-0.
Särkkä, Simo; Solin, Arno (2019). Applied Stochastic Differential Equations. Cambridge University Press. doi:10.1017/9781108186735. ISBN 978-1108-18673-5.

[1] Doob, Joseph L. (1957). "Conditional Brownian motion and the boundary limits of harmonic functions". Bulletin de la Société Mathématique de France. 45: 431–458. doi:10.24033/bsmf.1494. hdl:2027/mdp.39015095252097.

[2] Doob, Joseph L. (1958). "Probability and the first boundary value problem". Illinois Journal of Mathematics. 2: 19–36. doi:10.1215/ijm/1255380830.

[FOOTNOTEChungWalsh2005334-3] Chung & Walsh 2005, p. 334.

[FOOTNOTESärkkäSolin2019113–115-4] 1 2 Särkkä & Solin 2019, pp. 113–115.

[FOOTNOTERogersWilliams200083–86-5] 1 2 Rogers & Williams 2000, p. 83–86.

[FOOTNOTEChungWalsh200545-6] Chung & Walsh 2005, p. 45.

[FOOTNOTEChungWalsh2005320-7] Chung & Walsh 2005, p. 320.

[FOOTNOTEChungWalsh2005325-8] Chung & Walsh 2005, p. 325.

[FOOTNOTEChungWalsh2005326-9] Chung & Walsh 2005, p. 326.

[FOOTNOTEChungWalsh2005331-10] Chung & Walsh 2005, p. 331.

[FOOTNOTEChungWalsh2005303–304-11] Chung & Walsh 2005, pp. 303–304.

[FOOTNOTEChungWalsh2005333-12] Chung & Walsh 2005, p. 333.

[FOOTNOTEChungWalsh2005366-13] Chung & Walsh 2005, p. 366.

[FOOTNOTEChungWalsh2005368-14] 1 2 Chung & Walsh 2005, p. 368.

[15] Ye, Mao; Wu, Lemeng; Liu, Qiang (2022). "First Hitting Diffusion Models for Generating Manifold, Graph and Categorical Data". Advances in Neural Information Processing Systems. 35: 27280–27292. arXiv:2209.01170. doi:10.52202/068431-1978. ISBN 978-1-7138-7108-8.{{cite journal}}: CS1 maint: periodical has ISBN (link)

[16] Denker, Alexander; Vargas, Francisco; Padhy, Shreyas; Didi, Kieran; Mathis, Simon; Dutordoir, Vincent; Barbano, Riccardo; Mathieu, Emile; Komorowska, Urszula Julia; Lio, Pietro (2024). "DEFT: Efficient Fine-Tuning of Diffusion Models byLearning the Generalised h-transform". Advances in Neural Information Processing Systems. 37: 19636–19682. doi:10.52202/079017-0620. ISBN 979-8-3313-1438-5.{{cite journal}}: CS1 maint: periodical has ISBN (link)