0
$\begingroup$

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest example I can think of is probably a binary function $f: \{0,1\}^n \rightarrow \{0,1\}$ that is linear with $f(0) = 0$. Now in order to count the number of assignments resulting in $1$ I can do the following:

$1/2^n * \sum_{x \in \{0,1\}^n} f(x) = f(1/2^n * \sum_{x \in \{0,1\}^n} x) = f(1/2 e)$

where $e = (1,\dots, 1)$ is the all-one vector and thus $f(1/2 e) * 2^n$ gives me the answer i am looking for.

I vaguely recall that I have seen something like this beforehand and I guess that there is something like a whole theory about this type of combinatorial argument out there. It is also somehow about inferring the structure of the boolean function by evaluating it at non-boolean inputs. For example, I think that this is part of the idea of the algebraization as a barrier to showing P != NP where one of the oracles get enhanced power by not only being able to evaluate a certain function at 0/1 assignments but also any other point contained in $[0,1]^n$.

I would really appreciate any pointers or references or just names for what I am actually looking for.

Thanks a lot, Alberto

Improve this question
$\endgroup$
8
  • $\begingroup$ I still don't know what your question is, and your example computation doesn't make sense to me, either. $\endgroup$
    – Darsh Ranjan
    Commented Sep 17, 2010 at 2:23
  • 3
    $\begingroup$ Alberto, can you try re-writing your question so that you explain yourself more clearly? Are you saying the $e$ is the expected value (and not the constant 'e' used in exponentiation)? Are you asking if since you have a linear function, the average of the function $f$ over all possible values of binary strings of length $n$ is equal to the function of the average of the all of the expected binary strings, is equal to the function of one-half of the expected value of all binary strings of length $n$? Please restate your question more clearly. $\endgroup$
    – sleepless in beantown
    Commented Sep 17, 2010 at 6:20
  • $\begingroup$ sorry guys, you are absolutely right. The "e" here is the all-one vector. The example was just meant to point out the type of argument: I am looking for. Here, as the function is linear (as in being a homomorphism, i.e., f(0) = 0), I can compute the average of the evaluation function by computing the evaluation on the average. Than I can count by multiplying $2^n$. $\endgroup$
    – Alberto
    Commented Sep 17, 2010 at 16:17
  • $\begingroup$ I do not get “by evaluating it at non-boolean inputs” in your example. Since you could compute the same value as 2^{n−1}⋅f(e), where e is the all-one vector, it seems to me that you just chose to evaluate f at a non-boolean point when it was not necessary. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 17, 2010 at 22:43
  • 1
    $\begingroup$ By the way, I guess you should write (1/2)e or e/2 instead of 1/2e. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 17, 2010 at 22:45

3 Answers 3

Reset to default
0
$\begingroup$

There's a canonical way to extend a boolean function to the unit n-cube: you replace the boolean arguments by real numbers that are the probabilities of independent events, and the new output is the probability of the compound event defined by the original boolean function. For example, take the boolean function $(a,b,c)\mapsto (a\wedge b) \vee c$. If $a$, $b$, and $c$ are independent events with respective probabilities $p$, $q$, and $r$, then you can check that the probability of the event $(a\wedge b) \vee c$ is $pq +r -pqr$. I wrote a somewhat long post about this here: Finding minimal or canonical expressions for Boolean truth tables

I bring this up because if $f$ is an n-ary boolean function and $f^*$ is the probability version, then $f^*(1/2,...,1/2)$ is precisely the average value of $f$ over all possible boolean inputs. (That's obvious: if you flip a fair coin to determine the truth value for each of the n arguments of $f$, then by definition, $f^*(1/2,...,1/2)$ is the probability of $f$ evaluating to "true," but that probability is also clearly the average value of $f$ in this case.) That seems to be what you're looking for. (Unfortunately, computing $f^*$ for any reasonably complicated function $f$ is pretty much intractable: indeed, there is no polynomial-time algorithm unless P = #P, by the simple fact stated above.)

Improve this answer
$\endgroup$
0
$\begingroup$

One view of this is integration. If the curve (function) you have is sufficiently well understood, you can estimate the area under it by various approximation rules using a few points, e.g. Simpson's Rule. Thus you can generalize your linear example.

The other ways below involve obtaining the average through evaluating the function at some of the points in {0,1}^n . They don't speak to how to use this to infer properties of the function.

If your function is monotonic increasing, then in principle you can find the set of points which are least and sent to one under the function, and then use some form of inclusion-exclusion to get the count, or perhaps something simpler.

If your function domain can be nicely partitioned so that the result is a disjoint union of monotonic functions, then you have a divide-and-conquer strategy to implement.

If your function looks like XOR of several variables in some places, those places contribute a weight 1/2 to the average, and you might be able to handle the other places by something similar to the above.

The quickest way to estimate the average is by random sampling. The average of the function is likely to be close to the average of a random sample.

Gerhard "Ask Me About System Design" Paseman, 2010.09.17

Improve this answer
$\endgroup$
0
$\begingroup$

For the finite case I don't know anything which helps, but if your space is infinite you are looking for an Ergodic Theorem (or some type of mean/amenability if you are not in the case of a Dynamical System).

Hpe this helps

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .