Conditioned Brownian motion, 1st Laplacian eigenfunction, etc…

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

Advertisements

9 Comments

  1. April 19, 2012 at 3:54 am

    […] What does a real Brownian motion conditioned to stay inside the segment look like? (it can help to better understand BM) […]

  2. dynkin said,

    April 2, 2013 at 1:56 pm

    Hi. Very interesting post. Can You please give some refference of a more detailed text: either book or article or handout …whatever? Thanks very much!

  3. Alekk said,

    April 2, 2013 at 2:04 pm

    Thanks!
    References on which part of the post?

  4. dynkin said,

    April 2, 2013 at 2:14 pm

    Hi. Well, if there could be one sort of manual or handout about all the these things… that’d be wondreful
    I’m interested in random walks in bounded domains and i’ve found this post very useful.

  5. dynkin said,

    April 2, 2013 at 2:22 pm

    The issue I’m studying right now is the calculation of the multiplicity of the points of a random walk in an d-dimensional hypercube, starting on on some of the points of the border with given coordinates. So it would be just as what You describe here. The question is how to determine the zones with high frequency of visits of a random walk in dependence with the coordinates (or relative position) of the starting point of this randow walk.

  6. Alekk said,

    April 2, 2013 at 2:28 pm

    I do not really understand exactly what you mean by “multiplicity of the points of a random walk in an d-dimensional hypercube, starting on on some of the points of the border with given coordinates”. You can ask a specific question at http://math.stackexchange.com/ and if this is a research level question at http://mathoverflow.net/.

  7. dynkin said,

    April 2, 2013 at 2:36 pm

    OK, thanks a lot. Well, may be i didn’t express my question properly. However, do you have some references in form of a book, article, course of lectures of the random walks conditioned to stay inside a bounded domain?
    Thanks

  8. Alekk said,

    April 2, 2013 at 2:44 pm

    No sorry, I do not have more references than the first few google pages.

  9. dynkin said,

    April 2, 2013 at 2:48 pm

    Ok, thanks anyway. Just wanted to have a more detailed description of the things of this post in this particular context, with more detailed proofs, theorems and so on…


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: