I have been studying a streaming algorithm to determine if there is a majority element in a stream. But am confused by a proof for it.
The algorithm works as follows. You keep one counter $ c$ and a store for one item called $ a^*$ . When a new item arrives, first you check if $ c == 0$ . If so you set $ c=1$ and $ a^*$ stores the arriving item. Otherwise, if $ c>0$ and the arriving item is the same as $ a^*$ you increment $ c$ or decrement $ c$ if not.
If there is a majority element then it will be stored in $ a^*$ at the end.
In the notes from http://www.cs.toronto.edu/~bor/2420f17/L11.pdf there is a proof of this fact (called simpler proof).
I can see that if there is a majority item then $ c’$ will be positive at the end of the stream. But:
- How do we know that $ a^*$ will hold the majority item at the end?
- Does $ c’$ being positive imply that $ c$ will be positive too?