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 '17 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$ – Susan_Math123 Oct 6 '17 at 20:09
  • $\begingroup$ Use jump probabilities instead of jump time probabilities. $\endgroup$ – Therkel Oct 6 '17 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 '18 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 '18 at 21:09

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 '18 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$ – Susan_Math123 May 14 '18 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 '18 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$ – Susan_Math123 May 14 '18 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 '18 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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