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
    This is very related to a project I was(and am) working on. http://www.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! haha2011-01-19
  • 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
    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?2011-01-19
  • 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
    yes.the question is about maximal distance .Fixed.2011-01-19
  • 0
    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?2011-01-19
  • 0
    http://www.wolframalpha.com/input/?i=integrate+from+0+to+infty+(x^(1/2)/2^x)+dx2011-01-19
  • 0
    @picakhu: I think Yuval meant that integral to be an upper bound on the limit and not the actual limit itself.2011-01-19
  • 0
    Ah, I did not read that carefully.. sorry2011-01-19
  • 0
    You can calculate the actual sum by substituting the exact expression for the expected distance of a random walk (which is pretty simple), and then maybe you get $1/\sqrt{3}$.2011-01-19
  • 0
    @Yuval: Do you have a reference to the formula for $E(|S_n|)$ where $S_n$ is the $n$th stage of a random walk in terms of its transition probabilities? I tried deriving the expected distance using generating functions for this problem but got stuck after a while.2011-01-20
  • 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