4
$\begingroup$

Suppose we have a lattice path in 2D starting at the origin, in which north, south, east, and west steps are allowed. For a given path $L$, let $\max(L)$ be the maximum value of the $y$ coordinate achieved by $L$ over the length of its path. For example, the path NENWSWW would have $\max(L) = 2$.

What is known about the distribution of $\max (L)$ over all paths of length $n$?

(It seems like this problem would have been studied, but most of the results on lattice paths I've found allow only north and east steps. Perhaps I'm not using the right search terms.)

Clarification: My question is that if we list all possible paths of length $n$, and sort them by the value of $\max (L)$ for each path, how many are there with $\max (L) = 0, \max (L) = 1,$ etc.? If we think about this from a random walk perspective, it's equivalent to imposing a uniform distribution on the four possible steps at each point.

$\endgroup$
3
  • 4
    $\begingroup$ You didn't say anything about the distribution of the paths. I'll assume you intend it to be uniform. Given this, your problem can be re-phrased as a 1D problem by looking only at the $y$-coordinate. Consider a random walk where $Y_{n+1}=Y_n+1$ with prob. 1/4, $Y_n-1$ with prob. 1/4 and $Y_n$ with prob 1/2. Then you're asking for the distribution of the maximum value attained by this random walk. I don't have a reference handy - maybe Spitzer Principles of Random Walk?; maybe Feller; but this should not be hard to find out about... $\endgroup$ Commented Dec 29, 2011 at 21:03
  • $\begingroup$ @Anthony: Yes, I did mean it to be uniform. And that's a nice reformulation of the problem; thanks. $\endgroup$ Commented Dec 29, 2011 at 21:17
  • 2
    $\begingroup$ I think this can be explicitly answered using the reflection principle... $\endgroup$ Commented Dec 30, 2011 at 3:20

1 Answer 1

4
$\begingroup$

Anthony Quas's comments gave me the ideas I needed to answer the question. (Thanks, Anthony!) Here's the solution in case anyone else is interested. The answer turns out to be that the number of $n$-step paths with max height $y$ is $\binom{2n}{n+y} + \binom{2n}{n+y+1}$.

First, let $(X_n,Y_n)$ denote the final position of an $n$-step NSEW lattice path starting at the origin. Let's count $N((X_n,Y_n) = (x,y))$. By switching to $(\pm 1, \pm 1)$ (i.e, NW, NE, SW, SE) steps, we make the transformation $(x,y) \to (x+y,y-x)$. The choices of $+1$s and $-1$s for the two coordinates are now independent. The number of ways to choose $n$ total $+1$s and $-1$s that add to $x+y$ is $\binom{n}{(n+x+y)/2)}$, and the other coordinate is similar. Thus $$N((X_n,Y_n) = (x,y)) = \binom{n}{(n+x+y)/2)} \binom{n}{(n+y-x)/2}.$$

Next, we find $N(Y_n = y)$ by summing over all possible values of $x$. Since only values of $x$ that make $(n+x+y)/2$ and $(n+y-x)/2$ integers are allowed, thanks to Vandermonde's convolution we get $$N(Y_n = y) = \binom{2n}{n+y}.$$

Finally, let $M_n = \max_{0 \leq i \leq n} \{Y_i\}$. My question is asking for the value of $N(M_n = y)$. We have $N(M_n \geq y, Y_n = b)$ equal to $N(Y_n = b)$, if $b \geq y$; and, by the reflection principle (across the horizontal line of height $y$) equal to $N(Y_n = 2y-b)$, if $b < y$. Thus $$N(M_n \geq y) = \sum_{b \geq y} N(Y_n = b) + \sum_{b \leq y-1} N(Y_n = 2y-b)$$ $$= \sum_{b \geq y} N(Y_n = b) + \sum_{b \geq y+1} N(Y_n = b)$$ $$= N(Y_n = y) + 2 N(Y_n \geq y+1).$$ Therefore, $$N(M_n = y) = N(M_n \geq y) - N(M_n \geq y+1) = N(Y_n = y) + N(Y_n = y+1),$$ or $$N(M_n = y) = \binom{2n}{n+y} + \binom{2n}{n+y+1}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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