7
$\begingroup$

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.

  • 0
    Thanks - I think that counting method is a pretty elegant way of thinking about it. Feel free to submit one of these as an answer.2011-06-13

1 Answers 1

9

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$.

  • 0
    @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.2011-06-14