Pages

Tuesday 17 May 2016

A Random Walk

It is fascinating to see the use of the word 'random' and its resemblance to one of the most basic ingredients in some computer algorithms. One may ask what is it that makes something random?

- "So you just made a random deal?"
- "Students were randomly chosen to take part in a drama."
- "He figured out that he still had an hour to his departure, so he went for a random walk."




It is clear that when something is referred to as random it basically has a high uncertainty of achieving a number of possible outcomes. Dynamic system models use exactly the same idea to add the 'randomness' or noise for accurate modelling of dynamically changing properties of an object. Methods like Kalman and Particle filter can model the dynamics of any system given they are able to correctly infer the amount of randomness or uncertainty in the systems motion.

One algorithm which I recently looked at is called random walk. The basic idea is literally quite similar to an actual random walk. The system in a random walk algorithm has a high uncertainty of moving in any possible direction. This is straight-forward to implement. You start with a random position and update that by adding random displacement vectors. The result looks totally random which can be used in a number of applications to model highly uncertain systems.