2
$\begingroup$

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

  • 0
    Also, in literature, these types of problems are called random walk with killing perhaps that will help you out too.2011-01-19

2 Answers 2

2

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.

  • 0
    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$.2011-01-19
1

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?

  • 0
    For $n$ odd try $\sum_{k=(n+1)/2}^n \binom{n}{k}/2^{n-1} (2k-n) = \binom{n}{(n+1)/2}(n+1)/2^n$. For $n$ even you get something similar. To get the asymptotic, use Stirling's approximation.2011-01-20