Tuesday, April 9, 2013

Programming Puzzle: Random Walks with a Bound

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


  • 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)

With an output of:
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
        

Fairly close, huh? :) GitHub

Hope you find this article helpful.




No comments:

Post a Comment