Timeline for boolean functions and averaging / counting
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2010 at 19:09 | vote | accept | Alberto | ||
| Sep 19, 2010 at 1:30 | comment | added | sleepless in beantown | If you did mean something like that, then you would also have to supply a function $g: y \to z$, where $y \in \mathbb{R}$, and $z \in \{0,1\}$ mapping from the reals to a single digit binary toggle. | |
| Sep 19, 2010 at 1:28 | comment | added | sleepless in beantown | obviously, I wrote the incorrect range for the summation. $$x=\sum_{i=1}^{i=n} s_i 2^{i-1}$$ would be correct. | |
| Sep 19, 2010 at 1:27 | comment | added | sleepless in beantown | @Tsuyoshi Ito, @Alberto, I must agree with Tsuyoshi Ito. If you've defined $f$ as a function from $\{0,1\}^n \to \{0,1\}$, then there is no meaningful answer or definition to the concept of "evaluating it at non-boolean inputs". Perhaps you meant that $f: \x \to \y$, where $x,y \in \mathbb{R}$, but you just happen to evaluate $f$ at the integer values represented by the binary string $S=s_n s_{n-1} ... s_2 s_1$ evaluated as a base-$2$ integer, $x=\sum_{i=0}^{i=n-1} s_i 2^{i}$. It's impossible to answer your question unless you clarify what you are asking. | |
| Sep 18, 2010 at 3:58 | answer | added | Darsh Ranjan | timeline score: 0 | |
| Sep 17, 2010 at 22:45 | comment | added | Tsuyoshi Ito | By the way, I guess you should write (1/2)e or e/2 instead of 1/2e. | |
| Sep 17, 2010 at 22:43 | comment | added | Tsuyoshi Ito | 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. | |
| Sep 17, 2010 at 20:54 | answer | added | Nick S | timeline score: 0 | |
| Sep 17, 2010 at 20:51 | answer | added | Gerhard Paseman | timeline score: 0 | |
| Sep 17, 2010 at 20:46 | history | edited | Alberto | CC BY-SA 2.5 |
added 342 characters in body
|
| Sep 17, 2010 at 16:17 | comment | added | Alberto | 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$. | |
| Sep 17, 2010 at 14:58 | history | edited | Alberto | CC BY-SA 2.5 |
added a remark concerning e
|
| Sep 17, 2010 at 6:20 | comment | added | sleepless in beantown | 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. | |
| Sep 17, 2010 at 2:23 | comment | added | Darsh Ranjan | I still don't know what your question is, and your example computation doesn't make sense to me, either. | |
| Sep 17, 2010 at 0:29 | history | edited | Alberto | CC BY-SA 2.5 |
added tag and added remark
|
| Sep 17, 2010 at 0:18 | history | asked | Alberto | CC BY-SA 2.5 |