Probability and Stochastic Processes

14.5 Classical Examples of Martingale Reasoning

In this section, we present examples of using martingales to provide elegant solutions to seemingly complicated problems.

14.5.1 The expected number of tosses until a binary pattern occurs

Suppose we toss an unbalanced coin which has probability p of landing Head and probability of landing Tail. What is the expected number of tosses until a certain pattern appears for the first time?

To make the reasoning more accessible, we consider a specific pattern, say, for example, . This pattern may be any sequence of heads and tails. There are other ways to find the expected number of tosses until the pattern occurs for the first time, but by far the most elegant and interesting reasoning is using martingale theory.

To perform the martingale reasoning, we need to construct a martingale. To this end, consider a game where at each step we toss this coin which has probability p of landing H. Consider a sequence of gamblers. Gambler i starts playing at toss number i, and every gambler bets on the exact pattern we want to calculate the probability for.

Specifically, in our example (), gambler i bets on H at toss i.If the gambler wins, then he/she ...