I am trying to get the probability that a sample path ends at a high. To formulate the problem,
let sequence $\{S_n\}$ be a random walk, with $S_0 = 0$, defined by
$$ S_n = \sum_{k=1}^n X_k$$
Where $\{X_n\}$ are iid random variables with $P(X=1)=p$, $P(X=-1)=1-p$
Also define $M_n=max\{S_1, S_2,...,S_n\}$.
What is $$\sum_{x=0}^n P(M_n = x, S_n = x),\ where\ n\ is\ a\ even\ number$$ Simply put, the ending value of the sample path has to be greater than or equal to all the values that came before.
The hint was to think recursively, starting from $P(M_2=x, S_2=x)$ and generalize, but I counldn't quite get it.
Could someone help me out? Thanks in advance.