- 17 Sep 2015
In this post we interview Sid Redner, the instructor for our new tutorial on an Introduction to Random Walks. Sid is a physicist and Professor at the Santa Fe Institute. Prior to joining the Santa Fe Institute as part of the resident faculty, Sid was Professor in the Boston University Physics Department, member of the Center for BioDynamics and the Center for Polymer Studies. Connor O’Neil sat down with Sid to ask him a little about Random Walks.
Q. Why is the random walk a good tool for complex systems?
First of all, at the microscopic level, everything moves according to a random walk. For example, you just moved your chair; you pushed against the chair and it moved backwards. But if you were a trillion trillion times smaller, you would find air molecules in the way, and those would prevent you from moving deterministically. As a result, at the microscopic level, movement is determined just by friction with the medium, and the motion is random walk-like rather than deterministic.
That’s answer one. Answer two: in many sorts of complex systems, one is trying to look at the probability distribution of some complex state space. Typically these probability distributions evolve by some small changes in state space. The evolution of these probability distributions can be described by general stochastic processes, in which the tools of random walks are very useful.
Q. What kind of work in random walks do you currently find particularly interesting?
The field of random walks is really broad. The thing is it’s been around now for 120, 130 years, even longer than that; the application of random walks to gambling is more than 200 years old. So you think, it’s been around for so long, what else could possibly be new? And then people come up with all these incredible things. One topic that I find incredibly fascinating is search problems. You’re trying to find something that’s somewhere within a finite geometry with random walks, how long does it take for a random walk to find it? The interplay between the geometry and the specific rules of the search algorithm give rise to all kinds of very rich behaviors.
Q. What in your own work have you found interesting recently?
This work we did with the random walk picture of basketball scoring statistics; that was a lot of fun. Perhaps the thing that was most striking was that there’s this weird thing called the “arcsine law.” Let me tell you what the arcsine law is, because when you first hear it, you think, “this can’t be right, it just has to be wrong.”
So let’s play a gambling game. Heads I win, tails you win. You flip a coin once a second for a year, and clearly at the end of this year, if we each start out with a thousand pennies, then at the end of the year we should have the
same number of pennies because there’s no bias in the game. But you can ask the following question: “what fraction of the time are you ahead, and what fraction of the time am I ahead?” Clearly the average fraction is one half. But what if you ask, “What is the probability distribution of this fraction?” Naively you would say, it should be peaked at one half, but it turns out that no, it’s minimum at one half, and peaked at zero and one. I saw the look on your face. You think, “that can’t be right.” But it is! And that’s something called the arcsine law, and in fact we found the arcsine law was obeyed by basketball scoring statistics. It was really mind-boggling.
That arcsine law thing is something I find really seductive. I remember the first time I read it. It was in a very fancy probability theory book, and I thought, “this is like science fiction!” But it can be derived, and argued for why it has to be that way. It’s quite striking.
Q. Will we find the arcsine law anywhere in your tutorial?
No but I’m thinking about adding a “dessert” part to the end of the tutorial, just for the arcsine law because it’s so cool.
Q. How would you suggest students get the most out of your tutorial?
It really depends on what their interest is. If one truly has an academic interest, then I would say that the most useful thing is to be working on the homework, and to follow up on some of the reading I’ve suggested. The thing about random walks is that there are so many wonderful features, like this dichotomy between ‘sure-to-return’ and infinite return time, that if you start snooping a bit more, you’ll find something that will seduce you. And you’ll be hooked for life, as I am.
Q. What was the hook for you?
It was probably some article by Elliot Montroll. He has this really nice way of writing and I was taken in. This thing about transience vs. recurrence just sucked me in right away. I had always been using techniques from random walks in my research, and at some point I got frustrated because I realized that there’s this whole field of first passage processes that I was using over and over again, and there wasn’t any book on the field. So I wrote a book on the field, and that got me really hooked, because I feel that even though I wrote a book on it, I know so little, and there’s so much more to understand. I only have the rest of my life to understand it. It’s not going to be enough.
It’s truly awesome how beautiful it is, these things you think you know really well, and then you don’t.
Q. Is there anything else you’d like to tell the students?
There are so many wonderful resources out there and there are so many beautiful and non-intuitive results, and situations where people think they understand and they really don’t. Try to explore!
Check out the Random Walks tutorial here.
