A random walker starting at time $t=0$ and location $x=0$ moves to the right ($x+1$) or the left ($x-1$). The $k^{\mathrm{th}}$ moves to the right and left occure at the times $\sum_{i=1}^{k} R_i$ and $\sum_{i=1}^{k} L_i$, respectively, where $R_i$s and $L_i$s are independent samples of the probability density function $f(x)$. Show that for all $\delta>0$, there exists $m=\Theta(\sqrt{n})$ such that the probability that the location of the random walker remains $x\leq m$ from $t=0$ to the time of the $n^{\mathrm{th}}$ step to the right, is lower bounded by $1-\delta$, as $n\to\infty$.

My Effort: 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$ It looks to me as though the times are irrelevant to this problem, as $m$ is a function only of $n$, the "time" mentioned is defined in terms of when the $n^{th}$ step occurs, and the $R_i$ and $L_i$ are independent and drawn from the same distribution. That latter implies that the probability of a left or right move is $0.5$, so basically you have a random walk with $n$ steps to the right and probability parameter $0.5$ to work with, leading in the direction of a negative binomial distribution for the total number of steps (or steps to the left, depending on formulation.) $\endgroup$ – jbowman Oct 19 '18 at 19:18
  • $\begingroup$ @jbowman Thanks for your comment. Note that the probability of moving right or left is 0.5 only for the first step. The probability of the second step depends on the previous step, unless $f(x)$ is exponential and thus memoriless. $\endgroup$ – Sus20200 Oct 19 '18 at 19:23

Your Answer

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

Browse other questions tagged or ask your own question.