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

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