随机游走算法

Question

我正在尝试创建一个程序，使用以下算法绘制可以在笛卡尔平面上采取的不同路径和点： 从原点 (0, 0) 开始，在步骤 1 中，您执行以下操作之一：

*向右跳 1/2 或向左跳 1/2 或终止于所在位置。

如果运动尚未结束，则进行第2步：

*向上跳 1/4 或向下 1/4 或终止于所在位置。

如果运动尚未结束，则进行第3步：

*向右跳 1/8 或向左跳 1/8 或终止于所在位置等。

您实际上会无限期地执行此操作，在步骤 k 中，如果 k 是偶数并且运动尚未结束，您将向上或向下跳跃 (1/2)^k。类似地，在步骤 k 中，如果 k 是奇数，则向右或向左跳转 (1/2)^k 或终止于所在位置。

我想绘制出您可以通过这种方式在有限多个步骤中达到的端点集。下面的代码正确吗？顺便说一下，每条路径末端的彩色圆圈是端点。这些绘制正确吗？

import numpy
import pylab
import random
import matplotlib.pyplot as plt
axes = plt.axes()
k = 50

x = numpy.zeros(k)
y = numpy.zeros(k)
lst = []
for j in range(1,30):
  for i in range(1,k):
    dir = [-1,1][random.randint(0,1)]
    if i%2!=0:
        x[i] = x[i - 1] + 1/(2**(i)) * dir
        y[i] = y[i - 1]
    else:
      x[i] = x[i - 1]
      y[i] = y[i - 1] + 1/(2**(i)) * dir
  plt.plot(x, y,marker = 'o')
plt.title("Different paths the random walk movement sequences could take")
pylab.show()

Answer 1

我认为您发布的代码中缺少某些方面，例如任何给定的步行是否会终止。我试图实现下面所请求的功能。

控制台输出：

Walk 1
 at step 1 moves 1/2^2 along y
 at step 2 moves 1/2^3 along x
 terminates at step 3
Walk 2
 at step 1 moves 1/2^2 along y
 at step 2 moves 1/2^3 along x
 at step 3 moves 1/2^4 along y
 terminates at step 4
Walk 3
 at step 1 moves 1/2^2 along y
 at step 2 moves 1/2^3 along x
 at step 3 moves 1/2^4 along y
 at step 4 moves 1/2^5 along x
 terminates at step 5
Walk 4
 at step 1 moves 1/2^2 along y
 terminates at step 2

实施：

import numpy
import matplotlib.pyplot as plt

#walk parameters
steps_per_walk = 50
n_walks = 5
termination_prob = 0.2

#Each walk will have a colour
colour_map = plt.get_cmap('jet', n_walks)

numpy.random.seed(4) #make the randomness reproducible

for walk in range(n_walks):
    #Each walk starts at (0, 0)
    x = [0]
    y = [0]
    
    print('Walk', walk)
    
    for step in range(1, steps_per_walk + 1):
        step_size = 1 / 2 ** step
        
        #Chance of terminating at any given step
        terminates = True if numpy.random.rand() < termination_prob else False
        
        if terminates:
            #No more steps will be taken in this walk
            print(' terminates at step', step)
            break
        
        #Otherwise, movement will be either +step or -step with equal prob
        movement = step_size * [-1, 1][numpy.random.randint(2)]
        
        #Moving from previous point:
        x.append( x[step - 1] )
        y.append( y[step - 1] )
        
        #Move alternately along x for first step, then y
        if step % 2 != 0:
            x[step] += movement
        else:
            y[step] += movement
            
        print(' at step', step, f'moves 1/2^{step + 1}',
              'along', 'x' if not step % 2 else 'y')
            
    #Plot the walk's recorded path
    plt.plot(x, y, color=colour_map(walk), label=f'walk {walk} ({step - 1} steps)')
    #Add marker only at the walk's end point
    plt.plot(x[-1], y[-1], color=colour_map(walk), marker='s')
    
    #loops over remaining walks until all walks done...

plt.title("Different paths the random walk\nmovement sequences could take")
plt.legend(bbox_to_anchor=(1.4, 1))
plt.gcf().set_size_inches(7, 3)
plt.xlabel('x')
plt.ylabel('y')
plt.show()