Probability of reaching a maximum in a random walk

Question

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.

Answer 1

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.$$

1. Check that $(U_j)_{j \leq 2k}$ and $(V_j)_{j \leq 2n-2k}$ are independent.
2. Show that $$\{X_n = 2k\} = \{U_1 > 0,\ldots,U_{2k}>0\} \cap \{V_1\leq 0,\ldots,V_{2n-2k}\leq 0\}.$$
3. 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}$.

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