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

Autor(es)

Mendonca, J. Ricardo G.

• Tipo de documento: Artigo Científico
• Fonte: COMPUTATIONAL & APPLIED MATHEMATICS; v. 39, n. 3, p. 15-pg., 2020-08-13.

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
• Modalidade de apoio: 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
• Modalidade de apoio: Auxílio à Pesquisa - Regular