THE R-MAJORITY VOTE ACTION ON 0-1 SEQUENCES

The r-majority vote operator M replaces simultaneously each digit of a 0-1 sequence x by the majority bit of the cyclic (2r + 1)-interval it centers. This action was suggested and studied as a model for various phenomena in biology [1,2,4], where special attention is given to the set of fixed points (fp's) of this action. We provide an algorithm for M that utilizes the run-size-sequence x of a 0-1 sequence x in order to determine Mx, thereby shedding light on many of M's dynamic properties. We show that for finite x, the number run(x) of x-runs may not increase under M-action, and that it is preserved if and only if x is-an-element-of R2t is in one of r+1 convex regions C0, C1,...,C(r) subset-or-equal-to R2t. Within C(p), M's action is realized by a circulant matrix containing the row (1,-1,...,-1,1,0,...,0) of length 2t with 2p + 1 nonzero entries. An explicit description is obtained for M's fixed points along with all M's regular points, i.e. the x's satisfying M2x = x. C0 contains x iff x is a stable fp, i.e., all x-runs are longer than r. All other regular points lie in the other C(p)'s and they are all balanced - that is, contain an equal number of zeros and ones - in accordance with Agur's conjecture for finite nonstable fp's [2]. Moreover, any regular sequence that is not a stable fp - be it finite or two-way-infinite - is periodic, with a balanced period not longer than 2r2(r2 if it is an unstable fp).