Confused by proof of correctness of Majority

Question

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?

Answer 1

At each step,

• if $c == 0$, set $c=1$.
• Otherwise, if $c>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 "otherwise". The situation must be other than "otherwise", 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.