Titre
A Guided tour to the Random Walk for Computer Scientists
Résumé
The study of Random Walks finds application in many fields of Science: Computer Science and Information Technologies make no exception.
Random Walks models offer the conceptual ground to the study of several real-world graphs, such as those of peer-to-peer networks, social networks or the graph of web pages: for instance, the definition of the well-known (Google search) Page-Rank algorithm is structured around the ideal behavior of web random surfers. Many communication protocols for peer-to-peer networks and sensor networks are based on Radom Walks.
Furthermore, diffusion phenomena, consisting in the Random displacements of a population of hypothetic walkers inspire several image-processing algorithms for image filtering, segmentation and enhancement; they represent as well the key element of general purpose tools such as the Markov Chain Monte Carlo (Metropolis-Hastings) algorithms and of the Simulated Annealing optimization techniques.
Indeed, the full list of application in Computer Science would be very long.
Random walks models provide also several surprising connections between Computer Science and apparently distant fields of Knowledge such as Physics and Biology, and can be used to model Gambling, Finance and Economics.
The aim of this short series of lectures is to give an undergraduate-level introduction to the basic mathematical modeling tools for Random Walks and to propose a small sampler of the many aspects of the subject that a Computer Scientist might find intriguing, amusing or simply interesting.