Wednesday, April 6th, 2011
2:30pm - 4:00pm, in McCormack 2-116

James Propp

UMass Lowell

How well can you see the slope of a digital line? (and other applications of non-uniform averaging)

Abstract: If you have an n-by-n computer screen that shows a digitized version of some line (typicaly of irrational slope), and you estimate the slope of the line being digitized by the slope of the line joining the two farthest points, your error is likely to be on the order of 1/n. By looking at the points in between one can do better (though a simple geometry-of-numbers argument shows that one cannot expect to do better than 1/n^2). I'll describe a very simple scheme that has typical error on the order of 1/n^(3/2). A reformulation of the scheme leads to some novel approaches to other sorts of estimation problems, such as estimating the zeroeth Fourier coefficient of an unknown almost-periodic function, estimating a one-dimensional or multidimensional integral, and estimating an escape probability for a Markov chain. These applications share a common theme: when a source of data has built-in periodicity and you want to assess its long-term average behavior, you shouldn't use a simple uniform average of the values you've observed, but rather use an average in which values from the middle are weighted more heavily than values from the beginning and end. As a final application, I will use this method to derive improved ``estimates of pi'' from rotor-router walk (derandomized random walk). This is joint work with David Einstein, Gerry Myerson, Sinai Robins, and others, and was greatly facilitated by MathOverflow (see http://mathoverflow.net).