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&gt;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?
At each step,

if $c == 0$, set $c=1$.
Otherwise, if $c&gt;0$, either increment $c$ or decrement $c$.

Since $c$ is 0 initially, it is always true that $c\ge0$. That means, $-c\le0$ all the time.

Suppose, at some moment, $c'$ is positive. The definition of $c'$ says $c'=c$ when $a^*=v$ and $c'=-c$ otherwise. Since $-c\le0$, $c'\not=-c$. So, the situation cannot be &quot;otherwise&quot;. The situation must be other than &quot;otherwise&quot;, i.e, $a^*=v$ and, hence, $c'=c$.
We just proved that for any moment, if $c'$ is positive, then $a^*=v$ and $c=c'$ is also positive.
Now just apply the above conclusion to the very last moment.