Sasha Stolyar (Bell Labs)

We study a model which accommodates a wide range of seemingly very different resource allocation problems in communication networks. Some examples: utility based congestion control of complex time-varying (wireless) networks, minimizing average power consumption in wireless networks, scheduling in wireless systems subject to power consumption and/or traffic rate constraints.

The model is a controlled queueing network, where controls have dual effect. In addition to determining exogenous customer arrival rates, service rates at the nodes, and (possibly random) routing of customers among the nodes, each control decision produces a certain vector of "commodities." The set of available control choices depends on the underlying random network mode. Network "utility" is a concave function of the vector of long-term average rates at which commodities are produced. The goal is maximize utility while keeping network queues stable. We introduce a very parsimonious dynamic control policy, called Greedy Primal-Dual algorithm, and prove its asymptotic optimality. Although the model is formulated in terms of a queueing network, the algorithm can be viewed as a dynamic mechanism for solving rather general convex optimization problems.
top of page

Joe Blitzstein (Stanford)

Random graphs with a given degree sequence are a useful model capturing several features absent in the classical model, such as dependent edges and non-binomial degrees. We use a characterization due to Erdos and Gallai to develop a sequential algorithm for generating a random labeled graph with a given degree sequence. The algorithm is easy to implement and use with sequential importance sampling. Applications such as studying a real-world food web and estimating the number of graphs with a given degree sequence are discussed. Joint work with Persi Diaconis.
top of page

Milena Mihail (Georgia Tech)

The issue of performance scalability is of fundamental importance in complex communications networks. How does congestion scale on the Internet? At what rate do crawlers discover new web pages? Spectral graph theory is a powerful mathematical tool that helps characterize the performance of many algorithms when run on a particular graph. We use spectral graph theory to answer the above questions in several families of random graphs that model the Internet and the WWW.
top of page

Elizabeth Meckes (Stanford)

A theme in studying random matrices from the classical groups is that Haar-distributed matrices are close to Gaussian matrices in many ways; one way is that linear functions of random orthogonal matrices are asymptotically normally distributed (as the dimension approaches infinity). I will discuss an infinitesimal version of Stein's method, introduced by Stein in 1995, which can be used to obtain a rate of convergence in this and related theorems.
top of page

Sharad Goel (Stanford)

Given 52 playing cards, how many shuffles does it take to approximately randomize the deck? More generally, how long does it take a finite Markov chain to get close to its stationary distribution? In this talk, I'll introduce the spectral profile as a tool for proving upper and lower bounds on convergence rates. This approach extends the commonly used spectral gap method, and allows us to recover and refine previous conductance-based estimates of mixing time. I will illustrate how the spectral profile technique is applied in several models, including groups with moderate growth, the fractal-like Viscek graphs, and the torus. This work is joint with Ravi Montenegro and Prasad Tetali.
top of page

Peter Mörters (Univ. of Bath)

We discuss the Cauchy problem for the spatially discrete heat equation in a random i.i.d. potential with localised initial datum. The emphasis is on the question, which features of the potential distribution influence the qualitative behaviour of the solution of the problem. The talk is based on joint work with Wolfgang Koenig (Leipzig) and Remco van der Hofstad (Eindhoven).
top of page

Paul Dupuis (Brown)

Importance sampling is a variance reduction technique used to improve the efficiency of Monte Carlo approximation of probabilities and expected values. Under certain law of large numbers scalings, the optimal performance of importance sampling schemes can be characterized by a differential game, or equivalently, in terms of the solution to the related Isaacs equation (a nonlinear PDE).

In this talk, we will describe how subsolutions to the Isaacs equation can be used very effectively in the design and analysis of asymptotically optimal importance sampling schemes. The main ideas are first described for a multi-dimensional version of the level crossing problem studied by Siegmund. We then discuss other classes of problems to which the approach has been applied, including stochastic networks and sums of heavy-tailed random variables.
top of page

Amber Puha (CSU San Marcos)

A modified contact process on the homogeneous tree is considered. The modification is to the death rate: an occupied site becomes vacant at rate one if the number of occupied neighbors is at most one. This modification leads to a growth model that is reversible, off the empty set, provided that the initial set of occupied sites is connected. Reversibility admits tools for studying the survival properties of the system not available in a nonreversible situation. The main result is that there is exactly one phase transition and the value of the birth parameter at which the phase transition occurs is explicitly computed. In this talk, we demonstrate how reversibility is exploited to identify the exact location of the phase transition and discuss some directions for further investigation.
top of page

Ben Hough (UC Berkeley)

We consider a random analytic function f whose zero set is translationally invariant in the plane. This zero set is amazingly "lattice-like". A recent work of Sodin and Tsirelson shows that it can be matched to a perturbed lattice with Gaussian tails. Moreover, the "hole probability" that a disk of radius R contains no zeros of f decays exponentially in the square of the area of the disk. This asymptotic behavior is also observed in the perturbed lattice model in which lattice points are perturbed by independent complex normal random variables. Allowing the coefficients of f to evolve as independent Ornstein-Uhlenbeck processes, the zero set evolves as a time homogenous Markov process in the plane. We show that the probability of observing a hole of radius R for time T in the random zero model is exponentially worse than the corresponding probability for the perturbed lattice model in which lattice points evolve as independent Ornstein-Uhlenbeck processes.
top of page

Jonathan Taylor (Stanford)

We discuss the generic behaviour of the critical points / values of smooth Gaussian random fields on smooth manifolds $f:M \rightarrow \mathbb{R}$, which we think of as point processes on the parameter space of the field (the critical points) with real-valued marks (the critical values).

For parameter spaces of a fixed dimension, these marked point processes can be combined with some tools from differential topology to derive an accurate approximation to the supremum distribution $$\mathbb{P}\left\{\sup_{x \in M} f(x) \geq u \right\}$$ based on the geometry of the excursion sets $$ \left \{x \in M: f(x) \geq u \right\},$$ specifically the expected Euler characteristic of the excursion sets.

In general, the accuracy of the above expression is poorly understood if we allow the dimension of $M$ to grow. In this work, we investigate some aspects of the accuracy in the high dimensional setting, restricting attention to isotropic process on $[0,1]^n$ with $n$ growing. In this situation, the ``spectrum'' of critical values behave in some sense like the eigenvalues of a large GOE (Gaussian Orthogonal Ensemble) matrix at the bulk and the edge.

We identify two separate regimes for the behaviour of the mean spectral measure of the critical values of smooth isotropic Gaussian fields in high dimensions. Understanding the limiting behaviour of the mean spectral measure depends on a characterization of the covariance functions of isotropic processes in high dimensions.
top of page

Richard Kenyon (UBC)

This is joint work with David Wilson. Given a planar graph with selected vertices on its outer face (which we refer to as terminals), an essential spanning forest is a spanning forest in which every component contains at least one of the terminals. We show how to compute, for a randomly chosen essential spanning forest, the probability of any given topology of connections between the terminals. These probabilities are rational functions of the pairwise resistances between the terminals, and, when appropriately normalized, actually polynomials in these resistances.
top of page

Persi Diaconis (Stanford)

Szego's Theorem gives the asymptotic behavior of the eigenvalues of large toeplitz matrices. A generalization due to Kac-Murdock-Szego gives similar results where the diagonals are allowed to vary. There is a beautiful proof due to Hale Trotter. All will be explained in this expository talk.
top of page

Paul Jung (Cornell)

(Joint with M Aizenman.) Consider the contact process on any transitive graph with bounded degree starting from one particle. Using a variational derivative form of Russo's formula, we show that the expected number of particles of the process decays exponentially in time for all infection rates \lambda that are below the lower critical value \lambda_s. Along the way we obtain certain critical exponent bounds. Some of these results have previously been proven on Z^d in a well-known paper of Bezuidenhout and Grimmett.
top of page

Amin Saberi (Stanford)

It has been observed that many networks, notably the Internet, have scale-free structures in the sense that the degree distributions of these networks have power-law tails. Motivated by these observations, there has been a great deal of study, both non- rigorous and rigorous, of the detailed structural properties of so- called preferential attachment models and other models with power-law degree distributions. However, thus far, there has been much less work on the impact of these structures on processes occurring on these networks.

In this talk, I will discuss processes which model the spread of viral infections on scale-free structures, and show how these processes differ markedly from epidemics on more conventional structures. In particular, I will analyze the contact process on random graphs generated according to the preferential attachment scheme and show that any virus with a positive rate of spread from a node to its neighbors has a non-vanishing chance of becoming epidemic.

Since there are also observations which indicate that the network of human sexual contacts follows a power-law degree distribution, this analysis is probably relevant both in the context of the spread of computer viruses on the Internet, and the spread of sexually transmitted diseases (STD).

Joint work with N. Berger, C. Borgs, and J. Chayes
top of page

Gabor Pete (Berkeley)

Abstract: We consider a dependent bond percolation model on Z^2, introduced by Balint Toth, in which every edge is present with probability 1/2, and each vertex has exactly two incident edges, perpendicular to each other. We prove that all components are finite cycles almost surely, but the expected diameter of the cycle containing the origin is infinite. Moreover, we derive the following critical exponents: the tail probability Pr(diameter of the cycle of the origin > n) \approx n^{-\gamma}, and the expectation E(length of a cycle conditioned on having diameter n) \approx n^\delta. We show that \gamma=(5-\sqrt{17})/4=0.219... and \delta=(\sqrt{17}+1)/4=1.28... The relation \gamma+\delta=3/2 corresponds to the fact that the scaling limit of the natural height function in the model is the Additive Brownian Motion, whose level sets have Hausdorff dimension 3/2. The value of \delta comes from the solution of a singular sixth order ODE.
top of page

Mauro Maggioni (Yale)

Abstract: We present novel ideas and constructions that allow the multiscale organization of graphs and data sets. These constructions are based on ideas related to diffusions on data set, and use different time and space scales associated with diffusion to infer multiscale hierarchical organizations of a graph. They allow to organize complex data sets and to generalize important signal processing tools to graphs. In order to emphasize the wide applicability of these techniques we will touch upon their applications to the organization of document corpora, dimensionality reduction for dynamical systems, nonlinear image denoising, protein functionality prediction, reinforcement and semi-supervised learning.
top of page

Toufic Suidan (UC Santa Cruz)

Abstract: Many combinatorial and probabilistic models connected to random matrix theory can be analyzed by studying various non-intersecting random walks with very specific increment distributions. This talk will focus on removing the specific nature of the increment distributions in certain scaling regimes. The Tracy-Widom and sine kernel distributions of random matrix theory are shown to be limiting distributions for natural quantities associated to the non-intersecting random walks in the above mentioned scaling regimes. The resulting theorems can be viewed as central limit theorems for non-intersecting random walks with general increments.Strong approximation and Riemann-Hilbert techniques are used in the proofs. This is joint work with Jinho Baik.
top of page

Jean-Dominique Deuschel (Technische Universitat Berlin)

Abstract: This is joint work with Holger Koesters. We consider a class of random walks in a random environment on Z^d admitting a finite cycle representation, that is the corresponding jump rates are labeled by finite oriented cycles with ergodic weights, eg. [K], [M]. The reversible random conductances model with trivial two points cycles is a particular case, see [S] thus our model extends to the non reversible situation. Assuming uniform irreducibility, we prove a quenched invariant principle for the rescaled process. The annealed CLT result has been proved recently in the special case of two-fold walks by Komorovski and Olla in [K]. We adapt the quenched proof of Sidoravicius and Sznitman, [S], to the non reversible case using corrector, the sector condition and the heat kernels upper bounds for centered random walks by Mathieu, [M].

[K] Komorowski, T; Olla, S. A note on the central limit theorem for two-fold stochastic random walks
in a random environment. Preprint (2005).

[M] Mathieu, P. Carne-Varopulos bounds for centered random walks. Ann of Prob (2006).

[S] Sidoravicius, V ; Sznitman. A Quenched invariance principles for walks on clusters
of percolation or among random conductances. Probab. Theory Related Fields, 129, 219-244.
top of page

Manjunath Krishnapur (Berkeley)

Abstract: Determinantal (Fermionic) processes are a kind of point process that arise a lot in Random Matrix Theory and Combinatorics. Most of these processes studied have been in one dimension. The only interesting examples known in two dimensions are: (a) Eigenvalues of a matrix with i.i.d Complex Gaussian entries (Ginibre,1965); (b) Zeroes of an analytic function with i.i.d Complex Gaussian coefficients (Peres and Virag, 2003). In this lecture we exhibit a one parameter families of determinantal processes, one each on the Complex plane, the Sphere and the Unit disk (Hyperbolic plane) that are invariant in distribution under the action of the corresponding group of isometries (these correspond to the classical Bargmann-Fock Hilbert spaces of analytic functions). We ask for a probabilistic origin for these processes and show that: (1) The Spherical determinantal processes arise as the eigenvalues of a new random matrix ensemble; (2) Give partial evidence that the Hyperbolic determinantal processes arise as singular points of a random matrix valued analytic function.
top of page

Kevin Ross (UNC-Chapel Hill)

Singular control is an important and challenging class of stochastic control problems. Such problems can rarely be solved explicitly and thus numerical approximation schemes are necessary. In this work we take a probabilistic approach and, using the theory of weak convergence of stochastic processes, develop convergent numerical schemes that are based on approximating the underlying state process by a suitable controlled Markov chain.

In the first part of the talk we consider a problem of optimal consumption and portfolio selection with transaction costs. One challenging feature of this problem is that the directions of singular control are tangential to the boundary of the state space. This feature, along with degeneracy in the dynamics and unboundedness of the state and control spaces, makes the convergence analysis quite delicate.

Numerical schemes for singular control problems can be computationally intensive, and thus it is of great interest to develop less expensive schemes that take advantage of specific features of the underlying dynamics. Motivated by this, we consider a two-dimensional singular control problem that arises from queueing networks. Using the special form of the dynamics, we prove rigorously an equivalence between this problem and an optimal stopping problem, and we exploit this connection in developing simple computational schemes for the singular control problem.

This is a joint work with Amarjit Budhiraja.
top of page

Yuval Peres (Berkeley)

The infinity Laplacian (informally, the "second derivative in the gradient direction") is a simple yet mysterious operator with many applications, in particular to optimal Lipschitz extensions. Classical analysis of this operator is hampered by nonsmoothness of solutions. "Tug of war" is a two player random turn game played as follows: Given disjoint target sets T_1 and T_2 in the plane, and a token at x, toss a fair coin; the player who wins the coin toss moves the particle up to distance r in the direction of his/her choice. This is repeated until the token reaches a target set T_i; player i is then declared the winner. Write u_r(x) for the probability that player 1 wins when both players play optimally. We show that as r tends to 0, the functions u_r(x) converge to the infinity harmonic function with boundary conditions 1 on T_1 and 0 on T_2. Our analysis of tug of war leads yields new estimates, and significant generalizations of several classical results about infinity Laplacians. I will also describe our original motivation for studying random-turn games: A variant of the game of Hex with a conformally-invariant limit.

(Talk based on joint work with Oded Schramm, Scott Sheffield and David Wilson.)
top of page

Cyril Roberto

We expose rigorous results for the density and size dependence of relaxation times (the inverse of the spectral gap) for kinetically constrained spin models, both cooperative and non cooperative ones. These have been proposed as models of strong (FA1f, East) or fragile (FAf>1) glasses and more generally of systems undergoing jamming transitions (Knight models).

After a brief introduction of the physical issues, we explain our proof in detail on the east model, and then how it extends to models in higher dimention as the north-east or FA2f.

It follows that in the infinite volume limit the relaxation of the spin-spin auto-correlation function is exponential. This excludes the stretched exponential relaxation which was derived by numerical simulations.
top of page

Ashkan Nikeghbali

In this talk, we consider the special class of positive local submartingales (X_t) of the form: X_t = N_t + A_t where the measure (dA_t) is carried by the set {t: X_t = 0}. We show that many examples of stochastic processes studied in the literature are in this class and propose a unified approach based on martingale techniques to study them. In particular, we establish some martingale characterizations for these processes and compute explicitly some distributions involving the pair (X_t, A_t). We also associate with X a solution to the Skorokhod's stopping problem for probability measures on the positive half-line.
top of page

Sourav Chatterjee (Berkeley)

Although it is difficult to believe that there may be something new to say about normal approximation in the twenty-first century, the fact still remains that there exists no simple and certain method of proving central limit theorems. All techniques known to statisticians and probabilists require extensive information about the nature of the system, and some good luck. On the other hand, variance bounds (and hence weak laws) are routine issues which daunt no one. The purpose of this talk is to introduce a new method by which it is possible to reduce every normal approximation problem to a variance bounding exercise. Applications, including one involving a nontrivial statistical problem (due to Peter Bickel), will be described.
top of page

David Aldous (Berkeley)

After general remarks on the topic of flows through random networks, I will outline a proof of the following result. Consider routing traffic on the N x N torus, simultaneously between all source-destination pairs, to minimize the cost \sum_e c(e)f^2(e), where f(e) is the volume of flow across edge e and the c(e) form an i.i.d. random environment. One can prove existence of a rescaled N to infinity limit constant for minimum cost, by comparison with an appropriate analogous problem about minimum-cost flows across a M x M subsquare of the lattice.
top of page

Prasad Tetali (Georgia Tech)

Motivated by a common subproblem occurring in several factoring algorithms, in 1994 C. Pomerance introduced the so-called square dependence problem: select integers sequentially at random from the interval [1,x], for some large x, and stop once the product of a subsequence of the chosen integers is a square; the problem is to determine (as a function of x) the stopping time of this process. Pomerance and Schroeppel estimated the stopping time to lie in an interval, [y, y^{1+o(1)}], for an appropriate y=y(x). We tighten this interval significantly to [y, c y], for a small positive constant c.

This is joint work with Andrew Granville and Ernie Croot.
top of page

Steve Evans (Berkeley)

A fundamental theorem of Paul Levy characterises standard Brownian motion as the unique continuous martingale with the identity function as its quadratic variation process. It turns out that on any closed subset of the real line that is unbounded above and below there is a unique process that is a martingale, has the identity function as its quadratic variation process, and is ``continuous'' in the sense that its sample paths don't skip over points. This process is automatically a Feller-Dynkin Markov process and its generator is a natural generalisation of the operator f --> 1/2 f''.

An interesting special case occurs when the state space is the self-similar set {\pm q^k : k \in Z} \cup {0} for some q>1. The analysis of this process leads to continued fractions that appear in Ramanujan's ``lost'' notebook and can be evaluated in terms of q-analogues of classical hypergeometric functions. Moreover, the distributions of various features of the process involve q-analogues of classical distributions such as the Poisson distribution that have appeared elsewhere in the literature.

This is joint work with Shankar Bhamidi, Ron Peled and Peter Ralph.
top of page

Amir Dembo (Stanford)

We show that the properly scaled spectral measures of symmetric Hankel and Toeplitz matrices of size N by N generated by i.i.d. random variables of zero mean and unit variance converge weakly in N to universal, non-random, symmetric distributions of unbounded support, whose moments are given by the sum of volumes of solids related to Eulerian numbers. The universal limiting spectral distribution for large symmetric Markov matrices generated by off-diagonal i.i.d. random variables of zero mean and unit variance, is more explicit, having a bounded smooth density given by the free convolution of the semi-circle and normal densities.

Time permitting, I will also explain the formula for the large deviations rate function for the number of open path of length k in random graphs on N>>1 vertices with each edge chosen independently with probability 0<p<1, and more generally, for the same functionals applied to any sequence of matrices with bounded i.i.d. entries. Using the same rationale, we can guess the rate functions for the number of simple cycles of length k>2 in large random graphs, the derivation of which is yet an open problem.

This talk is based on joint works with Erwin Bolthausen, Wlodek Bryc, Francis Comets and Tiefeng Jiang.
top of page