1
$\begingroup$

Suppose we are doing a random walk on the infinite integer line. 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. Prove that the expected distance of the walker from the origin (i.e., the starting point of the walk) after $n$ steps is $\Theta(\sqrt{n})$.

Could we not just consider an equivalent problem: if a fair coin is flipped $n$ times, show that (WLOG) the difference in the number of flipped heads from the number of flipped tails in this sequence of flips is $\Theta(\sqrt{n})$? Given that the expected number of heads/tails for this sequence is $\frac{n}{2}$, from the linearity of expectation, we have that the expected difference is $\frac{n}{2} - \frac{n}{2} = 0 = O(\sqrt{n})$, but clearly $0 \neq \Omega(\sqrt{n})$.

$\endgroup$
  • $\begingroup$ "distance" is unsigned $\endgroup$ – snarfblaat Oct 17 '16 at 0:48
1
$\begingroup$

You need to look at the expected value for the absolute value of the difference, not the expected value for the difference.

$\endgroup$

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.