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 steps have a maximum height of ? (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 steps end up at a particular point . Let denote the final position of an -step NSEW lattice path. We want . A nice way to count these involves making the transformation and considering NW, NE, SW, and SE steps instead. Since these four diagonal steps are of the form , we need to count the number of ways to choose total +1s and -1s to get to for the first coordinate, and then multiply that by the number of ways to choose total +1s and -1s to get to . (In other words, the transformation allows us to deal with the two coordinates separately.) If we let and denote the number of +1s and -1s needed to reach , we have and . Thus , and so the number of ways to obtain the first coordinate is . Similarly the number of ways to obtain the second coordinate is , and so we get
Next, let’s find the number of -step NSEW lattice paths whose final position has a height of . To get this, we sum the answer we just obtained over all values of . The Chu-Vandermonde identity comes in handy, and we have .
Now we’re ready to find the number of -step NSEW lattice paths that have a maximum height of . For a particular -step path, let denote its maximum height. We want . To get this, let’s first look at the number of paths that end at a height of and have a maximum height of or greater. If , then .
Then consider the case . For any path that ends at and reaches a height of at least take the part of that path after the first step that reaches and reflect it across the horizontal line at height . Any path that ends at a height of gets transformed into one that ends at a height of . This transformation is reversible, and so if then . (This trick is called the reflection principle and is a common technique for working with lattice paths.)
Putting this together, we get that
which gives us the really nice answer