Home |
Research |
Teaching |
Contact |
| Date | Speaker | Title | Abstract |
| 19 Jan. | Chris Haulk (UCB Stat) | A de Finetti-type representation of exchangeable hierarchies |
A hierarchy on a set $S$ is a collection $H$ of subsets of $S$ for which for every pair $A,B$ of elements of $H$, either $A$ contains $B$ or $B$ contains $A$ or the intersection of $A$ and $B$ is empty. Additionally, a hierarchy on $S$ contains $S$ and all singleton subsets of $S$. Hierarchies are also known as laminar families and total partitions. A random hierarchy $H$ on a countable set $S$ is exchangeable if for every finite permutation $\sigma$ of $S$, $H$ is equal in distribution to the hierarchy $\sigma(H)$ derived from $H$ by relabeling the contents of the elements of $H$ by $\sigma$.
I will discuss the following de Finetti-type representation theorem for exchangeable hierarchies on the set of positive integers. Every exchangeable random hierarchy on positive integers has the same distribution as a random hierarchy $H$ associated as follows with a random real tree $T$ equipped with root element $0$ and a random probability distribution $p$ on the Borel subsets of $T$: given $(T,p)$, let $t_1,t_2, \ldots$ be independent and identically distributed according to $p$, and let $H$ comprise all singleton subsets of $\mathbb{N}$, and every subset of the form $\{j: t_j \in F_x\}$ as $x$ ranges over $T$, where $F_x$ is the fringe subtree of $T$ rooted at $x$. This is joint work with my advisor, Jim Pitman. |
| 26 Jan. | Steve Evans (UCB Math/Stat) | Go forth and multiply? | Organisms reproduce in environments that change in both time and space. Even if an individual currently resides in a region that is typically quite favorable, it may be optimal for it to "not put all its eggs in the one basket" and disperse some of its offspring to locations that are usually less favorable to cover the possibility that the effect of poor conditions in one place will be offset by fortuitously good conditions in another. I will describe joint work with Peter Ralph and Sebastian Schreiber (U.C. Davis) and Arnab Sen (Oxford) that combines stochastic differential equations, random dynamical systems, and even a little elementary group representation theory to explore the effects of such dispersal strategies. |
| 2 Feb. | Nathan Ross (UCB Stat) | A probabilistic approach to local limit theorems | We discuss a new method for obtaining a local limit theorem (LLT) from a known distributional limit theorem. The method rests on a simple analytic inequality which can be applied directly after quantifying the "smoothness" of the distribution of interest. These smoothness terms are non-trivial to handle and so we also provide new tools for this purpose. We illustrate our approach by deriving LLTs for the number of isolated vertices and the number of triangles in an Erdos-Renyi random graph. This is joint work with Adrian Roellin. |
| 9 Feb. | Rhonda Righter (UCB IEOR) | The impact of customer flexibility in service systems |
In many service, production, and traffic systems there are multiple
types
of customers requiring different types of "servers," i.e., different
services,
products, or routes. Providing flexible servers that can serve multiple
types
of customers improves performance, but the cost of providing this
flexibility,
e.g. for cross-training, may be very high. On the other hand, often
some of
the customers may be flexible, i.e., they may be willing to change their
type
in order to achieve faster service, and the infrastructure to take
advantage
of this customer flexibility is often relatively inexpensive. Our research
is in part motivated by a call center which provides service in both
English
and Spanish. Callers currently have the option of pressing "1" for English
and "2" for Spanish. Because of the training expense and high turnover of
agents, the company policy is to train agents to only handle calls in one
language. The company would like to know the benefit of adding a "Press 3"
option for bilingual customers, and how this depends on the proportion of
customers who are bilingual.
We model our system as a set of alternative multi-server queues, and with a mixture of dedicated (to a single queue) and flexible customers, and exponential services. We extend known results showing that JSQ - Join the Shortest Queue - is the optimal policy for flexible customers. For most of these extensions, the optimality is in a very strong sense: JSQ minimizes the queue length vector process in the weak majorization sense. This gives us monotonicity: mean steady-state waiting time is decreasing in the proportion of flexible customers, p. We then consider convexity, that the marginal improvement in performance is decreasing as more customers become flexible. We give a model where we can show a strong version of convexity, in a sample-path sense, but in general, convexity will not hold in this strong sense. We give conditions for weaker notions of convexity to hold. This is joint work with Osman Akgun and Ron Wolff. |
| 16 Feb. | Fraydoun Rezakhanlou (UCB Math) | Instantaneous Gelation | Marcus-Lushnikov Process is a simple mean field model of coagulating particles that converges to the homogeneous Smoluchowski equation in the large mass limit. If the coagulation rates grow sufficiently fast as the size of particles get large, giant particles emerge in finite time. This is known as gelation and such particles are known as gels. Gelation comes in different flavors; simple, instantaneous and complete. In the case of an instantaneous gelation, a giant particle is formed in a very short time. If all particles coagulate to form a single particle in a time interval that stays bounded as total mass gets large, then we have a complete gelation. In this talk, I discuss what conditions leads to instantaneous gelation and what mechanism is responsible for it. |
| 23 Feb. | Mohsen Bayati (Stanford) | Analysis of approximate message passing and the risk of LASSO |
Recently, Donoho, Maleki and Montanari introduced approximate message
passing (AMP)
as an extremely effective algorithm for reconstructing high dimensional
sparse signals
from a small number of observations. They also showed (through extensive
numerical experiments)
that dynamics of AMP is accurately tracked by a simple one-dimensional
iteration termed
"state evolution". In this talk we prove that state evolution holds
asymptotically for i.i.d.
Gaussian matrices. Using our analysis, we derive formulas for generic
characteristics of the minimizer
of a family of random convex functions. In particular, we prove rigorous
expressions for the risk of LASSO.
This is joint work with Andrea Montanari and Jose Bento. |
| 2 Mar. | Elchanan Mossel (UCB Stat/CS) | Quantitative social choice | I will survey recent results which give quantitative version of theorems in economics regarding social choice functions (i.e. how to vote). The focus of the talk will be a quantitative proof of Arrow's Impossibility Theorem which is based on new combinatorial arguments coupled with uses of inverse hyper-contraction (an exotic concept in functional analysis) and non-linear invariance principles (a recent development in probability theory). |
| 9 Mar. | Peter Ralph (UCD) | Advancing waves and point processes in the geographic process of adaptation | As selective pressures on a species change and new mutations arise that allow the species to adapt, if the rate of migration across the species range is slow enough, various spatial patterns in the organisms' genomes will be left behind. One such pattern is the patchwork formed by mutations of different origin, which is related to a simple, classical Poisson process model of crystalization going back to Kolmogorov. Another is the phenomenon of "allele surfing", which occurs when lucky individuals leave behind many offspring as the adaptation spreads. In the context of these simple models, I will review the connection of traveling waves to branching random walk, which for "surfing" will require coalescence as well. |
| 16 Mar. | Jingchen Liu (Columbia) | Some Asymptotic Results and Computational Methods of Gaussian Random Fields | Gaussian processes and multivariate Gaussian random vectors constitute a cornerstone of probability models in many disciplines. In this talk, we focus on the extreme behavior of Gaussian processes and their applications. In particular, we consider the tails of random variables that can be written as convex functionals of a Gaussian process including suprema and integrals of convex functions. We present asymptotic approximations of the tail probabilities and the density functions of such random variables and develop efficient Monte Carlo algorithms to compute them. The emphasis of this talk is the usage of change-of-measure-based techniques in the analysis of extreme behavior of random fields. |
| 23 Mar. | Spring break - no seminar. | ||
| 30 Mar. | No seminar - see Neyman Seminar. | ||
| 6 Apr. | Sebastien Roch (UCLA) | Phylogeny estimation beyond the classical model of sequence evolution | Much progress has been made in the design and analysis of efficient algorithms for reconstructing the tree of life from present-day molecular sequences. Most rigorous results however rely on biological assumptions which have been questioned in the phylogenetic literature. In this talk, I will discuss recent results on the probabilistic analysis of more realistic settings, including mutation-rate variations and insertion-deletion events. |
| 13 Apr. | Larry Goldstein (USC) | Applications of Bounded Size Bias Couplings for Concentration of Measure | Abstract here (PDF). |
| 20 Apr. | Peter Glynn (Stanford) | Queues with Long-range Dependent Input | Long-range dependence has been statistically identified in internet traffic traces, and various probabilistic explanations for its appearance have been given. In this talk, we will survey what is known about queues that are fed by long-range dependent sources (with a principal focus on fractional Brownian motion as a stylized model of such traffic), and discuss several recent results. |
| 27 Apr. | Jian Ding (UCB Stat) | Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees |
I will quickly review the joint work with Lee and Peres (2010), which
shows that the cover time for any graph is equivalent up to a universal
constant, to the product of the number of edges and the square of the
supremum of the Gaussian free field on that graph.
I will then report a recent progress on the asymptotics of cover times: on bounded degree graphs and general trees the cover time of the simple random walk is asymptotically equal to the product of the number of edges and the square of the supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. Previously, this was only proved for regular trees and the 2D lattice. Furthermore, for general trees, we derive exponential concentration for the cover time, which implies that the standard deviation of the cover time is bounded by the geometric mean of the cover time and the maximal hitting time. |