Stochastic Flips on Two-letter Words - Université Pierre et Marie Curie Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Stochastic Flips on Two-letter Words

Résumé

This paper introduces a simple Markov process inspired by the problem of quasicrystal growth. It acts over two-letter words by randomly performing flips, a local transformation which exchanges two consecutive different letters. More precisely, only the flips which do not increase the number of pairs of consecutive identical letters are allowed. Fixed-points of such a process thus perfectly alternate different letters. We show that the expected number of flips to converge towards a fixedpoint is bounded by O(n^3) in the worst-case and by O(n^(5/2) ln n) in the average-case, where n denotes the length of the initial word.
Fichier principal
Vignette du fichier
convergence2.pdf (155.12 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00436516 , version 1 (26-11-2009)

Identifiants

Citer

Olivier Bodini, Thomas Fernique, Damien Regnault. Stochastic Flips on Two-letter Words. ANALCO 2010 - 7th Workshop on Analytic Algorithmics and Combinatorics, Jan 2010, Austin, TX, United States. pp.48-55, ⟨10.1137/1.9781611973006.7⟩. ⟨hal-00436516⟩
449 Consultations
85 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More