Stochastic Flips on Two-letter Words

2010/10/06 by Olivier Bodini, Thomas Fernique, Bodini, Olivier +3
Computer Science · Materials Science · Mathematics · Physics and Astronomy · Social Sciences · #37A25 #52C23 #60C05 #60J10 #Cellular Automata and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Language and cultural evolution #Probability (math.PR) #Quasicrystal Structures and Properties #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.DM #math.PR #msc:37A25 #msc:52C23 #msc:60C05 #msc:60J10

paper · pdf · doi:10.48550/arxiv.1010.1086

ANALCO'10

arxiv created 2010/10/06 · openalex publication_date 2010/10/06 · arxiv updated 2010/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 fixed-point is bounded by O(n³) in the worst-case and by O(n^5/2lnn) in the average-case, where n denotes the length of the initial word.

Related

• Two-faced processes and random number generators
• Words in Random Binary Sequences I
• Inside the Binary Reflected Gray Code: Flip-Swap Languages in 2-Gray Code Order
• Periodic words, common subsequences and frogs
• Random Subwords and Pipe Dreams