Probability of reaching a maximum in a random walk Let's define a random walk in the following way
$$S_0 = 0, S_n = \sum_{i=1}^{n} \epsilon_i,$$
where:
$$\epsilon_i = \pm 1.$$
Moreover
$$P(\epsilon_i = - 1) = P(\epsilon_i = + 1) = \frac{1}{2}.$$
Again, let's define a random variable $X_n$ which gives us the position of the first maximum of a random walk of length $2n$.
I am to show that
$$P(X_n = 2k) = P(X_n = 2k + 1) = \frac{1}{2}u_{2k}u_{2n-2k}.$$
Here
$$u_{2n} = \frac{\binom{2n}{n}}{2^{2n}} = P(S_{2n} = 0) = P(S_1 \ge 0, S_2 \ge0, \ldots, S_{2n} \ge 0) = P(S_1 \neq0, S_2 \neq 0, \ldots, S_{2n} \neq 0).$$
I also know that
$$u_{2k}u_{2n-2k}$$
tells us about the probability that a randomly walking particle is $2k$ ,,moves'' above the $x$ axis and $2n-2k$ below. However I don't know how to combine all those things and give the proof. I would appreciate any hints or tips.
 A: Hints for $\mathbb{P}(X_n = 2k)$: For fixed $k \in \mathbb{N}$ define two auxiliary random walks by
$$U_j := \sum_{i=1}^j \epsilon_{2k-i}, \qquad 0 \leq j \leq 2k,$$
and
$$V_j := \sum_{i=1}^j \epsilon_{2k+i}, \qquad 0 \leq j \leq 2n-2k.$$


*

*Check that $(U_j)_{j \leq 2k}$ and $(V_j)_{j \leq 2n-2k}$ are independent.

*Show that $$\{X_n = 2k\} = \{U_1 > 0,\ldots,U_{2k}>0\} \cap \{V_1\leq 0,\ldots,V_{2n-2k}\leq 0\}.$$

*Combining Step 1+2 gives $$\mathbb{P}(X_n = 2k) = \mathbb{P}(U_1 > 0,\ldots,U_{2k}>0) \mathbb{P}(V_1 \leq 0,\ldots, V_{2n-2k} \leq 0).$$ Use the facts which you mentioned about $u_{2n}$ to prove that the right-hand side equals $\frac{1}{2} u_{2k} u_{2n-2k}$.



Hints for $\mathbb{P}(X_n = 2k+1)$: Set $$T_j := \sum_{i=2}^{j+1} \epsilon_i$$ and denote by $Y_n$ the position of the first maximum of $(T_j)_{j \leq 2n}$.


*

*Show that $\{X_n =2k+1\} = \{Y_n = 2k\}$.

*Deduce from the first part of this problem that $$\mathbb{P}(Y_n=2k) = \frac{1}{2} u_{2k} u_{2n-k}.$$

*Conclude.

