Complete self-avoiding random walk

Dear Matlab users,

I want to make a self-avoinding random walk. And by self avoiding I mean that the steps would never cross previous steps that have been taken until now.

So far I have written the code below:

a = 1 ; % Step size
N = 5 ; % Number of Random Walks
S = 100 ; % Number of steps
randWalkMat = [...
    1 -1 0  0 0  0;
    0  0 1 -1 0  0;
    0  0 0  0 1 -1;
    ];
X = zeros(S,N);
Y = X; 
Z = X; 
for k = 1:N
    t = randi(6, 1, S);
    randWalk = randWalkMat(:, t);
    X(:,k) = randWalk(1,:);
    Y(:,k) = randWalk(2,:);
    Z(:,k) = randWalk(3,:);
end
% Now we have the data for N number individual random seeds, and
% we have it for S number of steps:
% we get N sets of data for S random steps:
x_final = [[0,0];cumsum(X)];
y_final = [[0,0];cumsum(Y)];
z_final = [[0,0];cumsum(Z)];
% We plot the Random walk:
plot3(x_final,y_final,z_final,'x-')
grid on
axis equal

Any help is highly appreciated,

Argu

Answer 1

[Adam Danz]

The code you provided above (also see this source) will need to be slightly adapted to keep track of previous coordinates instead of keeping track of displacements.

I've made those adaptations below. At the top, you can set the step size, the number of random walks, and the number of steps per random walk. Walks start at (0,0). Each next-step is randomly chosen but is replaced with a different random choice if the next step is one of the previous coordinates. There a small possibility that the random walk will box iteself in such that there are no un-used local coordinates. To avoid an infinite while-loop in this case, if a solution is not found within 200 attempts (set by the user) the code will break and an error message will appear. I've tested it several times and this happens occationally when the number of steps is around 10,000 but typically an available step is found on the first or second attempt, occationally up to 10 attemps.

a = 1 ; % Step size
N = 2 ; % Number of Random Walks
S = 100 ; % Number of steps
whileCountMax = 200;
randWalkMat = [...
    1  0  0;
   -1  0  0;
    0  1  0;
    0 -1  0;
    0  0  1;
    0  0 -1];
xyz = zeros(S,3,N);  %rows = 1:S steps; cols = [x;y;z] coordinate; slices = [1:N] rand walkers
for k = 1:N
    % Choose random indices of randWalkMat
    for i = 2:S
        % reset flags
        accepted = false;
        whileCount = 0;
        while ~accepted
            % Choose next step
            nextStep = xyz(i-1,:,k) + randWalkMat(randi(6),:);
            % Determine if newest step has a unique coordinate
            ismem = any(ismember(xyz(:,:,k), nextStep, 'rows'));
            % Increment counter
            whileCount = whileCount + 1;
            if ~ismem
                accepted = true;
                xyz(i,:,k) = nextStep;
            elseif whileCount > whileCountMax
                error('Max while-count reached.  Random walk hit a dead end.')
            end
        end
    end
end
% We plot the Random walk:
plot3(squeeze(xyz(:,1,:)),squeeze(xyz(:,2,:)),squeeze(xyz(:,3,:)),'x-')
grid on
axis equal

Answer 2

[Ritish Kumar]

if we make a program for sef avoiding random walk for polymer than how can we approach that problem and how we calculate some parameters from that program. Any suggessions and help are highly appreciated.

[Adam Danz]

I'd start by stepping through the lines of code in the answer on this page so you can understand how it works. Here's another one:

https://www.mathworks.com/matlabcentral/answers/444374-self-avoiding-random-walk-help