Probability and Mathematical Physics Seminar

Columbia/Courant joint Probability seminar

Speaker: Christopher Hofman, Gaultier Lambert and Jonathan Niles-Weed, University of Washington, University of Zurich, and NYU

Location: Warren Weaver Hall 512

Date: Friday, November 8, 2019, 9:30 a.m.


9:30–10:30am  Christopher Hoffman (University of Washington)
The shape of a random pattern-avoiding permutation

A permutation that avoids the pattern 4321 has a longest decreasing sequence of length 3. We fix n, choose \sigma a 4321-avoiding permutation uniformly at random and plot the points of the form (i/n,\sigma(i)/n) for 1 \leq i \leq n. Looking at this plot it is clear that the indices 1 through n can be partitioned into three sets. By linear interpolation from these three sets we can generate three functions. We show that the scaling limit of this measure on triples of functions is given by the eigenvalues of a ensemble of random matrices. We also discuss the scaling limits of other patterns.

10:30–11am Coffee break  

11am–12pm Gaultier Lambert (University of Zurich)
Multivariate normal approximation for traces of random unitary matrices

Let us consider a random matrix U of size n distributed according to the Haar measure on the unitary group. It is well-known that for any k≥1, Tr[U^k] converges as n tends to infinity to a Gaussian random variable and that, surprisingly, the speed of convergence is super exponential. In this talk, we revisit this problem and present non asymptotic bounds for the total variation distance between Tr[U^k] and a Gaussian. We will also consider the multivariate problem and explain how this affect the rate of convergence. We expect that our bounds are almost optimal. This is joint work with Kurt Johansson (KTH).

12–1pm Jonathan Niles-Weed (New York University)
Estimation of Wasserstein distances in the Spiked Transport Model

We propose a new statistical model, generalizing the spiked covariance model, which formalizes the assumption that two probability distributions differ only on a low-dimensional subspace. We study various probabilistic and statistical features of this model, including the estimation of the Wasserstein distance, which we show can be accomplished by an estimator which avoids the "curse of dimensionality" typically present in high-dimensional problems involving the Wasserstein distance. However, this estimator does not seem possible to compute in polynomial time, and we give evidence that any computationally efficient estimator is bound to suffer from the curse of dimensionality. Our results therefore suggest the existence of a computational-statistical gap. Joint work with Philippe Rigollet.