A strict majority is an item appearing more than half the time. Counting every distinct label works, but a large or streaming alphabet may make a full frequency table expensive. The Boyer–Moore majority-vote algorithm stores only a candidate and a counter. Matching items support the candidate; different items cancel one unit. If a strict majority exists, it cannot be completely cancelled by all other items combined. Mathematics matters because a pairing invariant proves that one pass finds the only possible majority candidate, while a separate verification pass distinguishes a real majority from a survivor in data with no majority.
The practical search question is not simply “what is this named method?” but “which mathematical structure makes the method work, what does it guarantee, and what evidence would show that it is a poor choice?” This article keeps those questions together so students can connect mathematics education with computing, engineering, data reasoning and careful everyday decisions without turning one technique into a career promise.
Quick navigation: Why it matters · Mechanism · Worked example · Deeper ideas · Investigations · Limits · Learning route · Parent guidance · FAQs · Sources
Why this mathematics matters
Mathematics is important here because it turns an apparently visual or computational trick into a chain of reasons. The representation tells us what information is kept. The equation or invariant explains each legal step. The complexity analysis describes the work. The boundary conditions say when a conclusion should not be trusted. That combination is a practical form of problem-solving literacy.
A strong learner should be able to move in both directions: from a real task to a mathematical model, and from a formal guarantee back to its real meaning. Naming an algorithm is not enough. The useful achievement is to explain why the next operation is valid, check a small instance independently, and notice which assumptions the implementation has added.
Source: J Strother Moore’s author-maintained page for the MJRTY majority algorithm.
Primary or implementation reference: Boyer and Moore’s majority-vote chapter in Automated Reasoning.
How the mechanism works
Start with count zero. For each item x, if count is zero, set candidate=x and count=1. Otherwise increment count when x equals the candidate and decrement it when x differs. At the end, candidate is a necessary candidate, not automatically a certified majority. Count its occurrences in a second pass and accept it only when occurrences exceed n/2. The algorithm uses O(n) comparisons and O(1) machine words of auxiliary state in the usual random-access model. When the stream cannot be replayed, verification requires retained data, an external count, or a problem promise that a majority exists.
Imagine repeatedly deleting pairs of unequal items. Removing one copy of a strict majority and one non-majority item preserves the fact that the majority has more copies than all rivals combined. The counter represents uncancelled copies of the current candidate after processing a prefix. Whenever the counter reaches zero, that prefix can be partitioned into unequal pairs and has no unresolved survivor. Therefore a strict majority of the full sequence, if one exists, must be the final candidate. The proof does not say the final candidate is the mode, nor that a majority exists; only direct counting establishes the threshold.
Keep a four-column notebook labelled object, rule, guarantee and caveat. In the first column name the inputs and stored state. In the second write one update precisely. In the third state what remains true after the update. In the fourth record a tie, approximation, domain restriction or hardware assumption. This routine prevents symbols from drifting away from their meaning.
Worked example and core calculations
Process [A,B,A,A,C,A,A]. Read A: candidate A, count 1. Read B: count 0 after cancelling A with B. Read A: choose A, count 1. Read A: count 2. Read C: count 1. Read A: count 2. Read A: count 3. The candidate is A. A second pass counts five As among seven items, and 5>7/2, so A is a strict majority. Now try [A,B,C]: the procedure may finish with C, but C appears once and 1 is not greater than 1.5. The second pass correctly reports that no strict majority exists.
How to audit the calculation
- Recompute every intermediate value directly from the definition.
- Keep labels, indices, signs, units and normalisation visible.
- Test a case with a known exact answer.
- State tie rules, random seeds, tolerances and boundary conventions.
- Compare with a slower transparent baseline or trusted implementation.
- Separate agreement of numbers from suitability of the real-world model.
Small examples are not childish; they are diagnostic instruments. A five-line trace can reveal a reversed inequality, a missing scale factor or an inconsistent label convention before a large dataset hides the same error behind plausible output.
Four deeper ideas
Cancellation preserves an overwhelming surplus
A strict majority has more copies than every other label combined, so unequal pairs cannot remove all of it.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Did you know? The first-pass counter is not the frequency
It records a net uncancelled balance under the current pairing process, not the candidate’s total occurrences.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Candidate selection and certification are different tasks
The first pass narrows the answer to one possibility; the second pass checks the original definition.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Constant state has a replay cost
Low memory does not make verification free when a one-way stream cannot be read again.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Twelve practical investigations
1. Clear majority
Use [A,B,A,A,C,A,A]. Trace candidate and count.
What the mathematics reveals: Unequal pairs leave A. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Verify five of seven. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. No majority
Use [A,B,C]. Run both passes.
What the mathematics reveals: A survivor need not cross the threshold. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Never skip certification. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. Exact half
Use [A,A,B,B]. Count the candidate.
What the mathematics reveals: Half is not a strict majority. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Use > n/2, not ≥. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. All equal
Use [Q,Q,Q,Q]. Increment throughout.
What the mathematics reveals: No cancellation occurs. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Still define empty input. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Late majority
Place most majority copies near the end. Trace resets.
What the mathematics reveals: Order changes the path but not the guarantee. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Verification remains order-independent. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. Alternating prefix
Use A,B repeatedly then several As. Pair the prefix.
What the mathematics reveals: Balanced prefixes can vanish. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not interpret resets as errors. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Text labels
Use differently cased words. Normalise or keep distinct.
What the mathematics reveals: Equality is a modelling decision. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Record preprocessing. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Non-replayable stream
Allow one pass only. List evidence available.
What the mathematics reveals: Candidate and certificate are separate. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Store a count source or promise. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. Weighted votes
Give observations unequal weights. Compare with the unweighted rule.
What the mathematics reveals: The classic invariant assumes unit copies. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Derive a weighted method separately. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Several heavy hitters
Use threshold one quarter. Compare Misra–Gries.
What the mathematics reveals: One counter is insufficient. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Threshold controls counter count. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Frequency-table oracle
Count every label on small data. Compare the result.
What the mathematics reveals: A transparent baseline validates the stream algorithm. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Match strictness exactly. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Property test
Generate random sequences. Check any true majority equals the candidate.
What the mathematics reveals: The necessary-candidate theorem is testable. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Retain failures and equality rules. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
The classic method concerns a strict threshold greater than n/2. It does not directly find the mode, all frequent items, weighted majorities or items above a smaller threshold. Misra–Gries generalises the cancellation idea with several counters. Equality needs a stable, declared definition; floating representations, normalised text and composite records may complicate it. A second pass is necessary unless existence is promised. In distributed or parallel settings, partial summaries cannot always be merged by simply voting among local winners. A majority in collected data need not represent fairness, truth, preference intensity or a causal conclusion.
Five misconceptions to challenge
- The returned candidate is always a majority: It must be verified unless existence is guaranteed.
- The counter equals the candidate frequency: It is a cancellation balance.
- The algorithm finds the most common item: A mode may exist without exceeding half.
- One pass always solves the complete problem: Certification commonly needs a replay.
- Majority means at least half: The standard strict majority condition is greater than half.
Another broad misconception is that advanced mathematics automatically creates intelligence, admission, income or employment. It does not. Deliberate study can strengthen modelling, abstraction, calculation and explanation, while real pathways also depend on interests, communication, domain knowledge, opportunities and circumstances outside one topic.
A learning route for students
Move from a visible trace to a symbolic rule, then to code and critique. For every step below, prepare three pieces of evidence: a correct hand example, a boundary or failure case, and a short explanation using the relevant invariant. Do not advance merely because software returned a number.
Step 1: Define a strict majority
Begin with the smallest non-trivial instance that lets you define a strict majority. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 2: Trace candidate and counter
Begin with the smallest non-trivial instance that lets you trace candidate and counter. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 3: Model unequal-pair cancellation
Begin with the smallest non-trivial instance that lets you model unequal-pair cancellation. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 4: State the loop invariant
Begin with the smallest non-trivial instance that lets you state the loop invariant. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 5: Separate candidate from certificate
Begin with the smallest non-trivial instance that lets you separate candidate from certificate. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 6: Perform threshold verification
Begin with the smallest non-trivial instance that lets you perform threshold verification. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 7: Handle exact-half cases
Begin with the smallest non-trivial instance that lets you handle exact-half cases. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 8: Analyse streaming memory
Begin with the smallest non-trivial instance that lets you analyse streaming memory. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 9: Define equality consistently
Begin with the smallest non-trivial instance that lets you define equality consistently. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 10: Compare with a frequency table
Begin with the smallest non-trivial instance that lets you compare with a frequency table. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
A four-week practice plan
- Week 1 — vocabulary and diagrams: define each object, redraw the mechanism and reproduce the worked example.
- Week 2 — equations and manufactured tests: derive the key relation and test inputs with known answers.
- Week 3 — implementation and evidence: use a trusted library, record parameters and compare with a transparent baseline.
- Week 4 — transfer and critique: apply the method to a new context, report limits and identify when a different method is better.
Guidance for parents and educators
Ask “what stays true?” and “what could make this conclusion fail?” before asking for speed. Invite the student to draw the input and output, estimate the result and locate the first step that disagrees with a reference. These prompts reveal conceptual understanding more clearly than memorised terminology.
Advanced enrichment should sit beside secure school foundations in algebra, functions, geometry, statistics and computational thinking. It need not accelerate a student into a fixed career identity. A healthy goal is curiosity with discipline: the learner becomes comfortable reading unfamiliar notation, checking an example, revising a model and communicating uncertainty.
Evidence prompts for a useful conversation
- Which quantity is observed and which is inferred?
- Which step saves work, and why is it allowed?
- Is the claim exact, approximate, probabilistic or empirical?
- What units and conventions are in use?
- Which input makes the method struggle?
- What simple baseline could check the answer?
- What would count as evidence that the parameters are poor?
Mini-project assessment
A strong mini-project contains the original question, a small reproducible dataset, a hand-worked example, code or a spreadsheet trace, at least one boundary test, a comparison with a baseline, and a paragraph on limits. Assess the reasoning trail as well as the final output. Repairing a model after a surprising result is valuable mathematical progress.
Six evidence checks for a finished project
Check 1: Define a strict majority
Ask the student to demonstrate how to define a strict majority without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 2: Trace candidate and counter
Ask the student to demonstrate how to trace candidate and counter without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 3: Model unequal-pair cancellation
Ask the student to demonstrate how to model unequal-pair cancellation without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 4: State the loop invariant
Ask the student to demonstrate how to state the loop invariant without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 5: Separate candidate from certificate
Ask the student to demonstrate how to separate candidate from certificate without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 6: Perform threshold verification
Ask the student to demonstrate how to perform threshold verification without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Frequently asked questions
What does Boyer–Moore majority vote return?
The only possible strict-majority candidate.
Does it prove that a majority exists?
No; count the candidate in a second pass.
What is a strict majority?
More than half of all items.
What is the runtime?
O(n).
What auxiliary memory does it use?
O(1) machine words for one candidate and one counter.
Is the counter the total frequency?
No, it is a net cancellation balance.
Does it find the mode?
Not when the mode is at most half.
Can it work on a stream?
It can select a candidate, but verification may require replay or extra evidence.
What generalises it to lower thresholds?
Algorithms such as Misra–Gries use multiple counters.
What should students know first?
Counting, inequalities, sequences, invariants and proof by cancellation.
Useful next reading and sources
Source: J Strother Moore’s author-maintained page for the MJRTY majority algorithm.
Source: Boyer and Moore’s majority-vote chapter in Automated Reasoning.
Related eduKateSG reading: Misra–Gries counters and frequent items.
Related eduKateSG reading: Vose’s alias method and probability tables.
Related eduKateSG reading: Havel–Hakimi degree sequences.
Read sources with a question in mind: which definition, theorem, default or limitation is being supported? An authoritative link is useful evidence, but it does not replace a worked calculation or a clear statement of how the source applies to the example.
A cheerful final thought
Mathematics becomes friendlier when every symbol has a job and every claim has a boundary. Start small, make the state visible, test the awkward case, and celebrate the moment when a pattern becomes explainable. That is the practical benefit of learning mathematics: not certainty about every future, but a growing ability to ask better questions and build trustworthy answers.