The MJRTY algorithm, proposed in $[1]$, is a popular majority voting algorithm that runs in linear time. In this article I’m not going to focus on the algorithm per se but rather on the constraints that are imposed on the algorithm. Specifically I’m going to offer an explanation for why one of the constraints on MJRTY can be removed (the authors mention this but offer no explanation). So read through the paper (here) and come back.

The paper uses a theorem-prover to prove the correctness of the Fortran implementation of MJRTY. To feed into the theorem-prover, they define the constraints imposed on the algorithm. Two constraints are of interest to us: Constraint $(3)$ and Constraint $(5)$.

A few preliminaries

$A$ is the array of elements whose majority element we want
$i$ is the current index we are looking at
$cand$ is the majority element in $A[1...i]$ (or just some element if $A[1...i]$ doesn’t have a majority)
$k$ is the number of instances of $cand$ in $A[1...i]$ which remain after pairing up dissimilar elements in $A[1...i]$ and cancelling them out, according to the MJRTY algorithm.

Constraint $(3)$

The number of times $cand$ occurs in $A$ from $1$ through $i$ is at least $k$.

Constraint $(3)$ says that there are at least $k$ instances of $cand$ in $A[1...i]$, i.e., $k$ is either an underestimation or correct estimation of the number of instances of $cand$. It is an underestimation when some instances of $cand$ have been paired up with a dissimilar element and have not contributed to $k$.

Constraint $(5)$

For all $x$ other than $cand$, the number of times $x$ occurs in $A$ from $1$ through $i$ is no greater than $\frac{(i-k)}{2}$.

Constraint $(5)$ follows obviously when we split the elements of $A[1...i]$ into two groups (as they do in $[1]$), the “unanimous group” and the “majority-free group”. The unanimous group has the $k$ instances of $cand$ which haven’t been paired up (so they unanimously vote for $cand$) and the majority-free group has the remaining elements. There are $i-k$ elements in the majority-free group and since each element here must be paired up with a dissimilar element, there can be no more than $\frac{(i-k)}{2}$ elements of the same kind.

We can rephrase constraint $(5)$ as

Let $s$ be the element, other than $cand$, which has the most number of instances in $A[1...i]$ (if $cand$ is the majority element of $A[1...i]$ then $s$ will be the element with the second most number of instances in $A[1...i]$, otherwise $s$ will be the element with the most instances). The number of instances of $s$ is $\le \frac{(i-k)}{2}$. If there are two or more elements which satisfy the condition for $s$ then this must apply to all of them.

This phrasing is equivalent to constraint $(5)$ since, by the definition of $s$, it has more instances than any other element in $A[1...i]$ (leaving out $cand$). If s has less than $\frac{(i-k)}{2}$ instances so will the others. From here on we use this rephrasing rather than the original constraint.

$[1]$ provides a Fortran implementation of MJRTY in which they perform one small optimization over the algorithm. Once the array has been scanned and the so-called “pairing” phase is done, the program checks the value of $k$ to see if it is $>\frac{n}{2}$. If it is then they skip the “counting” phase since $k$, a possible underestimation of the number of instances of $cand$, already tells us that there are at least $\frac{n}{2}+1$ instances of $cand$. This trick is important later.

Using the constraints defined, $[1]$ proves that the Fortran implementation of MJRTY is correct. However they state this

Nevertheless, if one modifies the code so that $k$ is not tested against $\frac{n}{2}$ before entering the counting phase, one can omit conjunct $(3)$ of this invariant. That is, unless the program exits early when $k$ exceeds $\frac{n}{2}$, a demon within the first loop is permitted to raise $k$ above the count of $cand$ (within the constraint imposed by $(5)$) without causing the algorithm to perform incorrectly. We do not know how to interpret this lack of constraint.

Even the authors can’t tell us why constraint $(3)$ can be removed while adhering to constraint $(5)$. This demon must know something we don’t.

Interpreting

One thing we need to get out of the way is why $k$ should not be tested against $\frac{n}{2}$ if we wish to remove constraint $(3)$. This is because normally there are at least $k$ instances of $cand$. If $k>\frac{n}{2}$ then there must be at least $\frac{n}{2}+1$ instances of $cand$ so it is guaranteed to be the majority element and we don’t have to perform the counting phase to verify this (the “trick” we discussed before). But if we raise the value of $k$ (without affecting the result of the algorithm) then we can no longer be sure that there are at least $k$ instances of $cand$ and so we must never skip the counting phase.

Now onto the real deal. Why can we remove constraint $(3)$ while adhering to constraint $(5)$?

While the algorithm is executing and has just examined position $i$ in $A$, $cand$ either

holds the majority in element in $A[1...i]$ if $A[1...i]$ has a majority element
holds some element if $A[1...i]$ does not have a majority element

Let

$m$ be the majority element in $A$
$s$ be the element which we defined in the rephrasing of constraint $(5)$.
$N(x)$ denote the number of instances of $x$ in $A[1...i]$.

We say an array $B$ is equivalent in terms of majority to the array $A$ if $B$ has the same majority element as $A$ (or no majority element if $A$ has none).
At any point of the algorithm we can create an array $B$ by replacing all elements in $A[1...i]$, other than $m$, by $cand$. Created this way, $B$ will be equivalent in terms of majority to $A$ since we are not replacing any instances of $m$ and $m$ still remains the majority element. Let $k'$ be the value of $k$ we would get by applying MJRTY on $B[1...i]$. Since we are replacing other elements with $cand$ in $A[1...i]$ to get $B[1...i]$ we have $k'\ge k$. They will be equal if there are no elements in $A[1...i]$ other than $m$ and $cand$.

Now we can let the algorithm continue its execution from position $i$ in $B$ and it will yield $m$ itself as the majority element. Converting $A$ to $B$ and continuing on $B$ is equivalent to simply raising the value of $k$ to $k'$ and continuing on $A$. This is why the value of $k$ can be raised without affecting the result of the algorithm. Depending on how many replacements we can perform, $k'$ may be more than $N(cand)$ in which case constraint $(3)$ would need to be removed to allow this.

This method may actually let us raise the value of $k$ by more than what removing constraint $(3)$ while adhering to constraint $(5)$, will allow. To see why let’s consider the two possibilities

$s=m$
In this case the method I have described degenerates to removing constraint $(3)$. Consider the array $B$ that we constructed. In $B[1...i]$ we pair each instance of $m$ with an instance of $cand$ and the remaining instances of $cand$ contribute to $k'$. $N(m) = \frac{(i-k')}{2}$ since there are $i-k'$ paired elements and half of them will be instances of $m$. So we are adhering to constraint $(5)$ since $N(s) = \frac{(i-k')}{2} => N(s) \le \frac{(i-k)}{2}$. We are able to increase $k$ to $k' = i - 2 \times N(s)$.
$s \ne m$
Considering array $B$ again, we pair each instance of $m$ with an instance of $cand$ and the remaining instances of $cand$ contribute to $k'$. However this time we are not adhering to constraint $(5)$ since we are replacing $s$ by $cand$. Since, apart from $cand$, $B$ only has instances of $m$, we require that $m$ (and not $s$) must pair with instances of $cand$. And since $N(m) \le N(s)$ (equal if $m$ and the element chosen for $s$ have the same number of instances) and $N(m) = \frac{(i-k')}{2}$ we get $N(s) \ge \frac{(i-k')}{2}$. So $N(s)$ may be $>\frac{(i-k)}{2}$ and we may violate constraint $(5)$. In this case we have increased $k$ by more than if we had adhered to constraint $(5)$. We are able to increase $k$ to $k' = i - 2 \times N(m)$. Adhering to constraint $(5)$ would have let us increase $k$ to just $k' = i - 2 \times N(s)$.

In either case we get $k' = i - 2 \times N(m)$. Removing constraint $(3)$ permits us to raise $k$ above $N(cand)$. But this can only happen when $k'>N(cand) => i - 2 \times N(m)>N(cand) => N(m) < \frac{i - N(cand)}{2}$.

Note: Sometimes we can do even better than this (click to reveal)

We can increase $k$ past the previous method if we know $A[i+1...n]$. In this case we can even replace some instances of $m$ with $cand$ in $B[1...i]$. We just have to make sure that $B[i+1...n]$ has the correct elements to give the right answer. For example: $$A:\ [a\ e\ c\ e\ f\ |\ e\ e\ e\ b\ e\ e\ e\ d]\quad i = 5,\ cand = f,\ k = 1,\ m = e$$ We can replace everything in $A[1...5]$, even $e$, to get $$B:\ [f\ f\ f\ f\ f\ |\ e\ e\ e\ b\ e\ e\ e\ d]\quad i = 5,\ cand = f,\ k' = 5, m = e$$ Continuing from $B$ will still give us $e$ as the final result even though we replaced $e$ with $f$. Note that it is not just the number of instances of $m$ in $B[i+1...n]$ but also the order that we have to take into account. For example if we had $$A:\ [a\ e\ c\ e\ f\ |\ e\ e\ e\ e\ e\ b\ e\ d]\quad i = 5,\ cand = f,\ k = 1,\ m = e$$ Replacing we would get $$B:\ [f\ f\ f\ f\ f\ |\ e\ e\ e\ e\ e\ b\ e\ d]\quad i = 5,\ cand = f,\ k' = 5,\ m = e$$ But this would give the wrong final result, $d$. So this method is finicky and requires us to know $A[i+1...n]$ completely. But the method described earlier only requires us to know $m$ and does not need any information on $A[i+1...n]$.

We Did It! ….. Right?

We’ve managed to do better than what the paper tells us we can by removing constraint $(3)$. We did it!
There’s a tiny problem:
We assumed that we know the majority element $m$, the very thing the algorithm is trying to find! 😑

In reality we don’t know $m$ and so we can’t calculate $k' = i - 2 \times N(m)$. Raising $k$ to $k' = i - 2 \times N(m)$ would have allowed us to continue the algorithm without changing the result. But in the absence of $N(m)$ the best we can do is to raise $k$ to $k' = i - 2 \times N(s)$. This is guaranteed to not change the result since $N(m) \le N(s)$ and so $i - 2 \times N(m) \ge i - 2 \times N(s)$, i.e., if raising to $i - 2 \times N(m)$ won’t affect the result, raising it to a smaller value ($i - 2 \times N(s)$) certainly won’t. Raising $k$ to $k' = i - 2 \times N(s)$ gives $N(s) = \frac{(i-k')}{2}$ and so constraint $(5)$ is satisfied even after raising $k$ to $k'$.
Finally, removing constraint $(3)$ permits us to raise $k$ above $N(cand)$. But this can only happen when $k'>N(cand) => i - 2 \times N(s)>N(cand) => N(s) < \frac{i - N(cand)}{2}$.

We now know why we can remove constraint $(3)$ by raising $k$ while adhering to constraint $(5)$. The demon’s got nothing on us.

If you see any issues please let me know by filing an issue at https://github.com/GaneshBannur/ganeshbannur.github.io/issues.

References

$[1]$ Boyer, Robert S., and J. Strother Moore. “MJRTY—a fast majority vote algorithm.” Automated reasoning: essays in honor of Woody Bledsoe. Dordrecht: Springer Netherlands, 1991. 105-117.