A 1-D random walker strarting at time $t=0$ and location $x=0$, moves to the right ($x+1$) or the left ($x-1$) according to independent random variables $R_1,R_2,\ldots$ and $L_1,L_2,\ldots$, such that the $k^{\mathrm{th}}$ jump to the right occurs at the time $\sum_{i=1}^{k} R_i$ and the $k^{\mathrm{th}}$ jump to the left occurs at the time $\sum_{i=1}^{k} L_i$. Assume $R_i$s and $L_i$s are samples of the same probability density function $f(x)$. Show that the probability that the location of the random walker remains $x\leq M$ after the first $N$ steps to the right, tends to $1-\delta$, for all $\delta>0$, as $N, M \to\infty$, as long as $M=\mathcal{O}(\sqrt{N})$.

My Solution: If $f(x)=\lambda e^{-\lambda x}$, the memorylessness of exponential random variables makes this problem equivalent to a symmetric random walk, then we can find the survival probability of a random walk and use the Brownian motion limit to prove this (see Survival Probability in here). How about the general $f(x)$?

I think we make it equivalent to another Brownian motion, I don't know how to find the parameters of that Brownian motion.

  • $\begingroup$ I don't understand the role of $f_a/f_p$. Is this determining jump times or jump direction? $\endgroup$
    – Ian
    Oct 6, 2017 at 20:00
  • $\begingroup$ @Ian I edited the problem to clarify this. $f_r$ gives the jump time to right and $f_l$ gives the jump time to left. $\endgroup$ Oct 6, 2017 at 20:09
  • $\begingroup$ Use jump probabilities instead of jump time probabilities. $\endgroup$
    – Therkel
    Oct 6, 2017 at 20:09
  • 1
    $\begingroup$ Let $X(t)$ denote this process, with $f(x) = \lambda e^{-\lambda x} \cdot 1_{\{x>0\}}$. It seems like you are claiming that $P(X(R_n) \leq \sqrt n)$ should converge to $1$ as $n \to \infty$. I do not believe that this is true. By CLT together with basic properties of the Poisson process, you can prove that $\frac{X(R_n)}{2\sqrt{n}}$ converges in distribution to $N(0,1)$, therefore the probability $P(X(R_n) \leq \sqrt n)$ should tend to a number strictly less than $1$. $\endgroup$
    – shalop
    May 11, 2018 at 10:43
  • 1
    $\begingroup$ Hold your horses. It can't converge to $1-\delta$, for all $\delta>0$. Maybe you mean some $\delta>0$?. Or maybe you meant to choose a rate faster than $\sqrt N$, in which case it would converge to $1$? Hard to see what exactly you want here. $\endgroup$
    – shalop
    May 11, 2018 at 21:09

1 Answer 1


I agree with Shalop's comments, in particular, we need $M$ to grow faster than $\sqrt{n}$ to get a probability that converges to 1. Here is an analysis of the general problem.

Assume that $\{R_1, L_1, R_2, L_2, ...\}$ are i.i.d. positive random variables with mean $E[L]$ and variance $\sigma^2$. Assume $0<E[L]<\infty$, $0<\sigma^2<\infty$. Let $X(t)$ be the (integer) location at time $t \geq 0$, with initial condition $X(0)=0$. Define \begin{align} t^R_n &= R_1 + R_2 + … + R_n\\ t^L_n &= L_1 + L_2 + … + L_n\\ N^R(t) &= \mbox{Number of right arrivals during $[0,t]$} \\ N^L(t) &= \mbox{Number of right arrivals during $[0,t]$} \end{align} Then $X(t) = N^R(t) - N^L(t)$ for all $t \geq 0$ and $$ \boxed{X(t^R_n) = n - N^L(t^R_n)} \quad (Eq. *) $$ Now let $\{M_n\}_{n=1}^{\infty}$ be any sequence of non-negative integers that satisfies \begin{align} &n-M_n \geq 1 \quad \forall n \in \{1, 2, 3, ...\}\\ &\lim_{n\rightarrow\infty} \frac{M_n}{\sqrt{n}} = c \in [0, \infty) \end{align} We want to show that $$ \boxed{\lim_{n\rightarrow\infty} P[X(t^R_n) > M_n] = \int_{\frac{cE[L]}{\sqrt{2\sigma^2}}}^{\infty} \frac{1}{\sqrt{2\pi}}e^{-x^2/2}dx}$$ We will use the fact that for all $t \geq 0$ and all positive integers $k$ we have $$ \boxed{P[N^L(t)<k] = P[L_1 + … + L_k > t]} \quad (Eq. **) $$

Define for each $i \in \{1, 2, 3, …\}$ \begin{align} G_i &= \frac{1}{\sqrt{i}}\sum_{j=1}^i (L_i-E[L])\\ H_i &= \frac{1}{\sqrt{i}}\sum_{j=1}^i (R_i - E[L]) \end{align} Then $\{G_i\}_{i=1}^{\infty}$ and $\{H_i\}_{i=1}^{\infty}$ are independent, and the central limit theorem tells us that $G_i$ and $H_i$ both converge in distribution to a Gaussian with 0 mean and variance $\sigma^2$. We have \begin{align} P[X(t^R_n)>M_n] &\overset{(a)}{=} P[n-N^L(t^R_n) > M_n] \\ &= P[N^L(t^R_n) < n-M_n] \\ &\overset{(b)}{=} P[L_1 + … +L_{n-M_n} >t^R_n]\\ &\overset{(c)}{=} P[L_1 + … + L_{n-M_n} > R_1 + … + R_n] \\ &\overset{(d)}{=}P\left[\sum_{j=1}^{n-M_n}(L_i-E[L]) > M_nE[L] + \sum_{j=1}^n (R_i-E[L])\right]\\ &\overset{(e)}{=} P\left[G_{n-M_n} > \frac{M_nE[L]}{\sqrt{n-M_n}} + \left(\frac{\sqrt{n}}{\sqrt{n-M_n}}\right)H_n \right] \end{align} where (a) holds by (Eq *); (b) holds by (Eq **) with $t=t^R_n$ and $k=n-M_n$; (c) holds by definition of $t^R_n$; (d) holds by subtracting $(n-M_n)E[L]$ from both sides of the inequality inside the $P[\cdot]$; (e) holds by dividing both sides of the inequality inside the $P[\cdot]$ by $\sqrt{n-M_n}$ and using definitions of $H_i$ and $G_i$. Define $$ W_n = G_{n-M_n} - \left(\frac{\sqrt{n}}{\sqrt{n-M_n}}\right)H_n$$ Then $$ P[X(t^R_n)>M_n] = P\left[W_n > \frac{M_nE[L]}{\sqrt{n-M_n}}\right]$$ Note that $\lim_{n\rightarrow\infty} \frac{M_n}{\sqrt{n}} = c \in [0, \infty)$ implies the following: $$ \lim_{n\rightarrow\infty} \frac{\sqrt{n}}{\sqrt{n-M_n}} = 1 \quad ,\quad \lim_{n\rightarrow\infty} \frac{M_nE[L]}{\sqrt{n-M_n}} = cE[L] \quad, \quad \lim_{n\rightarrow\infty} (n-M_n) = \infty$$ Since $G_{n-M_n}$ and $H_n$ are independent and individually converge in distribution to a Gaussian with mean $0$ and variance $\sigma^2$, we know that $W_n$ converges in distribution to a Gaussian with mean $0$ and variance $2\sigma^2$. Hence $$ \lim_{n\rightarrow\infty} P[X(t^R_n)>M_n] = P[W > cE[L]]$$ where $W$ is Gaussian with mean 0 and variance $2\sigma^2$. $\Box$

  • $\begingroup$ On the other hand, if $\lim_{n\rightarrow\infty} \frac{M_n}{\sqrt{n}} = \infty$, then similar methods can be used to show that $$ \lim_{n\rightarrow\infty} P[X(t^R_n)>M_n] = 0$$ $\endgroup$
    – Michael
    May 14, 2018 at 5:42
  • $\begingroup$ Thank you! But, you are calculating the probability that the location of the random walker at the $n-th$ move to the right eventually becomes larger than $M_n$. I want something else. In my original proble, I want to show that the location has remained all the time less than $M$, from time zero to the time of the N-th move to the right., not eventually. $\endgroup$ May 14, 2018 at 15:15
  • $\begingroup$ That aspect was not clear in the wording. Nevertheless my answer indeed proves the thing you are trying to prove is false: The probability that we remain less than $M_n$ for all steps from 1...n is less than or equal to the probability that the $n$th step is less than $M_n$, which we know from the above answer does not go to 1. $\endgroup$
    – Michael
    May 14, 2018 at 15:32
  • $\begingroup$ Thank you for your comment. Please see Theorem 12.2 in "Stopped random walks" by Allan Gut. When the distributions of $L_i$ and $R_i$ are exponential, it becomes a normal random walk, and Theorem 12.2 says what I need for this case. Therefore, I don't think your proof is correct. $\endgroup$ May 14, 2018 at 15:50
  • $\begingroup$ I do not have access to that book. I suspect that you are misinterpreting a result given there. I observe that your use of $\delta$ in your question is awkward and that wording is unlikely to be in any book. That is because if $p$ is a probability that is greater than $1-\delta$ for all $\delta>0$, then $p=1$ and there is no need to mention $\delta$. Note that Shalop pointed out the same issue. $\endgroup$
    – Michael
    May 14, 2018 at 16:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .