Difference between revisions of "Runs"
m (→Properties) |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
Let <math>k > 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, | Let <math>k > 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) \\ | + | :::{| class="wikitable" |
| + | |- | ||
| + | |<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> | -1 & otherwise, \end{cases}</math> | ||
| + | |} | ||
with <math>x_i = x_{(i \mod n) + 1}</math> for <math>i > n</math>. | with <math>x_i = x_{(i \mod n) + 1}</math> for <math>i > n</math>. | ||
| Line 11: | Line 14: | ||
== Properties == | == 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> <ref>Mark F. Schilling (1990) [https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020742.02p0021g.pdf The Longest Run of Heads], The College Mathematics Journal, 21:3, 196-207, DOI: 10.1080/07468342.1990.11973306</ref>. | * 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> <ref>Mark F. Schilling (1990) [https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020742.02p0021g.pdf The Longest Run of Heads], The College Mathematics Journal, 21:3, 196-207, DOI: 10.1080/07468342.1990.11973306</ref>. | ||
| − | |||
== References == | == References == | ||
<references/> | <references/> | ||
| − | [[Category:monotone function]] [[Category:balanced function]] [[Category:transitive-symmetric function]] | + | [[Category:monotone function]] [[Category:balanced function]] [[Category:transitive-symmetric function]] [[Category:Noise sensitive function]] |
Latest revision as of 14:50, 7 April 2021
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] [1].
References
- ↑ Mark F. Schilling (1990) The Longest Run of Heads, The College Mathematics Journal, 21:3, 196-207, DOI: 10.1080/07468342.1990.11973306
