An asymptotic lower bound for the maximal-number-of-runs function.
František Franěk, Qian Yang · 2006
Abstract. An asymptotic lower bound for the maxrun function ρ(n) = max {number of runs in string x | all strings x of length n} is presented. More precisely, it is shown that for any ε> 0, (α−ε)n is an asymptotic lower bound, where α = 3 1+ √ ≈ 0.927. A 5 recent construction of an increasing sequence of binary strings “rich in runs ” is modified and extended to prove the result.