We have a random walk of length $n$, starting at $0$ and ending at $-6\,\sqrt{n}$. Can we give any sort of high probability bound on the number of steps before we first reach the value $-2\, \sqrt{n}$? I'm really looking for anything related to the random variable defined by the first time we reach the value $-2\,\sqrt{n}$, like probability distribution, expected value, etc.

As for the reference request, are there any books which discuss random walks with a given endpoint in more detail? The unfortunate thing is that knowing the endpoint loses the martingale property, so I don't really know of many ways to analyze this type of walk.

  • 1
    $\begingroup$ So $n$ is a square? What do you know about a Brownian bridge? $\endgroup$ – cardinal Jun 13 '11 at 0:23
  • $\begingroup$ You can assume $n$ is square, though the imprecision caused by rounding the root wouldn't be a big deal for this application. Also, I don't know much about Brownian bridges. I do notice that they're continuous-valued, which is a bit of a problem. Either way, can you recommend any good resources here? $\endgroup$ – Gautam Kamath Jun 13 '11 at 0:51
  • $\begingroup$ If the "imprecision of rounding the root" is not a big problem, then using a Brownian bridge as an approximation likely isn't either. Any good measure-theoretic probability text will treat the Brownian bridge. See Durrett, 3rd ed., Ch. 7 or 4th ed., Ch. 8 for a start on the Brownian bridge. Ch. 3 (resp. 4) has discussion of random walks, which might be helpful. The text doesn't treat this specific problem, but it will help you develop some of the necessary tools. Feller Vol. I also has nice treatment of random walks, which might provide some hints. $\endgroup$ – cardinal Jun 13 '11 at 1:02
  • 1
    $\begingroup$ You can also solve this using the reflection principle. Here's the basic idea: Let $m = \sqrt{n} \in \mathbb{N}$. Let $k = \min\{i: S_i = 2 m\}$. Condition on $k$ and looking backward in time, count the number of paths (via the reflection principle starting at $(0,0)$ and going to $(k-1,2m-1)$ that never hit $k$. Looking forward, count the number of paths going from $(k,2m)$ and ending at $(n,6m)$ (trivial). Dividing by the total number of paths gives the probability of hitting $2m$ for the first time at time $k$. From there you can compute the expectation as well. $\endgroup$ – cardinal Jun 13 '11 at 2:44
  • 1
    $\begingroup$ I have not checked this at all, so it could be embarrassingly wrong. Using the same notation as above, let $\alpha = m + k/2$, $\beta = (m^2+4m-k)/2$ and $\gamma = \alpha + \beta = (m^2 + 6m)/2$. Let $k$ be an even integer such that $2m \leq k \leq m^2-4m$. Then, the probability of hitting $2m$ for the first time at index $k$ is $\frac{2m}{k}{k \choose \alpha}{m^2-k \choose \beta}/{m^2 \choose \gamma}$. For all other $k$, the probability is zero. $\endgroup$ – cardinal Jun 13 '11 at 3:16

This follows the basic ideas I laid out in the comments.

Let $n = m^2$ be the total number of steps taken and $S_i$ be the value of the random walk at time $i$. We are interested in the probability distribution of the stopping time $\tau = \inf\{i: S_i = 2m\}$ conditional on the event $\{S_n = 6m\}$.

The key is to break things down according to the possible values that $\tau$ can take on and then consider how they could occur. First, note that $\tau$ must be an even integer in the range $[2m,n-4m]$ since we are considering a stopping time that stops when the height of the process reaches an even integer.

Suppose $\tau = k$. Then $S_i < 2 m$ for all $i < k$.

Question: How many paths are there from $(0,0)$ to $(k,2m)$ that never hit $2m$ prior to time $k$?

A: We find all the paths from $(0,0)$ to $(k-1,2m-1)$ and subtract away every path from $(0,0)$ to $(k-1,2m-1)$ which hits $2m$ at some point.

The number of paths from $(0,0)$ to $(k-1,2m-1)$ that hit $2m$ can be computed by the reflection principle since this is the same as the number of paths that go from $(1,1)$ to $(k,2m)$ without ever crossing zero (just rotate 180 degrees). By the reflection principle, this is ${k-1 \choose a}$ where $a = m + k/2$. Hence, the total number of paths from $(0,0)$ to $(k-1,2m-1)$ that never hit $2m$ prior to time $k$ is ${k-1 \choose a-1} - {k-1 \choose a} = \frac{2 m}{k} {k \choose a}$.

The total number of paths from $(k,2m)$ to $(n, 6m)$ is simply ${n-k \choose b}$ where $b = (n + 4m - k)/2$.

Finally, the total number of paths from $(0,0)$ to $(n, 6m)$ is ${n \choose a+b}$.

Hence, $$ \mathbb{P}(\tau = k \mid S_n = 6m) = \frac{2m}{k} \frac{{k \choose a}{n-k \choose b}}{{n \choose a+b}} = \frac{2m}{k} \frac{{k \choose m+k/2}{n-k \choose (n+4m-k)/2}}{{n \choose (n+6m)/2}} $$ for each even $k \in [2m, n-4m] $. Otherwise the probability is zero.

Here is an example with $n = 400$. One sample path is shown with the two horizontal barriers corresponding to $2m = 40$ and $6m = 120$. The vertical line indicates the value of $\tau$ for this sample path at which the lower barrier was hit for the first time. The histogram in the background is the distribution of $\tau$ with a height of 50 corresponding to a probability of 0.01. Some skew to the distribution is evident.

Sample path of random walk ending at 120

Aside: Note that it is easy to generate sample paths that always end at $6m$. Simply take the cumulative sum of the coordinates of a permutation of the vector $(+1,\ldots,+1,-1,\ldots,-1)$ which contains $(n+6m)/2$ entries that are $+1$ with the rest being $-1$.

  • $\begingroup$ Very nice job! Here are some suggestions. You could assume from the start that $\tau=2k$ instead of introducing $\tau=k$ and realizing later on that $k$ is even. // Replace $k$ by $2m$ in which hits $k$ and in that hit $k$. // The reflection principle applies without the 180 degrees rotation. // In the final formula you might replace $a$ and $b$ by their value, especially $a+b$ which does not depend on $k$. // Once again: a very good post. $\endgroup$ – Did Jun 14 '11 at 6:21
  • $\begingroup$ @Didier: Thanks for the comments, typo-corrections and suggestions. I'm making the typo corrections and will think about the best way to handle the definition of $\tau$. I did point out from the beginning that it must be an even integer, but you're right in that it probably makes sense to encode it more fully into the formulation. My "180 degree rotation" remark was simply meant as an aid for those that have read only the "typical" treatment of the reflection principle for random walks in Feller or Durrett, which deals with zero crossings. Perhaps it is superfluous. Thanks, again. $\endgroup$ – cardinal Jun 14 '11 at 13:54

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.