Gibbs Distribution Gibbs distribution u:o∈[g]' network GE): u(a)f(os) (f,S)∈F each(f,S)∈F is a local constraints(factors): f:[gs→R≥o SC Vwith diamG(S)=O(1)
Gibbs Distribution • Gibbs distribution µ : ∀σ∈[q]V network G(V,E): S µ() / Y (f,S)2F f(S) is a local constraints (factors): f : [q] S ! R0 S ⊆ V with diamG(S) = O(1) each (f,S) 2 F
Locality of Counting Sampling For Gibbs distributions(defined by local factors): Correlation Inference: Sampling: Decay: SSM local approx. local approx. inference sampling with additive error easy O(log2 n)factor local approx. local exact inference sampling with multiplicative error distributed Las Vegas sampler
Locality of Counting & Sampling SSM Correlation Decay: Inference: Sampling: local approx. sampling local approx. inference local approx. inference local exact sampling with additive error with multiplicative error For Gibbs distributions (defined by local factors): O(log2 n) factor easy distributed Las Vegas sampler
Locality of Sampling Correlation Inference: Sampling: Decay: SSM local approx. local approx. inference sampling each y can compute a return a random Y=(Y)vEr within O(log n)-ball whose distributionu s.t.drv(ag,8)≤pom drv(n,W≤poa sequential O(log n)-local procedure: scan vertices in V in an arbitrary order v1,v2,...,Vn for i=1,2,...,n:sample Yv;according tov 、Yu1,Ywi-1
Locality of Sampling Inference: Sampling: local approx. sampling local approx. inference SSM Correlation Decay: sequential O(log n)-local procedure: µ ˆ each v can compute a v within O(log n)-ball s.t. • scan vertices in V in an arbitrary order v1, v2, …, vn • for i=1,2, …, n: sample Y according to vi µ ˆ Yv1 ,...,Yvi1 vi return a random Y = (Yv)v∈V whose distribution µ ˆ ⇡ µ dTV (ˆµ, µ) 1 dTV poly(n) (ˆµ v , µ v ) 1 poly(n)