Let $S_n$ be a random walk with gaussian increments with $S_0=0$, i.e. $S_n-S_{n-1}\sim N(0,1), n\geq 1$. Fix $a>0,b\in \mathbb{R}$ and $c<a+bn$. Define the new process $$ B_{n,c}(k):=S_k-\frac{k}{n}\left (S_n-c\right) $$ to be a discrete bridge ending at $c$. I want to find an expression for the probability $$ \mathbb{P}\left(\max_{0\leq k\leq n}B_{n,c}(k)-bk\geq a\right), $$ which is only the probability that the bridge crosses the linear boundary by time $n$.

This expression is known in the continuous case (for the brownian bridge), see for example Scheike. The probability is given by $$ \mbox{exp}(-2a(a+bt-c)/t). $$ I have no reasons to believe that such an equivalent form would not hold in the discrete case. The proof given in the article above doesn't "discretize" well because of the time inversion and time scaling properties used in the continuous case that dont translate into the discrete case.

I'm looking for some insight on how to compute this probability. I would like to get an exact expression, but I could settle for an upper bound that goes in $1/n$.

If it can be of any help, I have shown that the probability (found in Scheike as well) $$ \mathbb{P}(\max_{0\leq s\leq t}W_s-bs\geq a)=1-\Phi(a/\sqrt{t}+b\sqrt{t})+exp(-2ab)\Phi(b\sqrt{t}-a/\sqrt{t}) $$ holds for the discrete brownian motion $S_n$.

  • $\begingroup$ I don't understand how you can get equality in your last expression. Surely a discrete Brownian motion can be represented as a continuous BM sampled at regular intervals. So the probability that a discrete BM hits a set must be strictly less than the probability a continuous BM hits the same set. $\endgroup$ – Tim May 5 '13 at 9:23
  • $\begingroup$ @Tim You may be right, in fact, I've shown the result for brownian motion without using time scaling and inversion properties, and educed that it should hold for discrete case since the process at integer times are equal in law. There might be more to it though $\endgroup$ – Jean-Sébastien May 6 '13 at 2:47
  • $\begingroup$ I agree with Tim. The error term should be an excess over the boundary term and of order $\frac 1 {\sqrt{n}}$. I think problem must be susceptible to martingale methods as in Siegmund, Sequential Analysis, chapt 3. Siegmund & Yuh may have random walk case in some detail $\endgroup$ – mike May 10 '13 at 14:02

I haven't managed a full answer for this, so this is just a sketch with a few ideas in it.

For notation I'm going to let $W(t)$ be a standard Brownian motion. I can then consider $W(k)$ for integer k. Similarly I'm going to consider a Brownian bridge $B_{n,c}(t)$ sampled at integer times.

Firstly I definitely think your estimate for the non bridge case is a strict upper bound and the error doesn't go away as $n\to\infty$.

To see this recall that with probability one for all positive $b$ there exists a time $T$ such that $W(t) < a +bt$ for every $t>T$. It is east to see that there is a positive probability that there is a non integer $t$ with $W(t)> a+bt$ but $W(k) < a+bk$ for every integer $k$. the difficult part of the question is not the bridge, it's the discretisation error.

Notice that the , your constant $c$ is superfluous, $B_{n,c}(k) > a + bk$ if and only if $B_{n,0}(k) > a + \left(b-\frac cn\right)k$ so we can focus on the $0$ to $0$ bridge. For small $n$ you can work this out exactly by writing down the correlation matrix of the $B_{n,0}(k)$'s and integrating over the multivariate Gaussian. Not very nice and there's probably no closed form, but it's the only way to get an exact answer.

For large $n$ I can construct my bridge $\tilde B_n(t)$ By letting $T$ be the largest time such that $W(T) = \frac{W(n)}2$ then setting $\tilde B_n(t) = W(t)$ for $t<T$ and $\tilde B_n(t) = W(n) - W(t)$ for $t\geq T$.

If $W(n)$ is positive then $\tilde B_n(t) > a+bt$ only if $W(t) > a+bt$ if $W(t)$ is negative the opposite is true, but if there exists $t$ such that $\tilde B_n(t) > a+bt$ but $W(t) < a+bt$ I can define $\tilde T<n$ as the largest time such that $W(T)=0$ and set $\tilde W(t)$ = $W(t)$ for $t<\tilde T$ and $\tilde W(t) = -W(t)$ for $t>\tilde T$.

You should be able to convince yourself that $\tilde W(t)\geq\tilde B_n(t)$ for every $t$ so if $\tilde B_n(t)$ crosses the boundary so does $\tilde W(t)$. Furthermore as $W(t)$ does not cross the boundary $\tilde B_n(t)$ can only cross the boundary for $t>T$. So if I create a bridge by reflecting $\tilde W(t)$ it does not cross the boundary.

So there exists a measure preserving map ($W\mapsto\tilde W$) that takes the set of paths where the bridge crosses the boundary but the path itself does not onto to the set of paths that do cross the boundary but the reflection bridge does not. So the probability that the path crosses the boundary is greater than or equal to the probability that the bridge crosses the boundary.

Notice that the argument does not break down if I only count boundary crossings that occur at integer times. I think that the error for the discrete process is bounded above by the error for the continuous process.

Another avenue you might want to consider is to get rid of $b$ by setting $\tilde c = c - nb$ Then $B_{n,c}(t) > a+bt$ if and only if $B_{n,\tilde c}(t) > a$. Now I can create a bridge from $0$ to $\tilde c$ the same way, by conditioning my bridge to hit $\tilde c$ before time $n$ and then reflecting as before to create a bridge. So now I'm interested in the probability that there exists a pair $k < t<n$ with $n\in\mathbb N$ and $t\in\mathbb R$ such that $W(k) > a$ and $W(t) = $\tilde c$. (or an alternative case where the bridge crosses but the Brownian motion doesn't I think these probabilities will drop off pretty rapidly. )

This might be a way of getting a handle on your discretisation error. Although it's essentially the same problem (What's the probability that a Brownian motion goes above a certain boundary at real times, but not integer times) it should be easier in this case because you can use the reflection principle and other tricks in this situation.

Sorry it's not an answer, but hopefully there's an idea or two in there that you can use.

  • $\begingroup$ I don't have time to check it all out right now, but it seems it may help. I'll award the bounty to you so it does not go to waste, and upvote\accept when I have time to read it. Thank you $\endgroup$ – Jean-Sébastien May 12 '13 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.