Abstract
An infinite sequence of 0's and 1's evolves by flipping each 1 to a 0 exponentially at rate 1. When a 1 flips, all bits to its right also flip. Starting from any configuration with finitely many 1's to the left of the origin, we show that the leftmost 1 moves right with bounded speed. Upper and lower bounds are given on the speed. A consequence is that a lower bound for the run time of the random-edge simplex algorithm on a Klee-Minty cube is improved so as to be quadratic, in agreement with the upper bound.
Original language | English (US) |
---|---|
Pages (from-to) | 464-483 |
Number of pages | 20 |
Journal | Random Structures and Algorithms |
Volume | 30 |
Issue number | 4 |
DOIs | |
State | Published - Jul 2007 |
Keywords
- Binary
- Bit
- Ergodic
- Flip
- Markov chain
- Simplex method
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics