Random Walk (2D) [5A - 80A]

Contributed by Francis Glassborow

Imagine you are walking on a square grid and that at each intersection you make choose randomly between each of the four directions (left, right, up and down) including the direction by which you entered the intersection. For the purposes of this project I am calling that a two dimensional random walk.

To find out more about this idea and the idea of random walks in general visit here.

There are quite a few investigations that lead to suitable programming projects.

• Calculate the number of paths of n steps (easy).
• Calculate the average distance that a path of n steps will take you from your starting point.
• Calculate the proportion of self-avoiding (paths that never visit the same point twice) paths of n steps.
• Calculate the average length of all self-avoiding paths contained within an n by m rectangle that start at the lower left vertex and end at the upper right vertex.
• Draw all the self avoiding paths of length n (for n less than ten).

If you read the material you will find by following the above provided link you will get ideas for very many more projects of varying difficulty.

Program elements

Most of the problems about random walks make relatively little demand on knowledge of your chosen programming language but require a great deal of thought about how to solve the problem at hand. Recursion can also be a useful technique for a number of the problems.

Extensions

Try 3D random walks.

Try turning it into a two-person game played on a limited size grid where the first person who cannot move without revisiting an already visited grid point looses. (As a modification allow revisiting but forbid reuse of a step.')