Random path through a rectangle

Question

I want to write a code to generate a random path trough a rectangle of a given size.

I will start from the point (0,0) and go up or right to reach xlim and ylim.

Here is my code,

y = 10;
x = 10;
yOld = 0;
xOld = 0;
figure
axis([0 x 0 y])
while yOld < y && xOld < x
    DirectionChange = randi([0 1],1);
    if DirectionChange == 0
        yNew = yOld + 1;
        xNew = xOld;
    else
        xNew = xOld + 1;
        yNew = yOld;
    end
    line ([xOld xNew],[yOld yNew],'LineWidth',3);hold on
    yOld = yNew;
    xOld = xNew;
end
line ([xNew x],[yNew y],'LineWidth',3);hold off 

The code has a while loop, and it ends when one of x or y reaches it's limit.

So It works fine provided x = y.

However, when y > x it's more probable that the path reaches xlim sooner.

for 12 runs of x = 10, y = 10I get (I made it colorful to look better!),

Setting x = 10, y = 20, I get,

As you can see I lose the randomness in latter case, as the probability of x reaching it's limit increases.

Any suggestions how to preserve randomness in case of x~=y?

Thanks.

Answer 1

You always need to make x steps to the right, and y steps up. So make an array containing those steps as encoded instructions (a simple array will do just fine here, we can use 0 for horizontal step and 1 for vertical). Then shuffle the array. This is guaranteed to hit the corner without any adjustments, and also all possible paths will be equally likely (as random as you can get).

x = 10;
y = 20;
steps = [ zeros(1,x) ones(1,y) ];
steps = steps( randperm(x+y) );

figure
hold on;

xOld = 0;
yOld = 0;
axis([0 x 0 y])
for step = steps,
    if (step == 1)
        yNew = yOld + 1;
        xNew = xOld;
    else
        xNew = xOld + 1;
        yNew = yOld;
    end
    line ([xOld xNew],[yOld yNew],'LineWidth',3);
    yOld = yNew;
    xOld = xNew;
end
line ([xNew x],[yNew y],'LineWidth',3);
hold off 

Answer 2

One option would be to condition the direction choice on the ratio of dimensions, e.g.

DirectionChange = rand(1);

if DirectionChange < y/(x+y)
    yNew = yOld + 1;
    xNew = xOld;
 else
    xNew = xOld + 1;
    yNew = yOld;
 end

Are there any requirements which should be kept? e.g. constant step size

EDIT: More effective strategy to avoid hitting the 'walls':

DirectionChange = rand(1);

% distance left to the end
xLeft = x - xOld;
yLeft = y - yOld;

if DirectionChange < yLeft/(xLeft+yLeft)
    yNew = yOld + 1;
    xNew = xOld;
else
    xNew = xOld + 1;
    yNew = yOld;
end

Answer 3

What you want to do is make it so that P(x increases) = x/(x+y) and P(y increases) = y/(x+y). In this way, the probability that x reaches its limit is the same as the probability of y reaching its limit.

Example: For a given xlim of 5 and a given ylim of 10, generate a random number from the continuous interval [0,1]. If this random number is less than .333, which is xlim/(xlim+ylim), you should increase xOld. Otherwise, increase yOld.

Use rand rather than randi.