Random Walk

Random walk는 방향에 대한 random sampling을 하는 것이다.

아래 코드 random_walk 함수를 보면 right, left, up, down의 4 방향 중 무작위로 선택하여 이동한다. 여기에 조건을 넣어 값을 취하게 되면 Monte Carlo simulation이 되는 것이다. 여기서는 random walk를 통해 집(원점)으로부터 떨어진 거리가 4 이하이면 교통수단 없이 집에 돌아올 수 있는데, 이것의 횟수가 평균(50%)이 되는 가장 긴 걸음 수를 구하는 문제이다. 답은 22걸음이다.

Question : What is the longest random walk you can take so that on average you will end up 4 blocks or fewer from home?

 

CODE : Random walk and Monte Carlo simulation

import random 

def random_walk(n):
    x, y = 0, 0
    for I in range(n):
        (dx, dy) = random.choice([(0,1), (0,-1), (1,0), (-1,0)])
        x += dx; y += dy
    return (x, y)

number_of_walks = 10000

for walk_length in range(1,31):
    no_transport = 0
    for I in range(number_of_walks):
        (x, y) = random_walk(walk_length)
        distance = abs(x) + abs(y)
        if distance <= 4:
            no_transport += 1
    no_transport_percentage
        = float(no_transport) / number_of_walks
    print(walk_length,':\t',no_transport,'\t',no_transport_percentage)

 

1 :      10000   100.0
2 :      10000   100.0
3 :      10000   100.0
4 :      10000   100.0
5 :      8804    88.03999999999999
6 :      9343    93.43
7 :      7680    76.8
8 :      8621    86.21
9 :      6775    67.75
10 :     7926    79.25999999999999
11 :     6010    60.099999999999994
12 :     7331    73.31
13 :     5461    54.61
14 :     6715    67.15
15 :     4866    48.66
16 :     6210    62.1
17 :     4338    43.38
18 :     5848    58.48
19 :     4177    41.77
20 :     5358    53.580000000000005
21 :     3802    38.019999999999996
22 :     5080    50.8
23 :     3646    36.46
24 :     4790    47.9
25 :     3317    33.17
26 :     4506    45.06
27 :     3087    30.869999999999997
28 :     4310    43.1
29 :     2998    29.98
30 :     4064    40.64

 

Reference

- https://www.youtube.com/watch?v=BfS2H1y6tzQ