World's most popular travel blog for travel bloggers.

# Random Walk on the Integer Line

, ,
Problem Detail:

Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next step of this walk, the walker moves to one of the two adjacent/neighboring integer points with equal probability (assume we start at integer 0). Let $S_l$ and $S_r$ be random variables denoting the number of leftward steps and rightward steps made over the whole $2n$-step walk, respectively.

There are two things I would like to show:

(1): For any $t > 0$, there exists a constant $c > 0$ such that Pr$[|S_l - S_r| > c\sqrt{n}] \leq t$.

(2): Derive a bound on $\beta$ given that Pr$[|S_l - S_r| > \beta] \geq 1 - \frac{1}{n}$ (i.e., find a bound on $\beta$ that gives us a high probability guarantee).

One approach I'm considering is that we can take $|S_l - S_r|$ as a random variable $D_{2n}$ denoting the distance from the origin after $2n$ steps. Now we can compute $E[D_{2n}] \approx \sqrt{\frac{2}{\pi}} \sqrt{2n}$. I'd imagine that at this point I'd either need to apply a Chernoff bound or the Chebyshev inequality, but I'm not sure how to apply either in this context.

###### Answered By : Yuval Filmus

Hint: $S_l - S_r$ is the sum of $2n$ independent variables $X_1,\ldots,X_{2n}$, with $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$.