Persi Diaconis (Stanford)

Adding a single column of digits give carries along the way. How many carries are typical (about 1/2?) and how are the carries distributed?
There are neat answers involving a strange corner of probability (one dependent point processes). These in turn are shown to be determinental (like the eigenvalues of random matrices).
Finally, the whole story is quite general, with many similar examples from combinatorics, algebra, and basic statistics shown to have similar structure.
This is joint work with Jason Fulman and Alexei Borodin.
top of page

Chris Burdzy (U. Washington)

Consider reflected Brownian motion X_t in a bounded Euclidean domain, with inert drift defined as follows. The process X_t has a constant drift K_t during every excursion of X_t away from the boundary of the domain. The drift K_t is the same as the total local time push (vector) accumulated before t at the boundary.
I will discuss the stationary distribution of (X_t, K_t) - can you guess what it is?
Time permitting, I will present some other results and problems related to X_t.
This is joint work with too many authors to be listed here (they will be listed in my presentation).
top of page

Michael Harrison (Stanford)

Let Z be an n-dimensional Brownian motion confined to the non-negative orthant by oblique reflection at the boundary. Such processes arise in applied probability as diffusion approximations for multi-station stochastic processing networks. For dimension n = 2, a simple condition is known to be necessary and sufficient for positive recurrence of Z. The obvious analog of that condition is necessary but not sufficient in three and higher dimensions, where fundamentally new phenomena arise. Building on prior work by Bernard and El Kharroubi (1991) and El Kharroubi et al. (2000, 2002), we provide necessary and sufficient conditions for positive recurrence in dimension n = 3. In this context we find that the fluid-stability criterion of Dupuis and Williams (1994) is not only necessary for positive recurrence but also sufficient; that is, in three dimensions Z is positive recurrent if and only if every path of the associated fluid model is attracted to the origin. A recently discovered example strongly suggests that this equivalence fails in four and higher dimensions. * Joint work with Maury Bramson, Dick Cottle and Jim Dai
top of page

Laurent Miclo (U. Toulouse)

Consider K>1 independent copies of the random walk on the symmetric group S_N starting from the identity and generated by the products of either independent uniform transpositions or independent uniform successive transpositions. At any time n, let G_n be the subgroup of S_N generated by the K positions of the chains.
In the uniform transposition model, we prove that there is a cut-off phenomenon at time N ln(N)/(2K) for the non-existence of fixed point of G_n and for the transitivity of G_n, thus showing that these properties occur before the chains have reach equilibrium.
In the uniform successive transposition model, a transition for the non-existence of fixed point of G_n appears at time of order N^{1+...}/2K (at least for K>2), but there is no cut-off phenomenon. In this model, we recover a cut-off phenomenon for the non-existence of fixed point at a time proportional to N by allowing the number K to be proportional to ln(N).
The main tools of the proofs are spectral analysis and coupling techniques.
This is joint work with André Galligo.
top of page

Yuval Peres (Microsoft)

Given an infinite collection of points in the plane (a point process) how do we allocate the same area to each point in a decentralized, shift invariant way?
Different approaches to this problem have connections with probability, combinatorics, ergodic theory, the Riemann mapping theorem, and Newtonian gravity (in higher dimensions); see the gallery at http://www.math.ucdavis.edu/~romik/home/Allocations.html, but there is lots of room for new creative ideas.
(Talk based on works of the speaker as well as C. Hoffman, A. Holroyd, S. Chatterjee, R. Peled, D. Romik and M. Krikun.)
top of page

Frank Gao (U. Idaho)

A function on R+ is called a (generalized) k-monotone function if the signs of its first k derivatives are constrained. Thus, a non-negative, decreasing, convex function is a 2-monotone function. These shape-constrained functions appear very commonly in nonparametric estimation in statistics via renewal theory and mixing of uniform distributions. In this talk I will present the rate of convergence of the Maximum Likelihood Estimator (MLE) of such a density. I will also discuss a multivariate generalization and the case k =infinity. Small ball probability of some associated Gaussian processes and bracketing entropy of convex hulls are the main tools used.
This is a joint work with Jon Wellner.
top of page

Jim Pitman (Berkeley)

This talk will present some recent progress and open problems about random permutations associated with models for randomly partitioning an interval into a countable collection of sub intervals. One model of particular interest is defined by cutting a unit interval at the times of vertices of the concave majorant of a Brownian motion. The talk will refer to two recent articles: "The distribution of the maximal difference between Brownian bridge and its concave majorant" (with Fadoua Balabdaoui) and "Characterizations of exchangeable partitions and random discrete distributions by deletion properties" (with Alexander Gnedin and Chris Haulk)
top of page

Matt Kahle (Stanford)

The field of topological data analysis has been very active in recent years, with powerful many algorithms developed and interesting applications found. To put this field on firmer mathematical foundations, one would like to have a detailed probabilistic picture to compare with data as a null model. One well-posed math problem, proposed by Persi Diaconis, is as follows. Take n random points in R^d. i.i.d. according to some probability distribution with a bounded measurable density function. Connect pairs of points by an edge if they are close, withing distance r = r(n), then build the Cech or Vietoris-Rips complex. Now what can one say about the homology of these complexes? I will discuss my recent preprint on this which includes results on expectation and variance of the Betti numbers, as well as central limit theorems and concentration of measure results. Since this is a talk in probability seminar, topological prerequisites will not be assumed, and the talk will aim to be self-contained.
top of page

Deanna Needell (Stanford)

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax = b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. In this talk I will discuss these results as well as recent results in the case where the system is corrupted by noise. The results in the presence of noise again prove exponential convergence, this time to a threshold depending on the noise magnitude.
top of page

Oren Louidor (Courant Institute, NYU)

We consider the discrete-time Glauber dynamics for the q-states Potts model on the complete graph with n vertices and analyze its mixing time, namely the time it takes until the state distribution is close enough to the Potts distribution, starting from the worst possible initial state. In the disorder phase \beta < \beta_c(q), we discover a critical inverse temperature 0 < \beta_d(q) < \beta_c(q) above which mixing time is exponential and below which mixing time is asymptotically C(\beta, q) n \log(n) where C(\beta, q) is known explicitly. In the latter case we prove that the chain exhibits a cutoff with a window of order n, namely after an initial C(\beta, q) n \log(n) time the state distribution becomes arbitrarily close to the stationary one in O(n) time. We also analyze the mixing time when the temperature is critical for mixing and more generally when \beta converges to \beta_d(q) with n. In this case the mixing time depends on how fast this convergence is and cutoff appears as long as the rate of convergence is slower then some critical threshold which we identify. In particular in the mixing-critical case we get \Theta(n^{4/3}) mixing time and no cutoff. We also discuss the essential mixing time of the chain and show that it is C(\beta, q) n \log(n) for all \beta < \beta_c(q). More precisely, the set of initial states starting from which mixing time is slower than C(\beta, q) n \log(n) has exponentially small probability under the Potts distribution.
top of page

Alexander E. Holroyd (UBC and Microsoft)

Sorting a list of items is perhaps the most familiar problem of computer science. If one must do this by swapping neighbouring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this. We consider a uniformly random n-item sorting network. Exact simulations and heuristic arguments have led to a wealth of astonishing conjectures about the n->infinity limit.
For instance, the half-time permutation matrix is believed to be circularly symmetric, while the trajectories of items appear to converge to random sine curves; the best known bounds on the permutation matrices and trajectories are much weaker (but still non-trivial). The conjectures fit together into a remarkable geometric picture. I will report on some recent progress on local sub-networks and random sub-networks, both of which shed some light on this picture.
Based on joint works with Omer Angel, Vadim Gorin, Dan Romik and Balint Virag. See top of page

Dima Shlyakhtenko (UCLA)

We discuss applications of free stochastic calculus (a free probability analog of stochastic calculus). These include applications to random matrix theory as well and questions around L^2 cohomology of discrete groups.
top of page