# Why is the probability of a random walk reaching 1 (in n steps) squared greater than the probability of it reaching 2 (in n steps)?

Let $$S_n$$ be a simple random walk. i.e.

$$S_n = \sum_{t=1}^n X_t,$$ where $${X_t}$$ are i.i.d random variables with

$$X_t = \begin{cases} +1, & \textrm{w/ probability } p \\ -1, & \textrm{w/ probability } q=1-p \end{cases}$$

Let $$P_k(n) = \mathbb{P}(\textrm{reach } x=k \textrm{ within the } n \textrm{ first steps})$$

Is there an easy way to prove $$P_1(n)^2 \geq P_2(n)$$? I tried to think of ways through induction or relating $$P_1(n)^2$$ to $$P_2(2n)$$. To no avail.

• Have you tried to explain how to get to 2 with $P_1(n)$? Commented Dec 29, 2018 at 17:18
• Have you considered the Chapman-Kolmogorov equations? Commented Dec 30, 2018 at 11:25

$$\begin {array}{} P_2(n) &=& \sum_{k=1}^{n-1}P_1 (n-k)( P_1(k)-P_1 (k-1)) \\&\leq& \sum_{k=1}^{n-1}P_1 (n)( P_1(k)-P_1 (k-1)) \\&\leq& P_1(n) \sum_{k=1}^{n-1} (P_1(k)-P_1 (k-1))= P_1 (n) P_1 (n-1) \\ &\leq& P_1 (n) P_1 (n)\end {array}$$
Where $$( P_1(k)-P_1 (k-1))$$ is the probability to reach position 1 in the $$k$$-th step (which is different from within $$k$$ steps). And then $$( P_1(k)-P_1 (k-1))P_1 ({n-k})$$ is then the probability to reach another step in the direction 1 after being the first time in position 1 at the $$k$$-th step.