# 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

-
This is very related to a project I was(and am) working on. artofproblemsolving.com/Forum/viewtopic.php?f=498&t=358543 has the details of the problem, perhaps you will get some ideas from there.. I would like to see some ideas that may help me too! haha – picakhu Jan 19 '11 at 7:41
Also, in literature, these types of problems are called random walk with killing perhaps that will help you out too. – picakhu Jan 19 '11 at 7:45

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.

-
Can you please explain how have you got that after 2logn steps the probaility to return to the origin is $1/n^2$?And from where you get 2logn? – tech Jan 19 '11 at 21:33
The probability that we don't return to the origin after $2\log n$ steps is $2^{-2\log n}=1/n^2$. I chose $2\log n$ to make that probability small relative to the number of "time spots", which is $n$. – Yuval Filmus Jan 19 '11 at 23:25

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?

-
yes.the question is about maximal distance .Fixed. – tech Jan 19 '11 at 7:14
Just an FYI: I simulated the original question numerically. As Yuval notes, the expectation of the location of the walk at the $n$th time instant is a constant around 0.577. I think the actual limit is $1/\sqrt{3}$. Is this true? – Dinesh Jan 19 '11 at 7:54
wolframalpha.com/input/?i=integrate+from+0+to+infty+(x^(1/2)/2^x)+dx – picakhu Jan 19 '11 at 8:00
@picakhu: I think Yuval meant that integral to be an upper bound on the limit and not the actual limit itself. – Dinesh Jan 19 '11 at 20:01
Ah, I did not read that carefully.. sorry – picakhu Jan 19 '11 at 20:12