🔍

# Heads or Tails? Professor Studies ‘Quasi-Random’ Processes

## Research Is Supported by \$200K NSF Grant

Prof. James Propp

12/12/2011
By Edwin L. Aguirre

The flip of a coin. The roll of a die. The spin of a roulette wheel. These are just some examples of random processes people are familiar with that involve a high degree of chance and unpredictability.

“Random processes have an intrinsic element of uncertainty — you can’t say what the future history of the system is going to be, and the best you can do is say what the system is likely to do,” says Prof. James Propp of the Mathematical Sciences Department. “In contrast, non-random processes are, in theory, completely predictable — if you know the initial state of the system, you can say exactly what’s going to happen at the next step and the step after that and so on.”

For example, if you toss a fair coin 10 times, then you can’t say how many times you’ll get heads, but you can say that on average you’ll get five heads, explains Propp.

Propp is exploring some new ideas for bridging the gap between random and non-random processes. His ongoing research, entitled “Deterministic Analogues of Random Processes,” is supported by a three-year \$200,000 grant from the National Science Foundation (NSF).

“In my work, I design ‘quasi-random’ processes that mimic the properties of random processes even though they’re not random at all,” he says. “In the coin-tossing example, a quasi-random analogue of the random coin process is a process that just alternates between heads and tails: heads, tails, heads, tails, etc. Of course, the examples I study are much more complicated than this!”

New Territory in Mathematics

Adds Propp: “My work has opened up new territory at the boundary between probability theory and combinatorics, which other researchers and I are just beginning to explore. Many phenomena governing random processes turn out to govern quasi-random processes as well, and we don’t really know why. My hope is that when we understand what’s going on for the non-random processes, it’ll shed light on what’s really going on with the random processes.”

He says what makes his work unique is that, as far as he knows, nobody else has realized that a simple idea like “heads, tails, heads, tails, etc.,” when properly exploited, can generate such a wide array of phenomena.

“My key insight is that ‘fairness’ is a surprisingly good substitute for ‘unpredictability,’” he says. “But maybe that isn’t really so surprising when you consider that the two main methods of deciding who goes next in a game are turn-taking — fairness — and tossing coins or rolling dice — unpredictability.”

Propp hopes to come up with general principles for designing non-random analogues of random processes and to prove theorems linking the behavior of random processes with their non-random counterparts.

“Eventually, I would like to construct a unified theory that encompasses both sorts of processes as well as hybrid processes that incorporate some elements of randomness but not as much as the original random processes,” he says.

He is currently mentoring some young people, ranging from high-school to college graduate students, and exposing them to the joys of mathematical research by giving them a chance to participate in his project and sending them on NSF-funded trips to attend conferences.

“My hope is that many of them will go on to have research careers of their own,” he says.

To learn more about Propp’s research, go to http://jamespropp.org.