distribution of highest point while traversing a rotated grid Referring to the image say I am on this $n \times n$ grid starting at the origin and I can move up with a probability p and down with probability q. Now I start from the origin and reach the end tracing some path. I have shown two sample paths in the image with their corresponding probabilities. My question is regarding the distribution of the peaks (highest point) of all possible paths. In the case I have presented it is $x_2$ and $x_1$ respectively.
Similarly all the possible eight paths can be plotted with their respective probabilities and maximum can be assigned in each case to some $x_r$. What the question concerns is the probability of $x_r$ being the maxima where $r$ ranges from $0$ to $n$ when all the possible paths are considered.
I tried backward recursion on this but got too complicated. Another fact is that a given point will be maximum when the number of up moves minus the number of down moves is the maximum till that point. How can I solve this problem?
Sample paths for a $3 \times 3$ grid

Let's start with the 1-step case.  In this, there are a total of two possibilities: the highest point is $1$ with probability $p$, and $0$ with probability $q$ -- because it went down, it goes from $0$ to $-1$.
With 2 steps, it's more complicated: you have $P(\max = 2) = p^2$ (up twice), $P(\max = 1) = pq$ (up then down), and $P(\max = 0) = qp + q^2 = q$ (down then up or down twice).
Aha!  This gives us some insight:  The maximum can only change in a step if the current value is equal to the maximum, so we need to include the current value in our recursive calculation function.
$$f(m, c, s) =
\begin{cases}
pf(m-1, c-1, s-1) & \text{if } m=c\\
pf(m, c-1, s-1) + qf(m, c+1, s-1) & \text{if } m > c\\
0 & \text{if } (c > m) \vee(|c|>s)\\
1 & \text{if } m=c=s=0
\end{cases}$$
I think that covers the bases.
Then the ultimate probability is
$$P(\max = m \text{ at step }s) =\sum_{c=-s}^{s}f(m, c, s)$$
Which should be somewhat tractible to compute, though it will take cubic resources to do so.
