The familiar bijections between the representations of permutations as words and as products of cycles have a natural class of ``data driven'' extensions that permit us to use purely combinatorial means to obtain precise probabilistic information about the geometry of random walks. In particular, we show that the algorithmic bijection of Bohneblust and Spitzer can be used to obtain means, variances, and concentration inequalities for several random variables associated with a random walk including the number of vertices and length of the convex minorant, concave majorant, and convex hull.
Probability and Combinatorics
Tuesday, March 20, 2001 - 4:30pm
Mike Steele
University of Pennsylvania, Statistics