2

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].$$ ...


Only top voted, non community-wiki answers of a minimum length are eligible