The Majority Event In Streaming Data

An interesting (and idiosyncratic) streaming algorithm

Imagine a possibly unbounded stream of incoming symbols. At a particular point, say there is some symbol that has occurred more than 50% of the time till then. We call it a majority symbol. It is obviously unique if it exists.

This post discusses an efficient streaming algorithm that “half” solves this problem. If the stream has a majority symbol, it finds it. (This is equivalent to saying that if the algorithm outputs NO, the stream for sure doesn’t…