## Random Walks and Probability

If we have a person who in t=0 (time) is standing on x=0 .
every one second (t=t+1) in without any dependency on previous steps :
he moves to right(x=x+1) in probability = 1/4
and he moves to left (x=x-1) in probability = 1/4 .
and he goes back to x=0 in probability = 1/2 .

show that within n seconds (t) he never be more than O(logn) steps away from x=0 (start point) .

now I know how to solve a similiar question : only he moves to right in prob=1/2 and to left in prob=1/2 (with chernoff bound) but the above question I don't know how to start ..

can anyone help me ?
thanks

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target

Blog Entries: 1
Recognitions:
Gold Member
Homework Help
Science Advisor
 Quote by RsMath show that within n seconds (t) he never be more than O(logn) steps away from x=0 (start point) .
This is clearly not true. He can be as many as n steps away from x = 0, with nonzero probability. Do you mean "on average"?

 yes , I meant expectation(average) "show that the expected maximum distance is not greater than O(logn)
 Thread Tools

 Similar Threads for: Random Walks and Probability Thread Forum Replies Calculus & Beyond Homework 3 Calculus & Beyond Homework 13 Set Theory, Logic, Probability, Statistics 0 Quantum Physics 1 General Math 3