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$

4 Answers 4

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$
2
  • $\begingroup$ I like this answer the best, sorry I can't upvote , you guys are all so smart! $\endgroup$ Feb 17, 2015 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, 2015 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$
3
  • $\begingroup$ Thank you DW, but I was not looking for a "word term", but scientific notation, like LA-TEX. $\endgroup$ Feb 15, 2015 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, 2015 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$ Feb 16, 2015 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 and acknowledge you have read our privacy policy.

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