I'm going to discuss an interesting task and an approach that might be useful to know.
The task is a Random-Walks with a Bound.
Input: Imagine a coordinates [0, +INFINITY), you stay at 0 and each time you can either hop left or right with equal probability, unless you stay at 0 (then you can only hop right with 100% probability).
Each hop increments you coordinate by 1 (right hop) or decrements it by 1 (left hop)
Output: What is the average number of hops to reach N coordinate (Ln).
Solution:
1) Let's introduce a function M(k) - it's an estimated number of hops to get from k to N. Then Ln = M(0)
2) M(k) = 1/2 * (M(k+1) + 1) + 1/2 * (M(k-1) + 1)
3) 2*M(k) = M(k-1) + M(k+1) + 2 <=> M(k) - M(k+1) = M(k-1) - M(k) + 2
4) M(0) - M(1) = 1 (Since there is only one step right when we at position 0), so
With an output of:
Fairly close, huh? :) GitHub
Hope you find this article helpful.
The task is a Random-Walks with a Bound.
Input: Imagine a coordinates [0, +INFINITY), you stay at 0 and each time you can either hop left or right with equal probability, unless you stay at 0 (then you can only hop right with 100% probability).
Each hop increments you coordinate by 1 (right hop) or decrements it by 1 (left hop)
Output: What is the average number of hops to reach N coordinate (Ln).
Solution:
1) Let's introduce a function M(k) - it's an estimated number of hops to get from k to N. Then Ln = M(0)
2) M(k) = 1/2 * (M(k+1) + 1) + 1/2 * (M(k-1) + 1)
3) 2*M(k) = M(k-1) + M(k+1) + 2 <=> M(k) - M(k+1) = M(k-1) - M(k) + 2
4) M(0) - M(1) = 1 (Since there is only one step right when we at position 0), so
- M(0) - M(1) = 1
- M(1) - M(2) = 3
- M(2) - M(3) = 5
- .....
- M(n-1) - M(n) = 2*n - 1
Summing all the and considering M(n) = 0
M(0) = 1 + 3 + 5 + .... (2*n-1) = n (2*n - 1 + 1) / 2 = n*n = n^2
So the answer is N^2
Experimental:
Let's try to confirm if the result matches in practice:
__author__ = 'vvlasov' import random as rd import numpy as np def generate_plain(tries, nsteps): walks = [] for j in xrange(tries): walk = np.zeros(dtype=int, shape=nsteps) walks.append(walk) position = 0 for i in xrange(nsteps): step = 1 if position == 0 or rd.randint(0, 1) else -1 position += step walk[i] = position return np.asarray(walks) if __name__ == '__main__': nsteps = 2000 walks = generate_plain(1000, nsteps) for crossingPoint in range(2, 21, 2): crossing_times = (walks >= crossingPoint).argmax(1) crossing_times = np.where(crossing_times > 0, crossing_times, nsteps) print "Reaching {} in {} steps average, where squared(n) = {}" \ .format(crossingPoint, crossing_times.mean(), crossingPoint ** 2)
Reaching 2 in 3.094 steps average, where squared(n) = 4 Reaching 4 in 15.312 steps average, where squared(n) = 16 Reaching 6 in 36.598 steps average, where squared(n) = 36 Reaching 8 in 65.286 steps average, where squared(n) = 64 Reaching 10 in 102.168 steps average, where squared(n) = 100 Reaching 12 in 143.56 steps average, where squared(n) = 144 Reaching 14 in 196.588 steps average, where squared(n) = 196 Reaching 16 in 258.082 steps average, where squared(n) = 256 Reaching 18 in 328.668 steps average, where squared(n) = 324 Reaching 20 in 400.973 steps average, where squared(n) = 400
Hope you find this article helpful.
No comments:
Post a Comment