---
title: "Randomised Algorithms and the Probabilistic Method"
description: "An algorithm allowed to flip coins can be simpler and faster than any deterministic one known, at the price of a guarantee about expectation rather than about every run. The same idea proves objects e"
canonical: https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-
source: https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Randomised Algorithms and the Probabilistic Method

An algorithm allowed to flip coins can be simpler and faster than any deterministic one known, at the price of a guarantee about expectation rather than about every run. The same idea proves objects exist by showing a random one works with positive probability.

Subject: Computing · Area: Algorithms & Data Structures · Ages 22 to 23
Page: https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-

## Ready when they can

- Separate an algorithm that is always correct and sometimes slow from one that is fast and sometimes wrong
- Compute the expected running time of a randomised routine on a worst-case input
- Use a counting argument over a random object to show something with a wanted property exists

## Lesson: Luck with a proof attached

Some objects are proven, not built. Pick one at random, and show the chance it works beats zero. A positive chance means at least one good choice sits out there, even when nobody can point at it. Counting every possibility by hand would be hopeless; one random experiment replaces the search.

The same habit runs algorithms that flip coins. A Las Vegas routine is always correct and sometimes slow: randomized quicksort averages n log n on any input, and only unlucky coins slow it. A Monte Carlo routine is fast and sometimes wrong, with a small error chance you shrink by repeating it.

**Example.** Count expected time over the coin flips on a worst-case input: the adversary picks the list, chance does the rest. For existence, bound the failure chance below one, and the bound turns chance into certainty. Random construction succeeding somewhere proves the object exists; random steps succeeding most of the time beat any careful deterministic plan.

**Tip.** Name which guarantee you surrender against a deterministic rival. Las Vegas surrenders fixed speed, Monte Carlo surrenders certainty, and both keep a precise statement about average or error instead. Never promise every run; promise the expectation or the bound.

**Recap.** Positive chance proves existence, coins buy speed or simplicity, and the guarantee moves from every run to average or error.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Probability Spaces: Sample Spaces, Events and Axioms](https://lightmysky.com/learn/mathematics/probability-spaces-sample-spaces-events-and-axioms-mt_4gsBeqJtIQ)
- [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-)
- [Big-O Notation and Orders of Growth](https://lightmysky.com/learn/computing/big-o-notation-and-orders-of-growth-mt_mkqgxhJ509)
- [Living with NP-Hardness: Approximation and Heuristics](https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u)

## Opens up

- [Concentration Bounds and a High-Probability Guarantee](https://lightmysky.com/learn/computing/concentration-bounds-and-a-high-probability-guarantee-mt_WIltjK12oW)