1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this answer the best, sorry I can't upvote , you guys are all so smart! $\endgroup$ – Maryanne Thomson Feb 17 '15 at 3:20
  • 1
    $\begingroup$ I dislike this because it admits more scenarios than the question. That is, non-uniform measures with unbalanced $f$ can still yield an expectation of $1/2$. $\endgroup$ – Raphael Feb 17 '15 at 7:47
3
$\begingroup$

A boolean function is called balanced if it is zero on half its inputs and one on half its inputs. So, "balanced" might be the term you are looking for.

$\endgroup$
  • $\begingroup$ Thank you DW, but I was not looking for a "word term", but scientific notation, like LA-TEX. $\endgroup$ – Maryanne Thomson Feb 15 '15 at 23:33
  • $\begingroup$ @MaryanneThomson, OK. I'm not sure what you are looking for, then. Please try to edit your question to give a more detailed explanation of what you're looking for, how you will recognize an answer that meets your needs, an example (of something similar), something like that. (By the way, for your information, nomenclature tends to refer to a name or terminology, so that might not be the word you want to use in the title of your question.) $\endgroup$ – D.W. Feb 16 '15 at 2:11
  • 1
    $\begingroup$ @MaryanneThomson The scientific notation is to say that the function is balanced. If you want symbolic notation, you can invent one yourself, since no standard one exists. $\endgroup$ – Yuval Filmus Feb 16 '15 at 6:33
2
$\begingroup$

If there's a word for it, use that one (see other answers).

Mathematically speaking, you look at functions $f : X \to \{0,1\}$ so that

$\qquad\displaystyle |f^{-1}(0)| = |f^{-1}(1)|$

where $f^{-1}$ denotes the inverse image of $f$.

So this is how one could define the property:

Let $X$ and $Y$ be finite sets with $|X| \in |Y|\mathbb{N}$. A function $f : X \to Y$ is balanced if

$\qquad\displaystyle |f^{-1}(y)| = \frac{|X|}{|Y|}$

for all $y \in Y$.

$\endgroup$
0
$\begingroup$

You could say that that boolean function follows the bernoulli distribution where an outcome of success (outputting a 1), with probability $p = 0.5$, and an outcome of failure (outputting a 0), with probability $q=(1-p)=1-0.5=0.5$. Depending on your context you can also make an output of 0 your success condition and flip your failure condition.

In terms of notation, if $x$, represents an arbitrary input, and you have such a function $f$, you could say $f(x) \sim Bernoulli(0.5)$ and $Pr(f(x)=1) = 0.5$, meaning that the probability of outputting a one on input x is 0.5 and the former porton means that f(x) follows the Bernoulli distribution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.