probability of random walk being equal to its running maximum

Question

For a Brownian process, the probability of being equal to the running maximum is zero, as in the related question here. For the discrete case, what is the probability that the current random walk value at step $N$ equal to its running maximum? $$\mathbb{P}\bigg\{(S_n = \sum_{j = 1}^{j=n} Z_j) = \max_{0\leq t\leq n}(S_t)\bigg\}$$

Answer 1

I assume a simple random walk. If we reverse the walk by taking $S'_k = S_N-S_N$, we still have a simple random walk, and the condition "$S$ is at its maximum at $N$" becomes "$S'$ is non-negative". We have reduced the problem to computing $\Pr(S \geq 0,\ \forall 0\leq k \leq N)$. The number of random walks with $N$ steps is $2^N$, the number $P_N$ of random walks with $N$ steps who stays non-negative can be computed by decomposing on the number of pluses $p$ and minuses $q$ and using the ballot theorem with ties (https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem#Variant:_ties_allowed)

$$P_N = \sum_{q+p =N, q\leq p} \binom N q \frac{p+1-q}{p+1} = \sum_{q\leq \lfloor N/2 \rfloor} \frac {N-2q+1}{N-q+1} \binom N q = \sum_{q\leq \lfloor N/2 \rfloor} \frac {N+1-2q}{N+1} \binom {N+1} q = \sum_{q\leq \lfloor N/2 \rfloor} \binom {N+1} q -2 \sum_{q\leq \lfloor N/2 \rfloor} \frac {q}{N+1} \binom {N+1} q = \sum_{q\leq \lfloor N/2 \rfloor} \binom {N+1} q -2 \sum_{q\leq \lfloor N/2 \rfloor} \binom {N} {q-1}$$

When $N$ is even, this is equal to $P_N = 2^{N} -2(2^{N-1} - \binom {N}{N/2}/2) =\binom {N}{N/2}$.

When $N$ is odd, this is $P_N = 2^N -\binom {N+1}{(N+1)/2}/2 -2(2^{N-1} - \binom {N}{(N-1)/2}) = 2\binom {N}{(N-1)/2} - \binom {N+1}{(N+1)/2}/2 = \binom {N}{(N-1)/2}$.

We can regroup both cases and obtain $P_N = \binom N {\lfloor N/2\rfloor}$, so the probability is $\frac 1{2^N} \binom N {\lfloor N/2\rfloor}$. It goes to $0$ when $N$ is large, which is consistent with the behavior of the brownian motion.