Runs

Definition

Let [math]k \gt 0[/math] be a positive integer. The [math]k[/math]-runs function is a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] which checks if there are [math]k[/math] consecutive [math]1[/math]s in the input string, wrapping around if needed (that is, the function treats the input bits as if they sit on a circle). Mathematically,

[math] f(x) = \begin{cases} 1, & \exists i: (x_{i}, x_{i+1}, \ldots, x_{i+k-1}) = (1,1,\ldots,1) \\ -1 & otherwise, \end{cases}[/math]

with [math]x_i = x_{(i \mod n) + 1}[/math] for [math]i \gt n[/math].

The Runs functions may be thought of as a more symmetric, "continuous", version of Tribes: Both functions require some [math]k[/math] consecutive bits to be set to 1, but whereas Tribes divides the input into predefined sets of size [math]k[/math], the Runs function doesn't care where the [math]k[/math] consecutive bits are found. With the proper choice of parameters, Runs therefore behaves similarly to Tribes (TODO: CITATION NEEDED).

Properties

• The runs function can be made balanced by choosing [math]k[/math] to be the median of the longest sequence of [math]1[/math]'s in a random [math]n[/math]-bit string. Asymptotically, this requires taking [math]k = \mathrm{log}_2(n/2)[/math] .