Lower bounds for randomized frequency estimation algorithms

Consider a stream of elements $s_1s_2\ldots s_N$. A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?

It is well known that answering such queries to within a one-sided additive error of $N/(k+1)$ requires at least $k$ counters by any deterministic algorithm (see here).

Assume we allow randomized algorithms for the task.

Which lower bounds (on the number of counters required) can we derive on a randomized algorithm which satisfies $$f_x -N\epsilon\le\mathbb E(\text{query}(x))\le f_x,$$ where the expectancy is over the algorithm internal randomness?

In particular, the Majority algorithm (see 1 and [2]) is able to find a majority item in the stream using a single counter.

Is there a randomized algorithm which is able to identify, using a single counter, an element arriving at least $N(0.5-c)$ of the time for some fixed $c>0$ (with probability larger than 1/2)?

1] R. Boyer and J. Moore. A Fast Majority Vote Algorithm. Technical Report 1981-32, Institute for Computing Science, University of Texas, Austin, 1981.

2] M. Fischer and S. Salzberg. Finding a Majority Among N Votes: Solution to Problem 81-5. Journal of Algorithms, 3:376–379, 1982.

• Setting $N = 1/\epsilon$, there is an easy reduction from the Index problem which gives $\Omega(1/\epsilon)$ space complexity. Commented Dec 6, 2015 at 5:25
• Thanks @SashoNikolov. I'm actually interested in the more fine-grained lower bound (i.e. not asymptotically). As in my second question, it's interesting to see if we can find elements appearing less than half of the stream with a single counter. I'm not sure any improvement over deterministic algorithms is possible, all I could come up with was a $0.5N-O(\sqrt N)$ identification using a single counter.
– R B
Commented Dec 6, 2015 at 8:43