Maximum vertical distance for a lattice path when NSEW steps are allowed

Question

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.

Answer 1

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