Directed random wandering.

Directed random wandering

I would like to pose a problem that some of you might find interesting.

I want to write Matlab code that generates a particular kind of random walk that meets the following requirements:

1 - Moves from a specific beginning point to a specific endpoint.

2 - moves in integral values of -1, 0 or 1.

For example, move in a random sort of way from (0,0) to 50,81) in 200 moves. I.e., not the quickest path but one that wanders.

Ideas?

Answer 1

[Walter Roberson]

Consider that when you move from 0 to 50, you need to take 50 "unbalanced" steps -- 50 steps that are +1 and for which there are no corresponding -1 steps. So create a temporary vector that is 50 copies of +1 . This used up 50 of the 200 moves, leaving 150 more moves.

Now of the 150 moves, up to 75 times you can have a move right that is counter-balanced by a move left -- one +1 for each -1. So generate a random number of "balanced" moves between 0 and floor((200-50)/2) . append that many copies of -1 to the temporary vector, and the exact same number of copies of +1 to the temporary vector. Now pad the temporary vector out with 0's to exactly length 200.

Do the same thing creating a temporary vector corresponding to the change in y, this time with 81 unbalanced +1 and up to 59 balanced +1 with the same number of -1, and as before pad out the vector with 0's to length 200.

Now use

steps = [xtemp(randperm(200)); ytemp(randperm(200))];

this is 2 x 200, each entry is -1 or 0 or +1, and by construction at the end you will have arrived at the desired location.

Note: with this particular construction, you might arrive at the endpoint early, and might leave it again or might sit there doing nothing.

If you do not want to permit sitting there doing nothing at the end (e.g., arrive at step 197 and do nothing for another 3 steps so on the 200th step you are (still) at the endpoint) then you should probably find the last column that is not [0,0] and exchange it with the last column, so that the last step will always be movement onto the final location.

If you do not want to permit the possibility of arriving at the point early and leaving again, then constructing the walk to prevent that possibility might be a bit tricky. It might be easier to regenerate the walk (but test that first! Do not assume that the process is definitely finite!)