The Number of NSEW Lattice Paths with a Maximum Height of y

I’ve been thinking and learning some about lattice path statistics lately, and a couple of days ago I worked out the answer to the following question (with help from some suggestions from Anthony Quas via Math Overflow).

Suppose we have a lattice path in 2D starting at the origin, in which north, south, east, and west steps are allowed.  How many lattice paths with n steps have a maximum height of y?  (By “maximum height” I mean the highest vertical distance the path achieves over the course of its entire length.)

To answer this question we need a couple of other lattice path statistics.

First, let’s count how many lattice paths with n steps end up at a particular point (x,y).  Let (X_n,Y_n) denote the final position of an n-step NSEW lattice path.  We want N((X_n,Y_n) = (x,y)).  A nice way to count these involves making the transformation (x,y) \to (x+y,y-x) and considering NW, NE, SW, and SE steps instead.  Since these four diagonal steps are of the form (\pm 1, \pm 1), we need to count the number of ways to choose n total +1s and -1s to get to x+y for the first coordinate, and then multiply that by the number of ways to choose n total +1s and -1s to get to y-x.  (In other words, the transformation allows us to deal with the two coordinates separately.)  If we let p and q denote the number of +1s and -1s needed to reach x+y, we have p + q = n and p - q = x+y.  Thus p = (n + x + y)/2, and so the number of ways to obtain the first coordinate is \binom{n}{(n+x+y)/2}.  Similarly the number of ways to obtain the second coordinate is \binom{n}{(n+y-x)/2}, and so we get \displaystyle N((X_n,Y_n) = (x,y)) = \binom{n}{(n+x+y)/2}\binom{n}{(n+y-x)/2}.

Next, let’s find the number N(Y_n = y) of n-step NSEW lattice paths whose final position has a height of y.  To get this, we sum the answer we just obtained over all values of x.  The  Chu-Vandermonde identity comes in handy, and we have \displaystyle N(Y_n = y) = \sum_x \binom{n}{(n+x+y)/2}\binom{n}{(n+y-x)/2} = \binom{2n}{n+y}.

Now we’re ready to find the number of n-step NSEW lattice paths that have a maximum height of y.  For a particular n-step path, let M_n denote its maximum height.  We want N(M_n = y).  To get this, let’s first look at the number of paths that end at a height of b and have a maximum height of y or greater.  If b \geq y, then N(M_n \geq y, Y_n = b) = N(Y_n = b).

Then consider the case b < y.   For any path that ends at b and reaches a height of at least y, take the part of that path after the first step that reaches y and reflect it across the horizontal line at height y.  Any path that ends at a height of b gets transformed into one that ends at a height of 2y-b.  This transformation is reversible, and so if b < y then  N(M_n \geq y, Y_n = b) = N(Y_n = 2y-b).  (This trick is called the reflection principle and is a common technique for working with lattice paths.)

Putting this together, we get that

\displaystyle N(M_n \geq y) = \sum_{b \geq y} N(Y_n = b) + \sum_{b \leq y-1} N(Y_n = 2y-b)
\displaystyle = \sum_{b \geq y} N(Y_n = b) + \sum_{b \geq y+1} N(Y_n = b).

Thus \displaystyle N(M_n = y) = N(M_n \geq y) - N(M_n \geq y+1) = N(Y_n = y) + N(Y_n = y+1),
which gives us the really nice answer \displaystyle N(M_n = y) = \binom{2n}{n+y} + \binom{2n}{n+y+1} = \binom{2n+1}{n+y+1}.

Advertisements
This entry was posted in combinatorics, lattice paths. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s