# Runs

## Definition

Let $k \gt 0$ be a positive integer. The $k$-runs function is a function $f:\{-1,1\}^n \to \{-1,1\}$ which checks if there are $k$ consecutive $1$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,

 $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}$

with $x_i = x_{(i \mod n) + 1}$ for $i \gt n$.

The Runs functions may be thought of as a more symmetric, "continuous", version of Tribes: Both functions require some $k$ consecutive bits to be set to 1, but whereas Tribes divides the input into predefined sets of size $k$, the Runs function doesn't care where the $k$ 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 $k$ to be the median of the longest sequence of $1$'s in a random $n$-bit string. Asymptotically, this requires taking $k = \mathrm{log}_2(n/2)$ .
• TODO.