1-D Random walk expectation calculation I need assistance with the following question:
The particle starts from the origin on the number line .
It makes n steps at total.
At each step it jumps with the probability 1/2 to the origin and with the uniform probability jumps to the one of its neighbors.I have to prove that the expectation of its maximal distance from the origin is proportional to logn
Thanks
 A: Here's a heuristic argument.
Upper bound: The probability that a walk will not be restarted after $2\log n$ steps is $1/n^2$, so we don't expect it ever to happen within the alloted $n$ steps. In particular, we don't expect the random walk to get farther than $2\log n$ away.
Lower bound: The probability that we make $(\log n)/4$ straight right steps is $1/\sqrt{n}$, so we expect that to happen within the alloted $n$ steps. Every time it happens, either the starting point or the end point must be at least $(\log n)/8$ away from the origin.
A: Actually the expectation is constant. Going back from the last step, the time until the first restart is (roughly) distributed $\mathrm{Geom}(1/2)$. If the walk lasts for $n$ steps, then the expected distance is about $\sqrt{n}$. So the expected distance is roughly $\int_0^n \sqrt{x}/2^x \, dx$. As it happens, this integral converges, i.e. $\int_0^\infty \sqrt{x}/2^x \, dx < \infty$.
Since already $\int_0^\infty x/2^x \, dx < \infty$, we didn't even need to know the expected distance after $n$ steps (it's clearly at most $n$).
Maybe the question was really about the expected maximal distance from the origin?
