How much memory is needed for counting distinct elements in a stream exactly with high probability
You can do $O(\log \frac n\epsilon)$ space if you only want an approximation.
The main idea is that you use the random hash function $h$ to do the same protocol as in the Goldwasser-Sipser Set Lowerbound (which you can find, e.g., in the Arora-Barak book).
So you pick a target $y$ and observe whether $h(x_i)$ holds for any $i$.
If the sequence is diverse, then whp. you can find such a $i$, otherwise you cannot.
To increase the probability of success, you can pick $O(\log \frac 1\epsilon)$ different $y$'s of length $O(\log n)$ and do the protocol for each.

If you want an exact answer, then more precise calculations are needed.
I think $O(polylog \frac n\epsilon)$ space might be still enough, but I might be wrong.