| A method of random integral representations in probability theory
(ps/pdf)
|
 |
|
Zbigniew J. Jurek (Wroclaw)
In probability and statistics, distributions are often described by Fourier or Laplace
transforms. In this talk we present a method that gives probability measures as laws of
some random integrals. These are integrals with respect to Levy processes.
We will illustrate this approach on:
(1) Self-decomposable (Levy class L) distributions;
(2) Free infinitely divisible measures;
(3) s-self-decomposable measures.
Some relevant papers and preprints are available at the web site
http://www.math.uni.wroc.pl/~zjjurek.
top of page
|
| Gibbs
sampling, exponential and orthogonal
polynomials (ps/pdf)
|
|
|
Persi
Diaconis (Stanford)
The widely used Gibbs Sampler (heat bath or Glauber dynamics)
seems hard to analyze. In joint work with K. Kahane and L. Saloff-Coste, we have found 18
classes of examples where sharp analysis is possible. This involves the six exponential
families with "quadratic variance functions" and their orthogonal polynomials. The results
show that seemingly close problems can involve very different mixing times.
top of
page
|
| A simple solution to the k-core problem
(ps/pdf)
|
|
|
Malwina
Luczak (LSE)
We study the k-core
of a random (multi)graph on n vertices with a
given degree sequence. We let n go to
infinity. Then, under some regularity
conditions on the degree sequences, we give
conditions on the asymptotic shape of the
degree sequence that imply that with high
probability the k-core is empty, and other
conditions that imply that with high
probability the k-core is non-empty and the
sizes of its vertex and edge sets satisfy a
law of large numbers; under suitable
assumptions these are the only two
possibilities. In particular, we recover the
result by Pittel, Spencer and Wormald (1996)
on the existence and size of a k-core in
G(n,p) and G(n,m), see also Molloy (2005) and
Cooper (2004). Our method is based on the
properties of empirical distributions of
independent random variables, and leads to
simple proofs. This is joint work with Svante
Janson.
top
of page
|
| Notions of correlation decay in random k-satisfiability
(ps/pdf)
|
|
|
Andrea Montanari (ENS Paris)
Let F be a random k-satisfiability formula and consider
the uniform measure over satisfying assignments (assuming
there exists at least one). We investigate the question
of how strongly different variables are correlated
by introducing three different notions of correlation
decay.
To each one of these notions, one can associate a threshold
clause density such that it holds below that density.
We estimate the threshold for two of them, and provide
an heuristic argument that locates the third one.
top
of page
|
| The rotor-router model and Diaconis-Fulton addition
(ps/pdf)
|
|
|
Yuval Peres (UC Berkeley and Microsoft Research)
Given two sets A and B in the lattice, the Diaconis-Fulton sum is a
random set obtained by putting one particle in every point of the
symmetric difference, and two particles in every point of the
intersection, of A and B. Each "extra" particle performs random walk
until it reach an unoccupied site, where it settles. The law of the
resulting random occupied set A+B does not depend on the order of the
walks.
We find the (deterministic) scaling limit of the sums A+B when A and B
consist of the lattice points in some overlapping planar domains. The
limit is described by focusing on the "odometer" of the process, which
solves a free boundary obstacle problem for the Laplacian.
The same scaling limit is obtained when the random walks are replaced
by deterministic rotor walks, as proposed by Jim Propp. In
particular, when a singleton at the origin is added to itself n times
Internal Diffusion-limited aggregation (IDLA) arises; Lawler, Bramson
and Griffeath (1992) proved the limit shape for IDLA is a disk and we
prove the analogous result for rotor-router aggregation.
(Joint work with Lionel Levine.)
top
of page
|
| Universality for level statistics of disordered Hamiltonians
(ps/pdf)
|
|
|
Gerard Ben Arous (NYU and EPF-Lausanne)
S. Mertens and his student H. Bauke recently observed that the statistics
of energy levels for very general random hamiltonians, when observed
microcanonically---i.e, in a small window in the bulk---are Poissonian, and
thus universal; they are insensitive to the specific model. They are the
same as those of the simplest model, the Random Energy Model or REM, hence
sometimes the name of this observation: the REM conjecture.
This conjecture seemed valid for very general hamiltonians of statistical
mechanics, as spin-glasses (mean field or not, i.e.
Sherrington-Kirkpatrick or Edwards-Anderson models). In fact it seemed
also valid (and that was the initial motivation) for various combinatorial
optimization problems (like number partitioning). During the last two
years, two groups of mathematicians have established this conjecture in
different contexts (J. Chayes-C. Borgs-Pittel at Microsoft for the number partitioning
question, and A. Bovier-I. Kurkova in Berlin for general
spin-glass questions).
I will report on recent progress on these questions
and on a new kind of universality, probably more suited to the needs of
non-equilibrium questions. The idea is that the level statistics should
also be universal, i.e. those of the REM, when observed on a random subset
of the configuration space (the hypercube for mean-field models), rather
than on a microcanonical window. Said differently, one simply should find
universal statistics fo the energy levels of random hamiltonians if one
resamples a sparse subset of the energy levels. This approach would feel
the extreme value distribution on the random subset, typically showing as
a consequence that the Gibbs measure restricted to a random subset of
configuration space is the same as for the REM, i.e. a Poisson-Dirichlet
process. This universality result has now been established with Alexey
Kuptsov (NYU) and V. Gayrard (Marseilles) for sparse random subsets, in
great generality.
The next question reads as follows: how dense should a
random subset of configuration space be for this universality to break
down? A very natural conjecture was made after discussions with physicists
(Mezard and Parisi). I will give very recent results
establishing this breakdown of universality and discuss the meaning of
this for dynamical questions.
top
of page
|
| Topology of random clique complexes and phase transitions for homology
(ps/pdf)
|
|
|
Matthew Kahle (Washington)
The Erdos-Renyi random graph G(n,p) is the probability space of
all graphs on the vertex set [n]={1,2,...n}, with each edge inserted
independently with probability p. Usually p is defined to be a function of n, and one
asks whether a graph in G(n,p) is likely to have some (monotone) property
as n goes to infinity. In their seminal 1959 paper, Erdos and Renyi showed
that if p << log(n)/n then G(n,p) is almost always disconnected, but if p
>> log(n)/n, then it is almost always connected.
We view this as a topological statement and seek higher-dimensional
analogues of the Erdos-Renyi Theorem. This requires notions of both higher-
dimensional random spaces (for the purposes of this talk, clique
complexes) and higher dimensional connectivity (homology). When we study
the higher homology groups of the clique complex of G(n,p), we find that
each fixed group passes through not one, but two distinct phase
transitions. Although the topological properties we're studying don't
correspond to monotone graph properties, we are still able to establish
generalizations and analogues of the Erdos-Renyi Theorem. This talk will
strive to be self-contained, with little or no topology prerequisites.
top
of page
|
| Finite size scaling for the core of large random hyper-graphs
(ps/pdf)
|
|
|
Amir Dembo (Stanford)
The (two) core of an hyper-graph is the maximal collection of
hyper-edges such that no vertex appears in only one of them.
It is of importance in tasks such as efficiently solving
a large linear system over GF(2), or iterative decoding
of low-density parity-check codes used over the binary
erasure channel. Similar structures emerge in a variety
of NP-hard combinatorial optimization and decision problems,
from vertex cover to satisfiability.
For a uniformly chosen random hyper-graph of M=rN vertices
and N hyper-edges, each consisting of the same fixed number
L > 2 of vertices, the size of the core exhibits for large N
a first order phase transition, changing from o(N) for r>b to
a positive fraction of N for r < b, with a transition window
size of order 1/sqrt(N) around b.
Analyzing the corresponding `leaf removal' algorithm, we
determine the associated finite size scaling behavior.
In particular, if r is inside the scaling window, the
probability of a core whose size is a positive fraction of N
has a limit strictly between 0 and 1, and a leading correction
of order N^{-1/6}, explicitly characterized in terms of the
distribution of a Brownian motion with quadratic drift,
from which it inherits the scaling with N.
This talk is based on a joint work with Andrea Montanari.
top
of page
|
| Several mathematical issues in information-based credit risk analysis
(ps/pdf)
|
|
|
Xin Guo (Berkeley)
Credit risk is one of the most active research topics in
mathematical finance. In this talk, we shall review the three
major approaches to study credit risk: reduced-form, structural,
and information-based approaches.
In particular,
we shall discuss a number of mathematical issues in the current
information-based approach. We shall show how these issues are
resolved by revisiting the classical filtration expansion results
established by Jeulin and Yor in the 1980s. We shall also discuss
some new results regarding the impact of filtration expansions on
optimal stopping and stochastic control problems.
This talk is based on several recent papers with A. Chakrabarty,
R. Jarrow, C. Menn, and Y. Zeng of Cornell.
top
of page
|
| Broadcasting on trees: on the tightness of a bound of Kesten and Stigum
(ps/pdf)
|
|
|
Sebastien Roch (Berkeley)
I will consider the problem of reconstructing the root value of a
broadcasting process on a tree, where each edge is a noisy channel. A
well-known result of [Kesten, Stigum'66] guarantees the feasibility of
such reconstruction under a condition on the second eigenvalue of the
channel. In recent work with Borgs, Chayes, and Mossel, we showed that
this condition is tight for binary channels, as long as the channel is not
too far from symmetric. This is the first exact result of this kind since
the solution of the symmetric case by [Bleher, Ruiz, Zagrebnov'95]. I will
sketch the proof and discuss applications in phylogenetic reconstruction
and mixing times of Glauber dynamics on trees.
top
of page
|
| Fragmentation and coalescence of conditioned Galton-Watson forests
(ps/pdf)
|
|
|
Jomy Alappattu (Berkeley)
Given a Galton-Watson forest of trees conditioned to have a fixed total number of vertices, we examine
the conditions under which deleting an edge uniformly at random from the forest yields another forest with a conditioned Galton-Watson distribution
based on the same offspring distribution as the original forest.
This question is related to recent work on fragmentation of partitions of the set [n]:= {1,2,...,n}. After reviewing the
known results about partitions, we show how to use generating functions to pass from partitions to forests, and determine the offspring distributions for which the forest fragmentation model works. We will also discuss certain interesting combinatorial interpretations of some of the offspring distributions. Finally, we describe how to go in the reverse direction, and determine how trees in a conditioned Galton-Watson forest should coalesce in order to preserve the conditioned structure. This talk is based on joint work with N. Berestycki and J. Pitman.
top
of page
|
| Intersections of paths and high-dimensional random walk in random environment
(ps/pdf)
|
|
|
Noam Berger (UCLA)
I will present an easy calculation governing the probability of
two RWRE paths to intersect. Then I will present two applications of this
estimate: the first is a law of large numbers for distributionally
symmetric RWRE in five or more dimensions, and the second is an almost
sure CLT for ballistic walks, again in five or more dimensions.
The talk is partly based on joint work with Ofer Zeitouni.
top
of page
|
| A theorem about card shuffling
(ps/pdf)
|
|
|
Ben Morris (UC Davis)
Durrett introduced the following "L-reversal model" for
evolution of a genome: there are n cards arrayed in a circle. At each step,
an interval of cards of length at most L is chosen uniformly at random and
its order is reversed.
E. Thorp introduced the following model of a card shuffle in 1973. Cut
the deck into two equal piles. Drop the first card from the left pile or
the right pile according to the outcome of a fair coin flip; then drop
from the other pile. Continue this way until both piles are empty.
We prove a theorem about card shuffling that yields mixing time bounds for
both the L-reversal model and Thorp shuffle that are within a few
logarithmic factors of optimal. Previously, the best bounds had been n
times optimal for the L-reversal model and more than (log n)^25 times
optimal for the Thorp shuffle. Also, previous proofs for the Thorp shuffle had
been valid only when n is a power of two.
top
of page
|
| Random walk driven by arbitrarily small conductances
(ps/pdf)
|
|
|
Marek Biskup (UCLA)
I will consider the random walk on Z^d driven by a field of random i.i.d.
conductances. The law of the conductances is bounded from above; no restriction is posed on the lower tail (at zero)
except that the bonds with positive conductances percolate. I will explain how the quenched invariance
principle is proved for this random walk despite the fact that the (quenched) heat kernel may exhibit anomalous
decay in time. I will also derive universal upper bounds on the heat-kernel decay which, as I will show,
can be saturated by appropriately chosen conductance distributions. This is based on joint work with
N. Berger, C. Hoffman, G. Kozma and T. Prescott.
top
of page
|
|
