# Category:Balanced function

## Definition

A Boolean function $f:\{-1,1\}^n \to \{-1,1\}$ is balanced if it obtains the value 1 on exactly half of its inputs. This can be written as:

 $\sum_{x\in\{-1,1\}^n} f(x) = 0$.

This also has a probabilistic view: if $X$ is a uniformly random vector in $\{-1,1\}^n$, then $\mathbb{E}f(X) = 0$.

Many times, a sequence of Boolean functions $(f_n)_{n\in \mathbb{N}}$ is said to be balanced, or "asymptotically balanced", if $\lim_{n\to \infty} \mathbb{E}f(x) = 0$.

A function which is not balanced is biased.

The bias of a Boolean function is related to its variance: If $\mathbb{E}[f] = p$, then $\mathrm{Var}(f) = 4p(1-p)$. Thus an unbiased function has variance 1, while a series of functions whose variance tends to 0 tend to a constant.

• TODO

## Subcategories

This category has only the following subcategory.

## Pages in category "Balanced function"

The following 15 pages are in this category, out of 15 total.