# Confused by proof of correctness of Majority

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?