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.

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

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.