Category:Balanced function

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