Median trick

Key takeaways

Median trick belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Median trick to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Median trick from memory before moving on to harder problems.

Reference excerpt

The median trick is a generic approach that increases the chances of a probabilistic algorithm to succeed. Apparently first used in 1986 by Jerrum et al. for approximate counting algorithms, the technique was later applied to a broad selection of classification and regression problems. The idea of median trick is very simple: run the randomized algorithm with numeric output multiple times, and use the median of the obtained results as a final answer. For example, if an algorithm takes a set of data as input, and has sublinear runtime, then the same algorithm can be run repeatedly (or in parallel) over randomly sampled subsets of input data, and, per Chernoff inequality, the median of the results will converge to solution rapidly. Similarly, for the algorithms that are sublinear in space (e.g., counting the distinct elements of a stream), different randomizations of the algorithm (say, with different hash functions) may be used for repeated runs over the same data.

Statement Given a set of independent random variables X 1 , … , X n {\textstyle X_{1},\dots ,X_{n}} , and an unknown deterministic number Y {\textstyle Y} . Suppose that each random variable X i {\textstyle X_{i}} falls within [ Y ± ϵ ] {\textstyle [Y\pm \epsilon ]} with probability ≥ p {\textstyle \geq p} where p > 1 / 2 {\textstyle p>1/2} is a constant, then the median trick states that M e d ( X i ) ∈ [ Y ± ϵ ] {\textstyle Med(X_{i})\in [Y\pm \epsilon ]} with probability ≥ 1 − e − 2 n ( p − 1 / 2 ) 2 {\textstyle \geq 1-e^{-2n(p-1/2)^{2}}} . In other words, in order to ensure that Y ∈ [ M e d ( X i ) ± ϵ ] {\textstyle Y\in [Med(X_{i})\pm \epsilon ]} with probability ≥ 1 − δ {\textstyle \geq 1-\delta } , it suffices to use ln ⁡ 1 δ 2 ( p − 1 / 2 ) 2 {\textstyle {\frac {\ln {\frac {1}{\delta }}}{2(p-1/2)^{2}}}} samples.

References

Sources Kogler, Alexander; Traxler, Patrick (2017). "Parallel and Robust Empirical Risk Minimization via the Median Trick". Mathematical Aspects of Computer and Information Sciences. Cham: Springer International Publishing. doi:10.1007/978-3-319-72453-9_31. ISBN 978-3-319-72452-2. ISSN 0302-9743. Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. (1986). "Random generation of combinatorial structures from a uniform distribution". Theoretical Computer Science. 43. Elsevier BV: 169–188. doi:10.1016/0304-3975(86)90174-x. ISSN 0304-3975. Wang, Dan; Han, Zhu (2015). "Basics for Sublinear Algorithms". Sublinear Algorithms for Big Data Applications. Cham: Springer International Publishing. doi:10.1007/978-3-319-20448-2_2. ISBN 978-3-319-20447-5. ISSN 2191-5768.

Worked examples

Example 1 — a first encounter with Median trick

Start with the simplest possible case. Write down what Median trick claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Median trick before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Median trick ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Median trick

In research: Median trick appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Median trick in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Median trick is common in secondary-school and first-year university syllabi. It links to neighbouring topics Algorithms and data structures stubs, Statistical randomness, so understanding it makes those chapters shorter.
In everyday life: Look for Median trick outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Median trick in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Median trick means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Median trick out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Median trick in simple terms?

The median trick is a generic approach that increases the chances of a probabilistic algorithm to succeed. Apparently first used in 1986 by Jerrum et al. for approximate counting algorithms, the technique was later applied to a broad selection of classification and regression problems.

Why does Median trick matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Median trick?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Median trick.