Markov bridge processes

Especially Lévy bridges, Doob h-transforms

2019-10-15 — 2022-04-20

Lévy processes
point processes
probability
spatial
stochastic processes

Suspiciously similar content

A bridge process for some time-indexed Markov process {x(t)}t∈[0,T] is obtained from that process by conditioning it to attain a fixed value at the final time x(T)=Y starting from x(0)=X, on an interval [0,T]. We write that as {x(t)∣x(0)=X,x(T)=Y}t∈[0,T]. Put another way, given the starting and finishing values of a stochastic Markov process, I would like to rewind time to find out the values of its path at a midpoint which is “compatible” with the endpoints.

There is a more general version given in e.g. Privault and Zambrini () where the initial and final states of the process are permitted to have distributions rather than fixed values. That distribution→distribution variant has recently become popular in generative modelling because although it is not easy to solve analytically, it is easy to learn; see Learning Schrödinger Bridges.

This notebook is about the most basic version of the bridge process.

1 Lévy bridges

I am mostly interested in bridges for Lévy increment processes in particular.

It is easy to define a bridge for a Lévy process. For simplicity, we shall take it to be {x(t)}t∈[0,1] for s∈(0,1) and assume x(0)=1. Suppose we wish to find the marginal distribution of one point on the bridge {x(s)∣x(1)=Y}s∈(0,1). We know x(1)=dx′(s)+x″(1−s) where x′(s) is an independent copy of x. Also, it follows that Ex″(1−s)=(1−s)Ex(1), Ex′(s)=sEx(1) and (x(s)∣x(1)=Y)+x‴(1−s)=dx(1). The bridge is a random function mapping y into the required conditional. TBC

It is trivial (more or less) to derive the properties of the bridge for a Wiener process, so that can be found in every stochastic processes textbook. There is an introduction for Lévy processes in (). 🚧TODO🚧 clarify

Fitzsimmons, Pitman, and Yor () describes a general assortment of methods for handling the properties of bridges, and Perman, Pitman, and Yor () specialises them on pure jump processes (Poisson, gamma).

🏗

Figure 1: In fact “bridge” is a terrible metaphor for these processes and it has simplified nothing for me to use this image as an illustration I am so sorry.

1.1 When is a Lévy bridge distribution computationally tractable?

I know it is simple for Gamma, Brownian, and Poisson Lévy processes. Are there others? Yor () asserts that among the Lévy processes, only Brownian and Gamma processes have closed form expressions for the bridge. That is not right; a Poisson process has a simple bridge (binomial sub-division of the increment). Also, both Gamma and Brownian can admit a deterministic drift term.

Anyway, there is a lot of work on conditioning Brownian processes and more generally Gaussian processes; see Gaussian processes, esp. Gaussian processes with pathwise conditioning.

However, I cannot think of other easy examples. Compound Poisson processes, for example, will have a nasty integral term over an unbounded number of dimensions if we do it the obvious way.

Surely there are proofs about this? I have half a mind to see if I cannot find a classification of processes admitting tractable bridges with my rudimentary variational calculus skills.

2 Continuous time, discrete-state Markov processes

A classic. TBC.

3 Doob’s h-transform

i.e. not just process with stationary increments, but satisfying the Markov property.

Alexandre Hoang Thiery describes Doob’s h-transform method for general Markov processes and notes that while it might be good for deducing certain properties of the paths of such a conditioned process, it is not necessarily a good way of sampling it. Although if you happen to derive an analytic form that way, it is good for both.

For a fairly old concept, work in the area skews surprisingly recent (i.e post 1990), given that applications seem to cite the early, gruelling () as the foundation; perhaps for about 30 years no-one wanted to learn enough potential theory to make it go? Or perhaps I am missing something because of e.g. terminology drift.

See also

4 References

Albergo, Boffi, and Vanden-Eijnden. 2023. “Stochastic Interpolants: A Unifying Framework for Flows and Diffusions.”
Arnaudon, van der Meulen, Schauer, et al. 2022. “Diffusion Bridges for Stochastic Hamiltonian Systems and Shape Evolutions.” SIAM Journal on Imaging Sciences.
Battisti. 2010. “Markov Chains and Schrodinger Bridges.”
Bertoin. 1996. Lévy Processes. Cambridge Tracts in Mathematics 121.
Bloemendal. 2010. “Doob’s h-Transform: Theory and Examples.”
Brekelmans, and Neklyudov. 2023. “On Schrödinger Bridge Matching and Expectation Maximization.”
Chen, Georgiou, and Pavon. 2014. “On the Relation Between Optimal Transport and Schr"odinger Bridges: A Stochastic Control Viewpoint.”
Chung, and Walsh, eds. 2005. “H-Transforms.” In Markov Processes, Brownian Motion, and Time Symmetry. Grundlehren Der Mathematischen Wissenschaften.
Chung, Walsh, and Chung. 2005. Markov Processes, Brownian Motion, and Time Symmetry. Grundlehren Der Mathematischen Wissenschaften 249.
De Bortoli, Thornton, Heng, et al. 2021. “Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling.” In Proceedings of the 35th International Conference on Neural Information Processing Systems. NIPS ’21.
Dembo. 2013. “Stochastic Processes Lecture Notes.”
Doob. 1957. “Conditional brownian motion and the boundary limits of harmonic functions.” Bulletin de la Société Mathématique de France.
Dufresne. 1998. “Algebraic Properties of Beta and Gamma Distributions, and Applications.” Advances in Applied Mathematics.
Émery, and Yor. 2004. “A Parallel Between Brownian Bridges and Gamma Bridges.” Publications of the Research Institute for Mathematical Sciences.
Fitzsimmons, Pitman, and Yor. 1993. “Markovian Bridges: Construction, Palm Interpretation, and Splicing.” In Seminar on Stochastic Processes, 1992. Progress in Probability.
Gasbarra, Sottinen, and Valkeila. 2007. “Gaussian Bridges.” In Stochastic Analysis and Applications.
Gottwald, Li, Marzouk, et al. 2024. “Stable Generative Modeling Using Schrödinger Bridges.”
Gottwald, Liu, Marzouk, et al. 2025. “Localized Diffusion Models for High Dimensional Distributions Generation.”
Gottwald, and Reich. 2024. “Localized Schrödinger Bridge Sampler.”
Heng, De Bortoli, Doucet, et al. 2022. “Simulating Diffusion Bridges with Score Matching.”
Jacod, and Protter. 1988. “Time Reversal on Levy Processes.” The Annals of Probability.
Janson. 2011. “Stable Distributions.” Eprint arXiv:1112.0220.
Léonard. 2012. “From the Schrödinger Problem to the Monge–Kantorovich Problem.” Journal of Functional Analysis.
———. 2014. “A Survey of the Schrödinger Problem and Some of Its Connections with Optimal Transport.” Discrete & Continuous Dynamical Systems - A.
Levin, Peres, and Wilmer. 2009. Markov Chains and Mixing Times.
Malory, and Sherlock. 2016. “Residual-Bridge Constructs for Conditioned Diffusions.”
O’Connell. 2003a. “A Path-Transformation for Random Walks and the Robinson-Schensted Correspondence.” Transactions of the American Mathematical Society.
———. 2003b. “Conditioned Random Walks and the RSK Correspondence.” Journal of Physics A: Mathematical and General.
Perman, Pitman, and Yor. 1992. “Size-Biased Sampling of Poisson Point Processes and Excursions.” Probability Theory and Related Fields.
Privault, and Zambrini. 2004. “Markovian Bridges and Reversible Diffusion Processes with Jumps.” Annales de l’Institut Henri Poincare (B) Probability and Statistics.
Shi, Bortoli, Deligiannidis, et al. 2022. “Conditional Simulation Using Diffusion Schrödinger Bridges.”
Steutel, F. W., and van Harn. 1979. “Discrete Analogues of Self-Decomposability and Stability.” The Annals of Probability.
Steutel, Fred W., and van Harn. 2003. Infinite Divisibility of Probability Distributions on the Real Line.
Stromme. 2023. “Sampling From a Schrödinger Bridge.” In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics.
Whitaker, Golightly, Boys, et al. 2017. “Improved Bridge Constructs for Stochastic Differential Equations.” Statistics and Computing.
Wolpert. 2021. “Lecture Notes on Stationary Gamma Processes.” arXiv:2106.00087 [Math].
Yor. 2007. “Some Remarkable Properties of Gamma Processes.” In Advances in Mathematical Finance. Applied and Numerical Harmonic Analysis.