Re: 1-dimensional random walk problem

Here's a little something that will be new to almost everyone here.

Rob Johnson wrote:

Suppose the expected time to +1 is x. There are two possibilities:
x is positive and finite, or x is infinite.

Suppose also that the probability of moving in the positive direction
is p.
[We calculate x by] breaking the walk into 2 possibilities:
probability p of moving to +1 in 1 step, and 1-p of moving to -1
and requiring 2x [more] steps to get to +1. From this we get

x = p + (1-p)(2x+1) <---Rob had a mistake here, forgot the last +1;

which implies that [ x = 1/(2p-1) ]

Therefore, if p <= 1/2, x is infinite, whereas, if p > 1/2, we have
x from the formula above.


This is [now] correct when x = E[ T ] and T is defined by...

______ time till hit +1, when this event occurs;
/
T = <
\______ +oo , when the above event doesn't occur.

However, in the case when p < 1/2 and the event is less than certain,
it's a bit wholesale and sledge-hammer to count the time as infinite.

For some reason, conditional expected values (as opposed to
conditional probabilities) are not much studied in text-books
and probability courses, though they are easy enough to handle,
and this is an excellent example of where it makes sense.

If we look at the above walk again, with p < 1/2, it is sensible
to ask, "What is the expected time of htting +1
GIVEN THAT we do evetually hit +1 ?"

It is simple enough to work this out by using methods similar to
that which Rob just used, and we get the surprising answer...

E[ T | T is finite ] = 1/(q-p) ,

which is exactly the same formula as above, with p & q reversed.

So the value of conditional E[ T ] is symmetric about p = 1/2. (!)


I say it's a surprising answer, but OC on 2nd look it's not so
surprising at all. After all, if p is close to zero, then the
event of hitting +1 almost never happens, so if it DOES happen
it's almost certainly due to happening on the very first step,
so, time = 1. And likewise, if p is only just less than 1/2,
then the event of hitting +1 is hardly changed from the
certain event of hitting it unconditionally, so the expected
value is very large indeed.

Altogether an amusing and satisfying little result
which really ought to be more widely disseminated!

Thanks for reading so far.

----------------------------------------
Bill Taylor W.Taylor@xxxxxxxxxxxxxxxxxxxxx
----------------------------------------
"Necessary evils" are seldom necessary, but always evil!
----------------------------------------

.

Relevant Pages

  • Re: a homework prob about series convergence
    ... infinite sum converges, and the function of x is an L^1 function. ... Lebesgue Monotone Convergence allows us to exchange the limit ... Rob Johnson ...
    (sci.math)
  • Re: Dirichlets nowhere differentiable function
    ... If k <= 2 then the argument that Rob Johnson gave shows that ... "upper derivative" is infinite everywhere; ... David C. Ullrich ... Prev by Date: ...
    (sci.math)
  • Re: SHA-1 question
    ... ggr@qualcomm.com (Gregory G Rose) writes: ... I find that very surprising. ... However, there aren't an infinite ... number of possible inputs to the compression function. ...
    (sci.crypt)
  • Re: limit of a limit
    ... Rob Johnson wrote: ... >>Robert Israel wrote: ... > of f is infinite at a, then the derivative of f will be infinite at a. ... Prev by Date: ...
    (sci.math)
  • Re: factrial limit
    ... Any help with little explanation on how you got the ... what you are analyzing is the binomial coefficient for p+q things ... The limit as n,r tend to infinite depends on HOW they are ... (not surprising, since Pascal's triangle lists all the ...
    (sci.math)