Difference between revisions of "Tribes"
Ori.sberlo (talk | contribs) (2^n) |
Ori.sberlo (talk | contribs) |
||
| Line 6: | Line 6: | ||
where we identify <math>-1</math> with logical True and <math>+1</math> with logical False. The Tribe function corresponds to the follows voting scheme. There are <math>t</math> tribes, each consists of <math>n</math> members and the value of <math>x_{i,j}</math> corresponds to the vote of the j'th member from the i'th tribe (with the above identification of logical values). First, each tribe takes a unanimous voting. Namely, if all tribe members voted True then the tribe vote is counted as True, otherwise the tribe vote it is considered False. Then, if at least tribe voted True then the entire vote is considered True and otherwise it is considered false. In other words, the value of <math>\mathrm{Tribes}_{t,n}(x)</math> is True if and only if at all the members of at least one tribe voted True. | where we identify <math>-1</math> with logical True and <math>+1</math> with logical False. The Tribe function corresponds to the follows voting scheme. There are <math>t</math> tribes, each consists of <math>n</math> members and the value of <math>x_{i,j}</math> corresponds to the vote of the j'th member from the i'th tribe (with the above identification of logical values). First, each tribe takes a unanimous voting. Namely, if all tribe members voted True then the tribe vote is counted as True, otherwise the tribe vote it is considered False. Then, if at least tribe voted True then the entire vote is considered True and otherwise it is considered false. In other words, the value of <math>\mathrm{Tribes}_{t,n}(x)</math> is True if and only if at all the members of at least one tribe voted True. | ||
| − | If one chooses the number of tribes and the tribe size appropriately, then the tribe function is an unbiased such that every variable has very little influence. Specifically, one can set <math>t,n< | + | If one chooses the number of tribes and the tribe size appropriately, then the tribe function is an unbiased such that every variable has very little influence. Specifically, one can set <math>t,n</math> such that <math>\mathrm{Pr}_{x}[\mathrm{Tribes}_{t,n}(x) = -1] = 1/2 - O(\frac{\log n}{n})</math> and the influence of every variable equals <math>\frac{\ln n}{n}(1+o(1))</math>. In fact, according to the KKL theorem this is tight up to constant factors, namely any unbiased function must have a variable with influence <math>\Omega(\frac{\log n}{n})</math>. |
== Properties == | == Properties == | ||
Revision as of 11:43, 2 September 2018
Definition
The tribe function with [math]t[/math] tribes of size [math]n[/math] is the boolean function [math]\mathrm{Tribes}_{t,n} : \{-1 ,+1\}^{tn} \rightarrow \{-1,+1\}[/math] defined by the DNF formula
- [math]\mathrm{Tribes}_{t,n}(x) = \bigvee_{i=1}^{t} \bigwedge_{j=1}^{n} x_{i,j}[/math],
where we identify [math]-1[/math] with logical True and [math]+1[/math] with logical False. The Tribe function corresponds to the follows voting scheme. There are [math]t[/math] tribes, each consists of [math]n[/math] members and the value of [math]x_{i,j}[/math] corresponds to the vote of the j'th member from the i'th tribe (with the above identification of logical values). First, each tribe takes a unanimous voting. Namely, if all tribe members voted True then the tribe vote is counted as True, otherwise the tribe vote it is considered False. Then, if at least tribe voted True then the entire vote is considered True and otherwise it is considered false. In other words, the value of [math]\mathrm{Tribes}_{t,n}(x)[/math] is True if and only if at all the members of at least one tribe voted True.
If one chooses the number of tribes and the tribe size appropriately, then the tribe function is an unbiased such that every variable has very little influence. Specifically, one can set [math]t,n[/math] such that [math]\mathrm{Pr}_{x}[\mathrm{Tribes}_{t,n}(x) = -1] = 1/2 - O(\frac{\log n}{n})[/math] and the influence of every variable equals [math]\frac{\ln n}{n}(1+o(1))[/math]. In fact, according to the KKL theorem this is tight up to constant factors, namely any unbiased function must have a variable with influence [math]\Omega(\frac{\log n}{n})[/math].
Properties
- [math]\mathrm{Pr}_{x}[\mathrm{Tribes}_{t,n}(x) = -1] = 1 - (1-2^{-n})^{t}[/math]
- Fourier Expansion: Index the Fourier coefficients of [math]\mathrm{Tribes}_{t,n}(x)[/math] as follows. Given [math]T \subseteq [nt][/math] write [math]T = (T_1,\ldots,T_s)[/math] where [math]T_i \subseteq \{(i-1)\cdot n+1,.\ldots , i\cdot n + n\}[/math] for [math]i = 1,2,\ldots,t[/math]. Then,
- [math]\widehat{\mathrm{Tribes}_{t,n}}(T) = \begin{cases} 2(1-2^{-n})^{t}-1 & T = \emptyset\\ 2(-1)^{|\{i : T_i \neq \emptyset\}|+|T|}2^{-|\{i : T_i \neq \emptyset\}| \cdot n}(1-2^{-n})^{t-|\{i : T_i \neq \emptyset\}|} & T \neq \emptyset\\ \end{cases} [/math]
