Cheap and Secure Web Hosting Provider : See Now

Random Walk on the Integer Line

, , No Comments
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.

Asked By : user95224
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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66890

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback