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$ Dec 29, 2018 at 17:18
  • $\begingroup$ Have you considered the Chapman-Kolmogorov equations? $\endgroup$
    – Xi'an
    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 that you have read and understand our privacy policy and code of conduct.

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