Self avoiding random walk help

Dear all,

I am trying to create SAW random walk in matlab. First I have written a code which it can have 6possible steps on a lattice(code is attached).

Now I want to create a self avoiding random walk, which after the first step, it can only have 5 possible steps (cannot go back on itself). Any idea that how may I change the code? should I write another code?

clear all
clc
a = 1 ; % Step size
N = 2 ; % Number of Random Walks
S = 100 ; % Number of steps
r=zeros(1,1);

for k = 1:N
 for i = 1:S
t = randi(6);
% Every step in "x" and "y" and "z" directions:
if t == 1
    x{i} = 1;
    y{i} = 0;
    z{i} = 0;
elseif  t == 2
        x{i} = -1;
        y{i} =  0;
        z{i} =  0;
   elseif  t == 3
        x{i} = 0;
        y{i} = 1;
        z{i} = 0;
      elseif  t == 4
            x{i} =  0;
            y{i} = -1;
            z{i} =  0;
          elseif  t == 5
                x{i} =  0;
                y{i} =  0;
                z{i} =  1;
              elseif  t == 6
                    x{i} =  0;
                    y{i} =  0;
                    z{i} = -1;
end
 
X = cell2mat(x);
Y = cell2mat(y);
Z = cell2mat(z);
 end
 
 X1=[r,X];
 Y1=[r,Y];
 Z1=[r,Z];
 % We sum the steps to get all the data in a new cell array:
X2{k}=cumsum(X1);
Y2{k}=cumsum(Y1);
Z2{k}=cumsum(Z1);
end
% Now we have the data for N number individual random seeds, and
% we have it for S number of steps:
x2=cell2mat(X2);
y2=cell2mat(Y2);
z2=cell2mat(Z2);

% we get N sets of data for S random steps:
x_final=reshape(x2,[S+1,N]);
y_final=reshape(y2,[S+1,N]);
z_final=reshape(z2,[S+1,N]);

% We plot the Random walk:
plot3(x_final,y_final,z_final,'x-')
grid on
axis equal

Best,

Argu

[James Tursa]

Cannot go back on itself only for the most recent step, or for any previous steps?

[Adam Danz]

Here is a much cleaner, more efficient version of your code. The nested conditional statements were replaced with the randWalkmat matrix. If you have any questions please let me know.

I haven't addressed your question here. I just cleaned up the code to make it more efficient.

% Random walk with integer steps.
clear all
clc
a = 1 ; % Step size
N = 2 ; % 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

[DEBIDATTA BEHERA]

What will be the scilab code for self avoiding random walk?

[Image Analyst]

I'd copy the code to a scilab discussion forum and ask for help translating it into that language.

Answer 1

[Adam Danz]

Working from the cleaner version of your code I provided in the comments under your question, here's an adapted version that avoids random steps that go back on the previous step.

Here are som key parts of the code

• 'randWalkMat' is a matrix of random steps; rows are X,Y,Z
• 'forbddenPairs': each row defines two columns of randWalkMat that would cancel out a step.
• The for-loop and the nested while-loop are designed to choose a random column in randWalkMat but to check that the chosen column is not a forbidden pair with the previously chosen column. If so, it chooses another one.
• Everything after that is just a cleaner version of your original code.

Feel free to ask followup questions!

clear all
clc
a = 1 ; % Step size
N = 2 ; % 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;
    ];

% list columns of randWalkMat that shouldn't be neighbors
% * Each row needs to be in accending order
forbiddenPairs = [ 
    1,2; 
    3,4; 
    5,6]; 

X = zeros(S,N);
Y = X; 
Z = X; 
t = randi(6); 

for k = 1:N
    % Choose random indices of randWalkMat
    for i = 2:S
        accepted = false; %reset flag
        while ~accepted         
            t(i) = randi(6);
            % Determine if current step goes back on previous step
            if ~ismember(sort(t(i-1:i)), forbiddenPairs, 'rows')   
                accepted = true; %step is OK, move on. 
            end
        end
    end

    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 = [zeros(1,N);cumsum(X)];       % * 
y_final = [zeros(1,N);cumsum(Y)];       % *
z_final = [zeros(1,N);cumsum(Z)];       % *

% We plot the Random walk:
plot3(x_final,y_final,z_final,'x-')
grid on
axis equal

[Adam Danz]

"Hi Adam,

Thanks for your help, I was sonering when I change the number of random walks it is not working. For example I run this code for several random walks(and not just for 2). Also I would also appreciate if you explain how the accepting method is working. I am also eager to create a situation with only 4 possible moves(90 degrees). from the previous step

with my berst regards,

Argu"

I updated 3 lines of the code marked by " % *". Now the code will work for any integer "N".

To understand the code, I suggest stepping through the code and understanding each section. If you have specific quesitons I'd be glad to help.

If only 90deg turns are accepted, that means 1) you can go back to the previous step (which we already took care of) and 2) you cannot go forward. Going forward means that the previous step and the current step both selected the same column in randWalkMat. So what you want to do is prevent the code from selecting the same column number twice in a row and that will be done in the while loop.

Replace this

            if ~ismember(sort(t(i-1:i)), forbiddenPairs, 'rows')   
                accepted = true; %step is OK, move on. 
            end

with this

            if ~ismember(sort(t(i-1:i)), forbiddenPairs, 'rows') && length(unique(t(i-1:i)))~=1
                accepted = true; %step is OK, move on. 
            end       

[Argumanh]

Thanks Adam,

This is really great, Its good to learn better coding. I appreciate your kind help.

Best,

Argu

[Adam Danz]

Glad it worked out!

Let me know if you have any followup questions.

[Argumanh]

Hi Adam,

I want to change this code, in a sense to create a self avoiding random walk. And by self aboiding I mean that the steps would never cross previous steps that have been taken until now. If you wish, I can create a new question and put the link here.

I would highly appreciate

[Argumanh]

Hi Adam,

You can follow the question from here:

https://www.mathworks.com/matlabcentral/answers/449454-complete-self-avoiding-random-walk

Answer 2

[Argumanh]

Hi Adam,

Thanks for your help, I was sonering when I change the number of random walks it is not working. For example I run this code for several random walks(and not just for 2). Also I would also appreciate if you explain how the accepting method is working. I am also eager to create a situation with only 4 possible moves(90 degrees). from the previous step

with my berst regards,

Argu

[Adam Danz]

See reply above. Please use comment section rather than proposing a solution unless that is your intent.