Countingk-Juntas,AsymptoticInfluences&
HammingGeometry
JuspreetSinghSandhu
September28,2018
1Introduction
WebeginbyintroducingthenotionsofInfluence,NoiseStability&k-Juntas
ofBooleanFunctions.Wethendeveloparecurrencerelationforhowtocount
k-Juntas,andattempttoreasonabouttheirasymptoticgrowth.Followingthis,
wetalkaboutthegeometryoftheHammingCubeanditsrelationtoInfluence,
particularlytheMajorityfunctionandmonotonefunctions.Wethenconclude
withasectionwherewestateandsketchtheproofforaweakversionofArrow’s
Theorem,andendbystatingthemorerobust(approximate)versionusingthe
FKNTheorem.
2Acknowledgements
Alargepartofthismusing/postisbasedonmyextensions/solutionstovarious
material/exercisesfromRyanO’Donnell’sbookontheAnalysisofBoolean
Functions.
3Influence,NoiseStability&k-Juntas
IntheAnalysisofBooleanFunctions,theconceptsofInfluence,NoiseStability
&Juntasplayacentralrole.Wewillusethissectiontodefinesomeofthese
basicnotionsandsomeproperties(analytical&combinatorial)aboutthem.
WewillconsidermainlyBooleanFunctions
f
embeddedin
H
2
n
.So,everyfunc-
tioninthispostisabooleanfunction.
(
BooleanFunction
)
f
:
{−
1
,
1
}
n
→{−
1
,
1
}
EveryBooleanFunctionhasa(unique)FourierExpansionasamulti-linear
1
Polynomial,writtenas:
(
FourierExpansion
):
∀
f
,
f
=
P
S
⊆
[
n
]
ˆ
f
(
S
)
χ
S
,where,
χ
S
=
Q
i
∈
S
x
i
Here,
χ
S
istheparityfunctionon
S
,andtheFourierExpansionisthelin-
earcombinationofthelinearlyindependentbasisonwhichevery
f
canbe
represented.Thisistherepresentationthatallowsustothinkof
f
asapoint
embeddedin
H
2
n
.Itisusuallycustomarytoscalethispointtobeofunitlength
(
L
2
norm).So:
(
Parserval’sTheorem
):
h
f,f
i
=
E
x
∼{−
1
,
1
}
n
f
2
(
x
)=
P
S
⊆
[
n
]
ˆ
f
2
(
S
)=1
Thisfollowsfromtheorthonormalityoftheparityfunctions,andthefactthat
squaringisequivalentto1in
F
2
.
WecannowdescribetheInfluenceofaBooleanFunction.Informally,theinflu-
enceofabooleanfunctiononthe
i
th
coordinatesimplyrepresentstheprobability
thatflipping
x
i
∈
x
willflip
f
(
x
).Moreformally:
(
Influenceati
):Theinfluenceatco-ordinate
i
forafunction
f
is:
Inf
i
[f]
=
Pr
x
∼{−
1
,
1
}
n
f
(
x
)
6
=
f
(
x
⊕
i
)
SincetheInfluenceofaBooleanFunctionisintrinsicallyrelatedtochangein
f
(
x
)withrespecttoachangein
x
i
,itcanbeseenasmeasuringtheindicator
ofthediscretedirectionalderivative(
D
i
)of
f
.Assuch,wecantaketheexpec-
tationof(
D
i
)
2
toarriveataFourier-analyticrepresentationof
Inf
i
[f]
:
Inf
i
[f]
=
P
i
∈
S
ˆ
f
2
(
S
)
Thisisagoodexampleofacasewherewecan,toparaphraseRyanO’Donnell,
”readoffaninterestingCombinatorialpropertyofaBooleanFunctionfromits
Fourierexpansion”.
Extendingthisidea,wecandefinethetotalInfluenceofafunction
f
as:
I[f]
=
P
n
i
=1
Inf
i
[f]
Animportantresultthatrelatesthevarianceof
f
withitstotalinfluenceis:
(
PoincareInequality
):
∀
f
,
Var[f]
≤
I[f]
.
WecanprovethisbycomparingtheFourier-analyticexpansionsofboththese
operators.WithalittlemoreelementaryCombinatoricswecanalsoextendthis
inequality(forbooleanfunctionswiththerange
{−
1
,
1
}
)to:
Inf
i
[f]
≤
Var[f]
≤
I[f]
Wecannowintroducetheconceptof
NoiseStability
inbooleanfunctions.In-
formally,thenoisestabilityofabooleanfunctionistheabilityofthefunction
tonotchangeitsoutputwhentheinputbitsareflippedbysomeprobability
(parametrizedby
ρ
).Formally:
2
(
NoiseStability
):
∀
f
,
∀
ρ
∈{−
1
,
1
}
,theNoiseStabilityof
f
at
ρ
is:
Stab
ρ
[f]
=
E
y
∼
N
ρ
(
x
)
[
f
(
x
)
f
(
y
)]
Bydefinition,
N
ρ
(
x
)definesthedistributionwhere
y
isdrawnsuchthatit
iscorrelatedwith
x
withprobability
ρ
.So,
E
(
x
i
y
i
)=
ρ
,whichmeansthatwe
cancomputethestabilityoftheparityfunctions:
Stab
ρ
[
χ
S
]
=
E
[
Q
i
∈
S
(
x
i
y
i
)]=
ρ
|
S
|
Therefore,theFourier-Expansionof
Stab
ρ
[f]
is:
Stab
ρ
[f]
=
P
S
⊆
[
n
]
ρ
|
S
|
ˆ
f
2
(
S
)
Wewillreturntotheaboveconceptslaterwhenwetryto,forexample,use
HammingGeometrytounderstandInfluence,andattempttostateandsketch
proofsofArrow’sTheorem&theFKNTheorem.
Wenowmoveontok-Juntas.Informally,ak-Juntameasuresthe”true”num-
berofvariablesafunction
f
dependson.Intuitively,onecanseethenumberof
variablesafunctiondependsonbyseeingwhichcoordinates
i
have
Inf
i
[f]
=0.
Weformallydefineak-Juntaas:
(k-Junta)
:
f
issaidtobeak-Juntaif:
f
=
g
(
x
i
1
,..,x
i
k
),where
{
i
1
,..,i
k
}⊂
[
n
]
Therefore,ak-Juntadependson
atmost
k
coordinates.
4Countingk-Juntas
Wewilltryandcountthenumberofk-Juntasgivensome
n
∈
N
,toestimate
the”richness”ofk-Juntasandthefractionofbooleanfunctionsitcaptureson
n
coordinates.
Itiseasytoseethatthenumberof1-Juntasforany
n
is:
|
1-Juntas
|
n
=2n+2,wherewehavetheconstantfunctions(2)andthedictator
(n)andanti-dictatorfunctions(n).Itis(quite)non-trivialtocountthenum-
berofk-Juntasforanarbitrary
k
∈
N
.Bydefinition,thenumberofk-Juntas
dependon
atmost
k
coordinates,andsowecanexpressthemas:
|
k
-Juntas
|
n
=
|
(
k
−
1)-Juntas
|
n
+
|{
g
:
g
dependsonexactlykcoordinates
}|
Theeffortgoesintocomputingthesecondtermoftherecurrence,sincewe
alreadyhaveourbasecase-
|
1
−
Juntas
|
n
=2
n
+2.
Now,functionsthatdependon
exactly
k
coordinatescandependonk-variables
chosenfromanyk-subsetof[
n
].Furthermore,thereare2
2
k
total(boolean)
functionson
k
variables.However,fromthese,wecansubtractoffunctions
3
thatdependon(
k
−
1)variablesofless.Thiscanbeaccomplishedbycalculat-
ingthenumberof(
k
−
1)-Juntasfor
n
=
k
andsubtractingthemfromthetotal
numberofk-aryfunctions.Thisleadstoanicerecurrencerelation:
|
k
-Juntas
|
n
=
|
(
k
−
1)-Juntas
|
n
+
n
k
!
(2
2
k
−|
(
k
−
1)-Juntas
|
n
=
k
)
Evaluatingleadstothefollowingexpressionsfor(certainvaluesof)
k
:
(k=1)
:
|
1-Juntas
|
n
=2
n
+2
(k=2)
:
|
2-Juntas
|
n
=10
·
n
2
!
+2
n
+2
(k=3)
:
|
3-Juntas
|
n
=218
·
n
3
!
+10
·
n
2
!
+2
n
+2
Introspectingtheleadingcoefficients(2,10,218...)doesnotindicateanyobvi-
ousseries.Asaresult,itishardtoarriveatacombinatorialgeneratingfunction
forthenumberofk-Juntasofan-arybooleanfunction.Despiteourefforts,we
wereunabletosolvetherecurrencetoarriveataclosedform.Wecan,however,
takeaquicklimittoverifythecorrectnessoftherecurrencerelation:
lim
k
→
n
|
k
-Juntas
|
n
=
|
(
n
−
1)-Juntas
|
n
+
n
n
!
(2
2
n
−|
(
n
−
1)-Juntas
|
n
)=2
2
n
Let
c
k
denotethenumberofk-arybooleanfunctionsthatdependonnomore
than(
k
−
1)-coordinates.Wecanalsoestimatethefractionofk-Juntaboolean
functionsovern-coordinates:
|
k
−
Juntas
|
n
|
B
n
|
=
|
(
k
−
1)
−
Juntas
|
n
2
2
n
+
n
k
!
(2
2
k
−
c
k
)
2
2
n
Theleadingordertermfor
|
(
k
−
1)
−
Juntas
|
n
is
O
(
n
k
−
1
·
2
2
k
−
1
),allowing
ustorewritethefractionas:
|
k
−
Juntas
|
n
|
B
n
|
=
O
(
n
k
−
1
·
2
2
k
−
1
)
2
2
n
+
n
k
!
(2
2
k
−
c
k
)
2
2
n
Itseems,atleastatfirstglance,thatthisisthebestanalysiswecanhave
aboutcountingk-Juntaswithoutacloseformgeneratingfunction.However,it
ispossibletogetaslightlymoreelegantboundwhenwe’researchingforJuntas
thatare’sparse’withrespecttothedimensionalityoftheinput.Morespecifi-
cally,if
k
≤
loglog(
n
),then:
|
k
−
Juntas
|
n
|
B
n
|
≤
O
(
n
loglog(
n
)
−
c
loglog(
n
)
)
2
2
n
5HammingGeometry&AsymptoticInfluences
Havingattemptedsomeformof(asymptotic)analysisoncountingk-Juntas,
wewillnowturnourattentiontotheinfluenceoftheMajorityfunction(and
4
monotonefunctions).WeshallalsodescribeaGraph-Theoretic/Geometricway
ofthinkingabout
Inf
i
[f]
,anduseittocalculate(exactly)
Inf
i
[MAJ
n
]
.
Goingbacktothebasicdescriptionof
Inf
i
[f]
,weseethatwecanviewthe
Influenceof
f
at
i
asthefractionofinput-switchingedgeswhenpartitioning
theHammingCubeinto2disjointsubsets,say
H
k
,H
m
,suchthat:
x
i
=1
,
∀
x
∈
H
k
and
x
i
=
−
1
,
∀
x
∈
H
m
.
Additionally,wedrawedgesbetweentwoinputs
x
∈
H
k
and
y
∈
H
m
iff
y
=
x
⊕
i
.
Thisisessentiallyabi-partitedecomposition
G
=(
V,E
),where
V
=
{−
1
,
1
}
n
and
E
=
{
(
x,y
)
|
y
=
x
⊕
i
}
.Aswearefixingco-ordinate
i
tobe+1inoneset
and-1intheotherset,wecanrewritethedefinitionfor
Inf
i
[f]
:
Inf
i
[f]
=
|{
(
x,y
):(
x,y
)
∈
E,f
(
y
)=
−
f
(
x
)
}|
|
E
|
=
|{
(
x,y
):(
x,y
)
∈
E,f
(
y
)=
−
f
(
x
)
}|
2
n
−
1
Theedgesinthenumeratorarecalled
BoundaryEdges
.IntheHammingCube,
theyarespreadacrossvariouslevelsofthecube.Theboundaryedgesare
clearlyalsopresentintheHammingCube,becausetheyexistbetweenpairs
withaHammingDistanceof1.Aseachedgerepresentsaparticularbit-flip
onafixedcoordinate,thesetofboundaryedgesforafixedcoordinatedonot
intersectwiththoseofanother.Thisalsoallowsustocountthetotalnumber
ofedgesintheHammingCube:
|
E
H
n
|
=
n
·
2
n
−
1
Thisgivesusarelationbetweenthe
total
fr* D E M O *ndaryedges(
B
f
)in
thebooleancubeand
I[f]
:
B
f
=
I[f]
n
Fortheremainderofthissection,wewillassumethat
n
∈
Z
odd
.
NOTE
:Theremainderofthissectionisapartialsolutionto
Exercise2.22
inO’Donnell’sbook.Skipitifyouwanttosolveityourself.
Wewillnow(preciselyandasymptotically)compute
Inf
i
[MAJ
n
]
.
Noticethat
MAJ
n
(
x
)=1whenthenumberof1’sin
x>
n
−
1
2
.Therefore,the
onlyboundaryedgesfor
MAJ
n
arebetweenlevel
n
−
1
2
and
n
+1
2
intheHamming
Cube.Itiseasytocountthenumberoftheseedgesusingelementarycombina-
torics:
|
B
f
|
=forward
deg(v)
·
n
n
−
1
2
!
,
∀
v
∈
H
n
n
−
1
2
H
n
n
−
1
2
denotestheBooleanvectorswith
n
−
1
2
onesinthem.Itiseasytouse
someelementarycombinatoricsandnoticethatforward
deg(v)=
n
+1
2
atlevel
5
n
−
1
2
.Infact,moregenerally:
forward
deg(v)=
n
−
k
atlevel
k
,
∀
v
∈
H
n
k
Wealsonoticethat
Inf
i
[MAJ
n
]
=
Inf
j
[MAJ
n
]
,
∀
i,j
∈
[
n
]
ThisiseasytoseeastheMajorityfunctionis
symmetric
(meaningthatitis
invariantunderpermutationstoitsinput).Therefore,weseethat:
|
B
f
[
i
]
|
=
|
B
f
|
n
Wecannowusethegraph-theoretic/geometricnotionofInfluencederivedabove
tocompute
Inf
i
[MAJ
n
]
:
Inf
i
[MAJ
n
]
=
|
B
f
[
i
]
|
2
n
−
1
=
(
n
+1
2
)
n
n
−
1
2
!
n
·
2
n
−
1
Withabitofalgebraicmanipulation,thisyields:
Inf
i
[MAJ
n
]
=2
1
−
n
·
n
−
1
n
−
1
2
!
Inordertounderstandhow
Inf
i
[MAJ
n
]
behavesfor
large
valuesof
n
,weuse
theStirlingApproximation:
(
StirlingApproximation
):
∀
m
,
m
!=(
m
e
)
m
(
√
2
πm
+
O
(
m
−
1
2
))
Applyingthisapproximationto
Inf
i
[MAJ
n
]
yields:
lim
n
→
large
Inf
i
[MAJ
n
]
=lim
n
→
large
2
1
−
n
·
(
n
−
1)!
((
n
−
1)!)
2
=lim
m
→
large
2
−
m
·
m
!
(
m
2
)
2
lim
n
→
large
Inf
i
[MAJ
n
]
=lim
m
→
large
(
√
2
π
·
m
+
O
(
m
−
1
2
))
(
√
π
·
m
+
O
(
m
−
1
2
))
2
lim
n
→
large
Inf
i
[MAJ
n
]
=lim
m
→
large
(
√
2
π
·
m
+
O
(
m
−
1
2
))
(
π
·
m
+
O
(
m
−
1
))
As
m
→
large
,wehavethat
m>>>
1
m
.Therefore:
lim
n
→
large
Inf
i
[MAJ
n
]
=
(
√
2
π
·
m
+
O
(
m
−
1
2
))
π
·
m
=
q
2
π
m
+
O
(
m
−
3
2
)
So,
I[f]
=
P
n
i
=1
Inf
i
[f]
=
n
·
Inf
i
[f]
=
q
2
π
·
√
n
+
O
(
n
−
1
2
)
Wenowstate2theoremsthatwewilluseforthenextsectiononArrow’s
TheoremandtheFKN-Theorem:
(
Th
m
1
):If
f
is
monotone
,then
I[f]
=
P
n
i
=1
ˆ
f
(
{
i
}
)
Proof
:Thisiseasilyseenwhenwerealizethat,inamonotonefunction,the
discretederivativeoperator(
D
i
)is
always
positive.Asaresult:
Inf
i
[f]
=
E
[
D
2
i
(
f
)]=
E
[
D
i
(
f
)]=
ˆ
f
(
{
i
}
)
6
Therefore,
I[f]
=
P
n
i
=1
Inf
i
[f]
=
P
n
i
=1
ˆ
f
(
{
i
}
)
QED
(
Th
m
2
):Theuniquemaximizersof
P
n
i
=1
ˆ
f
(
{
i
}
)arethemajorityfunctions.
So,
∀
monotone
f
,
I[f]
≤
Inf
i
[MAJ
n
]
=
q
2
π
·
√
n
+
O
(
n
−
1
2
).
Proof
:Thisiseasytosee,whenweuseaninner-productexpansionofthe
singletonfouriercoefficientssubjecttolinearityofexpectationandboundthem
fromabove:
P
n
i
=1
ˆ
f
(
{
i
}
)=
E
x
[
f
(
x
)(
x
1
+
..
+
x
n
)]
≤
E
x
[
|
x
1
+
..
+
x
n
|
]
Theequalityforthisholdsonlywhen
f
(
x
)isthemajorityfunction.
QED
Havingfinishedourforayintoasymptoticinfluences,basichamminggeometry,
thebehaviorofthemajorityfunctionandtheinfluencesofmonotonefunctions
ingeneral,wearenowequippedtomoveontoourfinaltopic.
6Arrow’sTheorem&FKNTheorem
Arrow’sTheoremisastatementabouttheoutcomeofanelectioninvolving
m-parties,wherewedevelopanorderingtodecidetheultimatewinnerbased
onhavingpair-wiseelections.
Ingeneral,foranelectionwith
n
peopleacross
m
parties,wechooseavoting
function:
f
:
{−
1
,
1
}
(
n
·
(
n
2
)
)
→
[
m
]
suchthat,
f
=(
g
1
,..,g
(
n
2
)
)and
g
:
{−
1
,
1
}
n
→{
i,j
}
,where
i
6
=
j
and
i,j
∈
[
m
].
WewillrestrictourselvesasO’Donnelldoes,toaweakerversionwhere
m
=3
and
g
i
=
g
j
,
∀
i,j
.
Whenwedothat,wehave3pair-wiseelectionsforeachparty:[1
,
2],[2
,
3]and
[1
,
3].EachoftheseelectionsisdecidedbythesameBooleanfunction.This
schemeofchoosingawinnerbasedonpair-wiseelectionsiscalledthe
Con-
dorcetMethod
.
However,ourschemecanrunintoanissuewheneverthereisa”cycle”(or
equivalently,thewinnersoreachelectiondon’tformalatticewithamaximal
element).Thishappenswhentheoutcomesofthepair-wiseelections(ordered
lexicographically)formanequality.So,iftheoutcomeofeachelectionis:(-1,
-1,-1)or(1,1,1)thenwechoose:
i)1
>
2,2
>
3,3
>
1
ii)1
<
2,2
<
3,3
<
1
7
Theseoutcomescannotresultinawinner,sofora
CondorcetElection
to
electawinnerina3-partyelectionusingsome
g
i
toconstructthevotingfunc-
tion
f
,itshouldbethecasethat
f
6
=
NAE
3
.
ThisleadsustothestatementoftheweakversionofArrow’sTheorem,where
weassume
g
1
=
g
2
=
g
3
=
f
:
(
Arrow’sTheorem
[Exact]):Givensome
f
:
{−
1
,
1
}
n
→{−
1
,
1
}
asavoting
rule,iftherealwaysexistsawinner,then
f
=
χ
i
,forsome
i
∈
[
n
].
(
ProofSketch
):TheprooffollowsrelatingtheprobabilityofaCondorcet
winnerexistingtotheStabilityofthefunctionandarguingthatifthisproba-
bilityis1,thenalltheFourierWeightof
f
mustbeconcentratedonthe1-degree
parityfunctions.Itiseasytoseefromthisexercise,thatthisonlyhappenswith
thedictatorornegated-dictatorfunctions.
(
Lemma
):Givenavotingrule
f
:
{−
1
,
1
}
n
→{−
1
,
1
}
,Pr[
∃
CondorcetWin-
ner]=
3
4
(1
−
Stab
−
1
3
[f]
)
Theproofforthislemmaisleftasanexerciseforthereader,butbasicallyfol-
lowsfromwritingouttheFourier-Expansionofthe
NAE
3
:
{−
1
,
1
}
n
→{
0
,
1
}
functionandthenusingLinearityofExpectationtoequateittothefactthat:
Pr[
∃
CondorcetWinner]=
E
x
∼{−
1
,
1
}
n
[
NAE
3
(
f
(
x
)
,f
(
y
)
,f
(
z
))]
WethensetPr[
∃
Condorcetwinner]=1=
3
4
(1
−
Stab
−
1
3
[f]
)
Thisleadstotheconclusionthat:
1=
3
4
(1
−
Stab
−
1
3
[f]
)=
3
4
(1
−
n
X
k
=0
(
−
1
3
)
k
W
k
[f])
Forequality,weneed
W
1
[f]=1,whichisonlypossiblewhen
f
=
χ
i
or
f
=
−
χ
i
,
forsome
i
∈
[
n
].
QED
TherobustversionofArrow’sTheoremprovidestheabilitytoassertthat,if
wewanttohaveaCondorcetWinnerwithveryhighprobability,thenwemust
bevery”close”tobeingadictatorfunction.By”close”here,wemeanthat
thedot-productof
f
mustbe1-
O
(
!
)forsome
χ
i
.Theprecisestatementisas
follows:
(
Arrow’sTheorem
)
[Robust]Givensome
f
:
{−
1
,
1
}
n
→{−
1
,
1
}
asavoting
rule,suchthat,Pr[
∃
CondorcetWinner]=1-
!
,then,
f
is
O
(
!
)-closetosome
χ
i
,with
i
∈
[
n
].
Theproofforthisstatementfollowsusingthefamed
FKNTheorem
:
(
Friedgut-Kalani-NaorTheorem
):Given
f
:
{−
1
,
1
}
n
→{−
1
,
1
}
,such
that,
W
1
[f]
≥
1
−
δ
,
f
is
O
(
δ
)-closetosome
χ
i
,with
i
∈
[
n
].
8