Category Markov Chains

The Ballot Theorem

Today’s post is going to be about politics. Consider an election where there are two candidates, call them A and B, who receive votes respectively, and let us assume that . Assume that all possible “trajectories” are equally likely. What is the probability that candidate B is ahead of A throughout the vote counting procedure? […]

Martingales & Coins: Waiting for Heads-Tails-Heads

Consider the following simple problem: let be a sequence of independent fair coin tosses. How many times do we have to toss the coin in expectation in order to observe the sequence HTH (H stands for heads and T for tails)? We will answer this question here with three different ways. The first way is […]

Metropolis Chain

Nicholas Metropolis, a Greek American physicist, is well known for the “Metropolis chains”.  It is a well known fact in Markov chain theory that for an irreducible matrix there is a unique stationary distribution satisfying .  A natural question which comes up is the following: Given a probability distribution on a state space , can […]