- You are here:
- GT Home
- Home
- News & Events

Series: Stochastics Seminar

Place Poi(m) particles at each site of a d-ary tree of height n. The particle at the root does a simple random walk. When it visits a site, it wakes up all the particles there, which start their own random walks, waking up more particles in turn. What is the cover time for this process, i.e., the time to visit every site? We show that when m is large, the cover time is O(n log(n)) with high probability, and when m is small, the cover time is at least exp(c sqrt(n)) with high probability. Both bounds are sharp by previous results of Jonathan Hermon's. This is the first result proving that the cover time is polynomial or proving that it's nonpolymial, for any value of m. Joint work with Christopher Hoffman and Matthew Junge.

Series: Stochastics Seminar

I will discuss two projects concerning Mallows permutations, with Ander
Holroyd, Tom Hutchcroft and Avi Levy. First, we relate the Mallows
permutation to stable matchings, and percolation on bipartite graphs.
Second, we study the scaling limit of the cycles in the Mallows
permutation, and relate it to diffusions and continuous trees.

Series: Stochastics Seminar

Series: Stochastics Seminar

It has been conjectured that phenomena as diverse as the behavior of large "self-organizing" neural networks, and causality in standard model particle physics, can be explained by suitably rich algebras acting on themselves. In this talk I discuss the asymptotics of large causal tree diagrams that combine freely independent elements of such algebras. The Marchenko-Pastur law and Wigner's semicircle law are shown to emerge as limits of a normalized sum-over-paths of non-negative elements assigned to the edges of causal trees. The results are established in the setting of non-commutative probability. Trees with classically independent positive edge weights (random multiplicative cascades) were originally proposed by Mandelbrot as a model displaying the fractal features of turbulence. The novelty of the present work is the use of non-commutative (free) probability to allow the edge weights to take values in an algebra.

Series: Stochastics Seminar

Series: Stochastics Seminar

Today's era of cloud computing is powered by massive data centers. A data center network enables the exchange of data in the form of packets among the servers within these data centers. Given the size of today's data centers, it is desirable to design low-complexity scheduling algorithms which result in a fixed average packet delay, independent of the size of the data center. We consider the scheduling problem in an input-queued switch, which is a good abstraction for a data center network. In particular, we study the queue length (equivalently, delay) behavior under the so-called MaxWeight scheduling algorithm, which has low computational complexity. Under various traffic patterns, we show that the algorithm achieves optimal scaling of the heavy-traffic scaled queue length with respect to the size of the switch. This settles one version of an open conjecture that has been a central question in the area of stochastic networks. We obtain this result by using a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expected total queue length in the network, in steady-state.

Series: Stochastics Seminar

Series: Stochastics Seminar

Cars are placed with density p on the lattice. The remaining vertices are parking spots that can fit one car. Cars then drive around at random until finding a parking spot. We study the effect of p on the availability of parking spots and observe some intriguing behavior at criticality. Joint work with Michael Damron, Janko Gravner, Hanbeck Lyu, and David Sivakoff. arXiv id: 1710.10529.

Series: Stochastics Seminar

We study an online algorithm for making a well—equidistributed random set of points in an interval, in the spirit of "power of choice" methods. Suppose finitely many distinct points are placed on an interval in any arbitrary configuration. This configuration of points subdivides the circle into a finite number of intervals. At each time step, two points are sampled uniformly from the interval. Each of these points lands within some pair of intervals formed by the previous configuration. Add the point that falls in the larger interval to the existing configuration of points, discard the other, and then repeat this process. We then study this point configuration in the sense of its largest interval, and discuss other "power of choice" type modifications.
Joint work with Pascal Maillard.

Series: Stochastics Seminar

The Sherrington-Kirkpatirck (SK) model is
a mean-field spin glass introduced by theoretical physicists in order
to explain the strange behavior of certain alloys, such as CuMn. Despite
of its seemingly simple formulation, it was conjectured to possess a
number of profound properties. This talk will be focused on the energy
landscapes of the SK model and the mixed p-spin model with both Ising
and spherical configuration spaces. We will present Parisi formule for
their maximal energies followed by descriptions of the energy landscapes
near the maximum energy. Based on joint works with A. Auffinger, M. Handschy, G. Lerman, and A. Sen.