Título: Random walk based algorithms for generating uniform spanning trees
Palestrante: Giulio Iacobelli (IM-UFRJ)
Organizadores: Guilherme Ost e Maria Eulalia Vares
Data: 14/12/2020
Horario: 15:00.a 16:00 (Rio de Janeiro local time)
Local: Transmissão online
Confira AQUI o link para a transmissão.
Resumo: The task of efficiently generating uniform spanning trees of a graph has received much attention. A breakthrough came with Aldous-Broder and Wilson's algorithms, which can efficiently generate spanning trees based on random walks. In this work, we study the transient behavior of both algorithms. We introduce the notion of branches, which are paths generated by the two algorithms on particular stopping times. This interpretation is used to show a transient equivalence between the two algorithms on complete graphs. This equivalence yields a hybrid approach to generate uniform spanning trees of complete graphs faster than either of the two algorithms. We also propose a two-stage framework to explore this hybrid approach beyond complete graphs, showing its feasibility in some examples.
All the talks are held in English.
Título: Percolation on a randomly stretched lattice
Palestrante: Marcelo Richard Hilário (Dep. de Matemática - UFMG)
Data: 07/12/2020
Horário: 15:00
Local: Transmissão Online
Confira AQUI o link para a transmissão.
Resumo: We consider a stretched version of the square lattice where the distances between neighboring vertical columns are given by interarrival intervals of a renewal process. Hence, horizontal edges that link vertices in the same pair of vertical columns have a common random length while every vertical edge has length one. Conditioned on the realization of the lattice, we define a bond percolation model where edges are open with probabilities that depend on their length. We relate the question of whether the model undergoes a non-trivial phase transition to the moments of interarrival times of the renewal process governing the distance among columns. We will also discuss some other related percolation models defined on media with similar types of columnar disorder. Based on a joint work with Marcos Sá, Augusto Teixeira and Remy Sanchis.
All the talks are held in English.
Organizadores: Guilherme Ost and Maria Eulalia Vares
Título: Long range percolation models on oriented trees
Palestrante: Sandro Gallo (DEs-UFSCar)
Data: 23/11/2020
Horário: 3 p.m. to 4 p.m. (Rio de Janeiro local time)
Local: Transmissão online.
Confira AQUI o link da transmissão.
Resumo: The objective of the talk is to discuss a long range percolation model on oriented trees which contains, as special cases, models such as the frog model with random lifetime and others we may present if time allows. We will be specially interested in localizing, as precisely as possible, the critical parameters
Título: Importance sampling with adaptive winsorization
Palestrante: Paulo Orenstein (IMPA)
Data: 30/11/2020
Local: Transmissão online
Clique AQUI para acessar a transmissão.
Resumo: Importance sampling is a widely used technique to estimate the properties of a distribution. The resulting estimator is always unbiased, but may sometimes incur huge or infinite variance. This work investigates trading-off some bias for variance by winsorizing the importance sampling estimator using an adaptive thresholding procedure based on the Balancing Principle (also known as Lepskii's Method). This provides a principled way to perform winsorization, with finite-sample optimality guarantees and good empirical performance.
Título: Truncation of long-range percolation model with square non-summable interactions
Palestrante: Bernardo Nunes Borges de Lima (Dep. de Matemática - UFMG)
Data: 09/11/2020
Horário: 15:00 - 16:00. (Rio de Janeiro local time)
Local: Transmissão online
Clique AQUI para acessar a transmissão.
Resumo: We consider some problems related to the truncation question in long-range percolation. It is given probabilities that certain long-range oriented bonds are open; assuming that these probabilities are not summable, we ask if the probability of percolation is positive when we truncate the graph, disallowing bonds of range above a possibly large but finite threshold. This question is still open if the set of vertices is $\Z^2$. We give some conditions in which the answer is affirmative. One of these results generalize the previous result in [Alves, Hilário, de Lima, Valesin, Journ. Stat. Phys. {\bf 122}, 972 (2017)].
Joint work with Alberto M. Campos.
