A random walk is a process whose future behaviour depends only on its present position, which charts successive steps on some mathematical space, according to a probability distribution. We call a random walk simple if the size of each step is fixed, and symmetric if the probability of the direction of the step is equal, no matter the direction. Random walks play a major role in the study of markets and the movements of share prices. They are important in modelling the movement of particles in fluids and gas diffusion and are of significant mathematical interest. We call a random walk recurrent if it will almost surely return to its starting point: meaning that since the n-th return to the starting point begins a random walk with the same probability of returning, the n+1st return is guaranteed. If it is not recurrent, then we call the walk transient. A theorem due to George Pólya, 1921, states that a simple random walk is recurrent on the integer line, and on the 2-dimensional grid, but for the 3-dimensional grid or higher dimensions the walk is transient. A mathematician Shizuo Kakutani summarised this well as “A drunk man will always find his way home, but a drunk bird may not.” The character of a random walk depends not only on how the walk is defined, but on what space it is defined. A group is given by a set of objects with a reversible operation, and in this way models symmetries. The different symmetries of a shape, or the symmetries of numbers, or the different ways to shuffle a deck of cards all define groups. There is a rich theory of random walks on these groups. Another interesting area for random walks is on graphs, where a graph is a network of points and lines between them. A random walk on a graph simply moves from node to node depending on the assigned probabilities for each line between them. Every group may be represented as a graph, but many graphs cannot be linked to a group. For example, the Petersen graph is a highly symmetric graph whose nodes and lines cannot represent any group. In our project we have attempted to create a generalisation of this theory from groups into a subset of particularly symmetric graphs called derived graphs, hoping to bring some of the stronger theories of random walks on groups to a larger space.
Alastair Anderberg was a recipient of a 2018/19 AMSI Vacation Research Scholarship.