Maximum vertical distance for a lattice path when NSEW steps are allowed - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T15:15:21Z http://mathoverflow.net/feeds/question/84527 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84527/maximum-vertical-distance-for-a-lattice-path-when-nsew-steps-are-allowed Maximum vertical distance for a lattice path when NSEW steps are allowed Mike Spivey 2011-12-29T16:55:43Z 2012-01-07T07:00:37Z <p>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$. </p> <blockquote> <p>What is known about the distribution of $\max (L)$ over all paths of length $n$?</p> </blockquote> <p>(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.)</p> <p><em>Clarification</em>: 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.</p> http://mathoverflow.net/questions/84527/maximum-vertical-distance-for-a-lattice-path-when-nsew-steps-are-allowed/84579#84579 Answer by Mike Spivey for Maximum vertical distance for a lattice path when NSEW steps are allowed Mike Spivey 2011-12-30T07:21:07Z 2011-12-30T07:21:07Z <p>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}$.</p> <p>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}.$$</p> <p>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}.$$</p> <p>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 &lt; 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}.$$</p>