|Feb19-11, 08:32 AM||#1|
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 ?
|Feb21-11, 01:31 PM||#2|
|Feb24-11, 08:41 AM||#3|
yes , I meant expectation(average)
"show that the expected maximum distance is not greater than O(logn)
|Similar Threads for: Random Walks and Probability|
|Probability: Random Walks||Calculus & Beyond Homework||3|
|[PROBABILITY] Conditional probability for random variable||Calculus & Beyond Homework||13|
|Ergodic Theorem for Bounded Random Walks||Set Theory, Logic, Probability, Statistics||0|
|Random walks and conservation laws in average||Quantum Physics||1|
|Random Walks||General Math||3|