3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suggest you keep trying. $\endgroup$ – Yuval Filmus Dec 3 '16 at 20:39
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 4 '16 at 2:01
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Do the standard Chernoff bounds still hold even if the $X_i$'s take on $-1$ rather than $0$? I'm only accustomed to these variables being indicators (i.e., take on either 0 or 1). $\endgroup$ – user95224 Dec 3 '16 at 21:18
  • 1
    $\begingroup$ Wikipedia has a good treatment of this topic. You might need to use one of the related bounds such as Hoeffding's. $\endgroup$ – Yuval Filmus Dec 3 '16 at 21:19
  • $\begingroup$ Your hint has helped me to solve (1). In particular, I have that $t = e^{-c^2/4}$. Should (2) follow trivially from (1)? The problem is that I can't see how to go about flipping the outer inequality from (1). $\endgroup$ – user95224 Dec 3 '16 at 22:16
  • $\begingroup$ For (2) you need an anticoncentration bound. In this case you can take any negative $\beta$, but not any non-negative one since $\Pr[S_l=S_r] = \Theta(1/\sqrt{n})$. Perhaps you copied that part wrong? $\endgroup$ – Yuval Filmus Dec 3 '16 at 22:26
  • $\begingroup$ But if $\beta$ is negative aren't we guaranteed that our final distance from the origin is $> \beta$? I should clarify that I think a bound on $\beta$ means: what is the highest value of $\beta$ such that Pr$[|S_l - S_r| > \beta] \geq 1 - \frac{1}{n}$. $\endgroup$ – user95224 Dec 3 '16 at 22:37

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.