A website, sensor or transaction system may receive far more items than memory can store. Yet the practical question is often not every exact frequency, but which items could be genuinely frequent. The Misra–Gries algorithm processes a stream once using only a fixed number of labelled counters. With k−1 counters, every item occurring more than n/k times is guaranteed to appear among the final candidates. The recorded counter is a lower estimate rather than an exact total; an optional second pass can verify candidate frequencies. Mathematics matters because a cancellation argument converts strict memory limits into a precise deterministic guarantee.
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: Misra and Gries’s 1982 “Finding repeated elements” paper.
Primary or implementation reference: Princeton-hosted copy of the Misra–Gries paper.
How the mechanism works
Choose an integer k≥2 and maintain at most k−1 item–count pairs. For each stream item: if it already has a counter, increment it; otherwise, if a counter slot is free, insert it with count one; otherwise decrement every stored counter by one and delete zeros. That full decrement can be viewed as cancelling a group of k distinct stream occurrences: the new untracked item plus one occurrence from each of the k−1 tracked labels. After the stream, return the remaining labels as candidates. To report exact frequencies, scan the original data again and count only those candidates.
Let n be stream length and D the number of full decrement steps. Each such step accounts for k cancelled occurrences, so D≤n/k. For any item x with true frequency f(x), its final stored count c(x) never exceeds f(x), and f(x)−D≤c(x) when absent candidates are treated as count zero. Therefore f(x)−c(x)≤D≤n/k. If f(x)>n/k, x cannot finish absent, because absence would imply f(x)≤D≤n/k. The guarantee is one-sided: all items above the threshold are included, but some candidates may be false positives and require verification.
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,A,B,A,C,B,A,D,E,A,B,A with k=4, so at most three counters are stored. The first seven items build A:4, B:2, C:1. D arrives when all three slots are full, so cancel one from A, B and C and discard D, leaving A:3, B:1. E then takes the free slot. The final A,B,A updates produce A:5, B:2, E:1. The true counts are A=6, B=3, C=D=E=1. Because n/k=3, A is guaranteed as it occurs more than three times; B sits exactly at the boundary and is a candidate but not covered by the strict heavy-hitter guarantee. A second pass recovers the exact counts.
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 is the proof device
A simultaneous decrement pairs k distinct occurrences, limiting how often any one item’s count can be hidden.
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.
Candidates are not certified heavy hitters
The first pass guarantees recall above the threshold, but surviving labels can have lower true frequencies.
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.
The threshold is strict
With k−1 counters, the theorem guarantees items with frequency greater than n/k; equality alone is not enough.
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.
Streaming changes what “answer” means
When exact storage is impossible, a useful contract separates candidate discovery, bounded error and optional verification.
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. Worked stream
Trace A,A,B,A,C,B,A,D,E,A,B,A. Recover A,B,E as candidates.
What the mathematics reveals: Counters encode cancellations. 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: Only A has the strict guarantee. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. Boundary frequency
Construct an item occurring exactly n/k times. Try several orders.
What the mathematics reveals: Equality need not guarantee survival. 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 the theorem’s strict inequality. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. False positive
End with a rare item in a free slot. Compare candidate and true count.
What the mathematics reveals: Candidates need verification. 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: Survival is not certification. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. Order change
Permute one multiset. Compare final counters.
What the mathematics reveals: Counts can differ while the guarantee remains. 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 treat state as canonical. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Second pass
Replay only candidate labels. Produce exact frequencies.
What the mathematics reveals: Verification is cheap when replay is available. 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: Some streams cannot be replayed. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. Memory trade-off
Increase k. Plot counters and threshold.
What the mathematics reveals: More memory lowers the guaranteed frequency cutoff. 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: Include label overhead. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Uniform stream
Feed many equally rare labels. Observe repeated cancellations.
What the mathematics reveals: No heavy hitter is a valid result. 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: Empty output is informative. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Dominant item
Make one label exceed half the stream. Use k=2.
What the mathematics reveals: Majority voting is a special case. 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: Frequency still needs verification. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. Token normalisation
Compare “Math” and “math”. Apply a declared rule.
What the mathematics reveals: Data modelling changes frequency. 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: Normalisation can merge distinct meanings. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Weighted events
Give events different weights. Compare a weighted variant.
What the mathematics reveals: Basic unit updates no longer fit directly. 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 silently repeat huge weights. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Distributed logs
Split a stream across machines. Study mergeable summaries.
What the mathematics reveals: Composition needs a proven rule. 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: Naive counter addition is unsafe. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Adversarial audit
Arrange cancellations deliberately. Check the n/k error bound.
What the mathematics reveals: Guarantees hold regardless of order. 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: Implementation bugs can violate them. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
Misra–Gries addresses insertion-only streams in its basic form. It does not by itself return exact counts, ranks, quantiles or distinct-item estimates. The k−1 counter convention must not be confused with implementations that name the parameter by number of counters. A second pass is impossible if the stream cannot be replayed unless another store exists. Weighted updates, deletions, distributed merging and sliding windows need carefully specified variants. Hash-table operations and item identifiers consume real memory beyond the abstract counter count. Very small k produces a coarse threshold. The method is deterministic, but input preprocessing, tokenisation and label normalisation still shape what counts as the same item.
Five misconceptions to challenge
- The final counter is the exact frequency: It is generally a lower estimate.
- Every surviving candidate exceeds n/k: False positives are possible.
- An item occurring exactly n/k times is guaranteed: The standard guarantee is strictly greater than n/k.
- The algorithm stores only numbers: Each counter also needs an item label and implementation overhead.
- Streaming guarantees remove the need for data definitions: Tokenisation and identity rules still determine the stream.
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: Trace bounded counters
Begin with the smallest non-trivial instance that lets you trace bounded counters. 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: Prove the cancellation bound
Begin with the smallest non-trivial instance that lets you prove the cancellation bound. 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: Distinguish candidates from answers
Begin with the smallest non-trivial instance that lets you distinguish candidates from answers. 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: Apply a strict threshold
Begin with the smallest non-trivial instance that lets you apply a strict threshold. 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: Verify counts in a second pass
Begin with the smallest non-trivial instance that lets you verify counts in a second pass. 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: Analyse memory–accuracy trade-offs
Begin with the smallest non-trivial instance that lets you analyse memory–accuracy trade-offs. 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: Test order sensitivity
Begin with the smallest non-trivial instance that lets you test order sensitivity. 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: Define stream item identity
Begin with the smallest non-trivial instance that lets you define stream item identity. 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: Compare deterministic sketches
Begin with the smallest non-trivial instance that lets you compare deterministic sketches. 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: State insertion-only assumptions
Begin with the smallest non-trivial instance that lets you state insertion-only assumptions. 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: Trace bounded counters
Ask the student to demonstrate how to trace bounded counters 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: Prove the cancellation bound
Ask the student to demonstrate how to prove the cancellation bound 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: Distinguish candidates from answers
Ask the student to demonstrate how to distinguish candidates from answers 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: Apply a strict threshold
Ask the student to demonstrate how to apply a strict threshold 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: Verify counts in a second pass
Ask the student to demonstrate how to verify counts in a second pass 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: Analyse memory–accuracy trade-offs
Ask the student to demonstrate how to analyse memory–accuracy trade-offs 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 problem does Misra–Gries solve?
It finds a small candidate set containing every sufficiently frequent item in a stream.
How many counters are used?
A common formulation uses k−1 counters for the n/k threshold.
What happens when all counters are occupied?
Every stored count is decremented and zero counts are removed.
Why does cancellation work?
Each full decrement accounts for k distinct occurrences, limiting hidden frequency.
Are stored counts exact?
No; they are lower estimates.
Are there false negatives above the threshold?
No, for frequencies strictly greater than n/k under the stated model.
Can there be false positives?
Yes.
How are exact counts obtained?
Replay the stream and count the final candidates.
Is the method randomised?
No, the basic algorithm is deterministic.
What should students know first?
Frequencies, inequalities, dictionaries and invariants.
Useful next reading and sources
Source: Misra and Gries’s 1982 “Finding repeated elements” paper.
Source: Princeton-hosted copy of the Misra–Gries paper.
Related eduKateSG reading: Reservoir sampling for unknown streams.
Related eduKateSG reading: Fisher–Yates uniform shuffling.
Related eduKateSG reading: Comparing percentages fairly.
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.