Return to search

Métodos de Monte Carlo para amostragem de permutações com restrições e aplicações / Monte Carlo sampling of restricted permutations and aplications

Neste trabalho definimos o processo de exclusão simples simétrico em tempo discreto sobre grafos por meio de permutações com restrições sobre os índices dos vértices dos grafos. O processo é uma generalização das permutações dos índices do grafo completo. Apresentamos algoritmos de Monte Carlo e de amostragem sequencial por importância para amostrar permutações com restrições inspirados pelo problema análogo de calcular permanentes. Como aplicação, utilizamos esses algoritmos para estimar os tempos de relaxação do processo de exclusão simples simétrico em tempo discreto sobre grafos aleatórios densos de Erdös-Rényi com laços / In this work we define the symmetric simple exclusion process in discrete time over graphs by means of suitably restricted permutations over the labels of the vertices of the graphs. The process is a generalization of the shuffling of labels on the complete graph. Straightforward Monte Carlo and sequential importance sampling algorithms to sample restricted permutations inspired by the related problem of computing permanents are discussed. We illustrate the formalism by estimating the relaxation times of the symmetric simple exclusion process in discrete time over dense loop-augmented Erdös-Rényi random graphs

Identiferoai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-06092018-144335
Date06 July 2018
CreatorsReale, Fábio Tosetto
ContributorsMendonca, Jose Ricardo Goncalves de
PublisherBiblioteca Digitais de Teses e Dissertações da USP
Source SetsUniversidade de São Paulo
LanguagePortuguese
Detected LanguagePortuguese
TypeDissertação de Mestrado
Formatapplication/pdf
RightsLiberar o conteúdo para acesso público.

Page generated in 0.0023 seconds