Riffle shuffles,cycles, and descents

We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS _n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.     

A different construction of Gaussian fields from Markov chains: Dirichlet covariances

We study a class of Gaussian random fields with negative correlations. These fields are easy to simulate. They are defined in a natural way from a Markov chain that has the index space of the Gaussian field as its state space. In parallel with Dynkin's investigation of Gaussian fields having covariance given by the Green's function of a Markov process, we develop connections between the occupation times of the Markov chain and the prediction properties of the Gaussian field. Our interest in such fields was initiated by their appearance in random matrix theory.     

Random doubly stochastic tridiagonal matrices

Let \begin{align*}{\mathcal T}\end{align*}n be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study ‘typical’ matrices T∈ \begin{align*}{\mathcal T}\end{align*}n chosen uniformly at random in the set \begin{align*}{\mathcal T}\end{align*}n. A simple algorithm is presented to allow direct sampling from the uniform distribution on \begin{align*}{\mathcal T}\end{align*}n. Using this algorithm, the elements above the diagonal in T are shown to form a Markov chain. For large n, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013     

Unitary Correlations and the Fejér Kernel

Let M be a unitary matrix with eigenvalues t _j , and let f be a function on the unit circle. Define X _f (M)=f(t _j ). We derive exact and asymptotic formulae for the covariance of X _f and X _g with respect to the measures |(M)|²dM where dM is Haar measure and an irreducible character. The asymptotic results include an analysis of the Fejér kernel which may be of independent interest.     

Moderate growth and random walk on finite groups

We study the rate of convergence of symmetric random walks on finite groups to the uniform distribution. A notion of moderate growth is introduced that combines with eigenvalue techniques to give sharp results. Roughly, for finite groups of moderate growth, a random walk supported on a set of generators such that the diameter of the group is requires order ² steps to get close to the uniform distribution. This result holds for nilpotent groups with constants depending only on the number of generators and the class. Using Gromov's theorem we show that groups with polynomial growth have moderate growth.     

The Asymmetric One-Dimensional Constrained Ising Model: Rigorous Results

We study a one-dimensional spin (interacting particle) system, with product Bernoulli (p) stationary distribution, in which a site can flip only when its left neighbor is in state +1. Such models have been studied in physics as simple exemplars of systems exhibiting slow relaxation. In our East model the natural conjecture is that the relaxation time (p), that is 1/(spectral gap), satisfies log (p) as p0. We prove this up to a factor of 2. The upper bound uses the Poincaré comparison argument applied to a wave (long-range) comparison process, which we analyze by probabilistic techniques. Such comparison arguments go back to Holley (1984, 1985). The lower bound, which atypically is not easy, involves construction and analysis of a certain coalescing random jumps process.     

The Markov moment problem and de Finetti’s theorem: Part II

This paper gives an abstract version of de Finettis theorem that characterizes mixing measures with L_p densities. The general setting is reviewed; after the theorem is proved, it is specialized to coin tossing and to exponential random variables. Laplace transforms of bounded densities are characterized, and inversion formulas are discussed.     

Geometric analysis for the metropolis algorithm on Lipschitz domains

This paper gives geometric tools: comparison, Nash and Sobolev inequalities for pieces of the relevant Markov operators, that give useful bounds on rates of convergence for the Metropolis algorithm. As an example, we treat the random placement of N hard discs in the unit square, the original application of the Metropolis algorithm.