The EM Algorithm: An Intuitive Guide with the Coin Toss Example

Imagine you're a casino inspector. You suspect a dealer has been switching between two biased coins, but you only have records of the outcomes - not which coin was used for each game. How do you figure out the bias of each coin? This is exactly the problem the Expectation-Maximisation (EM) algorithm solves. By the end of this post, you'll understand how EM iteratively infers hidden information and be able to implement it from scratch. This tutorial is based on the excellent paper by Do & Batzoglou (2008) from Nature Biotechnology. The Problem You have two coins (A and B) with unknown biases $\theta_A$ and $\theta_B$. You repeat this procedure five times: randomly choose one coin (with equal probability), then perform 10 independent tosses with that coin. The observed head counts are: Experiment Sequence Heads Tails 1 H T T T H H T H T H 5 5 2 H H H H T H H H H H 9 1 3 H T H H H H H T H H 8 2 4 H T H T T T H H T T 4 6 5 T H H H T H H H T H 7 3 Figure adapted from Do & Batzoglou