approximate_sampling_to_approximate_counting (1573B)
1 # Approximate sampling to approximate counting 2 3 ## For independent set 4 5 This file uses the notation of [markov_chain_monte_carlo]. It focuses on the problem of [counting] [independent_set], i.e., computing the probability that a random subset of vertices is an independent set. 6 7 ### With exact sampling 8 9 First assume we can do [sampling] exactly. 10 11 The probability that we want to compute is pi(emptyset) = 1/Z, because it gives us Z which is the quantity for which we want to do [counting] 12 13 We can write pi(emptyset) as Pr(X1=0) Pr(X2=0|X1=0) ... 14 15 So if we can approximate each [marginal_distribution] then we can approximate pi(emptyset) 16 17 We can marginalize in the following way: to set a vertex to 0, we just remove the vertex! A kind of [self_reducibility]. Note that removing a vertex does not increase Delta. 18 19 Further, we know that the marginals have probability at least 1/(1+lambda), hence sampling (on the graph with removed vertices, seeing in which proportion of the samples we find the vertex of interest) gives an [approximation_additive] which thanks to the lower bound is an [approximation_multiplicative]. 20 21 ### With approximate sampling 22 23 I think the same algorithm works if sampling is approximately uniform 24 25 ## In general 26 27 In general (for an arbitrary self-reducible problem): instead of picking the prefix 0 ... 0, choose the prefix with the choice that gives the most outcomes. This ensures that no denominator gets to zero, and also ensures a lower bound of 1/2 (give or take epsilon) on each marginal 28 29 Up: [sampling_approximate], [counting_approximate]