If you want to make money online : Register now

[Solved]: What do we call a function that outputs 0 on half and 1 on the other half of all inputs?

, , No Comments
Problem Detail: 

I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying this is the output is one half the time and zero half the time, on average. What is the scientific notation for describing this output scenario?

Asked By : Maryanne Thomson

Answered By : Yuval Filmus

If you absolutely insist on using symbolic notation, you can state that $\mathbb{E}[f] = 1/2$ (i.e., the expectation of $f$ is $1/2$, presumably with respect to the uniform measure over all inputs). You could also state that $\hat{f}(\emptyset) = 1/2$ (i.e., the Fourier coefficient at the empty set equals $1/2$), but $\mathbb{E}[f] = 1/2$ is probably better. Both of these assume that you already know that $f$ is Boolean.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38419

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback