Conditioned Brownian motion, 1st Laplacian eigenfunction, etc…

October 25, 2011 at 1:07 pm (Brownian motion, markov chain, Markov process, probability)
Tags: , , , , ,

Brownian Motion

Brownian Motion

A few days ago, a student asked the following question:

Consider a bounded domain {D \subset \mathbb{R}^d} and a Brownian motion conditioned to stay inside {D}. How does it look like ? What is the invariant distribution ?

This is very simple, and surprisingly interesting. This involves the first eigenfunction of the Laplacian on {D}. To make everything simple, and because this does not change anything, it suffices to study the situation where {D=[0,1] \subset \mathbb{R}}. In other words, what does a real Brownian motion conditioned to stay inside the segment {[0,1]} look like.

Discretisation

One could directly do the computations in a continuous setting but, as it is often the case, it is simpler to consider the usual random walk discretisation of a Brownian motion. For this purpose, consider a time discretisation {\delta>0} and a standard random walk {X_k} with increment {\pm \sqrt{\delta}}: with probability {\frac12} the random walk goes up {+\sqrt{\delta}} and with probability {\frac12} it goes down {-\sqrt{\delta}}. For clarity, assume that there exists an integer {m_{\delta} \in \mathbb{N}} such that {m_{\delta} \sqrt{\delta} = 1}. Suppose as well that it is conditioned on the event {X_k \in [0,1]} for {k=1, \ldots, N}. Later, we will consider the limiting case {N \rightarrow \infty} and {\delta \rightarrow 0}, in this order, to recover the Brownian motion case.

Conditioning

First, let us compute the probability transitions of the random walk {\{X_k\}_{k=0}^N} conditioned on the event {X_k \in [0,1]} for {k=1, \ldots, N}. For clarity, let us denote the conditioned random walk by {\hat{X} = \big\{ \hat{X}_k \big\}_{k \geq 0}}. This is a Doob h-transform, and the resulting process is a non-homogenous Markov chain. In this simple case the computations are straightforward. The conditioned Markov chain has transition probabilities given by {\hat{P}(k,x,y) = \mathbb{P}[\hat{X}_{k+1}=y \,|\hat{X}_k=x]} with {x,y \in D_{\delta}} where {D_{\delta} = \sqrt{\delta} \mathbb{N} \; \cap \; [0,1]}. One can compute the probability that the conditioned Markov chain follows a given trajectory {(x_0, \ldots, x_N)} of {D_{\delta}},

\displaystyle \begin{array}{rcl} \mathbb{P}[\hat{X}_0 = x_0, \ldots, \hat{X}_N=x_N] = \frac{1}{Z(N,\delta)} P(x_0,x_1) \times \ldots \times P(x_{N-1}, x_N) \end{array}

where {P(x,y)} is the transition kernel of the unconditioned Markov chain and {Z(N,\delta) = \mathbb{P}[X_k \in D_{\delta} \; \text{for} \; k=0, \ldots, N]} is a normalisation constant. The Doob h-transform simply consists in noticing that this also reads

\displaystyle \begin{array}{rcl} \mathbb{P}[\hat{X}_0 = x_0, \ldots, \hat{X}_N=x_N] = \hat{P}(0,x_0,x_1) \times \ldots \times \hat{P}(N-1,x_{N-1}, x_N) \end{array}

where the conditioned Markov kernel is {\hat{P}(k,x_k,x_{k+1}) = \frac{P(x,y) \, h(k+1,y)}{h(k,x)}} and the function {h(\cdot, \cdot)} is defined by

\displaystyle \begin{array}{rcl} h(k,x) = \mathbb{P}[X_{j} \in D_{\delta} \; \text{for} \; k+1 \leq j \leq N \, |X_k=x]. \end{array}

Of course we have {h(N,x)=1} for all {x \in D_{\delta}}. The quantity {h(x,k)} is the probability that a random walk starting at {x \in D_{\delta}} at time {k} remains inside {D_{\delta}} for time {k,k+1, \ldots, N}. Consequently, in order to find the transition probabilities of the conditioned kernel, it suffices to compute the quantities {h(k, x)} for all {x \in D_{\delta}}. Since we are interested in the limiting case {N \rightarrow \infty}, it actually suffices to consider the case {k=0}. It can be computed recursively since {h(k,x) = \frac12 \, h(k+1, x+\sqrt{\delta}) + \frac12 \, h(k+1, x-\sqrt{\delta})} with the appropriate boundary conditions. In other words, adopting the obvious matrix notations, the vector {h(k,\cdot)} satisfies

\displaystyle \begin{array}{rcl} h(k,\cdot) = A h(k+1, \cdot) \end{array}

where {\big( A_{i,j} \big)_{0 \leq i,j \leq m_{\delta}}} is the usual tridiagonal matrix given by {A_{i,j} = 1} if, and only if, {|i-j|=1} and {A_{i,j} = 0} otherwise. It is related to the discrete Laplacian operator. Indeed, because all the eigenvalues of {A} are real with modulus strictly inferior to {1}, it follows that {h(0,\cdot) = A^{N} \textbf{1} \approx \lambda^N \, \varphi_{\delta}(\cdot)} where {\lambda_{\delta}} is the highest eigenvalue of {A} and {\varphi_{\delta}(\cdot)} the associated eigenfunction. The eigenvalues of {A} are well-known, and as {\delta \rightarrow 0}, the highest eigenvalue converges to {1} and the associated eigenfunction converges to the first eigenfunction of the Laplacian on the domain {D=[0,1]} with Dirichlet boundary. In our case it is {\varphi(u) = \sin(\pi \, u)} and

\displaystyle \begin{array}{rcl} \lim_{N \rightarrow \infty} \frac{ h(1,x \pm \sqrt{\delta})}{h(0,x)} = \lambda_{\delta}^{-1} \frac{ \varphi_{\delta}(x \pm \sqrt{\delta})}{\varphi_{\delta}(x)}. \end{array}

In other words, the random walk with increments {\pm \sqrt{\delta}} conditioned to stay inside {D_{\delta}} has probability transitions given by

\displaystyle \begin{array}{rcl} \hat{P}(x, x \pm \sqrt{\delta}) = \frac{{\lambda_{\delta}}^{-1}}{2} \frac{ \varphi_{\delta}(x \pm \sqrt{\delta})}{\varphi_{\delta}(x)}. \end{array}

Next section investigates the limiting case {\delta \rightarrow 0}.

Conclusion

We have computed the dynamics of the conditioned random walk with space-increments {\sqrt{\delta}}. To obtain the dynamics of the conditioned Brownian motion it suffices to consider the limiting case {\delta \rightarrow 0}. The drift of the resulting diffusion is given by

\displaystyle \begin{array}{rcl} \text{(drift)} &=& \lim_{\delta \rightarrow 0} \frac{1}{\delta} \Big\{ \hat{P}(0,x,x+\sqrt{\delta})\sqrt{\delta} - \hat{P}(0,x,x-\sqrt{\delta})\sqrt{\delta} \Big\} \\ &=& \lim_{\delta \rightarrow 0} \frac{{\lambda_{\delta}}^{-1}}{2 \sqrt{\delta}} \Big\{ \frac{ \varphi_{\delta}(x + \sqrt{\delta})}{\varphi_{\delta}(x)} - \frac{ \varphi_{\delta}(x - \sqrt{\delta})}{\varphi_{\delta}(x)} \Big\} = \frac{1}{2} \frac{\varphi'(x)}{\varphi(x)}. \end{array}

The same computation gives the volatility of the resulting diffusion. It is given by

\displaystyle \begin{array}{rcl} \text{(volatility)} &=& \lim_{\delta \rightarrow 0} \frac{1}{\delta} \Big\{ \hat{P}(0,x,x+\sqrt{\delta})\delta + \hat{P}(0,x,x-\sqrt{\delta})\delta \Big\} \\ &=& \lim_{\delta \rightarrow 0} \frac{{\lambda_{\delta}}^{-1}}{2} \Big\{ \frac{ \varphi_{\delta}(x + \sqrt{\delta})}{\varphi_{\delta}(x)} + \frac{ \varphi_{\delta}(x - \sqrt{\delta})}{\varphi_{\delta}(x)} \Big\} = 1. \end{array}

As the consequence, this shows that a Brownian motion conditioned to stay inside {D=[0,1]} follows the stochastic differential equation {dX = \frac{1}{2} \frac{\varphi'(X)}{\varphi(X)} \, dt + dW_t} where {\varphi(\cdot)} is the first eigenfunction of the Laplacian on {D} with Dirichlet boundary conditions. More generaly, the same argument would show that a Brownian motion in {\mathbb{R}^d} conditioned to stay inside a nice bounded domain {D \subset \mathbb{R}^d} evolves according to the stochastic differential equation

\displaystyle \begin{array}{rcl} dX = \frac{1}{2} \frac{\nabla \varphi(X)}{\varphi(X)} \, dt + dW_t \end{array}

where {\varphi:D \rightarrow \mathbb{R}} is the first eigenfunction of the Laplacian on {D}. This is a Langevin diffusion and one can immediately see that the invariant distribution of this diffusion is given by

\displaystyle \begin{array}{rcl} \pi_{\infty}(x) \, \propto \varphi(x). \end{array}

For example, the following plot depicts the first eigenfunction of the Laplacian on the domain {D=[0,1]^2 \subset \mathbb{R}^2}.

First Eigenfunction

9 Comments