Difference between revisions of "Category:Balanced function"
m |
m |
||
| (One intermediate revision by the same user not shown) | |||
| Line 2: | Line 2: | ||
A Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is '''balanced''' if it obtains the value 1 on exactly half of its inputs. This can be written as: | A Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math> is '''balanced''' if it obtains the value 1 on exactly half of its inputs. This can be written as: | ||
| − | <math>\sum_{x\in\{-1,1\}^n} f(x) = 0</math>. | + | :::{| class="wikitable" |
| + | |- | ||
| + | |<math>\sum_{x\in\{-1,1\}^n} f(x) = 0</math>. | ||
| + | |} | ||
This also has a probabilistic view: if <math>X</math> is a uniformly random vector in <math>\{-1,1\}^n</math>, then <math>\mathbb{E}f(X) = 0</math>. | This also has a probabilistic view: if <math>X</math> is a uniformly random vector in <math>\{-1,1\}^n</math>, then <math>\mathbb{E}f(X) = 0</math>. | ||
| Line 10: | Line 13: | ||
A function which is not balanced is [[:Category:Biased function|biased]]. | A function which is not balanced is [[:Category:Biased function|biased]]. | ||
| + | The bias of a Boolean function is related to its variance: If <math>\mathbb{E}[f] = p</math>, then <math>\mathrm{Var}(f) = 4p(1-p)</math>. Thus an unbiased function has variance 1, while a series of functions whose variance tends to 0 tend to a constant. | ||
== Properties == | == Properties == | ||
Latest revision as of 13:36, 20 November 2019
Definition
A Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is balanced if it obtains the value 1 on exactly half of its inputs. This can be written as:
[math]\sum_{x\in\{-1,1\}^n} f(x) = 0[/math].
This also has a probabilistic view: if [math]X[/math] is a uniformly random vector in [math]\{-1,1\}^n[/math], then [math]\mathbb{E}f(X) = 0[/math].
Many times, a sequence of Boolean functions [math](f_n)_{n\in \mathbb{N}}[/math] is said to be balanced, or "asymptotically balanced", if [math]\lim_{n\to \infty} \mathbb{E}f(x) = 0[/math].
A function which is not balanced is biased.
The bias of a Boolean function is related to its variance: If [math]\mathbb{E}[f] = p[/math], then [math]\mathrm{Var}(f) = 4p(1-p)[/math]. Thus an unbiased function has variance 1, while a series of functions whose variance tends to 0 tend to a constant.
Properties
- TODO
References
Pages in category "Balanced function"
The following 17 pages are in this category, out of 17 total.
