Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Efficient generation of random derangements with the expected distribution of cycle lengths

Texto completo
Autor(es):
Mendonca, J. Ricardo G. [1]
Número total de Autores: 1
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Escola Artes Ciencias & Humanidades, BR-03828000 Sao Paulo, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: COMPUTATIONAL & APPLIED MATHEMATICS; v. 39, n. 3 AUG 13 2020.
Citações Web of Science: 0
Resumo

We show how to generate random derangements efficiently by two different techniques: random restricted transpositions and sequential importance sampling. The algorithm employing restricted transpositions can also be used to generate random fixed-point-free involutions only, a. k. a. random perfect matchings on the complete graph. Our data indicate that the algorithms generate random samples with the expected distribution of cycle lengths, which we derive, and for relatively small samples, which can actually be very large in absolute numbers, we argue that they generate samples indistinguishable from the uniform distribution. Both algorithms are simple to understand and implement and possess a performance comparable to or better than those of currently known methods. Simulations suggest that the mixing time of the algorithm based on random restricted transpositions (in the total variance distance with respect to the distribution of cycle lengths) is O(n(a) log n(2)) with a similar or equal to 1/2 and n the length of the derangement. We prove that the sequential importance sampling algorithm generates random derangements in O(n) time with probability O(1/n) of failing. (AU)

Processo FAPESP: 17/22166-9 - Recordes, alcance e maiores subsequências crescentes de passeios aleatórios
Beneficiário:José Ricardo Gonçalves de Mendonça
Linha de fomento: Bolsas no Exterior - Pesquisa
Processo FAPESP: 20/04475-7 - Maiores subsequências crescentes de passeios aleatórios e séries temporais correlacionadas
Beneficiário:José Ricardo Gonçalves de Mendonça
Linha de fomento: Auxílio à Pesquisa - Regular