By Miranda Louwerse (Contributor) – Email
Print Edition: March 25, 2015
The math club continued its Math Talk series on Thursday, March 19 by inviting Petra Berenbrink, an associate professor of computing science at SFU, to give a talk about her research interest to faculty and students from the math and CIS departments.
Berenbrink’s research is in the field of randomized algorithms — that is, algorithms that use randomness as part of their logic. She says she is interested in randomized algorithms because they are easy and elegant, and give reliable output.
One of the applications of these algorithms Berenbrink gave during her lecture is in speeding up random walks. A random walk is a process of covering a graph in an undirected, arbitrary way. The graph is made up of points (nodes) and lines connecting them (edges).
The standard random walk is the Markov process. In this process, when you are at a node, which node you go to next depends only on where you are, not on where you have been. In this way, the steps are totally random. However, it is also easy to imagine that the walk could randomly take you back and forth from one node to another multiple times. This is not the most effective way to cover the graph.
Berenbrink views the problem in a different way. She set up a system so that, beginning at one node, the next step goes to a random neighbouring node that has not previously been visited. This would certainly be a more effective way to cover the graph. In her proof, she showed that unvisited nodes are on cycles, so that if you find one unvisited node there will be a cycle of unused edges to follow next.
The idea of speeding up random walks has many applications in computing, which then translate into applications in things like robotics and exploring graphs.
Voter processes is another application that Berenbrink gave of the usefulness of randomized algorithms. In this situation, each node is a person and there are a number of opinions that person could have on something. This randomized algorithm looks at how the neighbouring nodes (or people) influence us.
There are different ways to model the process, but one such method Berenbrink described is a pull method. In this model, a node (person) takes on the opinion of one of their randomly selected neighbours. The idea is to see what opinion prevails and how long it takes to reach a majority.
Using these algorithms, the way information spreads and how long it takes for a system to reach a majority can be modelled in a simple way. Berenbrink’s talk demonstrated again to faculty and students the incredible power of math and computing in modelling real-world situations.
