TU Budapest -- BME

talks in Fall semester 2014 -- előadásai a 2014 őszi félévben

From trees to seeds: on the inference of the seed from large random trees

Abstract

I will discuss the influence of the seed in models of randomly growing
trees; in particular, I will focus on the preferential attachment and
uniform attachment models. In both of these models, different seeds lead to
different distributions of limiting trees from a total variation point of
view. I will discuss the differences and similarities in proving this for
the two models. This is based on joint work with Sebastien Bubeck, Ronen
Eldan, and Elchanan Mossel.

UNUSUAL TIME

2015.01.06 Tuesday, 16:15

An algorithmic version of the Lovász local lemma

Abstract

The probabilistic method is an efficient way to prove the existence of
certain combinatorial structures when constructions are not available
(or harder to get). For this we define a discrete probability space on
the structures and prove that the desired property holds with positive
probability. For a long while the method mostly worked if the
probability was not only positive but overwhelming (close to 1). While
effectively and deterministically find such a structure may still be
hard, a randomized algorithm is trivial: just pick a random sample
from the space and check if the desired property holds. The Lovász
local lemma (1975) gave a tool to prove the probability of a property
is positive in many cases even if the probability itself was
exponentially small. In these cases finding the desired structure (a
needle in the haystack) is challenging even for a randomized
algorithm. We show that a very simple and intuitive randomized
algorithm does exactly that: it quickly finds a desired structure.

Most of the talk is based on a 2010 joint paper with Robin Moser with pointers for more recent developments if time permits.

Most of the talk is based on a 2010 joint paper with Robin Moser with pointers for more recent developments if time permits.

2014.12.18 Thursday, 16:15

KPZ scaling theory for integrable exclusion processes

Abstract

The KPZ scaling theory provides a general method to compute all
model-dependent constants arising in limit theorems for a large class of
exclusion processes. The validity of this heuristic approach is rigorously
proved only for a few exactly solvable models. In this talk, we will discuss
how the theory applies for q-deformed exclusion processes introduced by
Borodin-Corwin and Povolotsky: The q-TASEP and the q-Hahn TASEP. We will
also introduce a two-sided generalization of the q-Hahn TASEP that preserve
the integrable structure and further confirm KPZ scaling theory. This is a
joint work with Ivan Corwin.

2014.11.20 Thursday, 16:15

Random walk on hyperbolic unimodular triangulations and circle packing

Abstract

We investigate the behaviour of random walk on the circle packing of a hyperbolic unimodular triangulations. A way to relate the geometry of such graphs with random walks is via circle packing: one can draw non-intersecting circles on the plane, one for each vertex and circles touch each other if and only if their vertices are adjacent. We show that such a triangulation can be packed in the unit disc and the unit circle gives a pretty accurate description of the final behaviour of the simple random walk on it. Joint work with Omer Angel, Tom Hutchcroft and Asaf Nachmias.

2014.11.13 Thursday, 16:15

Frequentist coverage of adaptive Bayesian credible sets

Abstract

In the beginning of the talk I will give a short introduction to the
frequentist analysis of Bayesian approaches, focusing mainly on
nonparametric and adaptive settings. Then I will present our results
on the frequentist coverage of Bayesian credible sets in a
nonparametric setting. In our work we consider a scale of priors of
varying regularity and choose the regularity by an empirical Bayes
method. Next we consider a central set of prescribed posterior
probability in the posterior distribution of the chosen regularity. We
show that such an adaptive Bayes credible set gives correct
uncertainty quantification of `polished tail' parameters, in the sense
of high probability of coverage of such parameters. On the negative
side we also show by theory and example that adaptation of the prior
necessarily leads to gross and haphazard uncertainty quantification
for some true parameters that are still within the hyperrectangle
regularity scale.

2014.10.30 Thursday, 16:15

Connectivity in confined dense networks

Abstract

We consider a random geometric graph model relevant to wireless mesh
networks. Nodes are placed uniformly in a domain, and pairwise connections
are made independently with probability a specified function of the distance
between the pair of nodes, and in a more general anisotropic model, their
orientations. The probability that the network is (k-)connected is
estimated as a function of density using a cluster expansion approach. This
leads to an understanding of the crucial roles of local boundary effects and
of the tail of the pairwise connection function, in contrast to lower
density percolation phenomena.

2014.10.16 Thursday, 16:15

Proportionally fair scheduling for traffic light networks

Abstract

We consider a decentralized traffic signal control policy for urban
road networks. The policy uses a proportionally fair scheme to
allocate green times at each junction using only local information of
queue lengths. At the same time it maintains a cyclic ordering of
service phases which is a desirable property for traffic safety. Our
model also includes elements of real life traffic behaviour such as
the use of switching times and the time dependency of service rates
due to the initial setup at the beginning of service phases. We
discuss the effect of these phenomena on the set of feasible traffic
demands. We also investigate the impact of the chosen cycle lengths on
the ensuing waiting times of the vehicles. As our main result, we show
that the proportionally fair policy stabilizes the network for any
feasible demand. In order to accomplish this, we construct the fluid
limit of the underlying stochastic system and give a formal proof of
convergence as a generalization of prior results in the context of
telecommunication applications. Existing stability results in the
literature for proportional fair scheduling cannot be directly applied
to our model because of several characteristics that are specific to
the application to road traffic networks, including the earlier
mentioned cyclic service patterns and the time dependency of service
rates.

2014.09.25 Thursday, 16:15

Random walks on Lie groups / Véletlen séták Lie csoportokon

Abstract

I will survey some results about the speed of equidistribution of
random walks on compact Lie groups and on the group of Euclidean
isometries. I will also give an application to smoothness of
selfsimilar measures. A random walk is a sequence of random elements
of the group obtained by computing the product of several independent
random elements.

2014.09.18 Thursday, 16:15