# Random Walk Problem (Integer Line)

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

• "distance" is unsigned – snarfblaat Oct 17 '16 at 0:48