MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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... – Anthony Quas Dec 29 '11 at 21:03
@Anthony: Yes, I did mean it to be uniform. And that's a nice reformulation of the problem; thanks. – Mike Spivey Dec 29 '11 at 21:17
I think this can be explicitly answered using the reflection principle... – Anthony Quas Dec 30 '11 at 3:20
up vote 4 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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