Re: Expected length of a random walk, counting only one end.

On Fri, 13 Jul 2007 08:10:24 -0000, depictivelogic@xxxxxxxxx wrote:

Hello,
From wikipedia I learn that the expected value of the length of a (1-
dimensional) random walk between 0 and n starting at k is k * (n - k)
steps.

[I started writing the text below some time ago. At the end I
found that much of it is silly - decided to post it anyway
to illustrate one way a person might try to answer the question.
I do think that the correct answer _is_ obtained below, but
there must be a much better way to get there...]

Hmm. Your statement is a little unclear - I can guess what the
missing details, let's see if I can prove the answer is correct,
in which case my guesses may be correct as well.

I'm guessing that we have a random walk staring at k, each
step is either plus or minus 1, each with probability 1/2,
and we're talking about the expected number of steps until
we reach 0 or n.

Let's say e(k) is this expected value. Then e(0) = e(n) = 0
and e(k) = [(1+e(k-1)) + (1+e(k+1)] / 2 for 0 < k < n. It's
not hard to see that those conditions determine e(k). So
the question is whether e(k) = k * (n - k) satisfies the
two conditions.

It's clear that e(0) = e(n) = 0. And

e(k-1) + e(k+2) = (k-1) * (n-k+1) + (k+1) * (n-k-1)
= 2k(n-k) - (n-k)+(k-1) + (n-k)-(k+1)
= 2 e(k) - 2.

Sure enough, that's right. So I imagine my guesses about
exactly what you meant by the problem statement are correct.

Now I wonder what if I am not interested in the times when the random
walk ends at 0? That is what is the expected value of the length of
random walks that end at n?

Any answer, with our without proof would be very helpful!

Well let's see. First, we can simplify the notation by
solving an equivalent problem: We start at a point k >= 0
and ask for e(k), the expected number of steps until we
reach 0. (If e(k) is the answer to that question then
the answer to your question is e(|n-k|).)

There's a hidden assumption here, namely that we do at
some point reach 0. That's true with probability 1,
so in fact the number of steps is almost surely finite.

We still have e(0) = 0, and we still have the same
recurrence, which we can write as

(*) e(k+2) - 2e(k+1) + e(k) = -2.

To find the general solution to (*) we think about
standard methods for differential equations, and
start with the homogeneous equation

(**) e(k+2) - 2e(k+1) + e(k) = 0.

And we assume that a^k is a solution to (**). That
says

a^2 - 2a + 1 = 0,

which has a = 1 as a double root. Sure enough,
e_1(k) = k is a solution to (**). We need a second
linearly independent solution e_2 - too bad we got
a double root... Oh: e_2(k) = 1 is an obvious solution.

So the general solution to (**) is

e(k) = c + dk

for constants c and d. Which come to think of it
should have been obvious, sorry.

So what about (*)? The general solution would be
any solution plus the general solution to (**).
Again by analogy with DE it seems like (**) should
have a solution of the form Ak^2:

-2 = A(k+2)^2 - 2A(k+1)^2 + Ak^2
= 2A.

So the general solution to (**) is

e(k) = -k^2 + c + dk.

Since e(0) = 0 we have

e(k) = -k^2 + dk

for some constant d.

And no matter how we choose d this is negative for large k,
which is nonsense. I've looked for an error in the calculuations
without finding any. (The fact that k(n-k) _is_ a solution to
the recurrence shows that it's not just a sign error, it really
is -k^2, not k^2.) Could be there's an error I haven't found;
if not then there must be some hidden assumption that led
to the contradiction... Oh. While it's a fact that the number
of steps is almost surely finite that doesn't imply that it
has a finite expected value, which we've been assuming
throughout all this. If the expected value is infinite
then the steps above involving subtracting something from
both sides of an equation are invalid.

I bet, based on this roundabout reasoning, that in fact
the expected value is infinite. A more direct proof of this
would be better. (It seems like the fact that k(n-k)
tends to infinity as n -> infinity points in this direction,
but offhand I don't see how to use this fact to actually
prove that e(k) is infinite.)

Regards,
Jonas Bjering


************************

David C. Ullrich
.

Relevant Pages

  • Re: solving trignometric equ for non trivial solutions
    ... The numerator is independant of k, so if you know the solutions ... scale them by k to get the general solution. ... so there will be infinite number of roots spaced at most Pi apart. ... increasing phase change as you go. ...
    (comp.soft-sys.matlab)
  • Re: Diophantine System
    ... There are an infinite number, so they cannot possibly be posted. ... The general solution is as follows, where q, s range independently ... But I'll leave you to mull over it ... John R Ramsden ...
    (sci.math)