self avoiding random walk

i need help. what i think i have to do is choose a direction at random and then look at a direction i want to go to if it's empty then carry on. if the direction is used then you start another walk. 1000 walks and lenght 1 to 25. how do i calcalute the number of successful walks. the code i have is a random walk

r=[0 0];
X=[0];Y=[0];
for
t= 1:1:100
B=rand(1,1)*4;
if B<1
new_position=r+[1 0];
elseif B<2
new_position=r+[0 1];
elseif B<3
new_position=r+[-1 0];
else
new_position=r+[0 -1];
end
X=[X new_position(1)];
Y=[Y new_position(2)];
r=new_position;
end
plot(X,Y)

[Image Analyst]

http://www.mathworks.com/matlabcentral/answers/13205-tutorial-how-to-format-your-question-with-markup How do you define "empty"? Are you trying to avoid having the next step cross any paths on the route so far?

[nawal]

By empty I mean the point is occupied/ already visited

Answer 1

[Roger Stafford]

As I see it from all you have stated, Nawal, you wish to "walk" point-to-point starting at (0,0) for a maximum of 25 steps, at each step moving a distance of one unit in one of four possible directions: up, left, down, or right with equal probabilities. However you wish to quit the walk if before 25 successful steps you would occupy a point that has already been traversed. Your aim is to count the number of successful walks, that is, the number in which you successfully reached 25 unoccupied points, out of a total of one thousand attempted walks. Do I state your problem correctly? (Your later remark that "it lands within a certain distance" throws some uncertainty into this interpretation. Are you sure you meant to concede this? You are dealing with exact integral positions here. Based on your earlier remarks, that "certain" distance should be an exact zero!)

In the following code the variable w will count the number of walks, the variable c will count the number of successful walks, the variable s will count the number of successful steps taken in each walk, and the 51 x 51 array Occ will record the positions already occupied during each walk.

c = 0; % This counts the number of "successful" walks
tx = [1,0,-1,0];
ty = [0,1,0,-1];
for w = 1:1000 % w counts the walks attempted
  Occ = zeros(51); % Keeps track of occupied points
  x = 26; % It is equivalent to start at (26,26) rather than (0,0)
  y = 26;
  Occ(x,y) = 1; % w counts the walks attempted
  s = 0; % Start number of steps at zero for each walk
  b = true;
  while b & (s<25) % Quit if walk abandoned or succesful
    r = randi(4);
    x = x + tx(r);
    y = y + ty(r);
    if Occ(x,y) == 1
      b = false;
    else
      Occ(x,y) = 1;
      s = s + 1;
    end
  end
  if s == 25
    c = c + 1; % Count the number of successful walks
  end
end

[nawal]

Yes that is what I meant. With the code you've done is there a way to record the proportion of successful ones, for all lengths up to 25. Is it possible to plot it?

Thanks

[Roger Stafford]

Yes, that's easy. Right after each exit from the above while-loop add 1 to an element of a 25-element array indexed by s where the array is initially all zeros. Afterwards the counts in this array when divided by 1000 would be your desired proportions. (The 25th element will actually be the sum of all the cases where the maximum would have been 25 or greater if the steps had been continued beyond 25.)

However, possibly you mean that you wish to repeat the whole thousand-walk experiment for each possible maximum value from 1 to 25. If that is your meaning, you pretty much place the above code within an outer for-loop that varies the limit from 1 to 25. You will have to place the c values in some array indexed by the outer for-loop varying maximum value, which when divided by 1000 would be the desired proportions. Note that these proportions have a different significance than those above. In each case they represent the proportion that would have run this particular maximum value or higher, whereas the earlier proportions were those that stopped exactly at the corresponding maximum value (except of course for the last, 25th value which has the same meaning in both cases.)

[Image Analyst]

nawal, you threw us when you used rand() instead of randi(), so your code generated fractional floating point numbers, not integers. But Roger suggested integers and you said that's what you meant (but didn't say). (Saying that in advance would have saved me and you the 5 attempts to get more information and clarification from you.) As he says, it's easy to record and plot the points at each step and I think you can do that yourself so if I were you I'd just mark Roger's answer as "Accepted" to close it out.

[Roger Stafford]

Image Analyst, where Nawal wrote

 B=rand(1,1)*4;
 if B<1
  new_position=r+[1 0];
 elseif B<2
  new_position=r+[0 1];
 elseif B<3
  new_position=r+[-1 0];
 else
  new_position=r+[0 -1];
 end

in his original problem statement, it was the logical equivalent of using the output of randi as an index, and his code did not produce fractional displacements of x and y but rather changes only by -1, 0, and +1 just as in my code. I only used randi because it produced more compact coding, and not to alter his logic.

[Image Analyst]

You're right. I didn't notice that. Comments in the code, and proper indenting, would have been helpful.

[nawal]

say instead of randomly choosing the direction say you make the first walk fixed d=direction. so if you're going in direction d the excluded direction is (d+2)mod4 and choosing a random number r=0,1 or 2 the new direction is (d+3+r)mod4. I'm just not sure how to write this.

Answer 2

[Image Analyst]

"By empty I mean the point is occupied/ already visited" - I doubt that will never happen, at least probably not in your lifetime. The chance of a pair of double precision numbers being repeated exactly is vanishingly small.

[Walter Roberson]

The direction is random, but it appears the choices of direction are left, right, up, down.

[Image Analyst]

Is he then saying that the quadrant has one or more points in it, as opposed to landing exactly on the precise location of a prior point?

[nawal]

Steps of one-Say you start at a point and you choose a direction to go (left, right, up, down) then at the new point you choose a direction. What I'm trying to do is to stop the walk if it the direction it chooses goes back to a point that was already visited

[Image Analyst]

Still unclear. What if I was at (1,0) and I stepped to (2,0). So if I step back in the general direction where I came from (back along the x axis towards the origin) and I would land at exactly (to the maximum precision allowed by the computer) (1,0) I can see that you want to stop. But like I said, you won't ever land there. So what if you'd land at (1.000000001, 0.000009), which is really really close? Do you want to stop in that case too?

[nawal]

if that is the case then i want it stop

[Image Analyst]

Still unclear. When do you want to stop it?

1. If it lands anywhere in the "backwards" half plane?
2. Or if it lands within a certain distance from the last point?
3. Or if it lands within a certain distance from any prior point?

Which case(s)?

[nawal]

if it lands within a certain distance from any prior point