Random Walks and Probability

[RsMath]

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 similar 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

 

[jbunniii]

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"?

 

[RsMath]

yes , I meant expectation(average)

"show that the expected maximum distance is not greater than O(logn)