# Tag Info

We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it. A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\... 1 You can compute the average using linearity of expectation. Let the random variable$X$denote the number of elements that are retained. Let$X_i$be an indicator r.v. that is 1 if the$i$th element is retained, or 0 otherwise. Then$X = X_1+\dots + X_n\$, so $$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$ ...